K-means算法最佳聚类数确定方法

K-means聚类算法是以确定的类数k为前提对数据集进行聚类的,通常聚类数事先无法确定。从样本几何结构的角度设计了一种新的聚类有效性指标,在此基础上提出了一种新的确定K-means算法最佳聚类数的方法。理论研究和实验结果验证了以上算法方案的有效性和良好性能。     

基于聚类准则函数的改进K-means算法

K-means算法所使用的聚类准则函数是将数据集中各个簇的误差平方值直接相加而得到的,不能有效处理簇的密度不均且大小差异较大的数据集。为此,将K-means算法的聚类准则函数定义为加权的簇内标准差之和,权重为簇内数据对象数占总数目的比例。同时,调整了传统K-means算法将数据对象重新分配给簇的方法,采用一个数据对象到中心点的加权距离代替传统K-means算法中的距离,将数据对象分配给使加权距离最小的中心点所在的簇。实验结果表明,针对模拟数据集的聚类,改进K-means算法可以明显减少大而稀的簇中数据对象被错误地分配到相邻的小而密簇的可能性,改善了聚类的质量;针对UCI数据集的聚类,改进算法使得各个簇更为紧凑,从而验证了改进K-means算法的有效性。     

考虑边界样本邻域归属信息的粗糙K-means增量聚类算法

在原有数据聚类结果的基础上,如何对新增数据进行归属度量分析是提高增量式聚类质量的关键,现有增量式聚类算法更多地是考虑新增数据的位置分布,忽略其邻域数据点的归属信息.在粗糙K-means聚类算法的基础上,针对边界区域新增数据点的不确定性信息处理,提出一种基于邻域归属信息的粗糙K-means增量式聚类算法.该算法综合考虑边界区域新增数据样本的位置分布及其邻域数据点的类簇归属信息,使得新增数据点与各类簇的归属度量更为合理;此外,在增量式聚类过程中,根据新增数据点所导致的类簇结构的变化,对类簇进行相应的合并或分裂操作,使类簇划分可以自适应调整.在人工数据集和UCI标准数据集上的对比实验结果验证了算法的有效性.     

基于K-means的最佳聚类数确定方法研究

确定数据集的最佳聚类数是聚类研究中的一个重要难题。为了更有效地确定数据集的最佳聚类数,该文提出了通过改进K-means算法并结合一个不依赖于具体算法的有效性指标Q(c)对数据集的最佳聚类数进行确定的方法。理论分析和实验结果证明了该方法具有良好的性能和有效性。     

基于类轮廓层次聚类方法的研究

传统的聚类算法在考虑类与类之间的连通性特征和近似性特征上往往顾此失彼。首先给出类边界点和类轮廓的基本定义以及寻求方法,然后基于类间连通性特征和近似性特征的综合考虑,拟定一些类间相似性度量标准和方法,最后提出一种基于类轮廓的层次聚类算法。该算法能够有效处理任意形状的簇,且能够区分孤立点和噪声数据。通过对图像数据集和Iris标准数据集的聚类分析,验证了该算法的可行性和有效性。     

一种基于图论的聚类算法NeiMu

提出一种新的基于图论的聚类算法NeiMu。该算法首先分析数据中的对象,寻找每个对象的k近邻,根据k近邻关系构造k近邻有向图,然后通过k近邻有向图中的k-互邻居关系构造k-聚类图,发现数据中的自然聚类。算法的特点是根据数据之间的互为k近邻关系确定数据中的自然簇,而不必引入其他方法来划分小簇,从而能够保证对象不会被错误聚类,仅会与其他小簇一起融合到一个大簇中。这一优点可以有效保证NeiMu算法的聚类质量。而且,NeiMu算法给出的这种类似自底向上的层次聚类结果还有利于用户根据渐变的结果确定最佳的k值。实验结果表明,该算法对密度变化大的数据、大小相差大的数据、任意分布形状的数据均具有很好的聚类质量,对孤立点也很健壮。     

基于数据场的类簇中心选取及其聚类

针对现有聚类算法普遍存在聚类质量低、参数依赖性大、孤立点难识别等问题,提出一种基于数据场的聚类算法。该算法通过计算每个数据对象点的势值,根据类簇中心的势值比周围邻居的势值大,且与其他类簇中心有相对较大距离的特点,确定类簇中心;根据孤立点的势值等于零的特点,选出孤立点;最后将其他数据对象点划分到比自身势值大且最近邻的类簇中,从而实现聚类。仿真实验表明,该算法在不需要人为调参的情况下准确找出类簇中心和孤立点,聚类效果优良,且与数据集的形状无关。     

基于层次划分的最佳聚类数确定方法

确定数据集的聚类数目是聚类分析中一项基础性的难题.常用的trail-and-error方法通常依赖于特定的聚类算法,且在大型数据集上计算效率欠佳.提出一种基于层次思想的计算方法,不需要对数据集进行反复聚类,它首先扫描数据集获得CF(clusteringfeature,聚类特征)统计值,然后自底向上地生成不同层次的数据集划分,增量地构建一条关于不同层次划分的聚类质量曲线;曲线极值点所对应的划分用于估计最佳的聚类数目.另外,还提出一种新的聚类有效性指标用于衡量不同划分的聚类质量.该指标着重于簇的几何结构且独立于具体的聚类算法,能够识别噪声和复杂形状的簇.在实际数据和合成数据上的实验结果表明,新方法的性能优于新近提出的其他指标,同时大幅度提高了计算效率.     

