Ordination-based verification of feature selection in pattern evolution research

Abstract

This article explains the idea of pattern systems that develop gradually. These systems involve symbolic communication that includes symbols, syntax, and layout rules. Some pattern systems change over time, like historical scripts. The scientific study of pattern systems is called pattern evolution research, and scriptinformatics is concerned with the modelling of the evolution of scripts. The symbol series consists of symbols from a pattern system, while the graph sequence is a symbol sequence applied with a specific technology. This article describes a method for examining tested pattern systems to confirm their classification, which focuses on more ancient features. The method’s effectiveness was tested on Rovash scripts and graph sequences. Multivariate analysis was carried out by using PAST4 software, employing principal coordinates analysis ordination and $k$ -means clustering algorithms.

Keywords

Feature selection k-means machine learning principal coordinates analysis scriptinformatics

1. Introduction

A pattern system is a form of symbolic communication consisting of symbols, syntax and layout rules that determine their use. Among the possible pattern systems, this research focuses on those with evolutionary properties. The evolutionary study of pattern systems is called pattern evolution research. In biology, a taxonomic unit (taxon) is usually a species, while in pattern evolution research a taxon can be any pattern system (Table 1), such as Morse code, different character encodings or various scripts (human writing systems). For example, Morse code has evolved in several versions over time, from the code invented by Samuel Finley Breese Morse, through the code modified by Alfred Lewis Vail (the American Morse code) to the international Morse code, which itself evolved in several steps. Similarly, the evolution was a long and complicated process from Jean Maurice Émile Baudot’s 5-bit character code system through the American Standard Code for Information Interchange (ASCII), various international and national code systems to the ISO multilingual standard (ISO/IEC DIS 10646) and the BTRON encoding system [37].

An interesting type of pattern systems is represented by various human writing systems, or scripts in short. The different scripts and variants used by mankind have evolved over a long period of time. Understanding the evolution of these scripts can be important for deciphering the many untranslated past inscriptions, the so-called script remains [11]. In addition, deciphering the origins of ancient manuscripts may require an accurate description of the evolution and interaction of the large number of script variants associated with a single script. The study of the development of historical scripts and script variants is called scriptinformatics. The long-term goal of scriptinformatics is to help the interpretation and deciphering of script remains by exploring the evolutionary relationships between scripts [14, 15]. Scriptinformatics investigates the evolution of symbols and reveals the relationships between scripts. Phylogenetic methods of biology can generally be applied to describe the evolutionary processes of scripts. The focus of this research is the evolution of historical scripts; however, the developed method can also be applied to other types of pattern systems The purpose of pattern evolution research is to better understand and model the evolution of pattern systems, including historical scripts.

Similarly to the biological species or various objects in machine learning, a pattern system can be described by a set of features. However, in the phylogenetic analysis of pattern systems, some of their features are not informative or even ambiguous. Therefore, prior to the actual phylogenetic modelling, a pre-processing step called feature selection (a kind of feature engineering) is required, which creates a filtered subset of features from the original full set of features for each pattern system by filtering out uninformative and useless features. Feature selection is a typical task of data mining and machine learning. In some cases, data analysis methods such as regression, clustering, and classification can be performed more precisely in the reduced-dimensional feature space than in the original space of features [4, 6, 21, 29, 42, 43].

Phylogenetic modeling can be performed not only on the scripts, but on inscriptions written by the scripts under study. In the present research both scripts (in general pattern systems) and inscriptions (in general graph sequences, see later in Table 1) are analyzed using the developed composite method. The objective of the research is to verify whether the developed composite multivariate method detects the difference between the use of the full and the filtered feature sets.

The article first discusses the scientific background of pattern evolution research, then describes the developed composite multivariate method, then presents and evaluates the results of the analysis in the Results and Discussion section. Finally, the Conclusions section summarizes the obtained results. At the end of the article, public availability of the data used for the analysis is given The multivariate analyses were performed by the PAST 4.12a [7, 8], the figures were resized by the Inkscape 1.2 software [18].

2. Background

2.1 Terms and concepts

Table 1
Basic terms and concepts of pattern evolution research and scriptinformatics

