一种基于路径的划分聚类算法

针对传统的划分聚类算法不能够发现任意形状的簇的缺点,本文引入一种能够有效反映样本间相似度的距离度量---基于路径的距离度量,并设计了新的目标准则函数,从而进一步提高算法的有效性。实验表明本文的算法能够自动确定聚类的个数,可以发现任意形状的类,对孤立点不敏感,而且具有高质量的聚类效果。     

一种基于模糊核聚类的谱聚类算法

谱聚类是对样本拉普拉斯矩阵的特征向量进行聚类,不局限于原始数据的分布形状,可收敛于全局最优解,但不能准确反映样本间的实际关系,而模糊核聚类可利用模糊数学理论确定样本间的模糊关系。为此,在调整相似度度量函数和距离度量函数的基础上,将模糊核聚类融合到谱聚类算法中,提出SC-KFCM算法,利用模糊划分改进谱聚类中的硬划分,根据特征向量间的相似性和关联程度建立模糊隶属关系并对样本进行聚类,从而弥补谱聚类中硬划分部分对聚类结果造成的影响。实验结果表明,SC-KFCM算法在不同分布特点及维数的数据集上均取得了较稳定的聚类结果和较高的聚类精度。     

一种适用于混合型分类数据的聚类算法

传统的K-modes算法采用简单的属性匹配方式计算同一属性下不同属性值的距离，并且计算样本距离时令所有属性权重相等。在此基础上，综合考虑有序型分类数据中属性值的顺序关系、无序型分类数据中不同属性值之间的相似性以及各属性之间的关系等，提出一种更加适用于混合型分类数据的改进聚类算法，该算法对无序型分类数据和有序型分类数据采用不同的距离度量，并且用平均熵赋予相应的权重。实验结果表明，改进算法在人工数据集和真实数据集上均有比K-modes算法及其改进算法更好的聚类效果。     

一种基于聚类集成技术的混合型数据聚类算法

提出了一种基于集成技术和谱聚类技术的混合数据聚类算法CBEST。它利用聚类集成技术产生混合数据间的相似性,这种相似性度量没有对数据特征值分布模型做任何的假设。基于此相似性度量得到的待聚类数据的相似性矩阵,应用谱聚类算法得到混合数据聚类结果。大量真实和人工数据上的实验结果验证了CBEST的有效性和它对噪声的鲁棒性。与其它混合数据聚类算法的比较研究也证明了CBEST的优越性能。CBEST还能有效融合先验知识,通过参数的调节来设置不同属性在聚类中的权重。     

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

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

一种多空间聚类算法

CLARANS算法是经典的划分聚类算法，其核心思想是采用随机重启的局部搜索方式搜索中心点．由于搜索空阀布满了局部最优解的“陷阱”，因此它难以获得全局最优解，从而影响了聚类质量．针对这个缺点，本文将多空闻思想与CLARANS算法相结合，提出了基于多空间思想的CLARANS算法-CABMS（CLARANS Algorithm Based on Multi—Space）．该算法的基本思路是采用空间变换策略构造一系列光滑程度不同的搜索空间，在不同的搜索空间中执行CLARANS算法，并利用前层搜索空间的聚类结果来引导本层搜索空间的聚类．CABMS能够跳过局部最优解的“陷阱”，增大获得全局最优解的概率，达到提高聚类质量的目的．本文给出了等距法多空间构造策略，并通过实验对比了CLARANS算法与CABMS算法的聚类质量．实验结果表明，CABMS的聚类质量较CLARANS有较大改进．     

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

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

一种基于距离的再聚类的离群数据发现算法

通过研究基于离群距离的数据发现（Cell-Based）算法的识别、分析和评价算法,指出了其优越性和不足,提出一种新的离群数据发现算法——基于距离的再聚类离群数据发现算法。理论分析和仿真结果表明,该算法有效地克服了传统的基于距离的数据发现算法易于随参数变化而需要调整单元结构,以及只适用于维度不高的离群数据发现等的缺点,并有效地避免了由于随机初始值选取导致不同的离群数据发现结果问题,同时也有较快的收敛速度。     

基于有效距离的谱聚类算法

