On the pattern recognition of noisy subsequence trees

We consider the problem of recognizing ordered labeled trees by processing their noisy subsequence-trees which are “patched-up” noisy portions of their fragments. We assume that H, a finite dictionary of ordered labeled trees, is given. X* is an unknown element of H, and U is any arbitrary subsequence-tree of X*. We consider the problem of estimating X* by processing Y, which is a noisy version of U. The solution which we present is, to our knowledge, the first reported solution to the problem. We solve the problem by sequentially comparing Y with every element X of H, the basis of comparison being a new dissimilarity measure between two trees, which implicitly captures the properties of the corrupting mechanism that noisily garbles U into Y. The algorithm which incorporates this constraint has been used to test our pattern recognition system, and the experimental results obtained demonstrate good accuracy     

An expressive dissimilarity measure for relational clustering using neighbourhood trees

Clustering is an underspecified task: there are no universal criteria for what makes a good clustering. This is especially true for relational data, where similarity can be based on the features of individuals, the relationships between them, or a mix of both. Existing methods for relational clustering have strong and often implicit biases in this respect. In this paper, we introduce a novel dissimilarity measure for relational data. It is the first approach to incorporate a wide variety of types of similarity, including similarity of attributes, similarity of relational context, and proximity in a hypergraph. We experimentally evaluate the proposed dissimilarity measure on both clustering and classification tasks using data sets of very different types. Considering the quality of the obtained clustering, the experiments demonstrate that (a) using this dissimilarity in standard clustering methods consistently gives good results, whereas other measures work well only on data sets that match their bias; and (b) on most data sets, the novel dissimilarity outperforms even the best among the existing ones. On the classification tasks, the proposed method outperforms the competitors on the majority of data sets, often by a large margin. Moreover, we show that learning the appropriate bias in an unsupervised way is a very challenging task, and that the existing methods offer a marginal gain compared to the proposed similarity method, and can even hurt performance. Finally, we show that the asymptotic complexity of the proposed dissimilarity measure is similar to the existing state-of-the-art approaches. The results confirm that the proposed dissimilarity measure is indeed versatile enough to capture relevant information, regardless of whether that comes from the attributes of vertices, their proximity, or connectedness of vertices, even without parameter tuning.     

Binary trees for dissimilarity data

Binary segmentation procedures (in particular, classification and regression trees) are extended to study the relation between dissimilarity data and a set of explanatory variables. The proposed split criterion is very flexible, and can be applied to a wide range of data (e.g., mixed types of multiple responses, longitudinal data, sequence data). Also, it can be shown to be an extension of well-established criteria introduced in the literature on binary trees.     

Pairwise-adaptive dissimilarity measure for document clustering

This paper introduces a novel pairwise-adaptive dissimilarity measure for large high dimensional document datasets that improves the unsupervised clustering quality and speed compared to the original cosine dissimilarity measure. This measure dynamically selects a number of important features of the compared pair of document vectors. Two approaches for selecting the number of features in the application of the measure are discussed. The proposed feature selection process makes this dissimilarity measure especially applicable in large, high dimensional document collections. Its performance is validated on several test sets originating from standardized datasets. The dissimilarity measure is compared to the well-known cosine dissimilarity measure using the average F-measures of the hierarchical agglomerative clustering result. This new dissimilarity measure results in an improved clustering result obtained with a lower required computational time.     

An association-based dissimilarity measure for categorical data

In this paper, we propose a novel method to measure the dissimilarity of categorical data. The key idea is to consider the dissimilarity between two categorical values of an attribute as a combination of dissimilarities between the conditional probability distributions of other attributes given these two values. Experiments with real data show that our dissimilarity estimation method improves the accuracy of the popular nearest neighbor classifier.     

Multivalued type dissimilarity measure and concept of mutual dissimilarity value for clustering symbolic patterns

A successful attempt in exploring a dissimilarity measure which captures the reality is made in this paper. The proposed measure unlike other measures (Pattern Recognition 24(6) (1991) 567; Pattern Recognition Lett. 16 (1995) 647; Pattern Recognition 28(8) (1995) 1277; IEEE Trans. Syst. Man Cybern. 24(4) (1994)) is multivalued and non-symmetric. The concept of mutual dissimilarity value is introduced to make the existing conventional clustering algorithms work on the proposed unconventional dissimilarity measure.     

A dissimilarity measure based on Jensen Shannon divergence measure