Term	Description
Pattern	In the context of pattern systems, a pattern means a symbol sequence on the one hand, and a graph sequence on the other.
Pattern system	A pattern system is a form of symbolic communication consisting of symbols, syntax and layout rules that determine their use. The pattern evolution research equivalent of a biological species is a pattern system.
Pattern evolution research	Applied computer science discipline that deals with the investigation of the evolution of time-varying pattern systems with machine learning and bioinformatics tools, the development of the necessary algorithms and the evolutionary analysis of the features of the pattern systems. It is noteworthy that there are several pattern systems which have somehow evolution. For example, Morse code has evolved over the centuries, and each human writing system (script) has its own evolution.
Scriptinformatics	As part of the pattern evolution research it is the field of evolutionary modelling of different scripts. It uses machine learning methods to handle any written data, spatially analyze diverse variants of symbols, and explore relationships found in the data of historical or current inscriptions [13].
Feature	The features of the pattern system are the symbols, the syntax and the layout rules.
Symbol sequence	A data series composed of symbols belonging to the same pattern system, edited according to the syntax of the pattern system. An example of a symbol sequence is a message created with Morse code or a text edited with a specific script.
Graph sequence	Implementation of a symbol sequence with a given technology, according to the layout rules belonging to the pattern system. Graph sequence e.g. a physically measured sequence of signals that can be interpreted as a message (symbol sequence) created by Morse code or as an inscription found on an artifact excavated by archaeologists, which can be interpreted according to the symbols and rules of a given script. The pattern evolution equivalents of biological entities are the graph sequences made with the given pattern system.
Object	In the cluster analysis the examined entities are objects (data points). In the present analysis, the objects are pattern systems or graph sequences.
Feature	Properties of the objects are features.

Basic concepts of the pattern evolution related research as presented in Table 1. On this basis, the evolution of pattern systems can be studied in a similar way to evolutionary biology and bioinformatics. In many cases, a surviving graph sequence is very short, but in principle, at the time of its creation, the creator (e.g., a scribe) of the symbol sequence implemented by the graph sequence had available a picture of the pattern system, i.e. the feature set (symbol set, syntax and layout rules) that the scribe knew; at most, only a small part of the feature set might be needed to implement the given symbol sequence or the graph sequence representing its implementation by a certain technology. Table 2 summarizes the corresponding concepts of pattern evolution research and scriptinformatics (a subfield of pattern evolution research).

Table 2

Corresponding concepts of pattern evolution research and scriptinformatics

Pattern evolution research		Scriptinformatics
Pattern system	$\Leftrightarrow$	Script or script variant
Symbol sequence	$\Leftrightarrow$	Text, paragraph, sentence or word
Graph sequence	$\Leftrightarrow$	Inscription, codex, book, scroll, manuscript, etc.

There is some research that is similar to pattern evolution investigation, and especially to scriptinformatics. An example is phylomemetics, which refers to the phylogenetic analysis of non-genetic data, such as the evolutionary analysis of manuscripts [16]. Another example of non-biological evolution is software evolution, which studies the evolutionary context of software [35]. Another body of research is scriptinformatics, which applies bioinformatic methods and convolutional neural networks [2, 34]. Cladistic tools have been used to examine manuscript versions of India’s national epic, the Mahabharata, written in various Brahmic scripts [30] It was established that the phylogenetic relationships of the scripts used for each manuscript version differ from those of the individual parts of the text itself. Phillips-Rodríguez pointed out that the phylogenetic relationships of the scripts used for the manuscripts should be considered external (codicological) data, while those of the text versions of the manuscripts should be considered internal (stemmatological) data [31].

In the case of pattern systems that have not been used for a long time and have often been forgotten, the features of the pattern systems can only be recognized from the surviving graph sequences (e.g. inscriptions), such as the pattern system of the Elymian script once used in western Sicily (Italy) [27] or the Khotanese version of the Brahmic pattern system [26]. The research efforts of the author’s research group cover a broad range of topics such as applying machine learning methods to explore similarities among scripts [11], reconstructing lineages of symbols in various scripts and investigating methods for testing the appropriateness of the reconstructed lineages [13].

2.2 Features and metrics

The features of the examined pattern systems (e.g. scripts) can be handled as categorical variables since these features have the two states, e.g., “presence of a variant of a symbol” and “absence of a variant of a symbol”. Therefore, the two feature states (presence or absence) can be represented as binary variables [40]; in other words, the categorical variables are transformed into Boolean indicator variables. If the number of objects is $n$ , and the number of features is $p$ , then the matching of the objects $x_{i}$ and $x_{j}$ ( $i,j\in\left\{{1,\ldots,n}\right\}$ ) in binary features can be described by the four values ( $a,b,c,d)$ in Table 3, where $a+b+c+d=p$ .

Table 3
Contingency table describing the matching probabilities of two objects $x_{i}$ and $x_{j}$ ( $i,j\in\left\{{1,\ldots,n}\right\})$ in binary features

	Number of feature states with 1 in the object $x_{j}$	Number of feature states with 0 in the object $x_{j}$
