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

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

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

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

基于共享k-近邻与共享逆近邻的密度峰聚类

为了更好地解决密度不均衡问题与刻画高维数据相似性度量问题，提出一种基于共享[k]-近邻与共享逆近邻的密度峰聚类算法。该算法计算两个点的共享[k]-近邻数与共享逆近邻数，并结合欧氏距离来确定这两个点之间的共享相似度；将样本点与其逆近邻点的共享相似度之和定义为该点的共享密度，再通过共享密度选取聚类中心。通过实验证明，该算法在人工数据集和真实数据集上的聚类结果较其他密度聚类算法更加准确，并且能更好地处理密度不均衡问题，同时也提高了高维数据的聚类精度。     

基于共享反K近邻的局部离群点检测算法

离群点检测和分析离群模式隐含的特征是离群点挖掘的重要研究内容.现有离群点检测算法存在两个明显的不足:根据离群度检测离群点,难以确定离群点的数量;忽略了与离群点邻接的聚类信息,不能提供解析离群模式的有效证据.为此,提出一种基于共享反K近邻的离群点检测算法,首先定义了一种对密度和维数变化不敏感的共享反K近邻相似度,然后应用聚类方法将数据集划分为聚类簇和包含离群点的离群簇,从而获取数据集中的离群点及解析离群点的聚类结构.仿真结果表明,反K近邻算法比现有方法更能精确地检测数据集中的局部离群点,具有很好的控制性能.     

一种基于共享近邻亲和度的聚类算法

为解决密度聚类算法在处理高维和多密度数据集时聚类结果不精确的问题,提出一种基于共享近邻亲和度（SNNA）的聚类算法。该算法引入[k]近邻和共享近邻,定义共享近邻亲和度作为对象的局部密度度量。算法首先根据亲和度来提取核心点,然后利用广度优先搜索算法对核心点进行聚类,最后对非核心点进行指派即完成整个数据集的聚类。实验结果表明,该算法能够发现任意形状、大小、密度的聚类;与同类算法相比,SNNA算法在处理高维数据时具有较高的聚类准确率。     

基于局部密度估计和近邻关系传播的谱聚类

对密度分布不均匀的数据采用近邻传播的谱聚类,存在误将不同类的样本传入同一高相似度的子集中的情况,因而得不到真实的相似度矩阵和准确的聚类结果.针对这一问题,提出一种基于局部密度估计和近邻关系传播的谱聚类(LDENP-SC)算法.该算法首先对样本进行密度估计并升维,然后对新数据采用传播算法更新相似度矩阵并谱聚类.在计算密度时提出一种简易的局部密度计算方法,该方法既能反应样本的密度又能减少运算时间;在更新相似度矩阵时基于传播算法提出一种更新子集间样本相似性的方法,使更新后样本的相似度更接近实际.实验结果表明,LDENP-SC算法能够得出取得理想的相似度矩阵和准确的聚类结果,具有较好的泛化能力,且对一定范围内的参数σ表现出鲁棒性.     

基于共享近邻的多视角谱聚类算法

为了解决谱聚类算法中相似矩阵的构造不能满足簇内数据点高度相似的问题,给出一种基于共享近邻的多视角谱聚类算法（MV-SNN）。首先,算法通过提高共享近邻个数多的两个数据点的相似度,使同簇的数据之间的相似度更高;然后,将改进后的多个视角的相似矩阵进行相加从而整合得到全局相似矩阵;最后,为了解决一般谱聚类算法在后期仍需要通过k均值聚类算法进行数据点划分的问题,给出拉普拉斯矩阵秩约束的方法,从而直接通过全局相似矩阵得到最终的类簇结构。实验结果表明,对比其他几种多视角谱聚类算法,MV-SNN算法在三个聚类衡量标准：准确度、纯度和归一化互信息上的性能提高了1%~20%,在聚类时间上减少了50%左右,可见MV-SNN算法的聚类性能更好,用时更短。     