The need of suitable measures to find the distance between two probability distributions arises as they play an eminent role in problems based on discrimination and inferences. In this communication, we have introduced one such divergence measure based on well-known Shannon entropy and established its existence. In addition to this, a new dissimilarity measure for intuitionistic fuzzy sets corresponding to proposed divergence measure is also introduced and validated. Some major properties of the proposed dissimilarity measure are also discussed. Further, a new multiple attribute decision-making (MADM) method based on the proposed dissimilarity measure is introduced by using the concept of TOPSIS and is thoroughly explained with the help of an illustrated example on supplier selection problem. Finally, the application of proposed dissimilarity measure is given in pattern recognition and the performance is compared with some existing divergence measures in the literature.     

An effective dissimilarity measure for clustering of high-dimensional categorical data

Clustering is to group similar data and find out hidden information about the characteristics of dataset for the further analysis. The concept of dissimilarity of objects is a decisive factor for good quality of results in clustering. When attributes of data are not just numerical but categorical and high dimensional, it is not simple to discriminate the dissimilarity of objects which have synonymous values or unimportant attributes. We suggest a method to quantify the level of difference between categorical values and to weigh the implicit influence of each attribute on constructing a particular cluster. Our method exploits distributional information of data correlated with each categorical value so that intrinsic relationship of values can be discovered. In addition, it measures significance of each attribute in constructing respective cluster dynamically. Experiments on real datasets show the propriety and effectiveness of the method, which improves the results considerably even with simple clustering algorithms. Our approach does not couple with a clustering algorithm tightly and can also be applied to various algorithms flexibly.     

A dissimilarity measure for an arbitrary number of probability distributions

In this article we introduce a new function whose value is measure of the dissimilarity between several probability distributions. After a brief review of some previous measures for two probability distributions, a new function is introduced and its useful characteristics are presented. The most interesting feature of this new function is that it can be used for an arbitrary number of probability distributions.     

A redundancy-based measure of dissimilarity among probability distributions for hierarchical clustering criteria

We introduce novel dissimilarity into a probabilistic clustering task to properly measure dissimilarity among multiple clusters when each cluster is characterized by a subpopulation in the mixture model. This measure of dissimilarity is called redundancy-based dissimilarity among probability distributions. From aspects of both source coding and a statistical hypothesis test, we shed light on several of the theoretical reasons for the redundancy-based dissimilarity among probability distributions being a reasonable measure of dissimilarity among clusters. We also elucidate a principle in common for the measures of redundancy-based dissimilarity and Ward's method in terms of hierarchical clustering criteria. Moreover, we show several related theorems that are significant for clustering tasks. In the experiments, properties of the measure of redundancy-based dissimilarity are examined in comparison with several other measures.     

A dissimilarity Jensen–Shannon divergence measure for intuitionistic fuzzy sets

The need of suitable divergence measures arise as they play an important role in discrimination of two probability distributions. The present communication is devoted to the introduction of one such divergence measure using Jensen inequality and Shannon entropy and its validation. Also, a new dissimilarity measure based on the proposed divergence measure is introduced. Besides establishing validation, some of its major properties are also studied. Further, a new multiple attribute decision making method based on a proposed dissimilarity measure is introduced and is thoroughly explained with the help of an illustrated example. The paper is summed up with an application of the proposed dissimilarity measure in pattern recognition.     

On the impact of dissimilarity measure in k-modes clustering algorithm

This correspondence describes extensions to the k-modes algorithm for clustering categorical data. By modifying a simple matching dissimilarity measure for categorical objects, a heuristic approach was developed in (Z. He, et al., 2005), (O. San, et al., 2004) which allows the use of the k-modes paradigm to obtain a cluster with strong intrasimilarity and to efficiently cluster large categorical data sets. The main aim of this paper is to rigorously derive the updating formula of the k-modes clustering algorithm with the new dissimilarity measure and the convergence of the algorithm under the optimization framework     

基于相异性度量选取初始聚类中心改进的K-means聚类算法

选取合理的初始聚类中心是正确聚类的前提,针对现有的K-means算法随机选取聚类中心和无法处理离群点等问题,提出一种基于相异性度量选取初始聚类中心改进的K-means聚类算法.算法根据各数据对象之间的相异性构造相异性矩阵,定义了均值相异性和总体相异性两种度量准则;然后据此准则来确定初始聚类中心,并利用各簇中数据点的中位数代替均值以进行后续聚类中心的迭代,消除离群点对聚类准确率的影响.此外,所提出的算法每次运行结果保持一致,在初始化和处理离群点方面具有较好的鲁棒性.最后,在人工合成数据集和UCI数据集上进行实验,与3种经典聚类算法和两种优化初始聚类中心改进的K-means算法相比,所提出的算法具有较好的聚类性能.     

