聚类趋势问题的研究综述*

聚类算法的性能与数据集的结构是密切相关的,虽然目前已经研究出了很多聚类算法,但没有普遍适用的万能聚类算法,欠缺对数据集结构的有效解释。对聚类分析过程中重要的关键性问题,即聚类趋势问题进行了系统性的研究,从统计检验、可视化分析等角度给予了讨论,为数据集的无监督聚类分析提供了合理和有效的前期分析工具。     

从多角度分析现有聚类算法

聚类是数据挖掘中研究的重要问题之一.聚类分析就是把数据集分成簇,以使得簇内数据尽量相似,簇间数据尽量不同.不同的聚类方法采用不同的相似测度和技术.从以下3个角度分析现有流行聚类算法: (1)聚类尺度; (2)算法框架; (3)簇的表示.在此基础上,分析了一些综合或概括了一些其他方法的算法.由于分析从3个角度进行,所提出的方法能够涵盖,并区分绝大多数现有聚类算法.所做的工作是自调节聚类方法以及聚类基准测试研究的基础.     

具有加权特性的弹性网络聚类算法研究

聚类分析是数据挖掘中重要内容之一,也是人们分析数据的重要工具。针对聚类分析中存在易受噪声干扰、高维数据聚类结果不佳等问题,对弹性网络进行了加权聚类方向的研究。该算法考虑到数据集中各特征属性在聚类过程中不同的重要程度,重新构造关联数据点、聚类中心点的能量函数,利用弹性网络算法的求解模式,结合极大熵原理、模拟退火思想,提出一种具有加权特性的弹性网络聚类算法。该算法无需人工指导训练,便可以自学习地求解出高质量的聚类结果。通过不同维度、不同数量级的随机数据集和UCI真实数据集仿真实验,验证了算法的有效性和稳定性。相较于传统聚类算法,该算法显著提高了聚类质量。     

基于k-means聚类算法的研究

分析研究聚类分析方法,对多种聚类分析算法进行分析比较,讨论各自的优点和不足,同时针对原k-means算法的聚类结果受随机选取初始聚类中心的影响较大的缺点,提出一种改进算法.通过将对数据集的多次采样,选取最终较优的初始聚类中心,使得改进后的算法受初始聚类中心选择的影响度大大降低;同时,在选取初始聚类中心后,对初值进行数据标准化处理,使聚类效果进一步提高.通过UCI数据集上的数据对新算法Hk-means进行检测,结果显示Hk-means算法比原始的k-means算法在聚类效果上有显著的提高,并对相关领域有借鉴意义.     

不同相似度测量方式的模糊C均值聚类分析

聚类技术是机器学习、模式识别及数据挖掘等领域中的一个重要研究内容。采用不同相似度测量方式,应用标准模糊C均值聚类算法在UCI的三个知名数据集上完成聚类实验,从正确率和运行效率两个方面对比分析其性能,为聚类分析研究提供了有益的参考。     

谱聚类算法研究综述

聚类分析是一种常见的分析方法,谱聚类作为聚类分析的一支,因其不受样本形状约束等特点备受瞩目。为及时掌握当前谱聚类算法研究动态,通过对比分析众多谱聚类优化算法,从半监督学习、二阶段聚类算法选择、算法执行效率优化等三个角度,将谱聚类优化算法分为三类,并对每类算法的优化思想进行综述。介绍经典多路谱聚类与基本理论,并分析相似矩阵及其特征值、特征向量选取原因及影响,旨在明确特征矩阵的重要性与优化的必要性。基于算法改进策略差异,梳理并总结每类算法的改进思想、研究现状及优缺点。在UCI数据集与手写体数据集上,针对谱聚类算法与优化算法进行实验对比,并对谱聚类优化算法的未来研究方向进行展望。     

模糊聚类分析及算法比较

聚类分析方法有多种,其中的模糊聚类应用最为广泛.简单介绍模糊聚类的发展历程和模糊聚类的几种常用算法,其中重点分析布尔矩阵法和最大树法两种模糊聚类分析算法,并用标准数据集对它们分别进行聚类分析和比较.     

数据挖掘中聚类算法比较研究

聚类分析技术是数据挖据中的一种重要技术.本文介绍了数据挖掘对聚类的典型要求和聚类方法的分类,研究分析了聚类的主要算法,并从多个方面对这些算法的性能进行比较.     

一种基于数据垂直划分的分布式密度聚类算法