基于共享近邻的多视角谱聚类算法

为了解决谱聚类算法中相似矩阵的构造不能满足簇内数据点高度相似的问题，给出一种基于共享近邻的多视角谱聚类算法（MV-SNN）。首先，算法通过提高共享近邻个数多的两个数据点的相似度，使同簇的数据之间的相似度更高；然后，将改进后的多个视角的相似矩阵进行相加从而整合得到全局相似矩阵；最后，为了解决一般谱聚类算法在后期仍需要通过k均值聚类算法进行数据点划分的问题，给出拉普拉斯矩阵秩约束的方法，从而直接通过全局相似矩阵得到最终的类簇结构。实验结果表明，对比其他几种多视角谱聚类算法，MV-SNN算法在三个聚类衡量标准：准确度、纯度和归一化互信息上的性能提高了1%~20%，在聚类时间上减少了50%左右，可见MV-SNN算法的聚类性能更好，用时更短。     

加权的自适应相似度度量

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

结合共享近邻和流形距离的自适应谱聚类算法

谱聚类算法是建立在图论的基础上,将聚类问题转化为图的划分问题,能识别任意形状的类簇且易于实现,因此比传统聚类算法具有更强的适应性。然而,该算法中常用的距离度量不能同时考虑全局和局部一致性,且易受到噪声影响;聚类结果依赖由输入数据构造的相似度矩阵,且通过特征分解得到松弛划分矩阵和离散化过程的两步独立策略难以得到一个共同最优解。因此,提出一种结合共享近邻和流形距离的自适应谱聚类算法(SNN-MSC),引入一种新的具有指数项和比例因子的流形距离,可以灵活调整同一流形内数据的相似度和不同流形之间数据的相似度之比,并将密度因子纳入流形距离度量中,以消除噪声影响;采用共享近邻重新定义相似度度量,能挖掘数据点之间的空间结构和局部关系;同时,对拉普拉斯矩阵施加秩约束,使相似度矩阵中的连通分量完全等于簇个数,能够在优化求解过程中自适应优化数据相似度矩阵和聚类结构,无须再进行离散化操作。在人工数据集和UCI真实数据集上的对比实验显示,所提算法在多个聚类有效性指标上能体现出更好的性能。     

基于共享最近邻的密度自适应邻域谱聚类算法

在谱聚类算法没有先验信息的情况下,对于具有复杂形状和不同密度变化的数据集很难构建合适的相似图,且基于欧氏距离的高斯核函数的相似性度量忽略了全局一致性。针对该问题,提出一种基于共享最近邻的密度自适应邻域谱聚类算法（SC-DANSN）。通过一种无参数的密度自适应邻域构建方法构建无向图,将共享最近邻作为衡量样本之间的相似性度量进而消除参数对构建相似图的影响,体现全局和局部的一致性。实验结果表明,SC-DANSN算法相比K-means算法和基于K最近邻的谱聚类算法（SC-KNN）具有更高的聚类精度,同时相比SC-KNN算法对参数的选取敏感性更低。     

公理化模糊共享近邻自适应谱聚类算法

针对传统的谱聚类算法通常利用高斯核函数作为相似性度量,且单纯以距离决定相似性不能充分表现原始数据中固有的模糊性、不确定性和复杂性,导致聚类性能降低的问题。提出了一种公理化模糊共享近邻自适应谱聚类算法,首先结合公理化模糊集理论提出了一种模糊相似性度量方法,利用识别特征来衡量更合适的数据成对相似性,然后采用共享近邻的方法发现密集区域样本点分布的结构和密度信息,并且根据每个点所处领域的稠密程度自动调节参数σ,从而生成更强大的亲和矩阵,进一步提高聚类准确率。实验表明,相较于距离谱聚类、自适应谱聚类、模糊聚类方法和地标点谱聚类,所提算法有着更好的聚类性能。     

基于共享近邻的成对约束谱聚类算法

