A family of similarity measures between two strings

We present a class of similarity measures for quantitatively comparing two strings, that is, two linearly ordered sets of elements. The strings can be of different lengths, the elements come from a single alphabet, and an element may appear any number of times. The limiting values of each measure are 0, when two completely different strings are compared, and 1, when the two strings are identical. Applications of similarity measures are numerous in nonnumerical computations, such as in heuristic search processes in associative networks, in pattern recognition and classification, in game playing programs, and in music and text analysis. We offer a number of feasible measures from among which some are discarded on plausibility grounds. One can select the measure most adequate for one's needs on the basis of a few characteristic examples of strings compared and by considering the specific requirements of the application at hand.     

A family of measures for best top-n class-selective decision rules

When classes strongly overlap in the feature space, or when some classes are not known in advance, the performance of a classifier heavily decreases. To overcome this problem, the reject option has been introduced. It simply consists in withdrawing the decision, and let another classifier, or an expert, take the decision whenever exclusively classifying is not reliable enough. The classification problem is then a matter of class-selection, from none to all classes. In this paper, we propose a family of measures suitable to define such decision rules. It is based on a new family of operators that are able to detect blocks of similar values within a set of numbers in the unit interval, the soft labels of an incoming pattern to be classified, using a single threshold. Experiments on synthetic and real datasets available in the public domain show the efficiency of our approach.     

On a reflexivity-preserving family of cardinality-based fuzzy comparison measures

In this paper, we generalize and extend previous work on a triparametric family of cardinality-based fuzzy similarity measures. More specifically, we (i) generalize this family to a broader family of fuzzy comparison measures, (ii) summarize previously obtained results regarding this family and fill up a few gaps by adding some novel results, (iii) compare our parametric family with an already existing one, and (iv) elaborate on the ranking invariance between certain members of the presented triparametric family of cardinality-based fuzzy comparison measures.     

A family of experiments to validate measures for UML activity diagrams of ETL processes in data warehouses

In data warehousing, Extract, Transform, and Load (ETL) processes are in charge of extracting the data from the data sources that will be contained in the data warehouse. Their design and maintenance is thus a cornerstone in any data warehouse development project. Due to their relevance, the quality of these processes should be formally assessed early in the development in order to avoid populating the data warehouse with incorrect data. To this end, this paper presents a set of measures with which to evaluate the structural complexity of ETL process models at the conceptual level. This study is, moreover, accompanied by the application of formal frameworks and a family of experiments whose aim is to theoretical and empirically validate the proposed measures, respectively. Our experiments show that the use of these measures can aid designers to predict the effort associated with the maintenance tasks of ETL processes and to make ETL process models more usable. Our work is based on Unified Modeling Language (UML) activity diagrams for modeling ETL processes, and on the Framework for the Modeling and Evaluation of Software Processes (FMESP) framework for the definition and validation of the measures.     

Introducing a family of linear measures for feature selection in text categorization

Text categorization, which consists of automatically assigning documents to a set of categories, usually involves the management of a huge number of features. Most of them are irrelevant and others introduce noise which could mislead the classifiers. Thus, feature reduction is often performed in order to increase the efficiency and effectiveness of the classification. In this paper, we propose to select relevant features by means of a family of linear filtering measures which are simpler than the usual measures applied for this purpose. We carry out experiments over two different corpora and find that the proposed measures perform better than the existing ones.     

A history of graph entropy measures

This survey seeks to describe methods for measuring the entropy of graphs and to demonstrate the wide applicability of entropy measures. Setting the scene with a review of classical measures for determining the structural information content of graphs, we discuss graph entropy measures which play an important role in a variety of problem areas, including biology, chemistry, and sociology. In addition, we examine relationships between selected entropy measures, illustrating differences quantitatively with concrete examples.     

Closure properties of uniform convergence of empirical means and PAC learnability under a family of probability measures

Open Problem No. 12.2 of (Vidyasagar, A Theory of Learning and Generalization: with Application to Neural Networks and Control Systems, Springer, London, 1997) asks: “Are the properties of uniform convergence of empirical means, and learnability preserved when the family of probability measures is replaced by its closure?” In this note, the question is answered in the affirmative. Further, it is shown that these properties are not preserved in general if the family of probability measures is replaced by its convex closure. An open question is posed as to whether it is possible to replace the family of probability measures by its convex closure in case the family is compact.     

A sinusoidal family of unitary transforms

A new family of unitary transforms is introduced. It is shown that the well-known discrete Fourier, cosine, sine, and the Karhunen-Loeve (KL) (for first-order stationary Markov processes) transforms are members of this family. All the member transforms of this family are sinusoidal sequences that are asymptotically equivalent. For finite-length data, these transforms provide different approximations to the KL transform of the said data. From the theory of these transforms some well-known facts about orthogonal transforms are easily explained and some widely misunderstood concepts are brought to light. For example, the near-optimal behavior of the even discrete cosine transform to the KL transform of first-order Markov processes is explained and, at the same time, it is shown that this transform is not always such a good (or near-optimal) approximation to the above-mentioned KL transform. It is also shown that each member of the sinusoidal family is the KL transform of a unique, first-order, non-stationary (in general), Markov process. Asymptotic equivalence and other interesting properties of these transforms can be studied by analyzing the underlying Markov processes.     

A family of rectangular bending elements