聚类分析是数据挖掘领域的一项重要研究课题,对大数据集的聚类更以其数据量大、噪声数据多等而成为一个难点.针对数据垂直划分的情况,提出连通点集及局部噪声点集等概念.在分析局部噪声点集与全局噪声点集以及局部连通点集与全局连通点集关系的基础上,对全局噪声点进行有效过滤,进一步设计闭三角链表结构存储各个结点的聚类中间结果,提出了基于密度的分布式聚类算法DDBSCAN.理论分析和实验结果表明,算法可以有效解决垂直划分的大数据集聚类问题,算法是有效可行的.     

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

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

面向混合属性数据集的双重聚类方法

面对复杂信息环境下的数据预处理需求,提出了一种可以处理混合属性数据集的双重聚类方法。这种双重聚类方法由双重近邻无向图的构造算法或其改进算法,基于分离集合并的双重近邻图聚类算法、基于宽度优先搜索的双重近邻图聚类算法、或基于深度优先搜索的双重近邻图聚类算法来实现。通过人工数据集和UCI标准数据集的仿真实验,可以验证,尽管这三个聚类算法所采用的搜索策略不同,但最终的结果是一致的。仿真实验结果还表明,对于一些具有明显聚类分布结构且无近邻噪声干扰的数据集,该方法经常能取得比K-means算法和AP算法更好的聚类精度,从而说明这种双重聚类方法具有一定的有效性。为进一步推广并在实际中发掘出该方法的应用价值,最后给出了一点较有价值的研究展望。     

一种基于密度峰值的针对模糊混合数据的聚类算法

将CFSFDP算法拓展到连续型模糊集和离散型模糊集上,提出了一种针对模糊混合数据的拓展型CFSFDP算法,将其命名为FMD-CFSFDP算法。FMD-CFSFDP算法将样本涵盖的经典信息拓展到了模糊集上,利用寻找密度峰值的方法对模糊样本进行聚类,这是一种建立在模糊集上针对模糊混合数据的基于密度的聚类算法。首先简单介绍了CFSFDP算法及其改进,给出了"模糊混合数据"的数学概念;然后结合传统模糊欧氏距离的概念,分别提出了误差更小的针对连续型模糊集与离散型模糊集的改进型欧氏距离,在此基础上,依托权值构建了针对混合型模糊数据的整体距离。参考CFSFDP算法的聚类步骤给出了FMD-CFSFDP算法的聚类步骤。随后,在不同样本量、不同指标数量、不同簇数、不同取数规则的条件下,对算法进行了随机模拟实验并对聚类结果进行了分析。最后分别总结了FMD-CFSFDP算法的优缺点,并在此基础上提出了改进方案,为今后深入研究提供了参考。     

Distance and density based clustering algorithm using Gaussian kernel

Clustering is an important field for making data meaningful at various applications such as processing satellite images, extracting information from financial data or even processing data in social sciences. This paper presents a new clustering approach called Gaussian Density Distance (GDD) clustering algorithm based on distance and density properties of sample space. The novel part of the method is to find best possible clusters without any prior information and parameters. Another novel part of the algorithm is that it forms clusters very close to human clustering perception when executed on two dimensional data. GDD has some similarities with today’s most popular clustering algorithms; however, it uses both Gaussian kernel and distances to form clusters according to data density and shape. Since GDD does not require any special parameters prior to run, resulting clusters do not change at different runs. During the study, an experimental framework is designed for analysis of the proposed clustering algorithm and its evaluation, based on clustering performance for some characteristic data sets. The algorithm is extensively tested using several synthetic data sets and some of the selected results are presented in the paper. Comparative study outcomes produced by other well-known clustering algorithms are also discussed in the paper.     

A new multiobjective clustering technique based on the concepts of stability and symmetry

