大规模数据集引力同步聚类

受Kuramoto模型启发,构造一种新的万有引力同步模型,用以解决现有同步聚类算法时间复杂度高的问题,并提出大规模数据集的引力同步聚类算法(LSCGS).首先,使用快速压缩集密度估计(RSDE)算法对大规模数据集进行压缩;然后,通过万有引力同步聚类算法对压缩数据集进行聚类,使用Davies-Bouldin指标自动寻优到最佳聚类数;最后,利用提出的剩余样本聚类(RSC)算法对除压缩集以外的剩余数据进行聚类,可以有效地区分孤立类以及噪声点.通过在大规模人造数据集、UCI真实数据集和图像数据上的实验,验证LSCGS算法的有效性,与传统同步聚类算法相比,聚类的运算成本得到大幅度的降低.     

在大规模数据集上进行快速自适应同步聚类

现有的同步聚类方法Sync在同步过程中需要将样本中的每一个分量看作相位振子进行计算,具有较高的时间复杂度,因此在大规模数据集上聚类时具有相当大的局限性.为了解决这一问题,提出了快速自适应同步聚类方法(fast adaptive KDE-based clustering by synchronization,FAKCS).FAKCS首先引入基于压缩集密度估计和中心约束最小包含球技术的快速压缩方法对大规模数据集进行压缩,然后通过使用Davies-Bouldin指标,在压缩集上进行ε参数自适应的同步聚类,并采用新定义的序列参量来评价局部同步的程度.另外,研究了序列参量和核密度估计间的联系,从理论上揭示了样本点的局部同步在概率密度意义下的本质.FAKCS可以在大规模数据集上得到任意形状、个数、密度的聚类而无需预设聚类数目.在图像分割和大规模UCI数据集上的实验验证了FAKCS的有效性.     

基于自适应可达距离的密度峰值聚类算法

针对基于快速搜索和发现密度峰值的聚类（CFSFDP）算法中截断距离需要人工选取,以及最近邻分配带来的误差导致的在具有不同密度簇的复杂数据集上的聚类效果不佳的问题,提出了一种基于自适应可达距离的密度峰值聚类（ARD-DPC）算法。该算法利用非参数核密度估计方法计算点的局部密度,根据决策图选取聚类中心,并利用自适应可达距离分配数据点,从而得到最终的聚类结果。在4个合成数据集和6个UCI数据集上进行了仿真实验,将所提算法ARD-DPC与基于快速搜索和发现密度峰值的聚类（CFSFDP）、基于密度的噪声应用空间聚类（DBSCAN）、基于密度自适应距离的密度峰聚类（DADPC）算法进行了比较,实验结果表明,相比其他三种算法,ARD-DPC算法在7个数据集上的标准化互信息（NMI）、兰德指数（RI）和F1-measure取得了最大值,在2个数据集分别取得F1-measure和NMI的最大值,只对模糊度较高、聚类特征不明显的Pima数据集聚类效果不佳;同时,ARD-DPC算法在合成数据集上能准确地识别出聚类数目和具有复杂密度的簇。     

医学图像分割中基于数据浓缩的谱聚类算法

基于传统Parzen窗密度估计函数的均值漂移谱聚类算法的时间复杂度不低于O(N2),不适合医学图像分割的实际需求。为此,通过压缩集密度估计和吸引盆均匀抽样两重数据浓缩策略以降低原MSSC的高时间开销问题,从而提出新的基于数据浓缩的谱聚类算法。实验结果表明,该算法能有效降低时间开销,较好地适应医学图像分割的要求。     

核密度估计及其在聚类算法构造中的应用

经典数理统计学中的核密度估计理论是构造基于数据集密度函数聚类算法的理论基础，采用分箱近似的快速核密度函数估计方法同样为构造高效的聚类算法提供了依据．通过对核密度估计理论及其快速分箱核近似方法的讨论，给出分箱近似密度估计相对于核密度估计的均方误差界，提出基于网格数据重心的分箱核近似方法．在不改变计算复杂度的条件下，基于网格数据重心的分箱核近似密度函数计算可以有效地降低近似误差，这一思想方法对于构造高效大规模数据聚类分析算法具有指导意义．揭示了基于网格上密度函数近似的聚类算法与核密度估计理论之间的关系．     

面向大规模数据的快速多代表点仿射传播算法

针对原始的仿射传播(affinity propagation,AP)聚类算法难以处理多代表点聚类,以及空间和时间开销过大等问题,提出了快速多代表点仿射传播(multi-exemplar affinity propagation using fast reduced set density estimator,FRSMEAP)聚类算法。该算法在聚类初始阶段,引入快速压缩集密度估计算法(fast reduced set density estimator,FRSDE)对大规模数据集进行预处理,得到能够充分代表样本属性的压缩集;在聚类阶段,使用多代表点仿射传播(multi-exemplar affinity propagation,MEAP)聚类算法,获得比AP更加明显的聚类决策边界,从而提高聚类的精度;最后再利用K-邻近(K-nearest neighbor,KNN)算法分配剩余点得到最终的数据划分。在人工数据集和真实数据集上的仿真实验结果表明,该算法不仅能在大规模数据集上进行聚类,而且具有聚类精度高和运行速度快等优点。     

