有效距离在聚类算法中的应用

聚类分析是数据挖掘领域的重要组成部分之一,而度量学习是聚类分析中的关键性步骤。传统聚类算法中通常使用欧氏距离进行距离度量,但是欧氏距离只关注两两样本之间的距离关系,并没有顾及数据的全局性分布结构。考虑到数据的全局性结构信息,提出了一种新的具有全局性的度量方法——有效距离度量(effective distance metric),其主要思想是通过稀疏重构的方法计算数据样本之间的有效距离。进一步地,将有效距离应用到K-means、K-medoids和FCM(fuzzy C-means)3种经典聚类算法中开发了3种基于有效距离的聚类算法,即EK-means,EK-medoids和EFCM聚类算法。通过与传统聚类算法在UCI标准数据集上的实验结果进行比较,验证了基于有效距离的聚类算法能显著提高聚类效果。     

一种基于邻域距离的聚类特征选择方法

针对高维复杂的符号数据集在聚类中的聚类效果差和计算耗时过大的问题,首先提出了一种基于邻域距离的无监督特征选择算法,然后在选择到的特征子集上进行重新聚类,从而有效提高了聚类结果的精度,降低了聚类计算的计算耗时。实验结果表明,该算法可以找到有效的特征子集,提高数据集的聚类精度,降低面对高维复杂数据集聚类的计算耗时。     

基于传递距离的谱聚类算法

谱聚类算法受到度量中尺度因子的影响,同时传统谱聚类算法通过欧氏距离度量样本间相似性也不准确。针对上述问题,提出一种基于传递距离的谱聚类算法。算法首先通过改进传统谱聚类中的度量方式,用基于传递距离的度量方式度量样本间相似性,并构建传递矩阵,接着用传递矩阵做相似度变换构建拉普拉斯矩阵,最终通过求特征值和特征向量完成聚类。基于传递距离的谱聚类算法在人工数据集及UCI数据集上均取得了良好的聚类结果,具有较好的鲁棒性和有效性。     

基于测地线的超像素谱聚类彩色图像分割

在图像分割中谱聚类算法得到了广泛的应用,但传统谱聚类算法易受到彩色图像大小和相似性测度的影响,导致计算量大和分割精度低的问题。为了解决这两个问题,提出一种新的基于超像素集测地线特征的谱聚类分割算法。该方法通过对彩色图像进行预分割得到超像素集,并以超像素集为基础构造加权图,利用测地线距离特征和颜色特征构造权值矩阵,最后应用NJW（Ng-Jordan-Weiss）算法得到最终的分割结果。对比实验结果表明该算法在分割精度和计算复杂度上都有较大改善。     

基于距离度量学习的集成谱聚类

无监督学习聚类算法的性能依赖于用户在输入数据集上指定的距离度量,该距离度量直接影响数据样本之间的相似性计算,因此,不同的距离度量往往对数据集的聚类结果具有重要的影响。针对谱聚类算法中距离度量的选取问题,提出一种基于边信息距离度量学习的谱聚类算法。该算法利用数据集本身蕴涵的边信息,即在数据集中抽样产生的若干数据样本之间是否具有相似性的信息,进行距离度量学习,将学习所得的距离度量准则应用于谱聚类算法的相似度计算函数,并据此构造相似度矩阵。通过在UCI标准数据集上的实验进行分析,结果表明,与标准谱聚类算法相比,该算法的预测精度得到明显提高。     

基于低密度分割密度敏感距离的谱聚类算法