Number of feature states with 1 in the object $x_{i}$	Number of feature states with 1 in both objects: $a$	Number of feature states with 1 in the object $x_{i}$ , and with 0 in the object $x_{j}$ : $b$
Number of feature states with 0 in the object $x_{i}$	Number of feature states with 0 in the object $x_{i}$ , and with 1 in the object $x_{j}$ : $c$	Number of feature states with 0 in both objects: $d$

In case of pattern systems the presence and absence of a feature is not symmetrical. Its reason is that only a minority of all features are actually present in each object (pattern system or graph sequence) under study. Therefore, the similarity measure that fits well with the examined dataset highlights similarities in the presence of features is the most appropriate one for the dataset in the present study, since the absence of a feature in an object (pattern system or graph sequence) is not characteristic. Hence the Sørensen–Dice coefficient [3, 39] is a good choice, since it emphasizes the effect of the co-existence of feature states; see Eq. (1).

$\displaystyle s_{ij}=\frac{2a}{2a+b+c},\quad i,j\in\left\{{1,\ldots,n}\right\}$ (1)

The Sørensen–Dice dissimilarity (distance) between objects $x_{i}$ and $x_{j}$ is given by Eq. (2).

$\displaystyle\delta_{ij}=1-s_{ij},\quad i,j\in\left\{{1,\ldots,n}\right\},$ (2)

There are many other measures that describe the similarity or dissimilarity of objects $x_{i}$ and $x_{j}$ ; e.g., Simple Matching Coefficient [38] or the Jaccard index [19].

2.3 Principal coordinates analysis (PCoA)

Ordination methods are a type of machine learning techniques that represent similarity relationships in some dimensions; they aim to reduce the dimensionality of large data structures with the least information loss. The dimensionality of a dataset is the number of features of the objects. Ordination extracts artificial variables to reduce the dimensionality of the original feature set of objects [32]. Dimensionality reduction is reducing the number of features while preserving as large a fraction of the variation in the original dataset as possible.

Multidimensional scaling (MDS), one of the ordination methods, performs a kind of feature extraction by creating new variables from original features. It transforms multidimensional spatial data into a space with a smaller ( $m\in\left\{{2,3}\right\}$ , typically) number of dimensions in an $m$ -dimensional space. The ordination input is an object-feature matrix of size $n\times p$ , in which each object is denoted by $x_{i}$ ( $i\in\left\{{1,\ldots,n}\right\})$ , where $n$ represents the number of objects and $p$ the number of features. Let $\delta_{ij}$ be the pairwise dissimilarity between $x_{i}$ and $x_{j}$ objects ( $i,j\in\left\{{1,\ldots,n}\right\})$ in the original space of their features, $\delta\left({x_{i},x_{j}}\right)=\delta_{ij}$ , where $\delta_{ij}$ is called the dissimilarity measure. By applying MSD to the dissimilarity matrix of size $n\times n$ it may be possible to study relationships between objects by extracting so-called ordination dimensions that are not visible in the original dissimilarity matrix, as previously unknown relationships are detected in the $m$ -dimensional Euclidean space resulting from MDS, where the pairwise distances $d_{ij}$ in the ordination structure are as close as possible to the original pairwise dissimilarities $\delta_{ij}$ . Another importance of MDS is to get a graphical representation of the examined objects, so that their relationships can be better understood.

One type of MDS is principal coordinates analysis (PCoA), an exploratory analysis method [5]. Along with principal component analysis and correspondence analysis, PCoA belongs to the group of linear scaling ordination methods These methods are widely used in data analysis, e.g. [17].

PCoA handles cases where the analysis starts from a single dissimilarity matrix and defines a measure for the input data [33, 36, 41]. It performs a linear mapping of the difference between objects in Cartesian ordination space and PCoA tries to explain the largest variance of the original dataset. The purpose of PCoA is to compute Euclidean distances representing a set of any dissimilarities of the objects [1]. PCoA maximizes the agreement between the calculated Euclidean distances in ordination space and the dissimilarities in the original space. In contrast to principal component analysis, PCoA can be applied not only to quantitative but also to any proximity measures (similarity or dissimilarity) Using the Euclidean distance gives results similar to principal component analysis. In the present case, however, the Sørensen–Dice dissimilarity Eq. (2) was applied.

