基于层次划分的密度优化聚类算法

针对传统的聚类算法对数据集反复聚类,且在大型数据集上计算效率欠佳的问题,提出一种基于层次划分的最佳聚类数和初始聚类中心确定算法——基于层次划分密度的聚类优化(CODHD)。该算法基于层次划分,对计算过程进行研究,不需要对数据集进行反复聚类。首先,扫描数据集获得所有聚类特征的统计值;其次,自底向上地生成不同层次的数据划分,计算每个划分数据点的密度,将最大密度点定为中心点,计算中心点距离更高密度点的最小距离,以中心点密度与最小距离乘积之和的平均值为有效性指标,增量地构建一条关于不同层次划分的聚类质量曲线;最后,根据曲线的极值点对应的划分估计最佳聚类数和初始聚类中心。实验结果表明,所提CODHD算法与预处理阶段的聚类优化(COPS)算法相比,聚类准确度提高了30%,聚类算法效率至少提高14.24%。所提算法具有较强的可行性和实用性。     

混合的密度峰值聚类算法

密度峰值聚类（DP）算法是一种新的基于密度的聚类算法，当它处理的单个聚类包含多个密度峰值时，会将每个不同密度峰值视为潜在聚类中心，以致难以在数据集中确定正确数量聚类，为此，提出一种混合的密度峰值聚类算法C-DP。首先，以密度峰值点为初始聚类中心将数据集划分为子簇；然后，借鉴代表点层次聚类算法（CURE），从子簇中选取分散的代表点，将拥有最小距离的代表点对的类进行合并，引入参数收缩因子以控制类的形状。仿真实验结果表明，在4个合成数据集上C-DP算法比DP算法聚类效果更好；在真实数据集上的Rand Index指标对比表明，在数据集S1上，C-DP算法比DP算法性能提高了2.32%，在数据集4k2_far上，C-DP算法比DP算法性能提高了1.13%。由此可见，C-DP算法在单个类簇中包含多密度峰值的数据集中能提高聚类的准确性。     

局部搜索自适应核模糊聚类方法

核模糊C-均值聚类KFCM是利用核函数将数据映射到高维空间,通过计算数据点与聚类中心的隶属度对数据进行聚类的算法,拥有高效、快捷的特点而被广泛应用于各领域,然而KFCM算法存在对聚类中心的初始值敏感和不能自适应确定聚类数两个局限性。针对这两个问题,提出一种局部搜索自适应核模糊聚类方法,该方法引入核方法提高数据的可分性,并构造基于核函数的评价函数来确定最优的聚类数目和利用部分样本数据进行局部搜索以寻找初始聚类中心。人工数据和UCI数据集上的实验结果验证了该算法的有效性。     

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

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

A hierarchical Gamma Mixture Model-based method for estimating the number of clusters in complex data

This paper proposes a new method for estimating the true number of clusters and initial cluster centers in a dataset with many clusters. The observation points are assigned to the data space to observe the clusters through the distributions of the distances between the observation points and the objects in the dataset. A Gamma Mixture Model (GMM) is built from a distance distribution to partition the dataset into subsets, and a GMM tree is obtained by recursively partitioning the dataset. From the leaves of the GMM tree, a set of initial cluster centers are identified and the true number of clusters is estimated. This method is implemented in the new GMM-Tree algorithm. Two GMM forest algorithms are further proposed to ensemble multiple GMM trees to handle high dimensional data with many clusters. The GMM-P-Forest algorithm builds GMM trees in parallel, whereas the GMM-S-Forest algorithm uses a sequential process to build a GMM forest. Experiments were conducted on 32 synthetic datasets and 15 real datasets to evaluate the performance of the new algorithms. The results have shown that the proposed algorithms outperformed the existing popular methods: Silhouette, Elbow and Gap Statistic, and the recent method I-nice in estimating the true number of clusters from high dimensional complex data.     

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

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

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

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

基于知识量加权的直觉模糊均值聚类方法