本文提出一种基于低密度分割密度敏感距离的谱聚类算法, 该算法首先使用低密度分割密度敏感距离计算相似度矩阵, 该距离测度通过指数函数和伸缩因子实现放大不同流形体数据间的距离和缩短同一流形体数据间距离的目的, 从而有效反映数据分布的全局一致性和局部一致性特征.另外, 算法通过增加相对密度敏感项来考虑数据的局部分布特征, 从而有效避免孤立噪声和"桥"噪声的影响.文中最后给出了基于SC (Scattering criteria)指标的k近邻图k值选取办法和基于谱熵贡献率的特征向量选取方法.实验部分, 讨论了参数选择对算法性能的影响并给出取值建议, 通过与其他流行谱聚类算法聚类结果的对比分析, 表明本文提出的基于低密度分割密度敏感距离的谱聚类算法聚类性能明显优于其他算法.     

基于密度敏感距离的改进模糊C均值聚类算法

模糊C均值（FCM）聚类算法无法识别非凸数据,算法中基于欧式距离的相似性度量只考虑数据点之间的局部一致性特征而忽略了全局一致性特征。提出一种利用密度敏感距离度量创建相似度矩阵的FCM算法。通过近邻传播算法获取粗类数作为最佳聚类数的搜索范围上限,以解决FCM算法聚类数目需要人为预先设定和随机选定初始聚类中心造成聚类结果不稳定的问题。在此基础上,改进最大最小距离算法,得到具有代表性的样本点作为初始聚类中心,并结合轮廓系数自动确定最佳聚类数。基于UCI数据集和人工数据集的实验结果表明,相比经典FCM、K-means和CFSFDP算法,该算法不仅具有识别复杂非凸数据的能力,而且能够在保证聚类性能和稳定性的前提下加快收敛速度。     

面向大数据处理的并行优化抽样聚类K-means算法

针对大数据环境下K-means聚类算法聚类精度不足和收敛速度慢的问题,提出一种基于优化抽样聚类的K-means算法(OSCK)。首先,该算法从海量数据中概率抽样多个样本;其次,基于最佳聚类中心的欧氏距离相似性原理,建模评估样本聚类结果并去除抽样聚类结果的次优解;最后,加权整合评估得到的聚类结果得到最终k个聚类中心,并将这k个聚类中心作为大数据集聚类中心。理论分析和实验结果表明,OSCK面向海量数据分析相对于对比算法具有更好的聚类精度,并且具有很强的稳健性和可扩展性。     

一种基于数据相关性的半监督模糊聚类集成方法

现有的半监督聚类集成方法能利用先验信息,使集成的准确性、鲁棒性和稳定性得到提高,但在集成阶段加入成对约束信息时,只考虑了给定的约束信息而忽视了约束点与被约束点的邻域点之间的关系.针对此问题,提出了一种基于数据相关性的半监督模糊聚类集成方法.该方法首先利用半监督模糊聚类算法建立集成信息矩阵,并将其转换为相似性矩阵;然后,利用已知的约束信息及约束点与被约束点的邻域点之间的关系来修改相似性矩阵;最后,利用图划分算法得到最终的聚类结果.真实数据上的实验结果表明,提出的方法可以有效提高聚类质量.     

一种基于约束的中垂面相似度准则

在数据挖掘和机器学习的基于距离的各种技术中,例如基于距离的聚类和基于距离的分类,如何度量数据间的相似性已经成为一项基础任务.对于某一具体问题,采用合适的相似性度量,会使问题得到更有效的解决.越来越多的研究表明,通过对成对约束(正约束和负约束)的充分利用,从而得到与问题相匹配的相似性度量,能够大幅度地提升算法性能.目前基于约束的相似性度量研究主要是基于约束的距离度量学习,通过对约束信息的利用,学习一个距离度量矩阵,然后再进行分类或者聚类.通过对成对约束尤其是负约束的挖掘,提出一种基于成对约束的相似性度量准则,然后将此准则应用于聚类和分类任务中,分别提出聚类和分类算法,最后在大量标准数据集上将这些算法的性能与目前流行的算法进行实验比较,并据此得出了一些经验性的启示.     

复杂高维数据的密度峰值快速搜索聚类算法

