Determining number of clusters and prototype locations via multi-scale clustering

In clustering algorithms, it is usually assumed that the number of clusters is known or given. In the absence of such a priori information, a procedure is needed to find an appropriate number of clusters. This paper presents a clustering algorithm that incorporates a mechanism for finding the appropriate number of clusters as well as the locations of cluster prototypes. This algorithm, called multi-scale clustering, is based on scale-space theory by considering that any prominent data structure ought to survive over many scales. The number of clusters as well as the locations of cluster prototypes are found in an objective manner by defining and using lifetime and drift speed clustering criteria. The outcome of this algorithm does not depend on the initial prototype locations that affect the outcome of many clustering algorithms. As an application of this algorithm, it is used to enhance the Hough transform technique.     

稳定的K-多均值聚类算法

指定K个聚类的多均值聚类算法在K-均值算法的基础上设置了多个次类,以改善K-均值算法在非凸数据集上的劣势,并将多均值聚类问题形式化为优化问题,可以得到更优的聚类效果。但是该算法对初始原型敏感,且随机选取原型的方式使聚类结果不稳定。针对上述问题,提出一种稳定的K-多均值聚类算法,并对该算法的复杂度与收敛性进行了简要讨论。该算法先基于数据样本的最邻近关系构造图,根据图的连通分支将数据分为若干组,取每组数据的均值点作为初始原型,再用交替迭代的方法对优化问题进行求解,得到最后的聚类结果。在人工数据集和真实数据集上的实验表明,该算法具有更稳定更优越的聚类效果。     

混合属性数据k-prototypes聚类算法

在现实世界中经常遇到混合数值属性和分类属性的数据, k-prototypes是聚类该类型数据的主要算法之一。针对现有混合属性聚类算法的不足,提出一种基于分布式质心和新差异测度的改进的 k-prototypes 算法。在新算法中,首先引入分布式质心来表示簇中的分类属性的簇中心,然后结合均值和分布式质心来表示混合属性的簇中心,并提出一种新的差异测度来计算数据对象与簇中心的距离,新差异测度考虑了不同属性在聚类过程中的重要性。在三个真实数据集上的仿真实验表明,与传统的聚类算法相比,本文算法的聚类精度要优于传统的聚类算法,从而验证了本文算法的有效性。     

改进的最小生成树自适应分层聚类算法

针对传统最小生成树聚类算法需要事先知道聚类数目和使用静态全局分类依据,导致聚类密度相差较大时,算法有效性下降,计算复杂度大等问题,提出一种改进的最小生成树自适应分层聚类算法,根据最近邻关系,自动为每个聚类簇设定独立的阈值,使之适应分布密度相差较大的情况,并能自动确定聚类数目。实验表明,算法具有较好的性能,尤其对数据密度分布不均匀的情况也能得到较好的聚类结果。     

Robust projected clustering

Projected clustering partitions a data set into several disjoint clusters, plus outliers, so that each cluster exists in a subspace. Subspace clustering enumerates clusters of objects in all subspaces of a data set, and it tends to produce many overlapping clusters. Such algorithms have been extensively studied for numerical data, but only a few have been proposed for categorical data. Typical drawbacks of existing projected and subspace clustering algorithms for numerical or categorical data are that they rely on parameters whose appropriate values are difficult to set appropriately or that they are unable to identify projected clusters with few relevant attributes. We present P3C, a robust algorithm for projected clustering that can effectively discover projected clusters in the data while minimizing the number of required parameters. P3C does not need the number of projected clusters as input, and can discover, under very general conditions, the true number of projected clusters. P3C is effective in detecting very low-dimensional projected clusters embedded in high dimensional spaces. P3C positions itself between projected and subspace clustering in that it can compute both disjoint or overlapping clusters. P3C is the first projected clustering algorithm for both numerical and categorical data.     

基于过滤模型的聚类算法

合理的聚类原型是正确聚类的前提.针对现有聚类算法原型选取不合理、计算聚类个数存在偏差等问题,提出基于过滤模型的聚类算法(CA-FM).算法以提出的过滤模型去除干扰聚类过程的边界和噪声对象,依据核心对象之间的近邻关系生成邻接矩阵,通过遍历矩阵计算聚类个数;然后,按密度因子将数据对象排序,从中选出聚类原型;最后,将其余对象按照距高密度对象的最小距离划分到相应的簇中,形成最终聚类.在人工合成数据集、UCI数据集以及人脸识别数据集上的实验结果验证了算法的有效性,与同类算法相比,CA-FM算法具有较高的聚类精度.     

改进的GK聚类算法