在现有多种距离度量和传统谱聚类算法的基础上,提出了一种新的基于有效距离的谱聚类算法(spectral clustering based on effective distance,SCED)。SCED算法通过稀疏重构系数来构建样本与样本之间的有效距离,从而代替传统谱聚类算法中的欧氏距离,进行样本之间的相似度评估。与传统距离度量相比,有效距离不仅利用了样本对之间的距离信息,同时考虑了目标样本与其他所有相关样本之间的距离信息,因而该距离度量具有全局特性。在UCI标准数据集上的实验结果表明,SCED算法能有效提高聚类效果。     

聚类算法综述

大数据时代，聚类这种无监督学习算法的地位尤为突出。近年来，对聚类算法的研究取得了长足的进步。首先，总结了聚类分析的全过程、相似性度量、聚类算法的新分类及其结果的评价等内容，将聚类算法重新划分为大数据聚类与小数据聚类两个大类，并特别对大数据聚类作了较为系统的分析与总结。此外，概述并分析了各类聚类算法的研究进展及其应用概况，并结合研究课题讨论了算法的发展趋势。     

Distance metric learning guided adaptive subspace semi-supervised clustering

Most existing semi-supervised clustering algorithms are not designed for handling high-dimensional data. On the other hand, semi-supervised dimensionality reduction methods may not necessarily improve the clustering performance, due to the fact that the inherent relationship between subspace selection and clustering is ignored. In order to mitigate the above problems, we present a semi-supervised clustering algorithm using adaptive distance metric learning (SCADM) which performs semi-supervised clustering and distance metric learning simultaneously. SCADM applies the clustering results to learn a distance metric and then projects the data onto a low-dimensional space where the separability of the data is maximized. Experimental results on real-world data sets show that the proposed method can effectively deal with high-dimensional data and provides an appealing clustering performance.     

高维数据的增量式聚类算法的距离度量选择研究

合适的距离度量函数对于聚类结果有重要的影响。针对大规模高维数据集,使用增量式聚类算法进行距离度量的选择分析。SpFCM算法是将大规模数据集分成小样本进行增量分批聚类,可在有限的计算机内存中获得较好的聚类结果。在传统的SpFCM算法的基础上,使用不同的距离度量函数来衡量样本之间的相似性,以得出不同的距离度量对SpFCM算法的影响。在不同的大规模高维数据集中,使用欧氏距离、余弦距离、相关系数距离和扩展的杰卡德距离来计算距离。实验结果表明,后3个距离度量相对于欧氏距离可以很大程度地提高聚类效果,其中相关系数距离可以得到较好的结果,余弦距离和扩展的杰卡德距离效果比较一般。     

基于蛋白质相互作用网络的聚类算法研究

蛋白质相互作用网络是计算机科学技术的一个新研究领域。蛋白质相互作用网络中结点之间的距离度量需要通过基于网络的最短路径距离来重新定义,其计算代价高,这使得已有的基于欧几何距离的聚类算法不能直接运用到这种环境中。因此,通过蛋白质相互作用网络的特征提出了一种新的聚类算法。算法使用网络中的边和结点信息来缩减搜索空间,避免了一些不必要的距离计算。实验结果表明,算法对于真实的蛋白质相互作用网络中的结点聚类是高效的。     

The upper bound of the optimal number of clusters in fuzzy clustering

The upper bound of the optimal number of clusters in clustering algorithm is studied in this paper. A new method is proposed to solve this issue. This method shows that the rule cmax≤n~(1/n), which is popular in current papers, is reasonable in some sense. The above conclusion is tested and analyzed by some typical examples in the literature, which demonstrates the validity of the new method.     

密度敏感的数据竞争聚类算法

针对数据竞争聚类算法在处理复杂结构数据集时聚类性能不佳的问题,提出了一种密度敏感的数据竞争聚类算法。首先,在密度敏感距离测度的基础上定义了局部距离,以描述数据分布的局部一致性;其次,在局部距离的基础上计算出数据间的全局距离,用来描述数据分布的全局一致性,挖掘数据的空间分布信息,以弥补欧氏距离描述数据分布全局一致性能力不佳的缺陷;最后,将全局距离用于数据竞争聚类算法中。将新算法与基于欧氏距离的数据竞争聚类算法进行性能比较,在人工数据集和真实数据集上的实验结果表明,该算法克服了数据竞争聚类算法难以处理复杂结构数据的缺点,聚类结果具有更高的准确率。     

加权PageRank改进地标表示的自编码谱聚类算法

