一种基于近似类抽样的组合聚类方法
摘 要：
k-means 聚类算法的时间复杂度(O(nmkt) )和Fuzzy C-Means 算法的时间复杂度(O(nmct) )，对于海量数据挖掘都还能让人接受，但聚类效果受初始化影响很大，以致结果很不稳定。当初始点集选择合适时，这两种算法的聚类结果很不错；而初始点选择很偏时，聚类效果很不理想。而k-中心点轮换法对结构较好的数据点集分布聚类效果不错，尤其是它对初始化不太敏感，所以当数据点集规模较小时，这种算法是一个不错的选择。其最大的缺点就是时间复杂度(O(n2k 2m) )太高了，显然不能直接应用到海量数据集的聚类中。为了克服这两类聚类算法的缺点，而充分利用它们的优点，很自然地提出一种基于近似类抽样的组合聚类算法。仿真实验结果表明，这种混和聚类算法的聚类结果与k-中心点轮换法一样好，在一般情况下，其时间复杂度只是(O(n2m) )。
关键词： k-means 聚类 k-中心点轮换法 组合聚类算法 近似类抽样
1．引言
聚类分析，一般认为就是试图发现数据点集中内在的结构，使同一簇内的数据点相似度高，不同簇之间的数据点相异度高。将聚类问题转化为一种优化问题，再通过数学规划的方法来进行求解是研究聚类分析的一个重要方向。
设在 m 维欧氏空间中有n 个点，在这个空间中的某个范围内选取k 个中心位置i m( i = 1,2,L, k )，使这n 个点到各自最近的中心位置的距离平方之和最小，这是最初的一种优化目标函数。MacQueen[1]于1967 年提出的k-means 聚类算法是一种很容易理解的交替优化聚类算法，这种优化策略并不是通过计算目标函数来进行寻优，所以其时间复杂度只是O(nmkt)，其中，n 是所有数据点的数目，m 是数据点的维数，k 是簇的数目，t 是迭代的次数。George Karypis[2]在一篇论文中提到k-means 聚类算法假定聚类是超椭球体形状、大小大致相等。这种算法不能发现大小变化很大的数据分布，也很难发现具有凹入形状的数据分布。这个结论从实验中也可以看到。
k-means聚类算法的时间复杂度和Fuzzy C-Means算法[3]的时间复杂度(O(nmct) )，对于海量数据挖掘都还能让人接受，但聚类效果受初始化影响很大，以致结果很不稳定。当初始点集选择合适时，这两种算法的聚类结果很不错；而初始点选择很偏时，聚类效果很不理想。而k-中心点轮换法[本文作者的一篇投出去的论文中的一个k-中心点聚类改进算法]对结构较好的数据点集分布聚类效果不错，尤其是它对初始化不太敏感，所以数据点集规模较小时，这种算法是一个不错的选择。其最大的缺点就是时间复杂度(O(n2k 2m) )太高了，显然不能直接应用到海量数据集的聚类中。为了克服这两类聚类算法的缺点，而充分利用它们的优点，很自然地提出一种组合聚类算法。
2．混和型聚类算法
2.1 对已有的改进型混和聚类算法的粗略介绍
N. Zahid[4]针对FCM 聚类算法需要好的初始点集才能获得好的聚类结果，这篇文章提出一种基于两层聚类策略，第一层是使用K-最近邻决策规则来获得初始聚类中心点，接着采用FCM 算法，实验证实这种方法效果不错。而且这种两层聚类策略无需事先给定聚类数目、聚类停止标准、模糊指数，最后还能判断聚类的质量。将传统的聚类算法结合一些优化方法加以改进，以获得更好的聚类结果，这方面的研究文献还有[5][6][7][8]。可见，将聚类问题转化为一种优化问题，然后运用数学规划方法进行优化求解；或者将一些优化方法融入到某些聚类算法中，来提高聚类效率、改进聚类结果，这是一个可行的研究方向。
2.2 组合聚类算法的描述
本组合聚类算法分三个阶段：
第一阶段剔除孤立点；先定义一个近似类阈值，根据近似类操作对剔除孤立点后的数据点集作抽样，减少待聚类的数据点集规模。按照近似类中元素个数的多少对近似类集簇进行降序排列，由前到后地挑选一个能覆盖当前近似类集簇中所有元素的近似类集合，并且使这个集合中的近似类有尽量少的重复元素（数据点）； 将这个能约简覆盖近似类集簇的近似类集合中的核心元组成一个集合，称为“抽样数据点集”；第二阶段采用 k-中心点轮换聚类法对抽样数据点集进行聚类，先是获取这种算法的聚类结果，再根据聚类结果求取每个聚类的平均点，将聚类的平均点集作为下一阶段聚类算法的初始点集；第三阶段根据第二阶段的结果作为本阶段聚类算法的初始点集，采用 k-means 聚类算法或FuzzyC-Means 算法对剔除孤立点后的数据点集进行聚类，以期获得更好的聚类结果。
具体步骤如下：
Step1 先定义一个近似类阈值，根据这个阈值对数据点集合（n 个m 维的数据点）作近似类操作，获得每个数据点的近似类，构成一个近似类集簇；Step2 将近似类的元素个数少于这个阈值的近似类作为孤立点近似类，并从近似类集簇中删去；Step3 按照近似类中元素个数的多少对近似类集簇进行降序排列，由前到后地挑选一个能覆盖当前近似类集簇中所有元素的近似类集合，并且使这个集合中的近似类有尽量少的重复元素（数据点）；Step4 将这个能约简覆盖近似类集簇的近似类集合中的核心元组成一个集合，称为“中心点轮换集”，对这个集合执行k-中心点轮换聚类法，先是获取这种算法的聚类结果，再根据聚类结果求取每个聚类的平均点，将聚类的平均点集作为下一阶段（第5 步）的初始点集；Step5 根据中心点集就可以获得各个聚类了。
Step5′ 根据中心点集再采用k-means 聚类算法或Fuzzy C-Means 算法对全部的数据点集进行聚类，以期获得更好的聚类结果。
这种组合聚类方法主要是为了克服 k-中心点轮换法的时间复杂度高的缺点，但这种方法仍需要O(n2m)。其中抽样的时间复杂度为O(n2m)，这也是本组合聚类算法的时间复杂度。
2.3 对几个概念和算法的具体实现的补充说明
定义 1[9]：近似关系S 是论域U （可以看作一个集合）上的二元关系，它满足：自反性和对称性。
定义 2[9]：设论域U 上有近似关系S ，则对每一个a∈U ，a的近似类记为S [a] ，它指下列集合a 称为S [a] 的代表元素（核心元素）。其中xSa 表示元素x 和a 具有近似关系S ，即(x,a)∈S 。
近似关系的构造可以通过定义一个近邻类阈值，集合的所有元素与其近邻类阈值内的元素就可以构成一个近似关系S 。每个元素的近似类元素都在这个元素的近邻类阈值内。通过这样一种近似关系，就可以对大量的密集数据元素集合进行近似类抽样，以减少数据规模。
这种近似类抽样方法能大致保持原数据元素集合的空间分布形状。其缺点是，其抽样复杂度是O(n2m)，还是不能应用到海量数据的抽样处理；对于具有不同密度分布的数据元素集合，在确定近邻类阈值后，就不能自适应地调整这个阈值，以保持数据元素集合的不同密度分布特性。
实现 1：近似类抽样步骤的仿真实验实现方法设数据点集合存在一个数组中，即 x[n]存储了n 个数据。则实现步骤如下：
Step1. 初始化数据集到数组x[]中，并标识每个数据为“未删除”；Step3. 将数据点数组x[]中标识为“未删除”的数据保存到一个新集合中，这个集合就是一个基于阈值A 作近似类抽样的集合。
实现 2：一种依赖标识来保存具有不同密度分布数据的抽样方法Step1. 取定一个阈值A，对数据集作近似类分析；Step2. 按照近似类中数据元素的个数多少对近似类集簇作降序排列；Step3. 由前向后从近似类集簇中挑选一个能以尽可能少的重复数据元素的近似类集合S 来覆盖描述原数据集；Step4. 对进入近似类集合S 的近似类，按照数据元素个数多少作标识，这样就可以区分抽样具有不同密度的数据分布。
实现 3：k-中心点轮换法，是将求解线性规划问题的经典方法－单纯型法，应用到k-中心点聚类算法中的一种改进型聚类算法。仿真实验结果表明，这个改进型算法比原始的k-中心点聚类算法有更好的聚类结果、更稳定的聚类效果。聚类效果好的根本原因就在于更换聚类中心点的策略有些不同，但付出的代价就是时间复杂度提高了。
改进 1：一种基于网格的近似类抽样方法采用一种动态网格法来抽样大数据集。完全采用近似类操作，时间复杂度就是O(n2m)。
但如果采用网格划分，在每个网格及其临近网格范围内考虑这个网格中每个数据点的近似类，这样在计算每个数据点的近似类时可以缩小考虑范围。这种方法要求每个网格在每一维上的宽度至少要大于近似类的阈值。确定一个最合适的多维网格子空间需要一定的优化处理方法。设网格数为K，则这种基于网格的抽样方法的时间复杂度为
3．仿真实验验证
3.1 仿真实验设计
采用 Java 应用程序，通过鼠标作出的由多个二维的数据点集组成的几个图片，其大小与显示器大小相等，即（1024×768），数据点的坐标保存为数据文件作为聚类算法的数据点输入。目标函数的距离度量都是采用平方距离总和。
3.2 仿真实验结果
4 个手工产生或随机数生成的二维数据点集，采用k-中心点轮换聚类法和混和聚类算法的实验比较结果表如表1 所示：
3.3 实验结果分析
这种混和聚类算法先采用 k-中心点轮换法来选择初始中心点集，然后利用k-means 聚类算法来对全部数据点集进行聚类。如果抽样率不超过某个阈值（小于k1 ），那么最终可以获得一种时间复杂度是(O(n2m) )的组合聚类算法，这也算是一种改进。从仿真实验可以看出，本组合聚类算法的实验结果还是比较稳定、聚类效果也还不错（当数据点集的分布不满足采用距离度量来作优化目标函数的一些聚类算法的基本要求时，聚类结果就不能保证了，如图7 就是一个例证）。仿真实验还表明，距离度量的合适选择对聚类结果也有一定的影响。
4．总结
每一种聚类方法都有各自的优点和缺点，所以有效地对一些能互相结合的聚类算法进行很好地融和，取长补短，从而构造出高效实用的聚类方法是可行的。在融和多种聚类算法的过程中，往往可以应用最优化方法来获得更有效的聚类方法。例如，本文的对原数据空间的最优网格划分就可以降低算法的时间复杂度，从而使这种混和聚类方法达到实用的程度。