针对聚类算法中特征数据对聚类中心贡献的差异性及算法对初始聚类中心的敏感性等问题,提出一种基于知识量加权的直觉模糊均值聚类方法。首先将原始数据集直觉模糊化并改进最新的直觉模糊知识测度计算知识量,据此实现数据集特征加权,再利用核空间密度与核距离初始化聚类中心,以提高高维特征数据集的计算精度与聚类效率,最后基于类间样本距离与最小知识量原理建立聚类优化模型,得到最优迭代算法。基于UCI人工数据集的实验结果表明,所提方法较大程度地提高了聚类的准确性与迭代效率,分类正确率及执行效率分别平均提高了10.63%和31.75%,且具有良好的普适性和稳定性。该方法首次将知识测度新理论引入模糊聚类并取得优良效果,为该理论在其他相关领域的潜在应用开创了新例。     

A potential-based clustering method with hierarchical optimization

This work proposes a novel data clustering algorithm based on the potential field model, with a hierarchical optimization mechanism on the algorithm. There are two stages in this algorithm. Firstly, we build an edge-weighted tree based on the mutual distances between all data points and their hypothetical potential values derived from the data distribution. Using the tree structure, the dataset can be divided into an appropriate number of initial sub-clusters, with the cluster centers close to the local minima of the potential field. Then the sub-clusters are further merged according to the well-designed merging criteria by analyzing their border potential values and the cluster average potential values. The proposed clustering algorithm follows a hierarchical clustering mechanism, and aims to optimize the initial sub-cluster results in the first stage. The algorithm takes advantage of the cluster merging criteria to merge the sub-clusters, so it can automatically stop the clustering process without designating the number of clusters in advance. The experimental results show that the proposed algorithm produces the most satisfactory clustering results in most cases compared with other existing methods, and can effectively identify the data clusters with arbitrary shape, size and density.     

基于粒计算的K-medoids聚类算法

传统K-medoids聚类算法的聚类结果随初始中心点不同而波动,且计算复杂度较高不适于处理大规模数据集;快速K-medoids聚类算法通过选择合适的初始聚类中心改进了传统K-medoids聚类算法,但是快速K-medoids聚类算法的初始聚类中心有可能位于同一类簇。为克服传统K-medoids聚类算法和快速K-medoids聚类算法的缺陷,提出一种基于粒计算的K-medoids聚类算法。算法引入粒度概念,定义新的样本相似度函数,基于等价关系产生粒子,根据粒子包含样本多少定义粒子密度,选择密度较大的前K个粒子的中心样本点作为K-medoids聚类算法的初始聚类中心,实现K-medoids聚类。UCI机器学习数据库数据集以及随机生成的人工模拟数据集实验测试,证明了基于粒计算的K-medoids聚类算法能得到更好的初始聚类中心,聚类准确率和聚类误差平方和优于传统K-medoids和快速K-medoids聚类算法,具有更稳定的聚类结果,且适用于大规模数据集。     

Cluster center initialization algorithm for K-modes clustering

Partitional clustering of categorical data is normally performed by using K-modes clustering algorithm, which works well for large datasets. Even though the design and implementation of K-modes algorithm is simple and efficient, it has the pitfall of randomly choosing the initial cluster centers for invoking every new execution that may lead to non-repeatable clustering results. This paper addresses the randomized center initialization problem of K-modes algorithm by proposing a cluster center initialization algorithm. The proposed algorithm performs multiple clustering of the data based on attribute values in different attributes and yields deterministic modes that are to be used as initial cluster centers. In the paper, we propose a new method for selecting the most relevant attributes, namely Prominent attributes, compare it with another existing method to find Significant attributes for unsupervised learning, and perform multiple clustering of data to find initial cluster centers. The proposed algorithm ensures fixed initial cluster centers and thus repeatable clustering results. The worst-case time complexity of the proposed algorithm is log-linear to the number of data objects. We evaluate the proposed algorithm on several categorical datasets and compared it against random initialization and two other initialization methods, and show that the proposed method performs better in terms of accuracy and time complexity. The initial cluster centers computed by the proposed approach are close to the actual cluster centers of the different data we tested, which leads to faster convergence of K-modes clustering algorithm in conjunction to better clustering results.     