Most clustering algorithms operate by optimizing (either implicitly or explicitly) a single measure of cluster solution quality. Such methods may perform well on some data sets but lack robustness with respect to variations in cluster shape, proximity, evenness and so forth. In this paper, we have proposed a multiobjective clustering technique which optimizes simultaneously two objectives, one reflecting the total cluster symmetry and the other reflecting the stability of the obtained partitions over different bootstrap samples of the data set. The proposed algorithm uses a recently developed simulated annealing-based multiobjective optimization technique, named AMOSA, as the underlying optimization strategy. Here, points are assigned to different clusters based on a newly defined point symmetry-based distance rather than the Euclidean distance. Results on several artificial and real-life data sets in comparison with another multiobjective clustering technique, MOCK, three single objective genetic algorithm-based automatic clustering techniques, VGAPS clustering, GCUK clustering and HNGA clustering, and several hybrid methods of determining the appropriate number of clusters from data sets show that the proposed technique is well suited to detect automatically the appropriate number of clusters as well as the appropriate partitioning from data sets having point symmetric clusters. The performance of AMOSA as the underlying optimization technique in the proposed clustering algorithm is also compared with PESA-II, another evolutionary multiobjective optimization technique.     

A fuzzy relational clustering algorithm based on a dissimilarity measure extracted from data.

One of the critical aspects of clustering algorithms is the correct identification of the dissimilarity measure used to drive the partitioning of the data set. The dissimilarity measure induces the cluster shape and therefore determines the success of clustering algorithms. As cluster shapes change from a data set to another, dissimilarity measures should be extracted from data. To this aim, we exploit some pairs of points with known dissimilarity value to teach a dissimilarity relation to a feed-forward neural network. Then, we use the neural dissimilarity measure to guide an unsupervised relational clustering algorithm. Experiments on synthetic data sets and on the Iris data set show that the relational clustering algorithm based on the neural dissimilarity outperforms some popular clustering algorithms (with possible partial supervision) based on spatial dissimilarity.     

A novel cluster center fast determination clustering algorithm

As one of the most important techniques in data mining, cluster analysis has attracted more and more attentions in this big data era. Most clustering algorithms have encountered with challenges including cluster centers determination difficulty, low clustering accuracy, uneven clustering efficiency of different data sets and sensible parameter dependence. Aiming at clustering center determination difficulty and parameter dependence, a novel cluster center fast determination clustering algorithm was proposed in this paper. It is supposed that clustering centers are those data points with higher density and larger distance from other data points of higher density. Normal distribution curves are designed to fit the density distribution curve of density distance product. And the singular points outside the confidence interval by setting the confidence interval are proved to be clustering centers by theory analysis and simulations. Finally, according to these clustering centers, a time scan clustering is designed for the rest of the points by density to complete the clustering. Density radius is a sensible parameter in calculating density for each data point, mountain climbing algorithm is thus used to realize self-adaptive density radius. Abundant typical benchmark data sets are testified to evaluate the performance of the brought up algorithms compared with other clustering algorithms in both aspects of clustering quality and time complexity.     

面向移动App流量的多特征集合集成聚类方法研究与应用

针对移动互联网流量识别问题,基于多项性能评估指标,分析K-均值和谱聚类算法在不同特征集合或不同识别目标流量数据集上的聚类性能,并提出基于多特征集合的集成聚类方法。比较分析实验表明,相同聚类方法在不同特征集合或不同识别目标数据集上性能有所不同,集成聚类方法能够有效提高利用单个特征集合聚类方法的性能。进一步将集成聚类方法应用于App关联分析,分析结果可为移动App的划分和用户行为分析提供客观依据。     

基于遗传算法的硬聚类算法改进

硬聚类算法HCM求解的结果通常都是局部的最优解,当模糊集合间的运算采用传统定义的时候,它的聚类结果中还会存在无意义的聚类集。本文通过研究表明,在HCM聚类算法中应用遗传算法,可以在一定程度上避免硬聚类算法收敛到局部最优解。因此,本文将遗传算法应用于硬聚类算法,并设计了相应的算法。但是,考虑到本算法实现时的开销 销和效率,又对该算法进行了改进,并最终提出一种新的算法--CHCM聚类算法。测试数据表明,采用改进后的聚类算法的结果90％以上能够取得全局的最优解,远远超过了采用硬聚类算法时所取得全局最优解的次数,证明了本算法的可推广性。     

混合属性数据集的基于近邻连接的两阶段聚类算法

面对混合属性数据集的数据预处理需求,本文在给出若干定义及相关性质之后,提出了一种基于近邻连接的两阶段聚类算法。为提高算法的时间效率,给出了算法改进的思路与技术。多个人工数据集和UCI标准数据集的仿真实验结果表明,对于一些具有明显聚类分布结构的数据集,该算法经常能取得比k-means算法和AP算法更好的聚类精度,说明它具有一定的有效性。为进一步推广并在实际中发掘出该算法的应用价值,最后给出了几点研究展望。