Both principal components analysis and PCoA are eigenanalysis techniques, i.e. objects are projected onto axes (coordinates), with the first axis explaining the greatest variation of the objects in the original space, the second axis explaining as much of the remaining variation as possible and so on. PCoA finds the eigenvalues and eigenvectors of the dissimilarity matrix of objects. Each eigenvalue has an associated eigenvector, which keeps its direction when it is multiplied by the transformation matrix. The associated eigenvalue is the scaling factor of the transformation along the direction of the eigenvector. The eigenvalue can be determined for each coordinate, giving the amount of variance caused by the corresponding eigenvector (coordinate). The importance of these axes is measured by the eigenvalues. The goodness of PCoA can be measured by the percentage of variation explained by each coordinate. However, in the case of PCoA, there is no direct connection between the components and the original variables, so interpreting the role of the variables can be difficult because, unlike in principal component analysis, the components are not linear combinations of the original variables.

PCoA creates a set of orthogonal (uncorrelated) axes to summarize the variability in the dataset. Each axis has an eigenvalue, the magnitude of which indicates the amount of variation captured in that coordinate The ratio of a given eigenvalue to the sum of all eigenvalues explores the relative importance of each coordinate. The PCoA result ideally generates some coordinates with relatively large eigenvalues, capturing more than half of the variation in the input data, while all other coordinates have small eigenvalues. The interpretation of a PCoA diagram is that objects that are closer together are more similar than those that are farther away. In the PCoA plot, coordinate 1 accounts for the largest data change, and coordinate 2 explains the largest proportion of the remaining data changes.

The scatter plot represents all objects in the coordinate system given by the PCoA, where the eigenvalue scaling was used, so each axis is scaled to the square root of the eigenvalue. In the PCoA process, before eigenanalysis, the dissimilarity values are raised to the power of the transformation exponent $c$ . The standard value ( $c=$ 2) was retained in the present calculations, since the results do not show the horseshoe effect (arch effect) significantly [33].

In case of the structure of the objects under study is not continuous, a scatter plot in the ordinated space using two or three principal variables may be sufficient to evidence the group structure of the objects [23]. A common goal in machine learning is to form well-distinguished clusters in a low-dimensional space; this requires mixing an ordination method with a clustering method, such as in [28]. In the present research, $k$ -means cluster analysis (detailed below) is used to evaluate the set of objects in the ordinate space to determine the optimal number of clusters of objects.

2.4 K-means

$K$ -means [25] is a divisive non-hierarchical clustering method that calculates the mean of data points that fall into a cluster. Therefore, it can only be used for objects of the type where the means of the clusters can be interpreted. Consequently, it cannot be used when there are categorical values among the variables of the objects. The $k$ -means clustering algorithm is a widely used technology in data mining, of which several variants are known, e.g. [22, 24].

In the $k$ -means algorithm, the number of clusters ( $k$ ) must be predefined. The choice of the initial cluster centres can have an impact on the final cluster structure. The clustering result may vary each time the algorithm is run. It has difficulty handling clusters that are not spherical or at least convex clusters, and clusters of different sizes or very different densities. Essentially, the cluster is represented by its means. It can be applied to sparse, multidimensional data. Clustering uses all features, not just a subset of features. It also finds overlapping clusters. If the centers are initialized randomly, different clusters are created per run. In the case of the $k$ -means algorithm, each cluster is represented by the average of the objects $x_{i}=\left({x_{i1},\ldots,x_{ip}}\right),i=1,\ldots,n$ which are in an $p$ dimensional vector space, where $p$ is the number of features. The $k$ -means method searches for cluster formation $C$ in which the sum of the squared distances $E\left(C\right)$ of the individual objects from the representative $r\left({C_{j}}\right)$ of their cluster (e.g. centroid), measure according to Eq. (3), is minimal. $E\left(C\right)$ can be viewed as an error of clustering $C$

$\displaystyle E\left(C\right)=\mathop{\sum}\limits_{j=1}^{k}\mathop{\sum}% \limits_{x_{i}\in C_{j}}d\left({x_{i},r\left({C_{j}}\right)}\right)^{2},$ (3)

where $d$ is the distance metric interpreted at the objects $x_{i}$ . The disadvantage of the procedure is that the error $E\left(C\right)$ may reach a local minimum. The chance of this can be reduced by running the algorithm several times with different (random) starting values. Also, the $k$ -means algorithm is sensitive to outlier objects. The number of iterations necessary is unknown since standard $k$ -means is not guaranteed to converge. Moreover, clusterings produced by $k$ -means are dependent on the starting points of the clusters. $K$ -means tends to produce convex clusters when Euclidean distance is used as the distance measure.

The cluster assignments are initially random. In an iterative procedure, objects are then moved to the cluster which has the closest cluster mean, and the cluster means are updated accordingly. This procedure continues until objects are no longer jumping to other clusters. The result of the $k$ -means clustering depends upon the initial, random ordering, and cluster assignments may therefore differ from run to run. This is normal behavior in $k$ -means clustering.

