加权的自适应相似度度量

聚类分析是数据挖掘中一种非常重要的技术.聚类算法中的关键问题是相异度或相似度的度量,聚类结果直接依赖于相异度或相似度度量,尤其对于谱聚类方法更是如此.谱聚类算法是近期兴起的一种基于相似度矩阵的聚类算法.相比于传统的划分型聚类算法,谱聚类算法不受限于球状聚类簇,能够发现不规则形状的聚类簇.在已有的谱聚类算法中,高斯核相似度是最常用的相似度度量准则.基于高斯核相似度度量及其扩展形式,提出了一种加权的自适应的相似度度量,此相似度可以用于谱聚类以及其他基于相似度矩阵的聚类算法.新的相似度度量不仅能够描述多密度聚类簇中数据点间的相似度,而且可以降低离群点(噪声点)与其他数据点间的相似度.实验结果显示新的相似度度量可以更好地描述不同类型的数据集中数据点间的相似度,进而得到更好的聚类结果.     

一种有效的蛋白质序列聚类分析方法

提出了一种有效的基于仿射传播聚类算法和后处理方法的蛋白质序列聚类方法.在聚类分析蛋白质序列时,为了优化仿射传播聚类算法的聚类结果,采用后处理的方式来提高聚类结果的质量.为了度量蛋白质序列之间的相似度,给出了一种改进的无比对计算方法.在6个蛋白质序列数据集上进行对比实验,实验结果表明,所给出的方法能够有效地分析蛋白质序列.     

基于新的相似性度量的加权粗糙聚类算法

聚类是数据挖掘中重要的研究方向。本文针对现有的聚类算法中相似度量的缺陷,提出了一种新的相似性度量方法。在此基础上,将粗糙集理论中的区分能力引入到聚类算法中,用来度量属性的重要性,进而提出了一种能够处理符号型数据的新的加权粗糙聚类算法。通过对UCI数据的实验表明,本文算法对数据输入顺序不敏感,且不需要预先给定簇的数目,提高了聚类的质量。     

符号序列的概率向量聚类方法*

针对符号序列聚类中表示模型及序列间距离度量定义的困难问题,提出一种基于概率向量的表示模型及基于该模型的符号序列聚类算法。该模型引入符号序列的概率分布表示法,定义了一种基于概率分布差异的符号序列距离度量及该模型的目标函数,最后给出了一种符号序列K-均值型聚类算法,并在来自不同领域的实际应用序列集上进行了实验验证。实验结果表明,与基于子序列表示模型的符号序列聚类算法相比,所提方法在DNA序列和语音序列等具有较多符号的实际数据上,有效提高聚类精度的同时降低聚类时间50%以上。     

基于空间结构的符号数据仿射传播算法*

由于符号型数据缺乏清晰的空间结构,很难构造一种合理的相似性度量,从而使诸多数值型聚类算法难以推广至符号型数据聚类.基于此种情况,文中引入一种空间结构表示方法,把符号型数据转化为数值型数据,能够在保持原符号型数据的结构特征的基础上重新构造样本之间的相似度.基于此方法,将仿射传播(AP)聚类算法迁移至符号数据聚类中,提出基于空间结构的符号数据AP算法(SBAP).在UCI数据集中若干符号型数据集上的实验表明,SBAP可以使AP算法有效处理符号型数据聚类问题,并且可以提升算法性能.     

基于趋势的时间序列相似性度量和聚类研究

由于时间序列的长度很大,并且不确定时间序列在每个采样点的取值具有不确定性,导致时间序列在相似性匹配和聚类挖掘中时间复杂度很高,为了解决该问题,提出了基于趋势的时间序列相似性度量方法和聚类方法.其中基于趋势的相似性度量方法根据时间序列的整体变化趋势,将时间序列映射为短的趋势符号序列,并利用各趋势的一阶连接性指数和塔尼莫特系数完成相似性度量;基于趋势的聚类方法通过定义趋势高度,并对趋势符号序列迭代进行区间划分和趋势判断,并以此构建趋势树,最后将趋势树根节点中趋势符号相同的序列聚集为一类.实验结果表明:a)五种趋势符号的一阶连接性指数可唯一地表示一条时间序列;b)基于趋势的相似性度量方法在多项式时间内可有效完成时间序列的相似性匹配;c)基于趋势的聚类方法将序列的相似性度量和聚类过程集中在一起,聚类效果显著.     

面向高维的共享近邻聚类内部指标