针对传统GK聚类算法无法自动确定聚类数和对初始聚类中心比较敏感的缺陷,提出一种改进的GK聚类算法。该算法首先通过基于类间分离度和类内紧致性的权和的新有效性指标来确定最佳聚类数;然后,利用改进的熵聚类的思想来确定初始聚类中心;最后,根据判定出的聚类数和新的聚类中心进行聚类。实验结果表明,新指标能准确地判断出类间有交叠的数据集的最佳聚类数,且改进后的算法具有更高的聚类准确率。     

基于网格相对密度的多密度聚类算法

提出网格相对密度的概念和边界点提取技术,在此基础上给出了一种多密度聚类算法。该算法使用网格相对密度识别具有不同密度聚簇的相对高密度网格单元,聚类时从相对高密度网格单元开始逐步扩展生成聚簇。实验结果表明,算法能有效地识别不同形状、不同密度的聚簇并对噪声数据不敏感,具有聚类精度高等优点。     

快速模糊C均值聚类彩色图像分割方法

模糊C均值(FCM)聚类用于彩色图像分割具有简单直观、易于实现的特点，但存在聚类性能受中心点初始化影响且计算量大等问题，为此，提出了一种快速模糊聚类方法(FFCM)。这种方法利用分层减法聚类把图像数据分成一定数量的色彩相近的子集，一方面，子集中心用于初始化聚类中心点；另一方面，利用子集中心点和分布密度进行模糊聚类，由于聚类样本数量显著减少以及分层减法聚类计算量小，故可以大幅提高模糊C均值算法的计算速度，进而可以利用聚类有效性分析指标快速确定聚类数目。实验表明，这种方法不需事先确定聚类数目并且在优化聚类性能不变的前提下，可以使模糊聚类的速度得到明显提高，实现彩色图像的快速分割。     

基于数据场的改进DBSCAN聚类算法

DBSCAN(density based spatial clustering of applications with noise)算法是一种典型的基于密度的聚类算法。该算法可以识别任意形状的类簇,但聚类结果依赖于参数Eps和MinPts的选择,而且对于一些密度差别较大的数据集,可能得不到具有正确类簇个数的聚类结果,也可能将部分数据错分为噪声。为此,利用数据场能较好描述数据分布,反映数据关系的优势,提出了一种基于数据场的改进DBSCAN聚类算法。该算法引入平均势差的概念,在聚类过程中动态地确定每个类的Eps和平均势差,从而能够在一些密度相差较大的数据集上得到较好的聚类结果。实验表明,所提算法的性能优于DBSCAN算法。     

基于密度的模糊代表点聚类算法

结合密度聚类和模糊聚类的特点,提出一种基于密度的模糊代表点聚类算法.首先利用密度对数据点成为候选聚类中心点的可能性进行处理,密度越高的点成为聚类中心点的可能性越大;然后利用模糊方法对聚类中心点进行确定;最后通过合并聚类中心点确定最终的聚类中心.所提出算法具有很好的自适应性,能够处理不同形状的聚类问题,无需提前规定聚类个数,能够自动确定真实存在的聚类中心点,可解释性好.通过结合不同聚类方法的优点,最终实现对数据的有效划分.此外,所提出的算法对于聚类数和初始化、处理不同形状的聚类问题以及应对异常值等方面具有较好的鲁棒性.通过在人工数据集和UCI真实数据集上进行实验,表明所提出算法具有较好的聚类性能和广泛的适用性.     

Self-Organizing-Map Based Clustering Using a Local Clustering Validity Index

Classical clustering methods, such as partitioning and hierarchical clustering algorithms, often fail to deliver satisfactory results, given clusters of arbitrary shapes. Motivated by a clustering validity index based on inter-cluster and intra-cluster density, we propose that the clustering validity index be used not only globally to find optimal partitions of input data, but also locally to determine which two neighboring clusters are to be merged in a hierarchical clustering of Self-Organizing Map (SOM). A new two-level SOM-based clustering algorithm using the clustering validity index is also proposed. Experimental results on synthetic and real data sets demonstrate that the proposed clustering algorithm is able to cluster data in a better way than classical clustering algorithms on an SOM.     

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.     

一种有效的用于数据挖掘的动态概念聚类算法

概念聚类适用于领域知识不完整或领域知识缺乏时的数据挖掘任务.定义了一种基于语义的距离判定函数,结合领域知识对连续属性值进行概念化处理,对于用分类属性和数值属性混合描述数据对象的情况,提出了一种动态概念聚类算法DDCA(domain-baseddynamicclusteringalgorithm).该算法能够自动确定聚类数目,依据聚类内部属性值的频繁程度修正聚类中心,通过概念归纳处理,用概念合取表达式解释聚类输出.研究表明,基于语义距离判定函数和基于领域知识的动态概念聚类的算法DDCA是有效的.     