The $k$ -means clustering algorithm calculates some parameters that characterize each $k$ -means run. One of them is the parameter Within-Group (or within-cluster) Sum of Squares, named WGSS. The larger is the cluster separation or the number of clusters, the smaller is WGSS Another parameter is the ratio of between-group to within-group sum of squares, which is called $F$ , which increases with cluster separation and number of clusters. The third parameter characterizing each $k$ -means run is Variance explained [%], which is the ratio of between-group to total sum of squares, multiplied by 100.

There are various methods to find the best value of $k$ . One of them is the Silhouette index-based method where the silhouette coefficient is calculated to measure how similar a given object is to objects in its own cluster, as compared to objects in other clusters. Silhouette is higher when clusters are dense, well separated, or convex, and a zero value indicates overlapping clusters. It provides a graphical representation of how well each object lies within its cluster [20]. The $S_{i}$ Silhouette index for the object $x_{i}$ is defined as Eq. (4).

$\displaystyle S_{i}=\frac{b_{i}-a_{i}}{\textit{max}\left({a_{i},b_{i}}\right)},$ (4)

where $a_{i}$ is the average distance from the object $x_{i}$ to all the other objects in the cluster to which $x_{i}$ belongs and $b_{i}$ is the average distance from the object $x_{i}$ to all different clusters; $i=1,\ldots,n$ where $n$ is the number of objects. The range of Silhouette index is $\left[{-1,1}\right]$ . A high Silhouette value indicates that the object $x_{i}$ is well matched to its own cluster, and poorly matched to neighboring clusters. If most objects have a high Silhouette value, then the clustering solution is appropriate. The Silhouette index can be used with any distance metric. The Average silhouette is calculated by Eq. (5).

$\displaystyle\textit{Average silhouette}=\frac{1}{n}\mathop{\sum}\limits_{i=1}% ^{n}S_{i}$ (5)

The optimal $k$ maximizes the Average silhouette. In cluster analysis, various approaches, such as the elbow method or X-means [12], can determine the number of clusters within a dataset. But in our case, the most vital thing is how easy it is to understand the result. So, the Silhouette results of the $k$ -means clustering are more important at different $k$ values.

2.5 The tested pattern systems and graph sequences

In the present study, the examined pattern systems are the Rovash scripts, which were used by some populations of the Eurasian steppe [13]; namely, Turkic Rovash (TR, also known as Turkic Runic), Székely-Hungarian Rovash (SHR), Carpathian-Basin Rovash (CBR) and Steppe Rovash (SR). In a process of data selection, the possible ancestors of these pattern systems were estimated by means of a phenetic-based successive elimination analysis [14]. These preliminary studies suggest that their probable ancestor could be a hybrid of the Aramaic, Middle Iranian and Brahmic scripts [15]. This hypothetical common ancestor (called Proto-Rovash, PR) was reconstructed [14], and it is used in the present analysis. The Rovash scripts that evolved gradually lost the features inherited from PR. Only a proportion of their features have their origin in PR, these features are collectively called filtered feature set The number of original, full features is 119, and that of filtered features is 72. The rest of the features resulted from later, local or occasional influences of various other scripts. Table 4 presents some properties of the pattern systems under study.

Table 4
Main properties of tested pattern systems

Name of the pattern system	Period of use	Area of use
Proto-Rovash (PR)	5^th–6^th century AD (hypothetic)	Inner Asia (hypothetic)
Turkic Rovash (TR)	8^th–10^th century AD	Inner Asia
Székely-Hungarian Rovash (SHR)	from around 900 AD to present day	Carpathian Basin
Carpathian Basin Rovash (CBR)	7^th–11^th century AD	Carpathian Basin
Steppe Rovash (SR)	8^th–10^th century AD	Inner Asia, Eastern European Steppe, Carpathian Basin

Of the pattern systems under study, only SHR has remained in use until the present day, the others became extinct a millennium ago. Very few surviving graph sequences (inscriptions) are known for the pattern systems examined in this research, and the age of most of them is either unknown or can only be estimated approximately. Since PR, TR, CBR and SR became extinct at the end of the 1^st millennium AD, the attribution of surviving Rovash graph sequences to one of Rovash pattern systems is not always clear. Table 5 shows the name and traditional classification of each surviving Rovash graph sequence into pattern systems. There are no surviving graph sequences that can be classified as PR. The detailed descriptions of the graph sequences in Table 4 are presented in the literature [9, 10, 14].

