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

针对初始聚类中心对传统K-means算法的聚类结果有较大影响的问题,提出一种依据样本点类内距离动态调整中心点类间距离的初始聚类中心选取方法,由此得到的初始聚类中心点尽可能分散且具代表性,能有效避免K-means算法陷入局部最优。通过UCI数据集上的数据对改进算法进行实验,结果表明改进的算法提高了聚类的准确性。     

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

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

基于MapReduce的K-Medoids并行算法

为了解决传统K-Medoids聚类算法在处理海量数据信息时所面临的内存容量和CPU处理速度的瓶颈问题,在深入研究K-Medoids算法的基础之上,提出了基于MapReduce编程模型的K-Medoids并行化算法思想。Map函数部分的主要任务是计算每个数据对象到簇类中心点的距离并（重新）分配其所属的聚类簇;Reduce函数部分的主要任务是根据Map部分得到的中间结果,计算出新簇类的中心点,然后作为中心点集给下一次MapReduce过程使用。实验结果表明：运行在Hadoop集群上的基于MapReduce的K-Medoids并行化算法具有较好的聚类结果和可扩展性,对于较大的数据集,该算法得到的加速比更接近于线性。     

结合最大最小距离和加权密度的K-means聚类算法

随机选取初始聚类中心和根据经验设置[K]值对[K]-means聚类结果都有一定的影响,针对这一问题,提出了一种基于加权密度和最大最小距离的[K]-means聚类算法,称为[KWDM]算法。该算法利用加权密度法选取初始聚类中心点集,减少了离群点对聚类结果的影响,通过最大最小距离准则启发式地选择聚类中心,避免了聚类结果陷入局部最优,最后使用准则函数即簇内距离和簇间距离的比值来确定[K]值,防止了根据经验来设置[K]值。在人工数据集和UCI数据集上的实验结果表明,KWDM算法不仅提高了聚类的准确率,而且减少了算法的平均迭代次数,增强了算法的稳定性。     

基于Spark的改进K-means算法的并行实现

针对K-means聚类算法存在的不足,提出了改进K-means来提高算法的性能,利用简化后的轮廓系数作为评估标准衡量K-means算法中◢k◣值,采用K-means++完成K-means算法初始中心点的选择。设置好◢k◣值以及初始中心点后使用形态学相似距离作为相似度测量标准将数据点归属到距离最近的中心点形成的簇中,最后计算平均轮廓系数确定合适的◢k◣值,并在Spark上实现算法并行化。通过对四个标准数据集在准确性、运行时间和加速比三个方面的实验表明,改进后的K-means算法相对于传统的K-means算法和SKDK-means算法不仅提高了聚类划分质量,缩短了计算时间,而且在多节点的集群环境下表现出良好的并行性能。实验结果分析出提出的改进算法能有效提高算法执行效率和并行计算能力。     

融合最近邻矩阵与局部密度的自适应K-means聚类算法

针对传统K-means聚类算法对初始聚类中心和离群孤立点敏感的缺陷,以及现有引入密度概念优化的K-means算法均需要设置密度参数或阈值的缺点,提出一种融合最近邻矩阵与局部密度的自适应K-means聚类算法。受最邻近吸收原则与密度峰值原则启发,通过引入数据对象间的距离差异值构造邻近矩阵,根据邻近矩阵计算局部密度,不需要任何参数设置,采取最近邻矩阵与局部密度融合策略,自适应确定初始聚类中心数目和位置,同时完成非中心点的初分配。人工数据集和UCI数据集的实验测试,以及与传统K-means算法、基于离群点改进的K-means算法、基于密度改进的K-means算法的实验比较表明,提出的自适应K-means算法对人工数据集的孤立点免疫度较高,对UCI数据集具有更准确的聚类结果。     

一种改进的K-means算法在入侵检测中的应用

传统的聚类算法存在很多缺点,因此需要做进一步的研究。通过对传统的K-means算法和加权熵措施的K-means算法的研究,提出了一种改进的加权熵措施的K-means算法,且该算法采用了一种新的计算对象间距离的方法,不仅能使在同一个簇中任意对象之间的距离尽可能的小,更能使得不同簇中的任意对象之间的距离尽可能的大。通过在KDD Cup99数据集上实验仿真,表明该算法具有较强的实用性和自适应功能。     

基于聚合距离参数的改进K-means算法

针对传统K均值聚类（K-means）算法随机选择初始中心及K值导致的聚类结果不确定且精度不高问题,提出了一种基于聚合距离的改进K-means算法。首先,基于聚合距离参数筛选出优质的初始聚类中心,并将其作用于K-means算法。然后,引入戴维森堡丁指数（DBI）作为算法的准则函数,循环更新聚类直到准则函数收敛,最后完成聚类。改进算法提供了优质的初始聚类中心及K值,避免了聚类结果的随机性。二维数值型仿真数据的聚类结果表明,改进算法在数据样本数达到10000时仍能保持较好的聚类效果。针对Iris和Seg这两个UCI标准数据集的调整兰德系数,改进算法比传统算法性能分别提高了83.7%和71.0%,最终验证了改进算法比传统算法聚类结果的准确性更高。     