谱聚类算法是基于谱图划分理论的一种机器学习算法，它能在任意形状的样本空间上聚类且收敛于全局最优解。但是传统的谱聚类算法很难正确发现密度相差比较大的簇，参数的选取要靠多次实验和个人经验。结合半监督聚类的思想，在给出一部分监督信息的前提下，提出了一种基于共享近邻的成对约束谱聚类算法（Pairwise Constrained Spectral Clustering Based on Shared Nearest Neighborhood，PCSC-SN）。PCSC-SN算法是用共享近邻去衡量数据对之间的相似性，用主动约束信息找到两个数据点之间的关系。在数据集UCI上做了一系列的实验，实验结果证明，与传统的聚类算法相比，PCSC-SN算法能够获得更好的聚类效果。     

基于堆和邻域共存信息的KNN相似图算法

在谱聚类算法中,相似图的构造至关重要,对整个算法的聚类结果和运行效率都有着巨大影响。为了加快谱聚类的运算速度和通过近邻截断提高其性能,通常选择K近邻(KNN)方法来构造稀疏的相似图,而K近邻图对离群点非常敏感,这种噪声边会严重影响聚类算法的性能。文中提出了一种新的高效稀疏亲和图构造方法HCKNN,其中基于堆的K近邻搜索比基于排序的近邻选择在效率方面提升了log(n),基于邻域共存累计的阈值化来进行邻域约减不仅能够去除噪声边以提高聚类性能,还能进一步稀疏化相似矩阵,从而加速谱聚类中的特征分解。     

基于共享近邻相似度的密度峰聚类算法

密度峰聚类是一种基于密度的高效聚类方法,但存在对全局参数d_c敏感和需要人工干预决策图进行聚类中心选择的缺陷。针对上述问题,提出了一种基于共享近邻相似度的密度峰聚类算法。首先,该算法结合欧氏距离和共享近邻相似度进行样本局部密度的定义,避免了原始密度峰聚类算法中参数d_c的设置;其次,优化聚类中心的选择过程,能够自适应地进行聚类中心的选择;最后,将样本分配至距其最近并拥有较高密度的样本所在的簇中。实验结果表明,在UCI数据集和模拟数据集上,该算法与原始的密度峰聚类算法相比,准确率、标准化互信息（NMI）和F-Measure指标分别平均提高约22.3%、35.7%和16.6%。该算法能有效地提高聚类的准确性和聚类结果的质量。     

基于网格和最近邻居的聚类算法

针对目前已有的聚类算法不能很好地处理包含不同密度的簇数据,或者不能很好地区分相邻的密度相差不大的簇的问题,提出1种新的基于严格最近邻居和共享最近邻居的聚类算法．通过构造共享严格最近邻图,使样本点在密度一致的区域保持连接,而在密度不同的相邻区域断开连接,并尽可能去除噪声点和孤立点．该算法可以处理包含有不同密度的簇数据,而且在处理高维数据时具有较低的时间复杂度、实验结果证明,该算法能有效找出不同大小、形状和密度的聚类．     

基于共享近邻和优化关联策略的边界剥离聚类

边界剥离聚类算法(BP)是一种基于密度的聚类算法,它通过逐渐剥离边界点来揭示聚类的潜在核心,已经被证明是一种十分有效的聚类手段.然而, BP算法仍存在一些不足之处:一方面,数据点的局部密度仅考虑了距离特征,使得边界点的确定不够合理;另一方面, BP算法中的关联策略容易误判异常值,并且在分配边界点时容易产生连带错误.为此,本文提出了一种基于共享近邻和优化关联策略的边界剥离聚类算法(SOBP).该算法使用了基于共享近邻的局部密度函数来更好地探索数据点之间的相似性,同时优化了BP算法中的关联策略,使得每次迭代中边界点不再仅与一个非边界点进行关联,并进一步采用了边界点与非边界点、已剥离边界点之间的双重关联准则.在一些数据集上的测试表明,相较于其他6种经典算法,该算法在评估指标上表现更佳.