机器学习的无监督聚类算法已被广泛应用于各种目标识别任务。基于密度峰值的快速搜索聚类算法(DPC)能快速有效地确定聚类中心点和类个数,但在处理复杂分布形状的数据和高维图像数据时仍存在聚类中心点不容易确定、类数偏少等问题。为了提高其处理复杂高维数据的鲁棒性,文中提出了一种基于学习特征表示的密度峰值快速搜索聚类算法(AE-MDPC)。该算法采用无监督的自动编码器(AutoEncoder)学出数据的最优特征表示,结合能刻画数据全局一致性的流形相似性,提高了同类数据间的紧致性和不同类数据间的分离性,促使潜在类中心点的密度值成为局部最大。在4个人工数据集和4个真实图像数据集上将AE-MDPC与经典的K-means,DBSCAN,DPC算法以及结合了PCA的DPC算法进行比较。实验结果表明,在外部评价指标聚类精度、内部评价指标调整互信息和调整兰德指数上,AE-MDPC的聚类性能优于对比算法,而且提供了更好的可视化性能。总之,基于特征表示学习且结合流形距离的AE-MDPC算法能有效地处理复杂流形数据和高维图像数据。     

基于余弦距离选取初始簇中心的文本聚类研究

文本聚类是文本信息进行有效组织、摘要和导航的重要手段,其中基于余弦相似度的K-means算法是最重要且使用最广泛的文本聚类算法之一。针对基于余弦相似度的K-means算法改进方案设计困难,且众多优异的基于欧氏距离的K-means改进方法无法适用的问题,对余弦相似度与欧氏距离的关系进行探讨,得到标准向量前提下二者的转化公式,并在此基础上定义一种与欧氏距离意义相近关系紧密的余弦距离,使原有基于欧氏距离的K-means改进方法可通过余弦距离迁移到基于余弦相似度的K-means算法中。在此基础上理论推导出余弦K-means算法及其拓展算法的簇内中心点计算方法,并进一步改进了聚类初始簇中心的选取方案,形成新的文本聚类算法MCSKM++。通过实验验证,该算法在迭代次数减少、运行时间缩短的同时,聚类精度得到提高。     

基于邻域关系模糊粗糙集的医学图像分类研究

对医学图像进行分类时,特征选择是影响分类准确率的非常重要的因素。针对医学图像的特殊性,以及目前提出的特征选择算法在应用于医学图像分类时效果不够理想等问题,提出一种基于邻域关系的模糊粗糙集模型,基于该模型给出特征选择算法,并将其应用于乳腺X光图像。实验结果表明,同已有的算法相比,该方法能有效选择特征,分类精度有较大的提升。     

蛋白质相互作用网络的蜂群信息流聚类模型与算法

蛋白质相互作用网络的聚类算法研究是充分理解分子的结构、功能及识别蛋白质的功能模块的重要方法.很多传统聚类算法对于蛋白质相互作用网络聚类效果不佳.功能流模拟算法是一种新型聚类算法,但该算法没有考虑到距离的作用效果并且需要人为地设置合并阈值,带有主观性.文中提出了一种新颖的基于蜂群优化机理的信息流聚类模型与算法.该方法中,数据预处理采用结点网络综合特征值的排序来初始化聚类中心,将蜂群算法的蜜源位置对应于其聚类中心,蜜源的收益度大小对应于模块间的相似度,采蜜蜂结点的所有邻接点按照结点网络综合特征值的降序排列,作为侦察蜂的搜索邻域.采用正确率、查全率等指标对聚类效果做出客观评价,并对算法的一些关键参数进行仿真、对比与分析.结果表明新算法不仅克服了原功能流模拟算法的缺点,且其正确率和查全率的几何平均值最高,能够有效地识别蛋白质功能模块.     

A new unsupervised feature selection algorithm using similarity‐based feature clustering

