一种基于概率的快速聚类算法

（重庆师范大学数学学院，重庆 400047）

（重庆师范大学数学学院，重庆 400047）

在聚类算法和特征向量维数确定的模式样本集中,各样本的每一维表示一个对应特征；鉴于此在基于层次算法的基础上,提出了一种基于概率的快速聚类算法；该算法先对各个特征进行分类,然后按照概率准则,每个向量先自成一类,将其对应概率最大的特征向量合并,减少类别数,直至达到要求为止；用UCI中的Iris和Wine数据集对该算法进行仿真实验,实验数据表明：用该算法进行聚类,能获得较好的聚类结果,说明算法具有一定的有效性。

聚类；样本；特征；概率

聚类分析是数据挖掘领域一个重要的研究课题，作为一种常见的数据分析工具，其目的是把大量数据点的集合分成若干类，使得每个类中的数据之间存在最大程度的相似，而不同类中的数据存在最大程度的不同［1］。聚类分析同时也是一个具有很强挑战性的领域，它的潜在应用对其提出了不同的聚类算法。迄今为止，人们已经提出了很多的聚类算法，最主要的方法是：划分方法［2］、分层类方法［3］、基于密度方法［4］、基于网格方法［5］和基于模型方法［6］。所有的这些算法都通过不同的途径实现了对数据集的有效聚类，但快速、精确而简便的聚类算法仍然是一个有待研究的开放问题。

在聚类算法中，首先要抽取和选择出能代表这个模式的特征［7］。用这些特征构成的特征向量占有Rn空间中的一点，也就是说，给定的数据集合是由若干样本组成的，每个样本是多维的，每一个维度对应着一个特征或者属性［8］。理想的特征是能够区分出属于不同类的样本，这些特征都有能反映本类别的数值范围。基于文献［10］一种基于参考点的快速k-均值算法，在此提出了一种基于概率的快速聚类算法，该算法根据样本每一个特征所属类别的数值范围，先对各个特征进行分类，然后根据层次聚类算法思路，每个特征先自成一类，按概率准则将其对应概率最大的特征向量合并，减少类别数，直至达到分类要求为止。

1 算法设计

在层次聚类算法中，先是初始模式样本自成一类，计算各类之间的距离，得到距离矩阵。然后根据要求进行合并。在借鉴了层次聚类算法思路的基础上，提出了基于概率的快速聚类算法，算法先对各个特征进行分类，然后按照层次聚类算法思路，得到概率矩阵，合并概率大的两项。

1.1 设计思想

假设样本数据集合：U0=｛χ1，χ2，…，χn｝，样本数据有m个属性，则样本数据可以表示为χ1=（χ11，χ12，χ13，…，χ1m）

定义1 阈值Ti定义为各个特征的数值范围：

定义2 样本数据点之间的概率定义为任两个类在m种分类中在同一类中的概率：

定义3［10］准确率：其中，ν为能够被正确分配到指定类的数据对象的个数，n为全部数据对象总数。

层次聚类算法中的最小距离算法，距离作为聚类准则，数据之间的距离越小越相似。在本文算法中，概率作为聚类准则，数据之间的概率越大越相似。本文算法首先根据特征向量的各个特征的不同取值范围，取出不同的阈值Ti，然后按照下面的步骤逐步将各个特征向量进行分类：先对第一个特征进行分类，若χli小于阈值T1时，则将数据χl归为集合W01类中，并将χl从集合U0中删除；若χli大于阈值T1时，则将数据χl归为集合W03类中，并将χl从集合U0中删除，得到集合W02，如此反复，对将所有的特征进行分类，可将数据点分为3类，共有m种分类方法。按照层次聚类算法思想，先将各个初始聚类模式自成一类，按照式（2）计算各类之间的概率，得到一个n×n的概率矩阵，找出对角线以外的最大概率，将其对应的两类合并为同一类。由此建立新的分类：P1（1），P2（1）…重新计算合并，直至达到要求为止。

假设现在有一个四维鸢尾花数据样本集合，含有15个数据点，样本数据表如表1所示。

表1 样本数据表

（1）按照本文算法思想，首先对数据点第1维属性按阈值T1=（5.1，5.8）进行分类，可将数据点划分为

同理按阈值T2=（3.0，3.3），阈值T3=（3.3，4.9），阈值T4=（1.0，1.6）对数据点的第2维属性，第3维属性和第4维属性进行分类，可将数据点划分为

（2）按照层次聚类算法思想，先将15个初始模式样本自成一类。计算各类及之间的概率得到一个15× 15维的概率矩阵。找出中对角线以外最大的概率，将其对应的两类合并为一类，原数据点新的分类结果：｛（χ1，χ2，χ3），（χ4，χ5），（χ6，χ7，χ8），（χ12，χ15），（χ9），（χ10），（χ11），（χ13），（χ14）｝。

表2 概率矩阵P(3)

分类结果为

这样就得到了鸢尾花较好的聚类结果。

1.2 算法描述

样本数据集合为U0=｛χ1，χ2，…，χn｝，具体算法描述如下：

输入：聚类个数k以及包含n个数据对象的数据集；输出：k个概率较高的聚类。

（1）按阈值Ti划分样本点的第i个分量，将样本点分为3类，有m种分类方法；