Table 5

Classification of graph sequences under study

Class (pattern system)	Graph sequence’s name
Turkic Rovash (TR)	Yabogan, Almaly II, Tamgaly, Kalbak Tash II, Koytubek, Kul Tegin, Kuljabasy I, II, Bichiktu Boom III, XV, Mendur Sokkon I, Kurgak I, Urkosh, Tuva III, Zhon Aryk
Székely-Hungarian Rovash (SHR)	Vargyas, Homoródkarácsonyfalva, Erdőszentgyörgy, Stick Calendar, Nikolsburg, Csíkszentmihály, Constantinople, Bodrog-Alsóbű, Székelyderzs, Bágy, Szamosközy, Wolfenbüttel, Rudimenta, Farkaslaki, Bonyhai, Kájoni-Ancient, Bél, Patakfalvi
Carpathian Basin Rovash (CBR)	Ozora-Tótipuszta, Jánoshida, Kiskőrös-Vágóhíd, Környe, Szarvas, Kiskundorozsma, Nagyszentmiklós
Steppe Rovash (SR)	Jitkov, Achik Tash, Mayaki, Mayatskoe 1, 2, 5, 10, Khumara 6, 7, 8, Kermen Tolga, Novocherkassk, Homokmégy-Halom, Algyő, Kievan Letter

3. Method

Some of the key questions of pattern evolution research are the following: what features characterize the pattern systems under study and at what stage of the evolution of the tested pattern systems did these features evolve? The former question has been addressed by extended phenetic modelling, the latter by the successive elimination of extended phenetic modelling; both were performed in a previous research [14, 15]. These examinations can be called a feature engineering phase or simply feature selection, where the tests were applied to special pattern systems, the Rovash scripts (see above). During this the existence of the putative common ancestors of these pattern systems was confirmed and it was determined which part of the full feature set of these pattern systems might have existed at the beginning of their evolution (in their hypothetical common ancestor, denoted by PR, see above). This earliest part of the full feature set is called the filtered set of features. Features that are not part of the filtered set may have evolved during the independent evolution of each pattern system. It is important to emphasize that the feature selection carried out in previous research [14, 15] was based exclusively on pattern systems, the surviving graph sequences were not directly included in that study.

The question of the present research is whether the correctness of the selection of the filtered feature set can be verified by the surviving graph sequences made with the pattern systems under study or not Its way is to check whether the results obtained using the filtered feature set are indeed less reflective of the separation of each tested pattern system from each other than those obtained using the full feature set. Figure 1 shows the flowchart of both feature selection as a feature engineering phase and verification of feature selection as a newly developed machine learning method based on PCoA and $k$ -means clustering.

Figure 1.

Main steps of the composite multivariate analysis method.

Figure 2.

PCoA results of the tested pattern systems with full feature set (left) and with filtered feature set (right).

The new composite multivariate method performs the PCoA of the pattern systems and the associated graph sequences separately, both for the full feature set and for the filtered feature set, respectively.

4. Results and discussion

4.1 PCoA of pattern systems and graph sequences

The PCoA scatter plots are shown in Fig. 2 for the pattern systems tested using the full feature set and the filtered feature set, respectively. The dissimilarity measure used was the Sørensen–Dice dissimilarity Eq. (2). Objects that are closer together have smaller dissimilarity scores in the scatter plot than those that are farther apart.

The eigenvalue is given for each axis, which gives a measure of the variance caused by the corresponding eigenvector (coordinate). The eigenvalues and the percentages of variance due to these components are given in Table 4.1 for the full feature set and filtered feature set cases, respectively.

Table 6

Eigenvalues and the percentages of variance for each component

Axis

Eigenvalue

(full feature set)

Percent

(full feature set)

Eigenvalue

(filtered feature set)

Percent

(filtered feature set)

4.3879

19.685

4.594

19.642

3.9130

17.555

3.480

14.880

1.4887

6.679

1.732

7.405

1.1509

5.163

1.321

5.649

1.1084

4.972

1.276

5.456

0.9148

4.104

1.015

4.341

Figure 6.

In case of $k=2$ , the Silhouette of the $k$ -means clustering of the tested graph sequences with full feature set (left) and with filtered feature set (right).

Feature set	$K$	WGSS	F	Variance explained	Average silhouette
Full (original) set	2	16.247	0.2472	19.821%	0.16714
	3	12.560	0.6134	38.020%	0.21715
	4	12.052	0.6813	40.522%	0.21916
	5	11.620	0.7438	42.655%	0.21525