一种改进K-means算法的聚类算法CARDBK

CARDBK聚类算法与批K-means算法的不同之处在于,每个点不是只归属于一个簇,而是同时影响多个簇的质心值,一个点影响某一个簇的质心值的程度取决于该点与其它离该点更近的簇的质心之间的距离值。 从聚类结果的熵、纯度、F1值、Rand Index和NMI等5个性能指标值来看,与多个不同算法在多个不同数据集上分别聚类相比, 该算法具有较好的聚类结果;与多个不同算法在同一数据集上很多不同的初始化条件下分别聚类相比,该算法具有较好且稳定的聚类结果;该算法在不同大小数据集上聚类时具有线性伸缩性且速度较快。     

网格聚类中的边界处理技术

提出利用限制性k近邻和相对密度的概念识别网格聚类边界点的技术,给出网格聚类中的边界处理算法和带边界处理的网格聚类算法(GBCB).实验表明,聚类边界处理技术精度高,能有效地将聚类的边界点和孤立点/噪声数据分离开来.基于该边界处理技术的网格聚类算法GBCB能识别任意形状的聚类.由于它只对数据集进行一遍扫描,算法的运行时间是输入数据大小的线性函数,可扩展性好.     

基于初始中心优化的遗传K-means聚类新算法

一个好的K-means聚类算法至少要满足两个要求：（1）能反映聚类的有效性,即所分类别数要与实际问题相符;（2）具有处理噪声数据的能力。传统的K-means算法是一种局部搜索算法,存在着对初始化敏感和容易陷入局部极值的缺点。针对此缺点,提出了一种优化初始中心的K-means算法,该算法选择相距最远的处于高密度区域的k个数据对象作为初始聚类中心。实验表明该算法不仅具有对初始数据的弱依赖性,而且具有收敛快,聚类质量高的特点。为体现聚类的有效性,获得更高精度的聚类结果,提出了将优化的K-means算法（PKM）和遗传算法相结合的混合算法（PGKM）,该算法在提高紧凑度（类内距）和分离度（类间距）的同时自动搜索最佳聚类数k,对k个初始中心优化后再聚类,不断地循环迭代,得到满足终止条件的最优聚类。实验证明该算法具有更好的聚类质量和综合性能。     

基于距离和权重改进的K-means算法

K-means聚类算法简单高效,应用广泛。针对传统K-means算法初始聚类中心点的选择随机性导致算法易陷入局部最优以及K值需要人工确定的问题,为了得到最合适的初始聚类中心,提出一种基于距离和样本权重改进的K-means算法。该聚类算法采用维度加权的欧氏距离来度量样本点之间的远近,计算出所有样本的密度和权重后,令密度最大的点作为第一个初始聚类中心,并剔除该簇内所有样本,然后依次根据上一个聚类中心和数据集中剩下样本点的权重并通过引入的参数[τi]找出下一个初始聚类中心,不断重复此过程直至数据集为空,最后自动得到[k]个初始聚类中心。在UCI数据集上进行测试,对比经典K-means算法、WK-means算法、ZK-means算法和DCK-means算法,基于距离和权重改进的K-means算法的聚类效果更好。     

基于密度峰值和网格的自动选定聚类中心算法

针对快速搜索和发现密度峰值的聚类算法(DPC)中数据点之间计算复杂,最终聚类的中心个数需要通过决策图手动选取等问题,提出基于密度峰值和网格的自动选定聚类中心的改进算法GADPC。首先结合Clique网格聚类算法的思想,不再针对点对象进行操作,而是将点映射到网格,并将网格作为聚类对象,从而减少了DPC算法中对数据点之间的距离计算和聚类次数;其次通过改进后的聚类中心个数判定准则更精确地自动选定聚类中心个数;最后对网格边缘点和噪声点,采用网格内点对象和相邻网格间的相似度进行了处理。实验通过采用UEF(University of Eastern Finland)提供的数据挖掘使用的人工合成数据集和UCI自然数据集进行对比,其聚类评价指标(Rand Index)表明,改进的算法在计算大数据集时聚类质量不低于DPC和K-means算法,而且提高了DPC算法的处理效率。     

A symmetry based multiobjective clustering technique for automatic evolution of clusters