基于数据场的数据势能竞争与K-means融合的聚类算法

K-means算法采用欧氏距离进行数据点的划分,不能够准确地刻画数据集特征,而随机选取聚类中心点的机制,也不能获得好的聚类结果。为此,提出一种基于数据场的数据势能竞争与K-means算法融合的聚类算法。算法中定义了数据场的概念,利用局部最小距离进行数据聚合势能的竞争,然后利用势能熵提取基于数据集分布的最优截断距离,根据截断距离与斜率确定出簇中心点,实现K-means聚类。在UCI数据集上的测试结果表明,融合后的算法具有更好的聚类结果。     

基于Hadoop的K-means聚类算法的实现

文中针对传统并行K-means聚类算法时间复杂度比较高的问题,结合Hadoop平台以及MapReduce编程模型的优势,提出了利用Hadoop及MapReduce编程模型实现大数据量下的K-means聚类算法.其中,Map函数完成每条记录到各个质心距离的计算并标记其所属类别,Reduce函数完成质心的更新,同时计算每条数据到其所属中心点的距离,并累计求和.通过实验,验证了K-means算法部署在Hadoop集群上并行化运行,在处理大数据时,同传统的串行算法相比,确实能够降低时间复杂度,而且表现出很好的稳定性和扩展性.     

基于三角不等式原理的K-means加速算法

K-means聚类算法简单快速,应用极为广泛,但是当处理海量数据时,时间效率仍然有待提高.当一个数据点远离一个聚类时,就没必要计算这两者之间的精确距离,以确定该数据点不属于这个类.应用三角不等式原理对其进行了改进,避免了冗余的距离计算.实验结果表明,改进之后在速度上有很大程度的提高,数据规模越大,改进效果越明显,且聚类效果保持了原算法的准确性.     

一种基于密度的K-means算法研究*

针对传统K-means算法必须事先确定聚类数目以及对初始聚类中心的选取比较敏感的缺陷,采用基于密度的思想,通过设定Eps邻域以及Eps邻域内至少包含的对象数minpts来排除孤立点,并将不重复的核心点作为初始聚类中心;采用类内距离和类间距离的比值作为准则评价函数,将准则函数取得最小值时的聚类数作为最佳聚类数,这些改进有效地克服了K-means算法的不足。最后通过几个实例介绍了改进后算法的具体应用,实例表明改进后的算法比原算法有更高的聚类准确性,更能实现类内紧密类间远离的聚类效果。     

优化初始聚类中心的K-means聚类算法

针对传统K-means算法对初始中心十分敏感,聚类结果不稳定问题,提出了一种改进K-means聚类算法。该算法首先计算样本间的距离,根据样本距离找出距离最近的两点形成集合,根据点与集合的计算公式找出其他所有离集合最近的点,直到集合内数据数目大于或等于[α]（[α]为样本集数据点数目与聚类的簇类数目的比值）,再把该集合从样本集中删除,重复以上步骤得到K（K为簇类数目）个集合,计算每个集合的均值作为初始中心,并根据K-means算法得到最终的聚类结果。在Wine、Hayes-Roth、Iris、Tae、Heart-stalog、Ionosphere、Haberman数据集中,改进算法比传统K-means、K-means++算法的聚类结果更稳定;在Wine、Iris、Tae数据集中,比最小方差优化初始聚类中心的K-means算法聚类准确率更高,且在7组数据集中改进算法得到的轮廓系数和F1值最大。对于密度差异较大数据集,聚类结果比传统K-means、K-means++算法更稳定,更准确,且比最小方差优化初始聚类中心的K-means算法更高效。     

Online Clustering with Variable Sized Clusters

Online clustering problems are problems where the classification of points into sets (called clusters) is performed in an online fashion. Points arrive at arbitrary locations, one by one, to be assigned to clusters at the time of arrival. A point can be either assigned to an existing cluster or a new cluster can be opened for it. Here, we study a one-dimensional variant on a line. Each cluster is a closed interval, and there is no restriction on the length of a cluster. The cost of a cluster is the sum of a fixed set-up cost and its diameter (or length). The goal is to minimize the sum of costs of the clusters used by the algorithm. We study several variants, each having the two essential properties that a point which has been assigned to a given cluster must remain assigned to that cluster and no pair of clusters can be merged. In the strict variant, the diameter and the exact location of the cluster must be fixed when it is initialized. In the flexible variant, the algorithm can shift the cluster or expand it, as long as it contains all points assigned to it. In an intermediate model, the diameter is fixed in advance but the exact location can be modified. Here we give tight bounds on the competitive ratio of any online algorithm in each of these variants. In addition, for each model we also consider the semi-online case where points are presented ordered by their location.     