基于随机抽样的加速 K-均值聚类方法

针对传统K-均值聚类方法不能有效处理大规模数据聚类的问题,提出一种基于随机抽样的加速K-均值聚类（K-means Clustering Algorithm Based on Random Sampling , Kmeans＿RS）方法,以提高传统K-均值聚类方法的效率。首先从大规模的聚类数据集中进行随机抽样,得到规模较小的工作集,在工作集上进行传统K-均值聚类,得到聚类中心和半径,并得到抽样结果;然后通过衡量剩下的聚类样本与已得到的抽样结果之间的关系,对剩余的样本进行归类。该方法通过随机抽样大大地减小了参与K-均值聚类的问题规模,从而有效提高了聚类效率,可解决大规模数据的聚类问题。实验结果表明,Kmeans＿RS方法在大规模数据集中在保持聚类效果的同时大幅度提高了聚类效率。     

快速核密度估计定理和大规模图论松弛聚类方法

首先证明了快速核密度估计 (Fast kernel density estimate, FKDE) 定理: 基于抽样子集的高斯核密度估计(KDE)与原数据集的KDE间的误差与抽样容量和核参数相关, 而与总样本容量无关. 接着本文揭示了基于高斯核形式的图论松弛聚类(Graph-based relaxed clustering, GRC)算法的目标表达式可分解成“Parzen窗加权和 + 平方熵”的形式, 即此时GRC可视作一个核密度估计问题, 这样基于KDE近似策略, 本文提出了大规模图论松弛聚类方法(Scaling up GRC by KDE approximation, SUGRC-KDEA). 较之先前的工作, 这一方法的优势在于为GRC作用于大规模数据集提供了更简单和易于实现的方案.     

考虑类内不平衡的谱聚类过抽样方法

不平衡数据分类问题是数据挖掘领域的关键挑战之一。过抽样方法是解决不平衡分类问题的一种有效手段。传统过抽样方法没有考虑类内不平衡,为此提出基于改进谱聚类的过抽样方法。该方法首先自动确定聚类簇数,并对少数类样本进行谱聚类,再根据各类内包含样本数与总少数类样本数之比,确定在类内合成的样本数量,最后通过在类内进行过抽样,获得平衡的新数据集。在4个实际数据集上验证了算法的有效性。并在二维合成数据集上对比k均值聚类和改进谱聚类的结果,解释基于两种不同聚类的过抽样算法性能差异的原因。     

基于核密度估计的K-CFSFDP聚类算法

快速搜索和发现密度峰值的聚类算法(Clustering by Fast Search and Find of Density Peaks,CFSFDP)是一种新的基于密度的聚类算法,它通过发现密度峰值来有效地识别类簇中心,具有聚类速度快、实现简单等优点。针对CFSFDP算法的准确性依赖于数据集的密度估计和截断距离(dc)的人为选择问题,提出一种基于核密度估计的K-CFSFDP算法。该算法利用无参的核密度估计分析数据点的分布特征并自适应地选取dc,从而搜索和发现数据点的密度峰值,并以峰值点数据作为初始聚类中心。基于4个典型数据集的仿真结果表明,K-CFSFDP算法比CFSFDP,K-means和DBSCAN算法具有更高的准确度和更强的鲁棒性。     

基于近邻传播算法的半监督聚类

提出了一种基于近邻传播(affinity propagation,简称AP)算法的半监督聚类方法.AP是在数据点的相似度矩阵的基础上进行聚类.对于规模很大的数据集,AP算法是一种快速、有效的聚类方法,这是其他传统的聚类算法所不能及的,比如:K中心聚类算法.但是,对于一些聚类结构比较复杂的数据集,AP算法往往不能得到很好的聚类结果.使用已知的标签数据或者成对点约束对数据形成的相似度矩阵进行调整,进而达到提高AP算法的聚类性能.实验结果表明,该方法不仅提高了AP对复杂数据的聚类结果,而且在约束对数量较多时,该方法要优于相关比对算法.     

基于Spark的点排序识别聚类结构算法

点排序识别聚类结构(Ordering Points to Identify the Clustering Structure,OPTICS)的密度聚类算法能以可视化的方式导出数据集的内在聚类结构,并且可以通过簇排序提取基本的聚类信息。但是该算法由于时空复杂度较高,不能很好地适应当今社会出现的大型数据集。随着云计算和并行计算的发展,提供了一种解决OPTICS算法复杂度缺陷的方法和一种建立在基于Spark内存计算平台的点排序识别聚类结构并行算法。测试的实验结果表明,它能极大地降低OPTICS算法对时间和空间的需要。     