In this paper the problem of automatic clustering a data set is posed as solving a multiobjective optimization (MOO) problem, optimizing a set of cluster validity indices simultaneously. The proposed multiobjective clustering technique utilizes a recently developed simulated annealing based multiobjective optimization method as the underlying optimization strategy. Here variable number of cluster centers is encoded in the string. The number of clusters present in different strings varies over a range. The points are assigned to different clusters based on the newly developed point symmetry based distance rather than the existing Euclidean distance. Two cluster validity indices, one based on the Euclidean distance, XB-index, and another recently developed point symmetry distance based cluster validity index, Sym-index, are optimized simultaneously in order to determine the appropriate number of clusters present in a data set. Thus the proposed clustering technique is able to detect both the proper number of clusters and the appropriate partitioning from data sets either having hyperspherical clusters or having point symmetric clusters. A new semi-supervised method is also proposed in the present paper to select a single solution from the final Pareto optimal front of the proposed multiobjective clustering technique. The efficacy of the proposed algorithm is shown for seven artificial data sets and six real-life data sets of varying complexities. Results are also compared with those obtained by another multiobjective clustering technique, MOCK, two single objective genetic algorithm based automatic clustering techniques, VGAPS clustering and GCUK clustering.     

新的K-均值算法最佳聚类数确定方法

K-均值聚类算法是以确定的类数k和随机选定的初始聚类中心为前提对数据集进行聚类的。通常聚类数k事先无法确定,随机选定的初始聚类中心容易使聚类结果不稳定。提出了一种新的确定K-均值聚类算法的最佳聚类数方法,通过设定AP算法的参数,将AP算法产生的聚类数作为聚类数搜索范围的上界kmax,并通过选择合适的有效性指标Silhouette指标,以及基于最大最小距离算法思想设定初始聚类中心,分析聚类效果,确定最佳聚类数。仿真实验和分析验证了以上算法方案的可行性。     

基于全局中心的高密度不唯一的K-means算法研究

传统的K-means算法敏感于初始中心点的选取,并且无法事先确定准确的聚类数目[k],不利于聚类结果的稳定性。针对传统K-means算法的以上不足,提出了基于全局中心的高密度不唯一的新方法--NDK-means,该方法通过标准差确定有效密度半径,并从高密度区域中选取具有代表性的样本点作为初始聚类中心。此外算法针对最高密度点不唯一的情况进行特别分析,选取距离全局中心最远的点集作为最优的初始中心点集合。在NDK-means算法基础上结合有效性指标BWP对聚类结果进行分析,从而解决了最佳有效聚类数目无法事先确定的不足。理论研究与实验结果表明所提方法的聚类结果具有更好的稳定性和可行性。     

新模糊聚类有效性指标

模糊聚类是模式识别、机器学习和图像处理等领域的重要研究内容。模糊C-均值聚类算法是最常用的模糊聚类实现算法,该算法需要预先给定聚类数才能对数据集进行聚类。提出了一种新的聚类有效性指标,对聚类结果进行有效性验证。该指标从划分熵、隶属度、几何结构角度,定义了紧凑度、分离度、重叠度三个重要特征测量。在此基础上,提出了一种最佳聚类数确定方法。将新聚类有效性指标和传统有效性指标在6个人工数据集和3个真实数据集进行实验验证。实验结果表明,所提出的指标和方法能够有效地对聚类结果进行评估,适合确定样本的最佳聚类数。     

Determining the number of clusters using information entropy for mixed data

In cluster analysis, one of the most challenging and difficult problems is the determination of the number of clusters in a data set, which is a basic input parameter for most clustering algorithms. To solve this problem, many algorithms have been proposed for either numerical or categorical data sets. However, these algorithms are not very effective for a mixed data set containing both numerical attributes and categorical attributes. To overcome this deficiency, a generalized mechanism is presented in this paper by integrating Rényi entropy and complement entropy together. The mechanism is able to uniformly characterize within-cluster entropy and between-cluster entropy and to identify the worst cluster in a mixed data set. In order to evaluate the clustering results for mixed data, an effective cluster validity index is also defined in this paper. Furthermore, by introducing a new dissimilarity measure into the k-prototypes algorithm, we develop an algorithm to determine the number of clusters in a mixed data set. The performance of the algorithm has been studied on several synthetic and real world data sets. The comparisons with other clustering algorithms show that the proposed algorithm is more effective in detecting the optimal number of clusters and generates better clustering results.     

ODIC-DBSCAN:一种新的簇内孤立点分析算法

长期以来,孤立点的检测一直聚焦于簇边缘的离散点,当聚类后簇的数目低于实际数目,或孤立点被伪装在簇内的情况下,簇内孤立点的判定则会更加困难.为判定簇内孤立点,提出一种基于密度聚类DBSCAN（Density based spatial clustering of application with noise）的簇内孤立点检测方法ODIC-DBSCAN（Outlier detection of inner-cluster based on DBSCAN）.首先在建立距离矩阵的基础上,通过半径获取策略得到针对该点集的k个有效半径Radius集合,并据此构造密度矩阵;然后建立点集覆盖模型,提出了相邻有效半径构造的覆盖多维体能够覆盖点集的思想,并通过拉格朗日乘子法求取最优的覆盖多维体数目之比,输出点比阈值组;最后重建ODIC-DBSCAN的孤立点检测方法,以簇发生融合现象作为算法终止的判定条件.实验通过模拟数据集,公开benchmark与UCI数据集共同验证了ODIC-DBSCAN算法,展示了聚类过程;分析了算法性能;并通过与其他聚类、孤立点判定方法的对比,验证了算法对簇内孤立点的判定效果.