蔡洪山 许峰

摘要：为了降低偶然因素的影响，提出了一种基于改进预测强度的大数据K-均值聚类方法，其基本思想是：首先将数据集若干等分，每一等分轮流作为测试集，取其平均预测强度，然后根据预测强度确定聚类数和聚类变量，再用K-均值聚类方法对数据集进行聚类。用上述方法研究了访客在某网站各栏目的平均停留时间，结果表明，基于预测强度的聚类方法较常规聚类方法更适宜于大数据的聚类分析。

关键词：大数据；K-均值聚类；预测强度；网站栏目关注度

DOIDOI：10.11907/rjdk.161106

中图分类号：TP301

文献标识码：A 文章编号：1672-7800（2016）005-0004-03

0 引言

聚类是数据挖掘中的重要问题，也是大数据分析的核心问题之一。K-均值聚类算法是一种应用非常广泛的聚类方法，由于此算法并不需要计算点之间的距离，因而对于大数据，K-均值聚类算法往往可以得到比其它聚类算法更快的收敛速度。但K-均值聚类算法有两个缺陷，一是需要事先确定聚类数，二是受初始聚类中心的影响较大。

近年来，许多学者从不同的角度对大数据K-均值聚类算法进行了研究。卞亦文[1]提出了一种基于黄金分割法的K-means聚类算法，该算法可在一定程度上自动确定聚类个数；陈丽敏等[2]提出了一种基于加速迭代的大数据集谱聚类算法；沈诗嫫[3]研究了初始聚类中心的选择问题，提出了一种基于小世界网络选取初始聚类中心的K-means聚类方法；陈思慧[4]提出了一种基于层次划分的大数据聚类算法；古凌岚[5]提出了一种基于数据集划分的大数据聚类方法；李雄[6]提出了一种并行化加权AP聚类算法，降低了算法的时间复杂度。

本文利用数据集等分思想，对基于预测强度的大数据K-均值聚类算法进行了改进，并通过实例对改进算法进行了性能测试。

1 基于BIC准则的模型分析

本文进行聚类分析的数据为某网站的后台数据，共有2 861行，15个变量。每一行代表一位网站访客，15个变量代表访客在网站的15个栏目上的平均停留时间。为方便起见，将15个栏目记为e1～e15。图1给出了访客在e1栏目上平均停留时间的频率直方图。

在进行聚类时，有许多聚类变量供选择，如何选择聚类变量称为模型的选择。选择模型时的准则通常有AIC准则（Akaike Information Criterion）、BIC准则（Bayesian Information Criterion）和HQ准则（Hannan-Quinn Criterion）。本文采用BIC准则，BIC随变量数即模型和聚类数变化曲线如图2所示。

从图2中可以看出：①随着聚类数的增加，BIC单调上升，并没有明显的单峰现象，这表明在本问题中，BIC准则对于聚类数的选择没有作用；②当聚类数大于4时，BIC增加得较为平稳，即聚类数的增加已经对模型的解释没有更大的贡献，这表明最优聚类数应该接近于4，但此方法并不能给出精确的取值。

预测强度计算过程如下：①将待聚类原始数据随机分成训练集和测试集；②取聚类数为k，对上述两个子集进行聚类，聚类结果记为I型聚类；③用训练集的聚类结果对测试集进行判别，结果记为II型聚类；④在测试集自身聚成的每个类中，考查任一对样本点i和i′是否在II型聚类中被错分在不同的类，并记录被正确划分的比例；⑤在上述k个比例构成中，最小者即为当前聚类数k下的预测强度。

显然，预测强度的直观含义是当前聚类结果能正确预测新样本点的能力。在实际中，可以预测强度为目标函数，以聚类数和变量子集为影响预测强度的因素，通过选择适当的聚类数和变量子集，使预测强度最大化。

2.2 改进的预测强度

在预测强度的计算过程中，因为训练集和测试集是随机划分的，所以某些偶然因素可能对预测强度的计算结果产生较大影响。为了降低偶然因素的影响，本文采用一种改进方法计算预测强度，具体做法为：首先将数据集随机分为若干等分，将每一等分轮流作为测试集，求出各自的预测强度后，再取其平均值为这一聚类数下的预测强度。

2.3 基于预测强度的模型分析结果

不同变量数和聚类数下的预测强度变化曲线如图3所示。

从图3（f）中可以看出，当聚类变量的个数为3时（变量子集为{e1，e2，e4}），整条预测强度曲线都维持在一个很高的水平上。特别地，当聚类数为4时，预测强度达到了全局最大值，这表明最优聚类方案是选取e1、e2、e4为聚类变量，聚类数为4。

3 聚类结果及分析

确定最优聚类方案后，即可利用K-均值聚类方法对原始数据进行聚类。4类访客在各栏目上的平均停留时间如图4所示。

从图4中可以看出，第一类访客几乎在所有栏目上的平均停留时间都较长，都超过其它3类，说明这类访客属该网站的高端忠实客户；第二类访客仅仅在第2、4栏目上的停留时间较长，表明这类访客属于专业访客，一般只对某几个特定栏目感兴趣，关注程度较高；第三类访客在每个栏目上的停留时间都不太长，且相差不大，表明这类访客属一般访客，对栏目没有特殊兴趣；第四类几乎在所有栏目上的停留时间都非常短，表明这类访客属典型的游客，对每个栏目都匆匆而过。由此可见，基于改进预测强度的K-均值聚类方法对实例中大数据的聚类结果是可信且有实际意义的。

4 结语

在K-均值聚类算法的基础上，引入了改进的预测强度，并以此确定聚类变量和聚类数。对网站栏目平均停留时间的聚类分析表明，这种改进的大数据聚类方法的聚类结果具有较为明确的实际意义，较常规聚类方法更适宜用来进行大数据的聚类分析。

需要指出的是，大数据聚类算法的理论基础还很薄弱，理论体系尚不完善，本文对新算法的性能研究也只能依赖于对具体实际问题的聚类分析结果，至于算法的收敛性和复杂度的理论分析则有待进一步研究。

参考文献：

[1]卞亦文.大样本数据聚类的改进方法[J].统计与决策，2009（1）：12-13.

[2]陈丽敏，杨静，张健沛.一种加速迭代的大数据集谱聚类方法[J].计算机科学，2012，39（5）：172-176.

[3]沈诗嫫.文本数据聚类算法的若干关键技术及应用研究[D].南宁：广西大学，2013.

[4]陈思慧.基于MIP和改进模糊K-means算法的大数据聚类设计[J].计算机测量与控制，2014，22（4）：1270-1275.

[5]古凌岚.面向大数据集的有效聚类算法[J].计算机工程与设计，2014，35（6）：2183-2187.

[6]李雄.面向大数据的数据挖掘算法研究[D].南京：南京邮电大学，2014.

[7]ROBERT TIBSHIRANI.Cluster validation by predication strength[J].2001.http：//citeseerx.ist.psu.edu/viewdoc/summary？ Doi=10.1.1.24.2960.

（责任编辑：孙 娟）

Abstract：In order to reduce the influence of accidental factor，a large data K-means clustering method based on improved prediction strength is put forward.The basic idea of method is that first data set is divided into equal parts，and each part is set up test set in turn.The average strength prediction is computed，and clustering number is determined according to the strength prediction，then K-means clustering method is applied for data set.By means of the above method，the average residence time of the visitors in a website is studied.The results show that the clustering method based on the prediction strength is more suitable for the cluster analysis of large data.

Key Words：Big Data；K-Means Clustering；Prediction Strength；Website Column Access Analysis