针对传统谱聚类算法在处理大规模数据集时,聚类精度低并且存在相似度矩阵存储开销大和拉普拉斯矩阵特征分解计算复杂度高的问题。提出了一种加权PageRank改进地标表示的自编码谱聚类算法,首先选取数据亲和图中权重最高的节点作为地标点,以选定的地标点与其他数据点之间的相似关系来逼近相似度矩阵作为叠加自动编码器的输入。然后利用聚类损失同时更新自动编码器和聚类中心的参数,从而实现可扩展和精确的聚类。实验表明,在几种典型的数据集上,所提算法与地标点谱聚类算法和深度谱聚类算法相比具有更好的聚类性能。     

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

近年来,混合型数据的聚类问题受到广泛关注。作为处理混合型数据的一种有效方法,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聚类的初始化问题。     

快速搜索与发现密度峰值聚类算法的优化研究

CFSFDP是基于密度的新聚类算法,可聚类非球形数据集,具有聚类速度快实现简单等优点。CFSFDP需人工尝试确定密度阈值dc且对一个类中存在多密度峰值的数据无法进行准确聚类,为解决该缺点,本文提出基于近邻距离曲线和类合并优化CFSFDP（简称 NM-CFSFDP）的聚类算法。首先,算法用近邻距离曲线变化情况自动确定密度阈值dc;然后,用本文提出自动确定dc的CFSFDP对数据聚类;最后用本文计算dc值的方法指导类的合并,引入内聚程度衡量参数解决了类合并后不能撤销的难题,从而实现对多密度峰值数据的正确聚类。通过实验对比,NM-CFSFDP算法确实比CFSFDP算法具有更加精确的聚类效果。     

Dynamical study of metallic clusters using the statistical method of time series clustering

We perform common neighbor analysis on the long-time series data generated by isothermal Brownian-type molecular dynamics simulations to study the thermal and dynamical properties of metallic clusters. In our common neighbor analysis, we introduce the common neighbor label (CNL) which is a group of atoms of a smaller size (than the cluster) designated by four numeric digits. The CNL thus describes topologically smaller size atomic configurations and is associated an abundance value which is the number of “degenerate” four digits all of which characterize the same CNL. When the cluster is in its lowest energy state, it has a fixed number of CNLs and hence abundances. At nonzero temperatures, the cluster undergoes different kinds of atomic activities such as vibrations, migrational relocation, permutational and topological isomer transitions, etc. depending on its lowest energy structure. As a result, the abundances of CNLs at zero temperature will change and new CNLs with their respective new abundances are created. To understand the temperature dependence of the CNL dynamics, and hence shed light on the cluster dynamics itself, we employ a novel method of statistical time series analysis. In this method, we perform statistical clustering at two time scales. First, we examine, at given temperature, the signs of abundance changes at a short-time scale, and assign CNLs to two short-time clusters. Quasi-periodic features can be seen in the time evolution of these short-time clusters, based on which we choose a long-time scale to compute the long-time correlations between CNL pairs. We then exploit the separation of correlation levels seen in these long-time correlations to extract strongly-correlated collections of CNLs, which we will identify as effective variables for the long-time cluster dynamics. It is found that certain effective variables show subtleties in their temperature dependences and these thermal traits bear a delicate relation to prepeaks and main peaks seen in clusters Ag₁₄, Cu₁₄ and Cu₁₃Au₁. We therefore infer from the temperature changes of effective variables and locate the temperatures at which these prepeaks and principal peaks appear, and they are evaluated by comparing with those deduced from the specific heat data.     

基于近邻传播聚类和TANE算法的高校数据中函数依赖的发现

针对高校实际数据质量检测过程中数据集存在缺失值以及发现的函数依赖个数较少且不准确的问题,提出了一种结合近邻传播（AP）聚类算法和TANE算法的高校函数依赖发现方法（APTANE）。首先,对数据集中的中文字段进行列剖析,将中文字段值用对应的数值来表示;其次,使用AP聚类算法对数据集中的缺失值进行填补;最后,使用TANE算法从处理好的数据集中自动发现出满足非平凡、最小要求的函数依赖。实验结果表明,在使用AP聚类算法对真实的高校数据集进行修复之后,相比于直接使用函数依赖自动发现算法,发现的函数依赖个数增加到了80个,经过缺失值填补后所发现的函数依赖在表示字段间关联关系时也更加准确,减少了领域专家的工作量,提升了高校数据所拥有数据的质量。