CLOPE快速有效聚类算法.docVIP

CLOPE：针对交易的数据快速有效聚类算法 摘要 本文研究分类数据的聚类问题，特别针对多维和大型的交易数据。从增加聚簇直方图的高宽比的方法得到启发，我们开发了一种新的算法---CLOPE，这是一种非常快速、可伸缩，同时又非常有效的算法。我们展示了算法对两个现实数据集聚类的性能，并将CLOPE与现有的聚类算法进行了比较。 关键词 数据挖掘，聚类，分类数据，可伸缩性 1.简介 聚类是一种非常重要的数据挖掘技术，它的目的是将相似的交易[12,?14,?4,?1]分组在一起。最近，越来越多的注意力已经放到了分类数据[10,8,6,5,7,13]的聚类上，分类数据是由非数值项构成的数据。交易数据，例如购物篮数据和网络日志数据，可以被认为是一种特殊的拥有布尔型值的分类数据，它们将所有可能的项作为项。快速而精确地对交易数据进行聚类的技术在零售行业，电子商务智能化等方面有着很大的应用潜力。 但是，快速而有效聚类交易数据是非常困难的，因为这类的数据通常有着高维，稀疏和大容量的特征。基于距离的算法例如k-means[11]和CLARANS[12]都是对低维的数值型数据有效。但是对于高维分类数据的处理效果却通常不那么令人满意[7]。像ROCK这类的分层聚类算法在分类数据聚类中表现的非常有效，但是他们在处理大型数据库时表现出先天的无效。 LargeItem[13]算法通过迭代优化一个全局评估函数对分类数据进行聚类。这个评估函数是基于大项概念的，大项是在一个聚簇内出现概率比一个用户自定义的参数——最小支持度大的项。计算全局评估函数要远比计算局部评估函数快得多，局部评估函数是根据成对相似性定义的。这种全局方法使得LargeItem算法非常适合于聚类大型的分类数据库。 在这篇文章中，我们提出了一种新的全局评估函数，它试图通过增加聚簇直方图的高度与宽度之比来增加交易项在聚簇内的重叠性。此外，我们通过引用一个参数来控制聚簇紧密性的方法来泛化我们的想法，通过修改这个参数可以得到不同的聚簇划分个数。实验表明，我们的算法运行速度比Largeltem快得多，聚类的质量与ROCK算法[7]相当接近。 为了解释算法的一些基本思想，我们采用一个非常小的交易数据库，其中包含5条交易数据{（苹果，香蕉），（苹果，香蕉，蛋糕），（苹果，蛋糕，盘子），（盘子，鸡蛋），（盘子，鸡蛋，鱼）}。为简单起见，交易（苹果，香蕉）被简称为ab，以此类推。对于这个小型数据库，比较下面两个聚类划分（1）{{ab，abc，acd}，{de，def}};（2）{{ab，abc}，{acd，de，def}}。对于每一个聚簇，我们计算每一个不同项的出现次数，然后得到聚簇的高度（H）和宽度（W）。例如，聚簇{ab，abc，acd}中a:3，b:2，c:2，d:1，H=2.0，W=4，图1将这些结果显示为几何上的直方图，按项出现频率降序排列，这样做只是为了更容易直观展示。 ? 图1 两个聚簇的直方图 我们通过分析聚簇的高度和宽度，从几何学上来评判这两个聚类的质量。不算{de，def}和{ab，abc}这两个拥有相同直方图的聚簇，另两个直方图的质量不同。聚簇{ab，abc，acd}的直方图8块区域(H=2.0,?H/W=0.5)只有4个不同项，但是聚簇{acd，de，def}对于相同的块数却有5个不同的项（H?=1.6，H/W=0.32）。很明显，聚类（1）比较好，因为我们更希望同一个聚簇中的交易有更多的重叠。 从上面的例子中，我们可以看到，拥有更大高宽比的直方图具有更好的簇内相似性。我们应用这一简单的直觉作为聚类算法的基础，用簇的直方图的几何性质定义全局评估函数。我们把这种新的算法叫做CLOPE——带有倾斜的聚类。CLOPE算法不仅非常有效，在聚类形如市场交易数据和网络服务器日志这类高维的大型交易数据时也非常之快而且具有较好的可拓展性。 本文的其它部分安排如下。第2节将更加正式地分析分类数据聚类问题，并提出我们的评估函数。第3节详细介绍CLOPE算法以及其实现问题。在第4节，将CLOPE与Largeltem对现实数据集聚类的实验结果进行比较。第5节介绍相关工作后，第6节对文章进行总结。 ? 2.CLUSTERING WITH SLOPE（具有倾斜的聚类） 符号：在整篇文章中，我们使用以下符号。交易数据集D是一组交易{t1, ...,tn}的集合。每条交易是一些项{i1, ..., im}的集合。一个聚簇{C1, ... Ck}是{t1, ..., tn}的一个划分，也就是说，C1 ∪ … ∪ Ck ={t1, ..., tn}而且对任意1?≤?i,?j?≤?k，满足Ci ≠ φ ∧ Ci∩Cj = φ。每一个Ci叫做一个簇。除非其它说明，n，m，k分别表示交易的个数、