密度敏感的层次化聚类算法研究

以密度敏感距离作为相似性测度,结合近邻传播聚类算法和谱聚类算法,提出了一种密度敏感的层次化聚类算法。算法以密度敏感距离为相似度,多次应用近邻传播算法在数据集中选取一些“可能的类代表点”;用谱聚类算法将“可能的类代表点”再聚类得到“最终的类代表点”;每个数据点根据其类代表点的类标签信息找到自己的类标签。实验结果表明,该算法在处理时间、内存占用率和聚类错误率上都优于传统的近邻传播算法和谱聚类算法。     

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

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

基于秩约束密度敏感距离的自适应聚类算法

传统的聚类算法一般使用欧氏距离获得数据的相似矩阵,在处理一些较复杂的数据时,欧氏距离由于不能反映全局一致性,因此无法有效地描述出数据点的实际分布。提出了一种基于秩约束密度敏感距离(Rank Constraints Density Sensitive Distance,RCDSD) 的自适应聚类算法。该方法首先引入密度敏感距离的相似性度量得到相似矩阵,有效地扩大了不同类数据点之间的距离,缩小了同类数据点间的距离,从而解决了传统聚类算法使用欧氏距离作为相似性度量导致聚类结果出现偏差的弊端;其次,在相似矩阵的拉普拉斯矩阵上施加秩约束,使相似矩阵的连通区域数等于聚类数,直接将数据点划分到正确的类中,得到最终的聚类结果,而不需要执行k-means或其它离散化程序。在人工仿真数据集和真实数据集上进行了大量实验,结果表明,所提算法得到了准确的聚类结果,并提高了聚类性能。     

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

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

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

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

用于彩图分割的自适应谱聚类算法

针对自调节谱聚类算法的缺陷,提出一种新的自适应谱聚类算法。它用全局平均N近邻距离作为比例参数σ,利用本征矢差异来估计最佳聚类分组数k,达到了比前者更好的效果,且更容易实现。在彩色图像分割实际应用中的实验结果表明,该算法适应性强、计算代价小、精度较高,性能好于或至少不差于以往的类似算法。     

密度敏感的距离测度在特定图像聚类中的应用

根据聚类假设,提出一种新的基于图的半监督学习算法,称为密度敏感的半监督聚类。该算法引入一种密度敏感的距离测度,它能较好地反映聚类假设,并且充分挖掘了数据集中复杂的内在结构信息,同时与基于图的半监督学习方法相结合,使得算法在聚类性能上有了显著的提高。经过实验仿真进一步表明,该算法在特定图像应用上具有优越性。     

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

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

基于密度峰值优化的谱聚类算法

针对经典谱聚类算法无法自适应确定聚类数目、以及在处理大数据量的聚类问题时效率不高的问题,本文提出了一种基于密度峰值优化的谱聚类算法。该方法首先计算数据对象的局部密度,以及每个数据对象与较其他数据对象的最小距离,并依据一定的规则自适应产生初始聚类中心,确定聚类数目。其次,使用Nystr?m抽样来降低特征分解的计算复杂度以达到提高谱聚类算法的效率。实验结果表明,本文方法能够准确地得到聚类数目,并且有效提高聚类的准确率和效率。     

密度敏感的多智能体进化聚类算法

采用密度敏感距离作为数据相似性度量,并基于多智能体进化的思想提出了一种密度敏感的多智能体进化聚类(density sensitive based multi-agent evolutionary clustering,简称DSMAEC)算法.算法设计了一种基于连接的编码方式,通过解码过程可直接得到最终的聚类结果,无需事先确定聚类类别数,有效地克服了对领域知识的依赖.针对聚类问题,设计了3个有效的进化算子来模拟智能体间的竞争、合作和自学习行为,共同完成智能体的进化,最终达到对数据聚类的目的.分别对人工数据集、UCI数据集以及合成纹理图像进行仿真,实验结果表明,该算法不但可以自动确定聚类类别数,而且能够应付不同结构的数据,适应不同的聚类要求,具有较强的实用价值.     

密度自适应的半监督谱聚类算法

谱聚类是一种新兴的聚类算法,数据点间的相似度定义对其聚类效果起着至关重要的作用。传统的谱聚类算法通常利用高斯核函数作为相似度函数,但是对于多密度的数据往往不能取得良好的效果。在定义新的相似度函数的基础上,提出了一种密度自适应的半监督聚类算法。该算法结合半监督聚类的成对约束理论,利用先验信息对样本点之间的相似度进行自适应调整,提高了聚类的精度。该算法在人工数据集和真实数据集上的仿真实验都取得了良好的效果。     

基于低密度分割几何距离的半监督KFDA算法