（2）n个初始模式样本自成一类，即建立n类P1（0），P2（0），…，Pn（0），计算各类之间的概率，得到一个n×n维的概率矩阵。标号（0）表示聚类开始运行前的状态；

（3）如在前一步聚类运算中，已求得概率矩阵P（n）（n为逐次聚类合并次数），则找出P（n）中对角线以外的最大概率，将其对应的两类合并为一类。由此建立新的分类：P1（n+1），P2（n+1）…；

（4）计算合并后计算新类别之间的概率，得到概率矩阵P（n+1）；

（5）跳至第（3）步，重新计算及合并；

（6）当P（n）的最大分量小于给定的阈值p时，算法停止，各类已足够。

2 实验结果与分析

2.1 实验描述

为了验证算法的有效性，将本文算法和最近邻算法、最短距离算法、k-means算法在UCI数据库中的Iris数据集和Wine数据集上进行了测试。Iris以鸢尾花的特征作为数据来源，包含了150条数据，分为3个类，每类各50条数据，每个数据均包含4个属性。Wine数据集来源于葡萄酒，包含178条数据，分为3个类，分别包含59、71、48条数据，每个数据均包含13个属性。分别在Iris和Wine上进行了测试。说明了本文算法的可实施性及有效性。

2.2 实验结果与分析

实验结果如表3所示，由于选取的不同聚类算法，得到的聚类结果也不相同。在Iris数据集上，准确率最高的是k-means算法，其准确率是89.33%。准确率最高低的是最近邻算法，其准确率是68.00%。而本文算法的准确率是79.33%，它高于最近邻算法和最短距离算法。在Wine数据集上，准确率最高的是k-means算法，其准确率是87.08%。准确率最高低的是最近邻算法，其准确率是42.70%.而本文算法的准确率是71.91%，它高于最近邻算法和最短距离算法。实验结果表明：该算法在算法效率、稳定性和准确率都相对较好，说明本文算法有一定的可实施性和有效性。

表3 数据集测试结果表

3 结束语

在聚类算法中，由各个特征组成的特征向量模式，由于各个特征的不同取值范围，本文提出了一种基于概率的快速聚类算法，先对各个特征分类，然后根据层次聚类算法思路进行聚类.在人们对实体（例如对象、个体、事件）进行分类时，基于概率的快速聚类算法更好的利用各个特征的特点，提高了聚类的精确度。

［1］HAN JW，MICHELINE K.Data Mining：Concepts and Techniques［M］.San Francisco：Morgan Kaufmann Publishers，2001：412-413

［2］KAUFAN L，ROUSSEEUW P.Finding Groups in Data：an Introduction to Cluster Analysis［M］.New York：John Wiley& Sons，1990

［3］MUATA K，BRYSO O.Towards Supporting Expert Evaluation of Clustering Results Using a Data Mining Process Model［J］. Information Sciences，2010，180（3）：414-431

［4］ESTER M，KRIEGEL H，SANDER J，XU X.A Density Based Algorithm for Discovering Cluster in Large Spatial Databases with Noise［A］.In：Simoudis E，Han JW，Fayyad UM，eds.Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining［C］.Portland：AAAIPress，1996：226-231

［5］AGRAWALR，GEHRKE J，GUNOPOLOSD.Automatic Subspace Clustering of High Dimensional Data for Data Mining Application［A］.In：Haas LM，Tiwary A，eds.Proceedings of the ACM SIGMOD International Conference on Management of Data［C］.Seattle：ACM Press，1998：94-105

［6］朱明.数据挖掘［M］.合肥：中国科技大学出版社，2002

［7］EISEN M，SPELLMAN P，BROWN P.Cluster Analysis and Display of Genome-wide Expression Data［J］.Proceedings of National Academy of Science，USA，1988（95）：14863-14868

［8］AMADOR J.Sequential Clustering by Statistical Methodology［J］.Pattern Recognition Letters，2005（26）：2152-2163

［9］李有明.一种基于参考点的快速k-均值算法［J］.重庆工商大学学报：自然科学版，2013（5）：101-103

［10］韩凌波，王强，蒋正峰，等.一种改进的k-means初始聚类中心选取算法［J］.计算机工程与应用，2010，46（17）：150-151

一种基于概率的快速聚类算法

李 婧

A Kind of Fast Clustering Algorithm Based on Probability

LI Jing

（School of Mathematics，Chongqing Normal University，Chongqing 400047，China）

In clustering algorithms，in model samples determined by eigenvector dimensions，every dimension of each sample represents a corresponding feature，based on this，this paper advances a kind of fast clustering algorithm based on probability on the basis of hierarchical algorithm.This algorithm firstly classifies each feature，then according to probability principle，makes each vector become a type，combines themaximum eigenvectorswith its corresponding probability to reduce the type number until the requirement is met，and conducts simulation experiment on this algorithm by using Iris and Wine data set in UCI.Experiment data show thatbetter clustering results can be obtained by using this algorithm for clustering，which illustrates that this algorithm has certain validity.

clustering；sample；feature；probability

代小红

TP349

A

1672-058X(2014)02-0061-05

2013-07-07;

2013-09-10.

李婧（1988-），女，重庆巫山人，硕士研究生，主要从事智能计算及应用研究.