基于网格技术的高维大数据集离群点挖掘算法

提出了一种基于网格技术的高维大数据集离群点挖掘算法（OMAGT）。该算法针对高维大数据集的分布特性，首先采用基于网格技术的方法寻找出聚类区域，并删除聚类区域内不可能成为离群点的聚类点集，然后运用局部离群因子（LOF）算法对剩下的点集进行离群点挖掘。OMAGT算法较好地实现了聚类信息的动态释放，将保留的离群点挖掘信息控制在一定的内存容量范围内，提高了算法的时间效率和空间效率。理论分析与实验结果表明OMAGT算法是可行和有效的。     

加速大规模数据集的离群点检测

针对现有基于距离的离群点检测算法在处理大规模数据时效率低的问题,提出一种基于聚类和索引的分布式离群点检测(DODCI) 算法。首先利用聚类方法将大数据集划分成簇;然后在分布式环境中的各节点处并行创建各个簇的索引;最后使用两个优化策略和两条剪枝规则以循环的方式在各节点处进行离群点检测。在合成数据集和整理后的KDD CUP数据集上的实验结果显示,在数据量较大时该算法比Orca和iDOoR算法快近一个数量级。理论和实验分析表明,该算法可以有效提高大规模数据中离群点的检测效率。     

基于网格最小生成树的聚类算法选择

为得到好的聚类效果,需要挑选适合数据集簇结构的聚类算法。文中提出基于网格最小生成树的聚类算法选择方法,为给定数据集自动选择适合的聚类算法。该方法首先在数据集上构建出网格最小生成树,由树的数目确定数据集的潜在簇结构,然后为数据集选择适合所发现簇结构的聚类算法。实验结果表明该方法较有效,能为给定数据集找出适合其潜在簇结构的聚类算法。     

Parallel WaveCluster: A linear scaling parallel clustering algorithm implementation with application to very large datasets

A linear scaling parallel clustering algorithm implementation and its application to very large datasets for cluster analysis is reported. WaveCluster is a novel clustering approach based on wavelet transforms. Despite this approach has an ability to detect clusters of arbitrary shapes in an efficient way, it requires considerable amount of time to collect results for large sizes of multi-dimensional datasets. We propose the parallel implementation of the WaveCluster algorithm based on the message passing model for a distributed-memory multiprocessor system. In the proposed method, communication among processors and memory requirements are kept at minimum to achieve high efficiency. We have conducted the experiments on a dense dataset and a sparse dataset to measure the algorithm behavior appropriately. Our results obtained from performed experiments demonstrate that developed parallel WaveCluster algorithm exposes high speedup and scales linearly with the increasing number of processors.     

基于数据集压缩的聚类算法性能优化研究

针对目前聚类算法对大数据集的聚类分析中存在时间花费过大的问题,提出了一种基于最近邻相似性的数据集压缩算法。通过将若干个相似性最近邻的数据点划分成一个数据簇并随机选择簇头构成新的数据集,大大缩减了数据的规模。然后分别采用k-means算法和AP算法对压缩后的数据集进行聚类分析。实验结果表明,压缩后的数据集与原始数据集的聚类分析相比,在保证聚类准确率基本一致的前提下有效降低了聚类的花费时长,提高了算法的聚类性能,证明该数据集压缩算法在聚类分析中的有效性与可靠性。     

一种优化初始点与自适应半径的密度聚类算法

传统DBSCAN算法不能正确聚类密度不均匀的数据集,聚类结果受邻域阈值和密度阈值参数的影响较大。提出一种新的优化初始点和自适应半径的密度聚类算法。利用反向最近邻和相似度矩阵发现当前全局密度最大的数据样本,分析该样本周围密度的分布情况,采用自适应的方法计算当前簇的邻域阈值,并利用DBSCAN算法进行聚类。在人工数据集和UCI数据集上进行测试的结果表明,与经典的DBSCAN、OPTICS、RNN-DBSCAN算法相比,优化初始点和自适应半径的密度聚类算法在ARI、NMI、Homogeneity、Completeness和V-measure 5个评价指标上整体取得最优值,其中在Compound、Jain等数据集上达到1.0,具有较高的聚类效率和准确度。     

基于最近邻相似度的孤立点检测及半监督聚类算法

传统的聚类算法是一种无监督的学习过程,聚类的精度受到相似性度量方式以及数据集中孤立点的影响,并且算法也没有很好的利用先验知识,无法体现用户的需求。因此提出了基于共享最近邻的孤立点检测及半监督聚类算法。该算法采用共享最近邻为相似度,根据数据点的最近邻居数目来判断是否为孤立点,并在删除孤立点的数据集上进行半监督聚类。在半监督聚类过程中加入了经过扩展的先验知识,同时根据图形分割原理对数据集进行聚类。文中使用真实的数据集进行仿真,其仿真结果表明,本文所提出的算法能有效的检测出孤立点,并具有很好的聚类效果。