针对因使用基于距离的相似性度量,传统聚类内部指标随着数据维数的增加而性能下降的问题,提出了一种基于共享近邻相似度的聚类内部指标.首先,利用共享近邻相似度和k最近邻(kNN)方法,估计数据点的密度,构建融合密度的共享近邻相似度图.然后,根据融合密度的共享近邻相似度图,利用最大流算法,计算出类内相似度和类间分离度,并结合两者计算出聚类内部指标.通过对人工数据集和真实数据集的测试表明,与9个基于距离的传统聚类内部指标相比,该指标能更准确评估数据集的最佳划分和预测数据集的最佳类数.因此,该指标处理复杂类结构和高维数据的能力优于所对比的其他聚类内部指标.     

一种基于相似性度量的高维数据聚类算法的研究

针对传统基于距离度量的聚类算法难以适合高维数据聚类以及高维数据之间相似度难定义的问题,提出了一种新的高维数据聚类算法.该算法基于一个能够更准确地表达出高维对象之间相似性的度量函数,首先计算对象两两之间的相似度并得出一个相似度矩阵,然后根据该相似度矩阵和阈值大小自底向上对数据进行聚类分析.实验结果显示,该算法能够获得质量更高的聚类结果,并且不受孤立点影响,对输入数据顺序也不敏感.     

一种新的不确定树模式聚类算法

不确定树模式聚类是数据挖掘领域中的一个重要问题,提出了一种新的不确定树模式聚类算法,有效地解决了因数据的不确定性而导致的无法聚类的问题.为了更加准确地度量树模式之间的相似性,提出了一种语义相似度计算方法与结构相似度计算方法.设计了一个动态聚类过程,自适应获取聚类阈值,较大程度上减少了人为干扰导致聚类结果不准确的影响,使得具有相似结构的子树聚集在同一个相似分组中,不同分组之间的子树相似度达到最小化.通过模拟数据和真实环境两部分实验表明,算法有效可行,聚类结果较准确且具有较好的运行效率.     

辅助信息自动生成的时间序列距离度量学习

对于时间序列聚类任务而言,一个有效的距离度量至关重要.为了提高时间序列聚类的性能,考虑借助度量学习方法,从数据中学习一种适用于时序聚类的距离度量.然而,现有的度量学习未注意到时序的特性,且时间序列数据存在成对约束等辅助信息不易获取的问题.提出一种辅助信息自动生成的时间序列距离度量学习(distancemetric learning based on side information autogeneration for time series,简称SIADML)方法.该方法利用动态时间弯曲(dynamic time warping,简称DTW)距离在捕捉时序特性上的优势,自动生成成对约束信息,使习得的度量尽可能地保持时序之间固有的近邻关系.在一系列时间序列标准数据集上的实验结果表明,采用该方法得到的度量能够有效改善时间序列聚类的性能.     

Hierarchical clustering of mixed data based on distance hierarchy

Data clustering is an important data mining technique which partitions data according to some similarity criterion. Abundant algorithms have been proposed for clustering numerical data and some recent research tackles the problem of clustering categorical or mixed data. Unlike the subtraction scheme used for numerical attributes, there is no standard for measuring distance between categorical values. In this article, we propose a distance representation scheme, distance hierarchy, which facilitates expressing the similarity between categorical values and also unifies distance measuring of numerical and categorical values. We then apply the scheme to mixed data clustering, in particular, to integrate with a hierarchical clustering algorithm. Consequently, this integrated approach can uniformly handle numerical data and categorical data, and also enables one to take the similarity between categorical values into consideration. Experimental results show that the proposed approach produces better clustering results than conventional clustering algorithms when categorical attributes are present and their values have different degree of similarity.     

类属型数据核子空间聚类算法

现有的类属型数据子空间聚类方法大多基于特征间相互独立假设,未考虑属性间存在的线性或非线性相关性.提出一种类属型数据核子空间聚类方法.首先引入原作用于连续型数据的核函数将类属型数据投影到核空间,定义了核空间中特征加权的类属型数据相似性度量.其次,基于该度量推导了类属型数据核子空间聚类目标函数,并提出一种高效求解该目标函数的优化方法.最后,定义了一种类属型数据核子空间聚类算法.该算法不仅在非线性空间中考虑了属性间的关系,而且在聚类过程中赋予每个属性衡量其与簇类相关程度的特征权重,实现了类属型属性的嵌入式特征选择.还定义了一个聚类有效性指标,以评价类属型数据聚类结果的质量.在合成数据和实际数据集上的实验结果表明,与现有子空间聚类算法相比,核子空间聚类算法可以发掘类属型属性间的非线性关系,并有效提高了聚类结果的质量.     

