大规模数据集聚类方法及其应用研究

【摘要】基于labels集开展的大规模数据集聚类别，采用SSLOK算法并结合labels集调节聚类过程，这样以来，在有限的主存空间内调换半监督聚类，确保整个数据集聚类工作的实现。本文则对大规模数据集聚类方法和应用进行分析。

【关键词】大规模数据集;方法;应用

随着数据库技术的普及使用，其商业化使用需求越来越高，并且聚类数据集越来越庞大，在较大容量硬盘和磁盘阵列中储存，数据库没有全部读入主存聚类。功能强的Kmeans算法需要反复多次对硬盘中的数据集进行扫描，且每条数据记录在每一次更迭过程中需要被访问1次，整个聚类过程所花费的时间较短。为了彻底消除Kmeans算法面对大规模数据集时效率很低的问题，有关人员建议对原始数据集只用扫描一遍即可，产生了对聚类结果的算法，该算法只需读入大规模数据集内的少部分，使其进入主存数据集聚类，当扫描后即可形成聚类。

一、Kmeans算法的认识和应用

这种算法实质属于概率方法，也可称作“K均值算法”，是现阶段广泛应用的一种聚类算法。算法先随机选取k个对象，而每个对象初始代表一个簇的平均数值或者中心，针对余下每个对象按照其和各个簇中心距离，赋给最近簇，再计算出每个簇的平均数值。这是一个不断重复的过程，直至准则函授收敛，其中准则函数E=，E表示数据集中全部数据点的平方误差总和，x表示空间内的点，表示簇Ci的平均数值，相应的准则函数促使生成结果尽量保持独立、紧凑。

Kmeans算法作为解决聚类问题的经典算法之一，实现较简单，若处理大规模数据集，这种算法存在一定局限性但其有相对可伸缩性，效率较高。所以，大多数科研人员在研究对于大规模数据集的高效聚类算法时，第一选择为Kmeans算法，在计算过程中试着找出平均误差函数数值最小的K个划分，结果簇密集，当簇和簇之间存在明显差别时，算法效果很好，算法常常得出局部最优解。

二、PAM 算法的认识和应用

这种算法最早是由Kaufman相关研究人员提出的中心点划分聚类算法，用簇中位置接近中心对象当作代表，然后对N个对象进行K个划分，代表对象即为中心点，其他对象与中心点相对应是非代表对象。随意选取K个对象为中心点，反复利用非代表对象取代代表对象，然后找出更佳中心点，不断改进聚类质量。

当重新分配时，替换总代价函数TC对平方误差E=会产生一定影响。故若一个目前代表对象被非代表对象取代，则TC会将计算E导致的差别，替换总代价作为全部非中心对象形成的代价之和。若总代价TC是负的，则E将会减少，说明代替合理。若相反则不需代替，保持原中心点不改变。为了进一步判断一个非代表对象Oh，能否取代另一个代表对象Oi，针对每个非代表对象需考虑一下四种情形：1）当Oj当前归属于中心点对象Oi时，若Oi被Oh取代成为中心点，Oj距离另一中心点Om最近，且i≠m，则Oj被重新分配到Om，此时Cijh=d（j，m）-d（j，i）。2）当Oj当前属中心点对象Oi时，Oi被Oh取代成为中心点，但Oj距离另一中心点Oh最近，则Oj可能被重新分配Oh，此时Cijh=d（j，h）-d（j，i）。3）当Oj当前属中心点对象Om，并且m≠i时，Oi被Oh取代成为中心点，Oj距离Om较近，各个对象之间隶属关系不变，此时Cijh=0。4）当Oj当前属中心点对象Om，并且m≠i时，Oi被Oh取代成为中心点，Oj距离Oh较近，Oi被分配到Oh，此时Cijh=d（j，h）-d（j，m）。

三、SSLOK算法的认识和应用

根据标记集半监督一遍扫描K均值即SSLOK算法。该算法时用标记数据指导整个聚类过程的，能够提升大规模数据集的聚类效率，且得到的聚类结果质量高。将标记过的数据称为标记集，且集内的数据可确定类别属性，对整个聚类过程有良好的引导作用。

1）不同数据点集的压缩、丢弃，若SSLOK算法中内存系统执行聚类时，第一步对数据点集按照普通Kmeans方法进行聚类，将将形成聚类结果的主聚类MC进行标记、压缩、丢弃数据点集中MC内的数据集，清理出主要存储空间，方便二次读入的各种聚类数据聚类，直至所有聚类工作结束。在这个过程中将丢弃过程分成主丢弃与次丢弃，但在整个丢弃过程中不能改变聚类归属点离开主存储，进而存入丢弃数据集的特点。