提出了一种基于低密度分割几何距离的半监督KFDA(kernelFisherdiscriminantanalysis)算法(semisupervised KFDA based on low density separation geometry distance,简称Semi GKFDA).该算法以低密度分割几何距离作为相似性度量,通过大量无标签样本,提高KFDA算法的泛化能力.首先,利用核函数将原始空间样本数据映射到高维特征空间中;然后,通过有标签样本和无标签样本构建低密度分割几何距离测度上的内蕴结构一致性假设,使其作为正则化项整合到费舍尔判别分析的目标函数中;最后,通过求解最小化目标函数获得最优投影矩阵.人工数据集和UCI数据集上的实验表明,该算法与KFDA及其改进算法相比,在分类性能上有显著提高.此外,将该算法与其他算法应用到人脸识别问题中进行对比,实验结果表明,该算法具有更高的识别精度.     

自适应快速搜索密度峰值聚类算法

CFSFDP算法（Clustering by Fast Search and Find of Density Peaks）具有简单高效且需要较少参数的优点,但存在需要人为确定截断距离参数和聚类中心的不足。为克服以上不足,提出了自适应快速搜索密度峰值聚类算法。该算法针对截断距离参数的确定问题,构造关于截断距离参数的局部密度信息熵,通过最小化信息熵自适应地确定截断距离参数;针对聚类中心的确定问题,利用从非聚类中心到聚类中心数据点局部密度和距离的乘积,存在明显跳跃这一特征确定阈值,从而能自动确定聚类中心。实验结果表明该算法能够取得较好的聚类性能,且无需人为确定截断距离参数和聚类中心。     

改进的自适应谱聚类NJW算法

聚类算法是近年来国际上机器学习领域的一个新的研究热点。为了能在任意形状的样本空间上聚类,学者们提出了谱聚类和图论聚类等优秀的算法。首先介绍了图论聚类算法中的谱聚类经典NJW算法和NeiMu图论聚类算法的基本思路,提出了改进的自适应谱聚类NJW算法。提出的自适应NJW算法的优点在于无需调试参数,即可自动求出聚类个数,克服了经典NJW算法需要事先设置聚类个数且需反复调试参数δ才能得出数据分类结果的缺点。在UCI标准数据集及实测数据集上对自适应NJW算法与经典NJW算法、自适应NJW算法与NeiMu图论聚类算法进行了比较。实验结果表明,自适应NJW算法方便快捷,且具有较好的实用性。     

自然邻居密度极值聚类算法

针对密度峰值聚类算法存在数据集密度差异较大时,低密度区域聚类中心难以检测和参数敏感的问题,提出了一种新型密度极值算法。引入自然邻居概念寻找数据对象自然近邻,定义椭圆模型计算自然稳定状态下数据局部密度;计算数据对象余弦相似性值,用余弦相似性值来更新数据对象连通值,采用连通值划分高低密度区域和离群点;构造密度极值函数找到高低密度不同区域聚类中心点;将不同区域非聚类中心点归并到离其最近的聚类中心所在簇中。通过在合成数据集和UCI公共数据集实验分析：该算法比其他对比算法在处理密度分布差异较大数据集上取得了更好的结果。     

基于问题性质的分布式低碳并行机调度算法研究

针对分布式低碳并行机调度问题(Distributed low carbon parallel machine scheduling problem, DLCPMSP), 由于该问题子问题众多, 为此, 首先将问题转换为扩展的低碳不相关并行机调度问题以降低子问题的数量; 然后提出了一种基于问题性质的非劣排序遗传算法-Ⅱ(Property-based non-dominated sorting genetic algorithm-Ⅱ, PNSGA-Ⅱ)以同时最优化总延迟时间和总能耗, 该算法运用针对问题特征的两种启发式算法初始化种群, 给出了问题的四种性质及证明, 提出了两种基于问题性质的局部搜索方法.运用大量实例进行了算法策略分析和对比实验, 结果分析表明, PNSGA-Ⅱ在求解DLCPMSP方面具有较强优势.     

基于新型光谱相似度量的高光谱影像谱聚类算法

高斯径向基函数是基于光谱向量间欧氏距离的度量,其对于同种地物光谱变化的适应性较弱,使得基于高斯径向基函数的高光谱影像谱聚类算法的性能下降。为了解决该问题,从光谱曲线形状描述出发,基于光谱角度余弦提出了一种新型光谱相似度量,并将其用于构建谱聚类算法的亲和度矩阵。最后利用多组高光谱数据进行了实验分析,结果证明了该算法的有效性。     

一种基于局部密度的分布式聚类挖掘算法

分布式聚类挖掘技术是解决数据集分布环境下聚类挖掘问题的有效方法.针对数据水平分布情况,在已有分布式密度聚类算法DBDC(density based distributed clustering)的基础上,引入局部密度聚类和密度吸引子等概念,提出一种基于局部密度的分布式聚类算法——LDBDC(local density based distributed clustering).算法适用于含噪声数据和数据分布异常情况,对高雏数据有着良好的适应性.理论分析和实验结果表明,LDBDC算法在聚类质量和算法效率方面优于已有的DBDC算法和SDBDC(scalable dellsity-based distributed clustering)算法.算法是有效、可行的.