Mining of mixed data with application to catalog marketing

Clustering is one of the most popular techniques in data mining. The goal of clustering is to identify distinct groups in a dataset. Many clustering algorithms have been published so far, but often limited to numeric or categorical data. However, most real world data are mixed, numeric and categorical. In this paper, we propose a clustering algorithm CAVE which is based on variance and entropy, and is capable of mining mixed data. The variance is used to measure the similarity of the numeric part of the data. To express the similarity between categorical values, distance hierarchy has been proposed. Accordingly, the similarity of the categorical part is measured based on entropy weighted by the distances in the hierarchies. A new validity index for evaluating the clustering results has also been proposed. The effectiveness of CAVE is demonstrated by a series of experiments on synthetic and real datasets in comparison with that of several traditional clustering algorithms. An application of mining a mixed dataset for customer segmentation and catalog marketing is also presented.     

基于Hellinger距离的混合数据集中分类变量相似度分析

分类变量的相似度分析是数据挖掘任务中的一个重要环节,现有的分类变量相似度算法中存在忽视变量差异、受不均衡分布影响严重、无法应用于混合数据集等缺点。为克服以上缺点,提出了一种基于Hellinger距离的分类变量相似度算法。该算法累加分类变量对应子集中不同属性变量的分布差异作为相似度,且支持混合数据集。将所提算法代入聚类算法并应用于UCI公共数据集,结果表明,该算法在准确度、有效性和稳定性上都有较大提高。     

New similarity measures of intuitionistic fuzzy sets based on the Jaccard index with its application to clustering

A similarity measure is a useful tool for determining the similarity between two objects. Although there are many different similarity measures among the intuitionistic fuzzy sets (IFSs) proposed in the literature, the Jaccard index has yet to be considered as way to define them. The Jaccard index is a statistic used for comparing the similarity and diversity of sample sets. In this study, we propose a new similarity measure for IFSs induced by the Jaccard index. According to our results, proposed similarity measures between IFSs based on the Jaccard index present better properties. Several examples are used to compare the proposed approach with several existing methods. Numerical results show that the proposed measures are more reasonable than these existing measures. On the other hand, measuring the similarity between IFSs is also important in clustering. Thus, we also propose a clustering procedure by combining the proposed similarity measure with a robust clustering method for analyzing IFS data sets. We also compare the proposed clustering procedure with two clustering methods for IFS data sets.     

属性加权的类属型数据非模聚类

类属型数据广泛分布于生物信息学等许多应用领域,其离散取值的特点使得类属数据聚类成为统计机器学习领域一项困难的任务.当前的主流方法依赖于类属属性的模进行聚类优化和相关属性的权重计算.提出一种非模的类属型数据统计聚类方法.首先,基于新定义的相异度度量,推导了属性加权的类属数据聚类目标函数.该函数以对象与簇之间的平均距离为基础,从而避免了现有方法以模为中心导致的问题.其次,定义了一种类属型数据的软子空间聚类算法.该算法在聚类过程中根据属性取值的总体分布,而不仅限于属性的模,赋予每个属性衡量其与簇类相关程度的权重,实现自动的特征选择.在合成数据和实际应用数据集上的实验结果表明,与现有的基于模的聚类算法和基于蒙特卡罗优化的其他非模算法相比,该算法有效地提高了聚类结果的质量.     

可处理混合属性的任意形状聚类

聚类是数据挖掘中一个非常活跃的研究分支,任意形状的聚类则是一个有待研究的开放问题。提出一种包含分类属性取值频率信息的类间差异性度量和一种对象与类的相似度定义,在此基础上提出一种能处理任意形状的聚类算法,可处理混合属性数据集。在人造数据集和真实数据集上检验了提出的算法,并与相关算法进行了对比,实验结果表明,提出的算法是有效可行的。     

Rough subspace-based clustering ensemble for categorical data

Clustering categorical data arising as an important problem of data mining has recently attracted much attention. In this paper, the problem of unsupervised dimensionality reduction for categorical data is first studied. Based on the theory of rough sets, the attributes of categorical data are decomposed into a number of rough subspaces. A novel clustering ensemble algorithm based on rough subspaces is then proposed to deal with categorical data. The algorithm employs some of rough subspaces with high quality to cluster the data and yields a robust and stable solution by exploiting the resulting partitions. We also introduce a cluster index to evaluate the solution of clustering algorithm for categorical data. Experimental results for selected UCI data sets show that the proposed method produces better results than those obtained by other methods when being evaluated in terms of cluster validity indexes.