Study on multi-center fuzzy C-means algorithm based on transitive closure and spectral clustering

Fuzzy C-means (FCM) clustering has been widely used successfully in many real-world applications. However, the FCM algorithm is sensitive to the initial prototypes, and it cannot handle non-traditional curved clusters. In this paper, a multi-center fuzzy C-means algorithm based on transitive closure and spectral clustering (MFCM-TCSC) is provided. In this algorithm, the initial guesses of the locations of the cluster centers or the membership values are not necessary. Multi-centers are adopted to represent the non-spherical shape of clusters. Thus, the clustering algorithm with multi-center clusters can handle non-traditional curved clusters. The novel algorithm contains three phases. First, the dataset is partitioned into some subclusters by FCM algorithm with multi-centers. Then, the subclusters are merged by spectral clustering. Finally, based on these two clustering results, the final results are obtained. When merging subclusters, we adopt the lattice similarity method as the distance between two subclusters, which has explicit form when we use the fuzzy membership values of subclusters as the features. Experimental results on two artificial datasets, UCI dataset and real image segmentation show that the proposed method outperforms traditional FCM algorithm and spectral clustering obviously in efficiency and robustness.     

A new algorithm for initial cluster centers in k-means algorithm

Clustering is one of the widely used knowledge discovery techniques to reveal structures in a dataset that can be extremely useful to the analyst. In iterative clustering algorithms the procedure adopted for choosing initial cluster centers is extremely important as it has a direct impact on the formation of final clusters. Since clusters are separated groups in a feature space, it is desirable to select initial centers which are well separated. In this paper, we have proposed an algorithm to compute initial cluster centers for k-means algorithm. The algorithm is applied to several different datasets in different dimension for illustrative purposes. It is observed that the newly proposed algorithm has good performance to obtain the initial cluster centers for the k-means algorithm.     

基于GSA算法改进的K均值聚类

为改善K均值聚类存在的对初始聚心敏感、全局搜索能力弱和凭经验确定聚类数等不足,提出一种基于GSA算法的改进K均值聚类。采用粒子编码策略,把聚类中心集合视作种群粒子,引入GSA搜索聚类质量最好的初始聚类中心,设均方误差为适应度函数,引导全局搜索方向,设置种群成熟度因子避免算法陷入局部最优,引入聚类质量评价指标获取最佳聚类数。通过在4种UCI数据集上做仿真测试,验证了改进后K均值聚类具有较高的正确率和更好的稳定性。     

创意FCM算法

针对现有模糊聚类方法仅仅是对已有数据点的聚类的不足,提出了在已有数据集的基础上找到新的一类集群的聚类方法 CFCM。该算法在FCM算法的基础上,通过引入观测点P作为聚类的先验知识,来大致确定未知集群的聚类中心,定义了权重系数λ来限定观测点对新的一类聚类中心形成的影响程度。人造数据集和UCI真实数据集的实验结果表明,该算法不仅对已知数据点有较好的聚类效果,并且可以在观测点P的作用下在特定区域创造出新的一类无已知数据点的集群中心点的大致位置,因而在实际中有潜在应用价值。     

一种融合免疫接种机制的改进鱼群聚类算法

传统的K-均值聚类方法,在聚类过程中过度依赖初始聚类中心的选择,同时由于全局搜索能力的不足,很难得到精确的聚类中心。鱼群算法在解决优化问题中表现出良好的并行性和全局搜索特性,但由于人为设置参数的影响可能会陷入局部最优。针对聚类问题的特征,将鱼群算法运用到聚类问题中,在使用自适应步长的鱼群算法的基础上,进一步融合免疫接种机制,加强算法对精确解的搜索性能,通过UCI数据集上的实验分析和比较,表明算法具有更好的有效性和稳定性。     