A pixel dissimilarity measure that is insensitive to image sampling

Because of image sampling, traditional measures of pixel dissimilarity can assign a large value to two corresponding pixels in a stereo pair, even in the absence of noise and other degrading effects. We propose a measure of dissimilarity that is provably insensitive to sampling because it uses the linearly interpolated intensity functions surrounding the pixels. Experiments on real images show that our measure alleviates the problem of sampling with little additional computational overhead     

A new evaluation measure using compression dissimilarity on text summarization

Evaluation of automatic text summarization is a challenging task due to the difficulty of calculating similarity of two texts. In this paper, we define a new dissimilarity measure – compression dissimilarity to compute the dissimilarity between documents. Then we propose a new automatic evaluating method based on compression dissimilarity. The proposed method is a completely “black box” and does not need preprocessing steps. Experiments show that compression dissimilarity could clearly distinct automatic summaries from human summaries. Compression dissimilarity evaluating measure could evaluate an automatic summary by comparing with high-quality human summaries, or comparing with its original document. The evaluating results are highly correlated with human assessments, and the correlation between compression dissimilarity of summaries and compression dissimilarity of documents can serve as a meaningful measure to evaluate the consistency of an automatic text summarization system.     

Algorithms for subsequence combinatorics

A subsequence is obtained from a string by deleting any number of characters; thus in contrast to a substring, a subsequence is not necessarily a contiguous part of the string. Counting subsequences under various constraints has become relevant to biological sequence analysis, to machine learning, to coding theory, to the analysis of categorical time series in the social sciences, and to the theory of word complexity. We present theorems that lead to efficient dynamic programming algorithms to count (1) distinct subsequences in a string, (2) distinct common subsequences of two strings, (3) matching joint embeddings in two strings, (4) distinct subsequences with a given minimum span, and (5) sequences generated by a string allowing characters to come in runs of a length that is bounded from above.     

Clustering with missing features: a penalized dissimilarity measure based approach

Many real-world clustering problems are plagued by incomplete data characterized by missing or absent features for some or all of the data instances. Traditional clustering methods cannot be directly applied to such data without preprocessing by imputation or marginalization techniques. In this article, we overcome this drawback by utilizing a penalized dissimilarity measure which we refer to as the feature weighted penalty based dissimilarity (FWPD). Using the FWPD measure, we modify the traditional k-means clustering algorithm and the standard hierarchical agglomerative clustering algorithms so as to make them directly applicable to datasets with missing features. We present time complexity analyses for these new techniques and also undertake a detailed theoretical analysis showing that the new FWPD based k-means algorithm converges to a local optimum within a finite number of iterations. We also present a detailed method for simulating random as well as feature dependent missingness. We report extensive experiments on various benchmark datasets for different types of missingness showing that the proposed clustering techniques have generally better results compared to some of the most well-known imputation methods which are commonly used to handle such incomplete data. We append a possible extension of the proposed dissimilarity measure to the case of absent features (where the unobserved features are known to be undefined).     

Data-dependent dissimilarity measure: an effective alternative to geometric distance measures

Nearest neighbor search is a core process in many data mining algorithms. Finding reliable closest matches of a test instance is still a challenging task as the effectiveness of many general-purpose distance measures such as \(\ell _p\)-norm decreases as the number of dimensions increases. Their performances vary significantly in different data distributions. This is mainly because they compute the distance between two instances solely based on their geometric positions in the feature space, and data distribution has no influence on the distance measure. This paper presents a simple data-dependent general-purpose dissimilarity measure called ‘\(m_p\)-dissimilarity’. Rather than relying on geometric distance, it measures the dissimilarity between two instances as a probability mass in a region that encloses the two instances in every dimension. It deems two instances in a sparse region to be more similar than two instances of equal inter-point geometric distance in a dense region. Our empirical results in k-NN classification and content-based multimedia information retrieval tasks show that the proposed \(m_p\)-dissimilarity measure produces better task-specific performance than existing widely used general-purpose distance measures such as \(\ell _p\)-norm and cosine distance across a wide range of moderate- to high-dimensional data sets with continuous only, discrete only, and mixed attributes.