By using separate independent transverse and rotational displacement variables in terms of a polynomial it is possible to produce high order conforming elements for plate bending and, at the same time, to include the effect of shear deformation in the analysis. The procedure for constructing a family of conforming rectangular plate bending elements with any number of nodes and the derivation of the stiffness matrix are illustrated. A computer programme is developed to generate the stiffness coefficients of the elements in this family; whereupon the characteristics of elements with as many as 17, 21 or 25 nodes and so on can be investigated. It is demonstrated that accurate results can be obtained for thin and moderately thick plates with various boundary conditions under bending by using just one or a few high order elements in this family. Hence the procedure for solving a problem in plate bending can be much simplified and the total number of nodes in a problem can be much reduced. Highlight in this family is the 17-node element which yields good results without involving too many nodes for many plate bending problems.     

A family of chebyshev-halley type methods

The aim of this paper is to find, for each nonlinear equation f (x) = 0, a Chebyshev-Halley type iterative process in the form x _n = F(x _n-1), with at least cubical convergence, to solve this equation. Moreover, from this study we obtain new global convergence Theorems for Halley and Chebyschev methods.     

A family of discrete Haar transforms

A new class of discrete orthogonal transforms called generalized Haar transforms, (GHT)_r is defined and developed. The base functions of (GHT)_r are linear combinations of Haar functions. Pertinent properties of (GHT)_r such as, linearity, uniqueness, dyadic autocorrelation, and dyadic shift invariance are developed. By factoring the transform matrices into a number of sparse matrices, efficient algorithms for fast computation of (GHT)_r and its inverse are developed. By subjecting these algorithms to successive bit-reversal operations, a single processor such as the Cooley-Tukey type can be used for implementing all the transforms. Specific examples illustrating the (GHT)_r its properties and the fast algorithms are included. The (GHT)_r is applied in digital information processing. Its utility and performance is compared with those of other discrete transforms such as Walsh-Hadamard, Haar, slant, Fourier, Karhunen-Loêve etc. Digital computer programs for fast implementation of (GHT)_r and for evaluating some of the performance criteria, such as variance and mean-square error are developed.     

A comparison of binless spike train measures

Several binless spike train measures which avoid the limitations of binning have been recently been proposed in the literature. This paper presents a systematic comparison of these measures in three simulated paradigms designed to address specific situations of interest in spike train analysis where the relevant feature may be in the form of firing rate, firing rate modulations, and/or synchrony. The measures are first disseminated and extended for ease of comparison. It also discusses how the measures can be used to measure dissimilarity in spike trains' firing rate despite their explicit formulation for synchrony.     

A class of measures on formal languages

Summary In this paper we introduce a class of measures on formal languages. These measures are based on the number of different ways a string of a specified finite length can be completed to obtain strings of the language. The relation with automata and grammars is established, and the polynomial measure, a special case of the general notion, is studied in detail. We give some closure properties for well-known operations on languages, and finally, we prove that the class of polynomial measurable languages is a Pre-AFL.     

A definition of measures over language space

As an attempt to associate a real number with a language, entropies of languages are computed by Banerji, Kuich, and others. As mappings from languages to real numbers, in this paper, measures over languages are presented. These measures satisfy additivity while entropies do not. Two kinds of measures, p-measure and ω-measure, are defined, and the computing method of these measures is shown for regular languages and context-free languages. Some properties of these measures are applied to show the nonregularity of several languages.     

A normed measures of variability among proportions

A measure of variability among a set of proportions is developed. There are no distributional assumptions, so the measure, H, is applicable in a wide variety of situations. H is scaled so that its range is zero (all proportions are equal) to one (maximum variability among the proportions, given the weighted average). The measure can be interpreted as a distance: the value of H indicates the position of the proportions relative to the possible extremes of no variability or maximum variability. Any set of constant weights can be applied to the proportions: the weights are used to compute the weighted average proportion and are also used to determine the extent to which each proportion affects the variability measure. Comparisons are made to other measures of variability and a numerical example is given.     

A comparative study of network robustness measures

The robustness is an important functionality of networks because it manifests the ability of networks to resist failures or attacks. Many robustness measures have been proposed from different aspects, which provide us various ways to evaluate the network robustness. However, whether these measures can properly evaluate the network robustness and which aspects of network robustness these measures can evaluate are still open questions. Therefore, in this paper, a thorough introduction over attacks and robustness measures is first given, and then nine widely used robustness measures are comparatively studied. To validate whether a robustness measure can evaluate the network robustness properly, the sensitivity of robustness measures is first studied on both initial and optimized networks. Then, the performance of robustness measures in guiding the optimization process is studied, where both the optimization process and the obtained optimized networks are studied. The experimental results show that, first, the robustness measures are more sensitive to the changes in initial networks than to those in optimized networks; second, an optimized network may not be useful in practical situations because some useful functionalities, such as the shortest path length and communication efficiency, are sacrificed too much to improve the robustness; third, the robustness of networks in terms of closely correlated robustness measures can often be improved together. These results indicate that it is not wise to just apply the optimized networks obtained by optimizing over one certain robustness measure into practical situations. Practical requirements should be considered, and optimizing over two or more Received February 22, 2016; accepted September 29, 2016 E-mail: neouma@163.com suitable robustnessmeasures simultaneously is also a promising way.