用Labels标记集中的所有点参与该过程，更好地指导聚类行为。若某一个MC聚类系统内数据点集xm=（xn1，xn2，……xmn）p，其中m=1、2、……n，计算出聚类中心点，则u=，协方差距阵Sij=cov（xm，xj）=E[（xm-um））xj-uj）]得到数据点至聚类中心u的马氏距离是Dm（xm，u）=。

2）SSLOK大规模数据集聚类过程，首先从数据集内依据顺序阅读各数据点，当其进入管道以后，填满整个管道空间，对于管道中每个数据点，Labels进行有限主存系统的半监督，直至收敛，在系统化聚类实施过程中，SS所属关系可能出现改变，或产生新的SS，聚类过程如图1所示，New集如下图2所示。OUTS的从属关系不会发生改变，其始终从属相应的MC，用来累计记录聚类信息。在图1中，表示labels，SS是压缩后的替代点集，OUTS是移出主存点集，MC是最后聚类结果，其中的管道表示空间受限主存。

图1 SLOK聚类过程

四、实例分析

（一）测试人工生成数据集

该数据集主要通过流程依照K非高斯的分布情况随机出现的，每各高斯分布都是由一个随机权重决定能否产生数据。且高斯分布中心是随意形成的，其区域范围为[-5，5]，而数据点的各个维度数值区域范围为[0.7，1.5]，形成的原始数据集合中含有100维，并且采用linux文件进行保存。科学评价每一种算法导致的聚类质量，若聚类数量为2，观察各个聚类中心，比较算法的聚类质量。在一系列实验过程中有12个不同的人工生成数据集，假设管道主存上限数据为整个数据集的5%，并且用取得的平均数值评价算法聚类质量。

因为对于原始数据集实施随机采样，但无论何种方式采样都不可能表示全部原始数据，聚类结果可能会受到初始条件及原始数据分布情况的影响，导致聚类质量稳定性差。相比之下，Scalable-kmeans固然聚类质量高，但是这种算法对于初始化参数十分敏感，导致聚类质量较低，而SSLOK这种算法使用labels集合来调节聚类，很明显会提升聚类质量。Random-kmeas因为是5%采样，算法较简单，故运行时间很短，提高数据点所属种类计算，聚类过程收敛，进一步减少了聚类收敛时间，提高聚类效率。

（二）测试数据集

运用真实数据集测试算法，数据集可记录用户对邮件的反映情形。为了尽最大限度降低

原始数据对形成的聚类结果质量可能造成的坏影响，经过预处理后的数据集被二次按照随机排列的方法，排列（10～12）次，随后按照一定的算法进行运行，运行达到50次以后，若将聚类数目设置为10，管道主存上限设计成数据集的10%左右可以看到主存空间对形成的聚类结果的作用。

在本试验过程中，真正的数据集并不是实际聚类中心，故不用Distance To True Cluster Mean作为客观的评判标准，评价聚类结果质量情况，用非真实的数据集当作标准。由于其增加了采样数据点，可获得较好的聚类质量。并且SSLOK融合了半监督聚类的有关思想，并用labels当作集指导聚类，在原有基础上可提高聚类质量。且在算法执行效率方面也取得明显成效。再次测试labels标记集的质量对聚类结果产生的影响，证明之前检验所得结果。可知在labels标记集合中聚类信息越多，采用SSLOK算法得到的聚类结果质量越有保障。

五、结语

随着挖掘数据规模的增长，过去的聚类算法因需多次扫描原始数据适用性弱，目前一遍扫描原始数据集成为首要研究目标，但对于大规模数据集的算法极易受到初始化参数及原始数据分布的影响，聚类结果质量无保障，且不稳定，鉴于此，参照半监督类思想，提出依据标记集扫描K均值算法。这种算法主要运用驻留主存的标记集引导聚类过程，提高聚类效率与聚类结果质量。且实验结果表明SSLOK算法可大幅度提高大规模数据集聚类结果的质量，提高聚类过程收敛速度，及其执行效率。尽管SSLOK算法有一定的优点，但也存在不少问题，有待于进一步改进，需要在以后的研究过程中不断完善。

参考文献

[1]薛安荣，鞠时光.离群点挖掘方法综述[J].计机科学， 2008，35（11）：13-18.