Pairwise Matching of 3D Fragments Using Cluster Trees

We propose a novel and efficient surface matching approach for reassembling broken solids as well as for matching assembly components using cluster trees of oriented points. The method rapidly scans through the space of all possible contact poses of the fragments to be (re)assembled using a tree search strategy, which neither relies on any surface features nor requires an initial solution. The new method first decomposes each point set into a binary tree structure using a hierarchical clustering algorithm. Subsequently the fragments are matched pairwise by descending the cluster trees simultaneously in a depth-first fashion. In contrast to the reassemblage of pottery and thin walled artifacts, this paper addresses the problem of matching broken 3D solids on the basis of their 2.5D fracture surfaces, which are assumed to be reasonable large. Our proposed contact area maximization is a powerful common basis for most surface matching tasks, which can be adapted to numerous special applications. The suggested approach is very robust and offers an outstanding efficiency.     

Unsupervised minor prototype detection using an adaptive population partitioning algorithm

This paper presents a new partitioning algorithm, designated as the Adaptive C-Populations (ACP) clustering algorithm, capable of identifying natural subgroups and influential minor prototypes in an unlabeled dataset. In contrast to traditional Fuzzy C-Means clustering algorithms, which partition the whole dataset equally, adaptive clustering algorithms, such as that presented in this study, identify the natural subgroups in unlabeled datasets. In this paper, data points within a small, dense region located at a relatively large distance from any of the major cluster centers are considered to form a minor prototype. The aim of ACP is to adaptively separate these isolated minor clusters from the major clusters in the dataset. The study commences by introducing the mathematical model of the proposed ACP algorithm and demonstrates its convergence to a stable solution. The ability of ACP to detect minor prototypes is confirmed via its application to the clustering of three different datasets with different sizes and characteristics.     

Dynamic local search based immune automatic clustering algorithm and its applications

Based on clonal selection mechanism in immune system, a dynamic local search based immune automatic clustering algorithm (DLSIAC) is proposed to automatically evolve the number of clusters as well as a proper partition of datasets. The real based antibody encoding consists of the activation thresholds and the clustering centers. Then based on the special structures of chromosomes, a particular dynamic local search scheme is proposed to exploit the neighborhood of each antibody as much as possible so to realize automatic variation of the antibody length during evolution. The dynamic local search scheme includes four basic operations, namely, the external cluster swapping, the internal cluster swapping, the cluster addition and the cluster decrease. Moreover, a neighborhood structure based clonal mutation is adopted to further improve the performance of the algorithm. The proposed algorithm has been extensively compared with five state-of-the-art automatic clustering techniques over a suit of datasets. Experimental results indicate that the DLSIAC is superior to other five clustering algorithms on the optimum number of clusters found and the clustering accuracy. In addition, DLSIAC is applied to a real problem, namely image segmentation, with a good performance.     

基于相对密度估计和多簇合并的密度峰值聚类算法

密度峰值聚类(DPC)算法是一种新颖的基于密度的聚类算法,其原理简单、运行效率高.但DPC算法的局部密度只考虑了样本之间的距离,忽略了样本所处的环境,导致算法对密度分布不均数据的聚类效果不理想;同时,样本分配过程易产生分配错误连带效应.针对上述问题,提出一种基于相对密度估计和多簇合并的密度峰值聚类(DPC-RD-MCM)算法. DPC-RD-MCM算法结合K近邻和相对密度思想,定义了相对K近邻的局部密度,以降低类簇疏密程度对类簇中心的影响,避免稀疏区域没有类簇中心;重新定义微簇间相似性度量准则,通过多簇合并策略得到最终聚类结果,避免分配错误连带效应.在密度分布不均数据集、复杂形态数据集和UCI数据集上,将DPC-RD-MCM算法与DPC及其改进算法进行对比,实验结果表明:DPC-RD-MCM算法能够在密度分布不均数据上获得十分优异的聚类效果,在复杂形态数据集和UCI数据集的聚类性能上高于对比算法.