基于密度可达的多密度聚类算法

为对多密度数据集聚类,提出一种基于密度可达的多密度聚类算法。使用网格划分技术来提高计算每个点密度值的效率,每次聚类都是从最高密度点开始,根据密度可达的概念和广度优先的策略逐步向外扩展进行聚类。实验表明,该算法能够有效地对任意形状、大小的均匀数据集和多密度数据集进行聚类,并能较好地识别出孤立点和噪声,其精度和效率优于SNN算法。     

A fuzzy modeling method via Enhanced Objective Cluster Analysis for designing TSK model

This paper proposes a fuzzy modeling method via Enhanced Objective Cluster Analysis to obtain the compact and robust approximate TSK fuzzy model. In our approach, the Objective Cluster Analysis algorithm is introduced. In order to obtain more compact and more robust fuzzy rule prototypes, this algorithm is enhanced by introducing the Relative Dissimilarity Measure and the new consistency criterion to represent the similarity degree between the clusters. By these additional criteria, the redundant clusters caused by iterations are avoided; the subjective influence from human judgment for clustering is weakened. Moreover the clustering results including the number of clusters and the cluster centers are considered as the initial condition of the premise parameters identification. Thus the traditional iteration modeling procedure for determining the number of rules and identifying parameters is changed into one-off modeling, which significantly reduces the burden of computation. Furthermore the decomposition errors and the approximation errors resulted from premise parameters identification by Fuzzy c-Means clustering are decreased. For the consequence parameters identification, the Stable Kalman Filter algorithm is adopted. The performance of the proposed modeling method is evaluated by the example of Box–Jenkins gas furnace. The simulation results demonstrate the power of our model.     

基于量子遗传聚类的入侵检测方法*

现有基于聚类的入侵检测算法,聚类过程中需要预设聚类数,且算法的性能受初始数据输入顺序的影响,为此提出了一种新的基于量子遗传聚类入侵检测方法。该方法的基本思想是先自动建立初始聚类簇,再用改进量子遗传算法对初始聚类组合优化,最后进行入侵检测。实验结果表明,该方法能够有效地检测出网络中的入侵数据。     

基于最小生成树的密度聚类算法研究

传统DBSCAN算法对密度分布不均匀的不平衡数据集的聚类效果并不理想,同时传统算法的聚类结果对邻域半径(Eps)以及核心点阈值(MinPts)敏感。针对以上问题,改进了传统算法,提出了一种基于最小生成树的密度聚类算法(MST-DBSCAN)。由于对象之间的距离对聚类结果影响较大,为了更好地表示对象之间的距离特性,首先使用相互可达距离(mutual reachability distance)代替传统算法中的欧氏距离,表示数据集中对象与对象之间的距离,解决因密度分布不均匀导致效果不佳的问题;为了建立对象与对象之间的联系,同时保留对象之间的距离特性,引用Prim算法对数据集中的所有对象构建最小生成树;其次根据指定的簇的数目及最小簇对象数数目参数对得到的最小生成树进行剪枝;根据剪枝的结果,将剪枝后的各个部分进行聚类。在公开的UCI数据集上的实验结果表明,提出的MST-DBSCAN算法与现有DBSCAN、OPTICS、KANN-DBSCAN算法相比,在密度分布不均匀的数据集上聚类效果有所提升并且较原有传统算法有较高的聚类准确性。     

基于密度敏感距离的改进模糊C均值聚类算法

模糊C均值（FCM）聚类算法无法识别非凸数据,算法中基于欧式距离的相似性度量只考虑数据点之间的局部一致性特征而忽略了全局一致性特征。提出一种利用密度敏感距离度量创建相似度矩阵的FCM算法。通过近邻传播算法获取粗类数作为最佳聚类数的搜索范围上限,以解决FCM算法聚类数目需要人为预先设定和随机选定初始聚类中心造成聚类结果不稳定的问题。在此基础上,改进最大最小距离算法,得到具有代表性的样本点作为初始聚类中心,并结合轮廓系数自动确定最佳聚类数。基于UCI数据集和人工数据集的实验结果表明,相比经典FCM、K-means和CFSFDP算法,该算法不仅具有识别复杂非凸数据的能力,而且能够在保证聚类性能和稳定性的前提下加快收敛速度。     

多数据流的实时聚类算法

针对当前对多条数据流的聚类算法不能兼顾质量和效率的矛盾,提出了基于相关系数的多条数据流的聚类算法,实现固定长度的在线动态聚类。算法引入衰减系数提高聚类质量,以相关系数作为流数据间相似度的度量标准,将数据流划分若干个数据段,以各数据流的相关统计信息进行聚类,得到实时的聚类结构。实验结果表明,算法有较高的效率、聚类质量和稳定性。