Unsupervised feature selection is an important problem, especially for high‐dimensional data. However, until now, it has been scarcely studied and the existing algorithms cannot provide satisfying performance. Thus, in this paper, we propose a new unsupervised feature selection algorithm using similarity‐based feature clustering, Feature Selection‐based Feature Clustering (FSFC). FSFC removes redundant features according to the results of feature clustering based on feature similarity. First, it clusters the features according to their similarity. A new feature clustering algorithm is proposed, which overcomes the shortcomings of K‐means. Second, it selects a representative feature from each cluster, which contains most interesting information of features in the cluster. The efficiency and effectiveness of FSFC are tested upon real‐world data sets and compared with two representative unsupervised feature selection algorithms, Feature Selection Using Similarity (FSUS) and Multi‐Cluster‐based Feature Selection (MCFS) in terms of runtime, feature compression ratio, and the clustering results of K‐means. The results show that FSFC can not only reduce the feature space in less time, but also significantly improve the clustering performance of K‐means.     

结合类内和类间距离的可能聚类分割算法

目的 为了进一步提高噪声图像分割的抗噪性和准确性,提出一种结合类内距离和类间距离的改进可能聚类算法并将其应用于图像分割。方法 该算法避免了传统可能性聚类分割算法中仅仅考虑以样本点到聚类中心的距离作为算法的测度,将类内距离与类间距离相结合作为算法的新测度,即考虑了类内紧密程度又考虑了类间离散程度,以便对不同的聚类结构有较强的稳定性和更好的抗噪能力,并且将直方图融入可能模糊聚类分割算法中提出快速可能模糊聚类分割算法,使其对各种较复杂图像的分割具有即时性。结果 通过人工合成图像和实际遥感图像分割测试结果表明,本文改进可能聚类算法是有效的,其分割轮廓清晰,分类准确且噪声较小,其误分率相比其他算法至少降低了2个百分点,同时能获得更满意的分割效果。结论 针对模糊C-均值聚类分割算法和可能性聚类分割算法对于背景和目标颜色相近的图像分类不准确的缺陷,将类内距离与类间距离相结合作为算法的测度有效的解决了图像分割归类问题,并且结合直方图提出快速可能模糊聚类分割算法使其对于大篇幅复杂图像也具有适用性。     

基于互信息与层次聚类双重特征选择的改进朴素贝叶斯算法

根据朴素贝叶斯算法的特征条件独立假设,提出一种基于互信息和层次聚类双重特征选择的改进朴素贝叶斯算法。通过互信息方法剔除不相关的特征,然后依据欧氏距离将删减后的特征进行分层聚类,通过粒子群算法得到聚类簇的数量,最后将每个聚类簇中与类别互信息最高的特征合并为特征子集,并由朴素贝叶斯算法得到分类准确率。根据实验结果可知,该算法可以有效减少特征之间的相关性,提升算法的分类性能。     

采用离群点检测技术的混合型数据聚类初始化方法

近年来,混合型数据的聚类问题受到广泛关注。作为处理混合型数据的一种有效方法,K-prototype聚类算法在初始化聚类中心时通常采用随机选取的策略,然而这种策略在很多实际应用中难以保证聚类结果的质量。针对上述问题,采用基于离群点检测的策略来为K-prototype算法选择初始中心,并提出一种新的混合型数据聚类初始化算法(initialization of K-prototype clustering based on outlier detection and density, IKP-ODD)。给定一个候选对象,IKP-ODD通过计算其距离离群因子、加权密度以及与已有初始中心之间的加权距离来判断候选对象是否是一个初始中心。IKP-ODD通过采用距离离群因子和加权密度,防止选择离群点作为初始中心。在计算对象的加权密度以及对象之间的加权距离时,采用邻域粗糙集中的粒度邻域熵来计算每一个属性的重要性,并根据属性重要性的大小为不同属性赋予不同的权重,有效地反映不同属性之间的差异性。在多个UCI数据集上的实验表明,相对于现有的初始化方法,IKP-ODD能够更好地解决K-prototype聚类的初始化问题。