Filtered (reduced) set	2	40.164	0.1057	9.5615%	0.04418
	3	39.094	0.1360	11.972%	0.05693
	4	38.027	0.1679	14.375%	0.07036
	5	34.876	0.2734	21.469%	0.06032

Footnotes

Data availability

The pattern systems (scripts), graph sequences (inscriptions) and symbols used in this article can generally be found in the book titled Scriptinformatics []. The applied dataset is publicly available on GitHub (https://github.com/hosszu/2023_Ordination-based_verification_of_feature_selection).

References

Borcard

Gillet

Legendre

, Numerical Ecology with R, Second Edition, Springer, Cham, 2018.

Daggumati

Revesz

P.Z.

, Convolutional Neural Networks Analysis Reveals Three Possible Sources of Bronze Age Writings between Greece and India, Information 14 (2023), 227.

Dice

L.R.

, Measures of the Amount of Ecologic Association Between Species, Ecology 26 (1945), 297–302.

García

Maldonado

Vairetti

, Efficient N-gram Construction for Text Categorization Using Feature Selection Techniques, Intelligent Data Analysis 25 (2021), 509–525.

Gower

J.C.

, Some distance properties of latent root and vector methods used in multivariate analysis, Biometrika 53 (1966), 325–338.

Gupta

Chug

, A Feature Selection Strategy for Improving Software Maintainability Prediction, Intelligent Data Analysis 26 (2022), 311–344.

Hammer

Ø.

, PAST: PAleontological STatistics Version 4.12, Reference manual, University of Oslo, (1999–2022), https://www.nhm.uio.no/english/research/resources/past/downloads/past4manual.pdf.

Hammer

Ø.

Harper

D.A.T.

Ryan

P.D.

, PAST: Paleontological Statistics software package for education and data analysis, Palaeontologia Electronica 4 (2001), 9.

Hosszú

, Heritage of Scribes. The Relation of Rovas Scripts to Eurasian Writing Systems. Rovas Foundation, Budapest, 2013, http://google.hu/books?id=TyK8azCqC34C&pg.

10.

Hosszú

, The Rovas: A Special Script Family of the Central and Eastern European Languages, Acta Philologica 44 (2013), 91–102.

11.

Hosszú

, Mathematical Statistical Examinations on Script Relics, in: Bhatnagar

, ed., Data Mining and Analysis in the Engineering Field, Information Science Reference, Hershey, 2014, pp. 142–158.

12.

Pelleg

Moore

, X-means: Extending K-means with Efficient Estimation of the Number of Clusters, in: Langley

, ed., Proceedings of 17th International Conference on Machine Learning, Morgan Kaufmann, San Francisco, 2000, pp. 727–734.

13.

Hosszú

, Phenetic Approach to Script Evolution, in: Busch

Fischer

Sahle

, eds., Codicology and Palaeography in the Digital Age 4, Books on Demand, Norderstedt, 2017, pp. 179–252.

14.

Hosszú

, Scriptinformatics, Extended Phenetic Approach to Script Evolution, Nap, Budapest, 2021, http://napkiado.hu/media/Hosszu_Gabor-Scriptinformatics.pdf.

15.

Hosszú

, Data-Driven Phenetic Modeling of Scripts’ Evolution, in: Liu

Bohács

Shi

Shang

Huang

, eds., LISS 2020, Proceedings of the 10th International Conference on Logistics, Informatics and Service Sciences, Springer, 2021, pp. 389–403.

16.

Howe

C.J.

Windram

H.F.

, Phylomemetics – Evolutionary Analysis beyond the Gene. PLoS Biology 9 (2011), e1001069.

17.

Huang

Jin

, A Robust Anomaly Detection Algorithm Based on Principal Component Analysis, Intelligent Data Analysis 25 (2021), 249–263.

18.

Inkscape Project (2020) Inkscape. Retrieved from https://inkscape.org.

19.

Jaccard

, Etude de la distribution florale dans une portion des Alpes et du Jura. Bulletin de la Societe Vaudoise des Sciences Naturelles 37 (1901), 547–579.

20.

Kaufman

Rousseeuw

P.J.

, Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley & Sons, New York, 1990.

21.

Kim

K.J.

Jun

C.H.

, Dynamic Mutual Information-based Feature Selection for Multi-label Learning, Intelligent Data Analysis (2023), 1–19, doi: 10.3233/IDA-226666.

22.

Krechowicz

, Content-aware Data Distribution over Cluster Nodes, Intelligent Data Analysis 25 (2021), 907–927.

23.

Legendre

, Numerical Ecology. Third English Edition, Elsevier, 2012.

24.

Liu

, Bayesian Hierarchical K-means Clustering, Intelligent Data Analysis 24 (2020), 977–992.

25.

MacQueen

J.B.

, Some methods for classification and analysis of multivariate observations, in: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967, pp. 281–297.

26.

Maggi

, Some remarks on the history of the Khotanese orthography and the Brāhmī script in Khotan, in: Kudo

, ed., Annual Report of the International Research Institute for Advanced Buddhology at Soka University for the Academic Year 2021 Volume XXV, Soka University, 2022, pp. 149–172.

27.

Marchesini

, The Elymian language, in: Tribulato

, ed., Language and Linguistic Contact in Ancient Sicily, Cambridge University Press, 2012, pp. 95–114.

28.

Matsuda

Morikuni

Imakura

Sakurai

, Multiclass Spectral Feature Scaling Method for Dimensionality Reduction, Intelligent Data Analysis 24 (2020), 1273–1287.

29.

Pan

Sun

Wang

Cao

, A Multi-label Feature Selection Method Based on an Approximation of Interaction Information, Intelligent Data Analysis 26 (2022), 823–840.

30.

Phillips-Rodríguez

W.J.

, The Evolution of a Sanskrit Epic: Some Genetic Considerations about Scripts, in: The Evolution of Texts: Confronting Stemmatological and Genetical Methods, Istituti editoriali e poligrafici internazionali, Pisa, 2006, pp. 175–190.

31.

Phillips-Rodríguez

W.J.

, Scripts and Manuscripts: Two Independent Speciation Processes in the Mahabharata Textual Tradition, in: The Churning of the Epics and Purāṇas: Proceedings of the Epics and Purāṇas Section at the 15th World Sanskrit Conference, Dev Publishers & Distributors, New Delhi, 2018, pp. 1–13.

32.

Podani

, Introduction to the Exploration of Multivariate Biological Data, Backhuys Publishers, Leiden, 2000.

33.

Podani

Miklós

, Resemblance coefficients and the horseshoe effect in principal coordinates analysis, Ecology 83 (2002), 3331–3343.

34.

Revesz

P.Z.

, Bioinformatics evolutionary tree algorithms reveal the history of the Cretan Script Family. Int J Appl Math Inform 10 (2016), 67–76.

35.

Sampaio

, Software Phenetics, Phylogeny and Evolution, in: Third International IEEE Workshop on Software Evolvability, 2007, pp. 60–66.

36.

Schiffman

S.S.

Reynolds

M.L.

Young

F.W.

, Introduction to Multidimensional Scaling, Academic, New York, 1981.

37.

Searle

S.J.

, A Brief History of Character Codes in North America, Europe, and East Asia, in: TRON Web, 1999–2004, accessed: 11 June 2013 from http://tronweb.super-nova.co.jp/characcodehist.html.

38.

Sokal

R.R.

Michener

C.D.

, A Statistical Method for Evaluating Systematic Relationships. Univ Kans sci bull XXXVIII (1958), 1409–1438.

39.

Sørensen

T.J.

, A Method of Establishing Groups of Equal Amplitude in Plant Sociology Based on Similarity of Species Content and its Application to Analyses of the Vegetation on Danish Commons. I kommission hos E. Munksgaard, København, 1948.

40.

Tan

Steinbach

Kumar

, Introduction to Data Mining. Addison-Wesley, Boston, 2005.

41.

Torgerson

W.S.

, Multidimensional scaling: I. Theory and method. Psychometrika 17 (1952), 401–419.

42.

Wang

Han

Zhang

, A Relief-PGS Algorithm for Feature Selection and Data Classification, Intelligent Data Analysis 27 (2023): 399–415.

43.

Zhou

Zhu

, A Grouping Feature Selection Method Based on Feature Interaction, Intelligent Data Analysis 27 (2023): 361–377.

Ordination-based verification of feature selection in pattern evolution research

Abstract

Keywords

1. Introduction

2. Background

2.1 Terms and concepts

Table 1 Basic terms and concepts of pattern evolution research and scriptinformatics

Table 3 Contingency table describing the matching probabilities of two objects x i and x j ( i , j ∈ { 1 , … , n } ) in binary features

2.4 K-means

Table 4 Main properties of tested pattern systems

4.1 PCoA of pattern systems and graph sequences

Footnotes

Data availability

References

Table 1
Basic terms and concepts of pattern evolution research and scriptinformatics

Table 3
Contingency table describing the matching probabilities of two objects $x_{i}$ and $x_{j}$ ( $i,j\in\left\{{1,\ldots,n}\right\})$ in binary features

Table 4
Main properties of tested pattern systems