基于加权距离计算的自适应粗糙K均值算法*

针对粗糙K均值算法的执行效率较低和对数据对象的处理不准确,本文提出了基于加权距离计算的自适应粗糙K均值算法。该算法首先在粗糙集理论应用的基础上修正数据集合的隶属度函数,其次结合属性约简方法,根据数据属性对聚类效果的影响因子设置权值,在欧氏距离中引入权值系数来初始化簇的中心点,最后通过K值递增的改进算法对数据集进行正态检验来验证每个簇的数据是否符合高斯分布模型,从而能够自适应地确定K值。实验结果表明,改进后的算法相比原算法在能保证一定执行效率的同时,能获得较高的聚类精确度,且对高维数据集也有较强的适应性,从而表明该算法是有效可行的。     

Approximation Scheme for a Quadratic Euclidean Weighted 2-Clustering Problem

We consider the strongly NP-hard problem of partitioning a finite set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sums of the squared intra-cluster distances from the elements of the cluster to its center. The weights of the sums are equal to the cardinalities of the clusters. The center of one of the clusters is given as input, while the center of the other cluster is unknown and is determined as the mean value over all points in this cluster, i.e., as the geometric center (centroid). The version of the problem with constrained cardinalities of the clusters is analyzed. We construct an approximation algorithm for the problem and show that it is a fully polynomial-time approximation scheme (FPTAS) if the space dimension is bounded by a constant.     

基于加权集成Nyström采样的谱聚类算法

针对Nyström方法在谱聚类应用中存在聚类效果不稳定、样本代表性较弱的问题,提出基于加权集成Nyström采样的谱聚类算法.首先利用统计杠杆分数区别数据间的重要程度,对数据进行加权.然后基于权重采用加权K-means中心点采样,得到多组采样点.再引入集成框架,利用集群并行运行Nyström方法构建近似核矩阵.最后利用岭回归方法组合各个近似核矩阵,产生比标准Nyström方法更准确的低秩近似.在UCI数据集上的测试实验表明,文中算法取得较理想的聚类结果.     

一种基于影响因子的快速K-均值算法

K-均值聚类算法的执行时间过度依赖于初始点的选取,但是在实际问题中并不知道k的取值和怎样才能有效地选取初始点。在对K-均值算法中初始点的选取进行深入研究的基础上,提出了一种有效的初始点选取算法。现存的类间相似度并不能很好地度量两个类的相似性,为此提出了一种新颖的度量方法：类间影响因子,使用类间影响因子对类进行合并。该方法和上面提出的初始点选取算法能够根据数据集本身的特性快速地自动选取初始中心并给出初始点的个数。最后用高斯数据集对算法进行测试,得到了一个令人满意的结果。     

A Point Symmetry-Based Clustering Technique for Automatic Evolution of Clusters

In this article, a new symmetry based genetic clustering algorithm is proposed which automatically evolves the number of clusters as well as the proper partitioning from a data set. Strings comprise both real numbers and the don't care symbol in order to encode a variable number of clusters. Here, assignment of points to different clusters are done based on a point symmetry based distance rather than the Euclidean distance. A newly proposed point symmetry based cluster validity index, {em Sym}-index, is used as a measure of the validity of the corresponding partitioning. The algorithm is therefore able to detect both convex and non-convex clusters irrespective of their sizes and shapes as long as they possess the point symmetry property. Kd-tree based nearest neighbor search is used to reduce the complexity of computing point symmetry based distance. A proof on the convergence property of variable string length GA with point symmetry based distance clustering (VGAPS-clustering) technique is also provided. The effectiveness of VGAPS-clustering compared to variable string length Genetic K-means algorithm (GCUK-clustering) and one recently developed weighted sum validity function based hybrid niching genetic algorithm (HNGA-clustering) is demonstrated for nine artificial and five real-life data sets.     

基于非参数核密度估计的密度峰值聚类算法*

针对密度峰值聚类算法CFSFDP(Clustering by fast search and find of density peaks)计算密度时人为判断截断距离和人工截取簇类中心的缺陷,提出了一种基于非参数核密度估计的密度峰值的聚类算法。首先,应用非参数核密度估计方法计算数据点的局部密度;其次,根据排序图采用簇中心点自动选择策略确定潜在簇类中心点,将其余数据点归并到相应的簇类中心;最后,依据簇类间的合并准则,对邻近相似子簇进行合并,并根据边界密度识别噪声点,得到聚类结果。在人工测试数据集和UCI真实数据集上的实验表明,新算法较之原CFSFDP算法,不仅有效避免了人为判断截断距离和截取簇类中心的主观因素,而且可以取得更高的准确度。