K-Means聚类法

K-Means聚类法（共7篇）

K-Means聚类法 篇1

随着互联网的兴起,网购正成为一种趋势和潮流,在人们的日常生活中占据越来越重要的位置。众所周知,大学生接受新事物能力强,能熟练使用互联网,因此大学生对于网购的接受程度比其他人群更高,现在的在校大学生将成为未来网购市场的主要组成部分。但是大学生网购常常会遇到不满意的情况,产生抱怨行为,若不能有效安抚抱怨者的情绪,其忠诚度会大打折扣。所以,电商必须了解大学生抱怨行为的类型和特点,采取有效的补救策略,消除他们的抱怨情绪。本文在借鉴前人研究成果和方法的基础上,主要以在校大学生为样本,研究他们在近年兴起的网购大潮中的抱怨行为类型。

1 文献回顾

1.1 顾客抱怨

顾客抱怨是指顾客对产品或服务的不满和责难,顾客对产品或服务的抱怨即意味着经营者提供的产品或服务没达到他的期望、没满足他的需求。另外,也表示顾客仍旧对经营者具有期待,希望能改善服务水平。其目的就是为了挽回经济上的损失,恢复自我形象。大致在20世纪70年代,由于受到消费至上主义的影响,西方学者就已经开始注意对顾客投诉行为的研究。直到现在,顾客抱怨领域总是能引起很多研究者的兴趣。通过对以往有关抱怨主题的研究文献进行收集整理,发现这一主题的研究成果逐渐成熟和完善。

1.2 网购抱怨行为

1999年年底,随着互联网高潮来临。中国网络购物的用户规模不断上升。2010年中国网络购物市场延续用户规模、交易规模的双增长态势。《2013—2017中国网络购物行业市场前瞻与投资预测分析报告》统计数据显示,2010年中国网络购物市场交易规模接近5000亿元,达4980.0亿元,占到社会消费品零售总额的3.2%;同时,网络购物用户规模达到1.48亿,在网民中的渗透率达30.8%。网购将成为未来发展的必然趋势,在人们的生活中占据十分重要的位置。不可否认的是网购的兴起和蓬勃发展为人们的生活带来很多的便利,同时本身也存在很多的问题:大量的假冒伪劣产品充斥着网购;诚信问题;配送的速度不一;退货不方便等。由于这些问题的存在使得网购的抱怨行为难以避免,同时,网购抱怨行为发生的频率更高,传播性更广,危害性也更大,不同于线下购买的顾客抱怨行为。网购抱怨行为是绝大多数电商必将面临的重要问题,具有十分重要的研究意义。

1.3 K-means聚类

聚类分析中常用的一种聚类算法是1967年Mac Queen提出的基于误差平方和准则的K-均值算法,该算法因具有简单且容易理解,计算方便、速度快以及能够有效处理大型数据库的优点而成为聚类分析中的经典算法。K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。

2 研究方法

2.1 研究对象及数据收集

本文以有网上购物经历的在校大学生为研究对象。2008年6月发布的《中国网络购物报告》显示网购用户中学历是大专及以上的用户比例已高达85%。其中大专和本科学历的用户占75%,也就是说,在校的本科、专科大学生将成为未来网购市场的主要组成部分。从2012年来看,在校大学生网购用户占总体网购用户的3成,亚马逊网和拍拍网用户群体中在校大学生比例超过4成。目前,在校大学生的网购人数有增无减。由此可见,在校大学生已经在现在的网购的市场中占据不可忽略的位置,也必将在未来的网购市场中占据十分重要的位置,因此本文选择在校大学生为研究对象。向某高校的大学生随机发放问卷,共发放了150份,回收136份,有效问卷125份。

2.2 变量测量

本文采用了Likert 5分量表法,它是由美国社会心理学家李克特于1932年在原有的总加量表基础上改进而成的。该量表由一组陈述组成,每一陈述有“非常同意”“同意”“不一定”“不同意”“非常不同意”五种回答,分别记为5、4、3、2、1,每个被调查者的态度总分就是他对各道题的回答所得分数的加总,总分的高低说明了消费者的态度强弱。在参考相关文献的基础上,本研究中涉及的变量及测项如表1所示。

3 数据分析与结果

整理问卷数据并录入,运用SPSS软件进行K-means聚类运算。得到表2、表3、表4,如下:

利用方差分析可以判断所分的类别是否合理。由表2可以看出,分类后各变量在不同类别之间的差异都是显著的,P值均小于0.05,说明分类比较合理。

表3数据表示各类别在各变量上的平均值,比如:2.82就表示第一类在变量V1上的平均值。可以看出,大学生网上购物抱怨行为共分为3类。

第一类在变量V2、V7上的平均值较大,在其他变量上的平均值较小。根据V2和V7描述的特点,把这类抱怨行为定义为“传播型抱怨者”。

第二类在变量V1、V5上的平均值较大,在其他变量上的平均值偏小,我们可以把这种期望通过抱怨获得一定补偿的行为定义为“效用型抱怨者”。

第三类在变量V3、V4、V6上的平均值较大,而在其他变量上的平均值较小。根据这三个变量描述的特点,把这类抱怨者命名为“沉默型抱怨者”。

由表4可知,第一类“传播型抱怨者”含33个样本,占总样本(125个)的26.4%;第二类“效用型抱怨者”含27个样本,占总样本的21.6%;第三类“沉默型抱怨者”含65个样本,占总样本的52%,显然沉默型抱怨者占绝大部分。

4 管理启示

通过对以上数据分析与结果的思考,得出以下管理启示:

第一类“传播型抱怨者”仅占了26.4%的比例,但对电商的声誉会造成很大影响。他们会向周围的人或通过社交媒体传播负面口碑,并转向其他竞争者。电商可以采取以下补救措施:培养与顾客的关系,牢固的关系是电商发生严重失误时的缓冲剂,可以降低消极口碑出现的可能性;从流失的顾客身上学习,发现自身的不足之处,避免以后再出现同样的失误。

第二类“效用型抱怨者”对抱怨产生的结果抱有积极的预期,不会轻易选择转向其他电商。建议电商采取以下措施:首先了解抱怨者抱怨的原因及对补救结果的最高期望和最低期望。其次补救结果不能低于其最低期望,否则“效用型抱怨者”将转为“传播型抱怨者”或“沉默型抱怨者”。

第三类“沉默型抱怨者”是大学生网购抱怨群体的主流,也是电商应给予重点关注的群体。这类抱怨者具有以下特点:保持沉默,很少采取行动,不太可能进行负面口碑传播,更不会向第三方投诉,只是会吸取经验教训,默默转向其他电商。针对这类抱怨者,电商可以采取如下补救措施:一开始就把事情做好,这是最佳的补救策略。如果大学生一开始就对网购很满意,自然就没有抱怨,不会转换电商;鼓励并跟踪抱怨,鼓励抱怨是打破沉默、促使大学生直接向电商抱怨的有效办法,电商可以通过大学生网购满意度调查、关键事件研究等来鼓励和跟踪抱怨。

5 结论

对大学生网购抱怨行为进行K-means聚类分析有利于电商深入了解大学生抱怨行为的内在特点,大学生抱怨行为的类型及各抱怨类型所占比例,并根据不同的抱怨类型有针对性地采取相应的补救策略,加强补救的效果,维持和提高大学生对电商的认可度和忠诚度。

摘要：文章运用聚类分析中的K-means聚类法对在校大学生网购抱怨行为进行聚类分析。研究发现,大学生网购抱怨类型可以分为传播型抱怨者、效用型抱怨者和沉默型抱怨者,不同类型的抱怨者各有其特点,这就要求电商应根据不同的抱怨类型的特点采取相应的补救策略,以保持和提高大学生网购的忠诚度。

关键词：抱怨行为,K-means聚类分析,补救策略

参考文献

[1]刘靖明,韩丽川,候立文.基于粒子群的K均值聚类算法[J].系统工程理论与实践,2005(6):54-58.

[2]杨善林,李永森,胡笑旋,等.K-means算法中的K值优化问题研究[J].系统工程理论与实践,2006(2):97-101.

[3]刘艳丽,刘希玉.K-均值算法聚类分析及其在人力资源管理中的应用[J].山东科学,2008(4).

[4]赵喜仓,崔冬梅,窦志红.聚类分析在客户细分中的研究与应用[J].江苏商论,2007(8).

[5]郭志刚.社会统计分析方法——SPSS软件应用[M].北京:中国人民大学出版社,1999.

[6]金立印.顾客抱怨倾向的决定因素:模型及基于中国零售业的实证检验[J].南开管理评论,2007,10(1):38-43.

[7]朱美艳,庄贵军,刘周平.顾客投诉行为的理论回顾[J].山东社会科学,2006(11):137-144.

[8]薄湘平,周琴.服务补救:重建顾客满意的重要手段[J].湖南大学学报:社会科学版,2005(1).

[9]李克芳,聂元昆.服务营销学[M].北京:机械工业出版社,2012.

K-Means聚类法 篇2

基于K-means聚类思想，采用改进的形态学方法对红外图像进行预处理，然后采用基于二维梯度信息的K-means聚类算法，完成对红外图像中典型目标的检测。

1 Top-Hat算子预处理

形态学是一种非线性滤波，应用于图像和模式识别领域，其理论基础深，综合了多门学科知识，但其原理却比较简单，主要体现逻辑推理和严谨的数学演绎。设f(x,y)为输入图像；b(x,y)为结构元素；其中，(x,y)为图像平面空间的坐标点；f为(x,y)点的灰度值；b为(x,y)的结构函数值；Df和Db分别是f和b的定义域，则定义如下运算[11]

(1）膨胀

其中，[(s-x,t-y)]∈Df;(x,y)∈Db。

(2）腐蚀

其中，[(s+x,t+y)]∈Df;(x,y)∈Db。

(3）开运算

(4）闭运算

Top-Hat算子具有高通滤波的某些特性，开运算可以检测出图像中的峰，闭运算则能检测出图像中的谷。形态学Top-Hat算子能有效地识别出各种背景下的点目标，但是对于有较强背景噪声干扰的点目标图像，传统的Top-Hat算子的抑制效果不佳。为此，有学者提出修正的Top-Hat形态学滤波算子。修正Top-Hat形态学滤波器结构元由两部分组成：内部结构元C1（大小为n×n）和外部结构元C2（大小为m×m），即C1⊆C2。定义边缘结构元为A=C2-C1，在此基础上定义改进的Top-Hat算子为

改进的Top-Hat形态学滤波器能更好的抑制噪声影响。

2 改进的K-means聚类

K-means聚类是基于图像中目标和背景的灰度差异以及目标自身灰度的相似性进行分割检测，其聚类的基础是依据不同的属性进行分类，进而将具有相似属性的像素聚为同一类别。

2.1 二维梯度属性建立

经过预处理的红外图像，目标与背景的噪声得到抑制，对比度有了一定程度的增强，遍历图像中的每一像素点，分别计算图像行方向及列方向的梯度，得到每一像素点的二维梯度信息

其中，代表行方向上梯度信息；代表列方向上梯度信息；a,b代表梯度数值大小；（i,j）表征位置信息。将处于相同位置上的行向及列向梯度向量相加，即得到当前像素点的真实梯度特征为

这样得到梯度特征，表征当前点梯度信息，其模值代表梯度值大小。

2.2 梯度属性阈值预处理

二维梯度属性图中，梯度较大的像素点所在位置可认为是目标与背景的交界处，这些属性点组成了红外目标的边缘。而背景及目标内部，由于灰度值相差不大，其梯度属性要比边缘点小得多，为提高聚类效率，可选取合适的阈值TH，对梯度属性图进行处理，如下式

初始中心点的选择在K-means聚类算法中极其重要，为使各类像素点具有一定的区分度，通常寻找散布较大的点作为初始中心点。传统的K-means聚类算法是随机选取初始中心点，文中为了更好地进行红外目标分割，对在阈值和最大梯度模值之间的数值进行均分为

式中，将梯度属性图分成k类；μ（s）是第s类的中心值；max是最大梯度模值；TH为选定的阈值。

具体实现步骤如下：

(1）根据式（9）选取k个初始梯度模值均值

μ1(1）,μ2(2）,…,μk(k）。

(2）在第i次迭代时，根据如下准则将每个梯度模值都赋予k类之一（j=1,2，…，k,l=1,2，…，k,j≠l）；若

即将每个梯度模值赋予与它最相似的梯度模均值类。

(3）若对于j=1,2，…，k，有更新类梯度模均值

(4）如果对所有的j=1,2，…，k，有μ1(n+1）=μ1(n），则算法结束；否则进入步骤（2）继续下一次迭代。

3 实验结果与分析

为验证本算法对红外目标检测的效果，对实际拍摄得到的大视场红外图像进行处理，并与传统算法进行对比，结果如图1所示。其中，图1a为原始红外图像，图1b为K均值聚类处理结果，图1c为SUN-SAN算子处理结果[12]，图1d为文中算法处理结果。

原始红外图像中，主要是以天空、树木和路面为背景，以人为典型目标的图像。K均值聚类方法处理时，将部分树木和路面聚为一类，没有很好地突出树林中的目标。使用SUNSAN算子进行处理，虽然检测出目标，但处理结果中含有大量噪声点。文中算法的处理结果图中，很好地检测出目标，且较好地剔除了噪声点的影响。

为了对检测结果进行更好的评价，采用目标检测领域标准通用的几个评价指标进行客观评价，包括信噪比增益（ISNR)[13]，对比度增益（ISCR）和运行时间。ISNR和ISCR越大，说明算法抑制背景杂波和凸显目标的能力越强，各指标定义如下[1]

其中，SNRin、SNRout分别代表原始图像和处理后图像的信噪比；SCRin、SCRout分别代表原始图像和处理后图像的标准差。具体结果如表1所示。

可以看出，文中算法相较于其他两种算法，计算方便，运行时间短，并且对背景抑制作用明显，能更好的检测出目标。

4 结论

K-Means聚类法 篇3

聚类就是对数据集中的数据分组, 使得组内数据具有高度的相似性, 而组间的数据有较大的相异性。聚类分析是一种重要的数据分析方法, 广泛应用于数据挖掘、模式识别、机器学习等领域。

K-means算法是一种简单快速的聚类算法。在文本聚类领域, K-means聚类算法已经成为一种基本算法[1]。

Weka (Waikato Environment for Knowledge Analysis) 是一款开源的基于Java语言的机器学习和数据挖掘软件[2], 由新西兰Waikato大学开发。以Weka平台为基础, 分析了K-means算法在文档聚类中的应用, 在Weka平台实现文档聚类。首先用文档向量空间模型[3]表示文档, 对Web文档进行数量化的描述。在文档向量化的过程中, 特征词的选取至关重要, 前人在这方面做了一些研究工作。研究表明[4], 特征词过多导致高维数据, 不仅增大了空间开销, 还加重机器学习的负担, 特征词过少, 影响聚类的效果。最后利用Weka平台中对Web文档进行聚类测试。实验结果表明K-means聚类算法对Web文档聚类有较好的效果。

2 K-means 算法

2.1 算法思想

1967年Macqueen提出了K-means算法[10], 基本思想是把数据集中的数据点随机生成k组, 把每组的均值作为中心点。重新计算每个数据点与各组的中心点的相似性, 根据数据点相似性的度量准则, 把每个数据点重新分组, 计算每组新的均值作为中心点。不断重复上述过程, 直到中心点的均值收敛, 停止迭代过程。

K-means算法是一种比较快速的聚类方法 , 时间复杂度为O ( nkt ), 其中n是数据点的数目, k是分组数目, t是迭代次数。K-means算法也存在不足, 最大问题要指定分组数目并且在运行过程中容易导致局部最优。

2.2 算法在文档聚类中的应用

K-means算法在不同的领域都有成功的运用。运用K- means算法进行文档聚类 , 首先需要对文档建立文档表示模型, VSM (vector space model) 模型是一种常用的文档表示模型。VSM模型用向量表示文档, 文档转换成向量数据, 可以利用K-means算法实现文档聚类。算法流程如下:

输入: 文档向量集D= {d1, d2, …, dn}, 聚类个数k

输出: k个聚类

s1: 从文档向量集D中随机取k个向量作为k个聚类的中心点C1, C2, …, Ck。

s2: 遍历文档向量集D中的向量di, 计算di与Cj(j=1, 2, …, k) 的相似度, 把di重新分配到最相似的组。

s3: 根据s2得到新的k个聚类 , 重新计算每个聚类中的向量的均值作为中心点C1, C2, …, Ck。

s4: 比较聚类的中心点。

s5: 如果中心点位置不再变化, 则停止迭代; 否则, 转入s2。

算法中需要建立文档相似性函数和聚类效果评价函数。文档的相似性表征了文档之间的相关程度。度量文档的相似性普遍采用两类方法, 一种是基于距离的度量方法, 一种是基于相似系数的度量方法[9]。基于距离的度量方法包括欧式距离、曼哈顿距离、 明考斯基距离。基于相似系数的度量方法包括余弦相似系数、Jaccard系数。在文档聚类中, 通常采用余弦相似系数作为文档相似的度量值, 公式如下:

公式中di表示聚类中第i个文档向量, di,k表示向量di中的第k个分量。计算值越大, 文档相似度越高。

聚类效果评价函数通常采用平方误差和, 公式如下:

公式中Si表示第i个聚类, di表示聚类Si中的向量, ci表示聚类Si的均值。函数值越小, 表明聚类内部越紧密。

3 基于 Weka 平台的 K-means 聚类

K-means算法可以用来实现Web文档的聚类。Weka平台实现了包括K-means算法在内的一些聚类算法。利用Weka平台实现文档聚类只需要做一些文档的前端处理工作, 生成指定格式的文件, 再调用Weka中的K-means算法, 即可以完成文档的聚类分析。文档的前端处理工作包括文档分词化、去停用词、 生成文档集词语表, 根据词语表统计每篇文档的词频, 建立词频矩阵; 选择特征词生成特征向量; 对每篇文档计算特征词的权重, 完成文档的向量化。具体流程如图1所示。

3.1 文档预处理

文档预处理包括文档分词化、去掉停用词、生成词频矩阵。 首先对文档分词化, 分词软件采用中科院张华平老师开发的NLPIR汉语分词系统 (又名ICTCLAS2014版)[11]。所有的文档被切分成词语, 去掉对聚类分析无意义的停用词。停用词采用哈工大停用词表。在去停用词过程中, 把单字词全部作为停用词处理。经过分词、去停用词处理后, 得到文档集词表。

词频是指词语在一篇文档中出现的次数。对文档集中的每篇文档的进行统计, 统计文档集词表中的词语在每篇文档中的出现次数, 得到一个词频矩阵。

3.2 特征选择

K-means聚类属于无监督的机器学习, 由于事先不知道类别的信息, 文档的特征词只能采用无监督的特征选择算法。常见的无监督的特征选择算法包括3种[5], 文档频数 (docu- ment frequency, DF) , 单词权 ( term strength, TS) , 单词熵 (entropy-based feature ranking, EN)。

文档频数 (document frequency, DF), 词语的文档频数是指文档集中包含该词的文档数。文档频数的假设前提是, 出现次数过多或过少的词语对区分类别没有贡献, 删除这些词语可能有助于提高聚类结果。该算法时间复杂度O ( n ), 适合海量数据处理。在实际应用中, 文档频数的上限值和下限值的设定没有可靠的理论依据, 可以根据实验结果做调整。

单词权 (term strength, TS) 该方法的理论假设是, 词语在相关的文本中出现的频率越高, 在不相关的文本中出现的频率越低, 该词的对类别区分越重要。单词权的计算不依赖类信息, 适合用于无监督的文本聚类。计算单词权, 首先必须计算所有文本对之间的相似度, 该算法的时间复杂度较高, 至少是O (n2)。

单词熵 (entropy-based feature ranking, EN) 是专门用于聚类问题的特征选择方法。该方法的理论假设是, 不同的词语对数据的结构或分布的影响是不同的, 单词越重要对数据的结构影响也就越大, 不重要的词语对数据的结构几乎没有贡献。词语熵的时间复杂度为O (mn2), 不适合海量数据的处理。

在第4节的实验中, 采用文档频数 (DF) 方法选择特征词。根据第3.1中的词频矩阵, 把文档集词表中的高频词和低频词删除掉, 得到文档集的特征词向量。

3.3 文档向量化

VSM模型是G.Soltn等在1975年提出来的一种文档表示模型, 最先用在文档检索的过程中。VSM模型可以运用到文档聚类领域里, 设D是文档集合, 对于dj∈D, 则文档dj可以用向量表示成:

公式中wi,j表示第i个特征词在第j篇文档中的权重。通过计算向量之间的相似度就可以判断文档是否属于同一类别。

建立向量模型的要点是在特征词的选取和特征词权重的计算。特征词权重的计算最基本的模型是TF-IDF (term fre- quency-inverse document frequency) 模型[12]。

TF表示某个特征词在某篇文档中出现的次数。计算公式 如下:

公式中ni,j表示第i个特征词在第j篇文档中的出现次数, 而分母则是在第j篇文档中所有特征词的出现次数之和。

IDF是一个特征词普遍重要性的度量。计算公式如下:

公式中N表示文档总数, ni表示是包含特征词i的文档数量。特征词权重wi,j计算公式如下:

利用3.2节中所选的特征词向量、3.1节中的词频矩阵和本节的公式 (5), 对文档集合D中的每篇文档计算特征词向量的权重, 完成文档的向量化, 所有的文档形成一个向量集。

3.4 调用 Weka 中的 K-means 算法

Weka平台已经实现了一些基本的聚类算法 , 其中包括K-means算法。利用Weka平台完成文档聚类, 要求把文档向量集写成arff (Attribute-Relation File Format) 格式的文件, 作为Weka的输入数据。关于arff格式的规范, 在Weka的联机文档和官方网站都详细的介绍。把文档向量集转换成arff格式文件后, 把生成的arff格式文件加载到Weka平台, 利用平台的可视化界面, 按聚类过程操作步骤, 设置聚类的类别数目和种子数目, 完成文档的聚类分析。通过调用Weka的vi- sulize cluster assignments功能 , 图形化地观察聚类结果 , 然后保存聚类结果, 以便程序分析文档的聚类效果。在利用Weka完成聚类分析时, 也可以在Java语言编写的程序中直接调用Weka软件包中相关类, 得到聚类结果。

4 实验与结果分析

在文档聚类分析中, 查准率和查全率是对聚类效果进行评价的最基本的最常用的指标。查准率和查全率的计算公式如下:

公式中ni表示聚类后形成的第i个聚类中与类别相关的文档数目, Si表示聚类后形成的第i个聚类中的全部文档数目, Ni表示第i个聚类中与类别相关的全部文档数目。

实验中, 使用搜狗语料库的精简版作为测试数据来源。搜狗语料库是搜狗实验室从因特网搜集的文档, 进行人工分类后的文档集, 从精简版选择了5大类, 每类50篇文章, 作为测试数据集, 对每篇文章的文件名作了类别标注, 以便程序计算实验结果查准率和查全率。

测试步骤如下:

(1) 生成arff格式的文件。

(2) 在Weka中进行聚类分析, 保存分析结果。

(3) 计算分析结果的查准率、查全率。

测试过程中, 开始设定种子数为10, 聚类数为5。反复测试了6次, 每次测试种子数增加1, 每次测试结果不一样。在Weka平台, 以平方误差和 (sum of squared errors) 作为聚类评价指标, 该值越小表明聚类效果越好。选取平方误差和最小的一次, 实验结果如表1所示。

实验数据表明K-means算法在Web文档聚类中具有较好的聚类效果。6次测试中每次结果不一样, 表明聚类的结果不稳定, 与种子的数目和选择有关, 但实验数据上也没有呈现出种子数目越多平方误差和越小的趋势。为了到达较好的聚类效果, 需要反复测试几次, 选取平方误差和最小的一次作为实验结果。

5 结语

K-Means聚类法 篇4

文本聚类作为文本处理领域非常重要的组成部分,可以为自然语言处理、信息检索、搜索引擎和问答系统等领域提供基础支撑,文本聚类已经在当前的文本挖掘领域领域占据着非常的重要的地位。信息检索和搜索引擎系统通过对数据库中无类别文本进行聚类操作将文本转换为规则化可处理文本,问答系统需要对短文本进行聚类操作,将文本转换为有价值的结构化数据,文本聚类具有非常重要的现实意义。

文本聚类主要是依据著名的聚类假设:同类的文档相似度较大,而不同类的文档相似度较小。作为一种无监督的机器学习方法,聚类由于不需要训练过程,以及不需要预先对文档手工标注类别,因此具有一定的灵活性和较高的自动化处理能力,已经成为对文本信息进行有效地组织、摘要和导航的重要手段,为越来越多的研究人员所关注。

2 文本聚类

文本聚类表示将大量的无类别文本按照一定的规则将内容相似的文本划分为同一类别的过程。文本聚类涉及对文本的预处理操作,包括文本分词,文本关键词权重计算,文本表示和文本相似度计算。下面将针对每个过程进行逐条陈述。

2.1 文本分词

中文分词(Chinese Word Segmentation)指的是将一个汉字序列切分成一个一个单独的词。中文分词是文本挖掘的基础,对于输入的一段中文,成功地进行中文分词,可以达到电脑自动识别语句含义的效果。目前比较常用和实用的主要有最大匹配法(The MaximumMatching Method,MM)、反向最大匹配法(The Reverse Direction Maximum Matching Method,RMM)、二次扫描法、联想一回溯法、基于词频统计的分词法,以及基于知识的专家系统方法、神经网络方法等。中文句子的切分方法不是唯一的,主要原因就是歧义字段的存在。目前中文分词工二具比较经典的是IKAanalyer工具和中科院ICT-CLAS工具,IKAanalyer是最早来源于Lucence项目,最后独立出来经过不断的改善从而使得更适用于中文的分词;相比而言,ICTCLAS对于中文分词而言更加专业,ICTCLAS采用最大熵的切分方法,同时支持对文本进行词性标注,词性标注采用隐马尔科夫模型实现,相对于IKAanalyer工具,ICTCLAS工具分词的准确率高,且功能更加完备,但部署较为麻烦。

2.2 关键词权重计算

TF-IDF (term frequency-inverse document frequency)是一种用于信息搜索和信息挖掘的常用加权技术。在搜索、文献分类和其他相关领域有广泛的应用。

在一份给定的文件里,词频(term frequency,TF)指的是某一个给定的词语在该文件中出现的次数。这个数字通常会被归一化,以防止它偏向长的文件。(同一个词语在长文件里可能会比短文件有更高的词频,而不管该词语重要与否。)逆向文件频率(inverse document frequency,IDF)是一个词语普遍重要性的度量。某一特定词语的IDF,可以由总文件数目除以包含该词语之文件的数目,再将得到的商取对数得到。某一特定文件内的高词语频率,以及该词语在整个文件集合中的低文件频率,可以产生出高权重的TF-IDF。因此,TF-IDF倾向于过滤掉常见的词语,保留重要的词语。

使用TF*IDF可以计算某个关键字在某篇文章里面的重要性,因而识别这篇文章的主要含义,实现计算机读懂文章的功能。TF-IDF算法的量化表示如公式1所示。

在公式1中,Ct表示关键词在当前文本中出现的次数,nt表示该关键词在整个文本集中出现的次数,表示该关键词在整个文本集中出现的次数越频繁,表明该关键词对整个文本的表征能力越差,对该比值取对数的目的是为了进行数据平滑,0.01的目的防止N=nt时出现关键词权值为零的情况。从该公式上也可以反映TF-IDF算法能够实现对文本中特征项提取从而完成文本的区分。

除了TF-IDF方法,还有很多经典的关键词计算方法,诸如卡方统计(CHI)算法、信息增益(IG)算法等。其中卡方统计算法是讲关键词根据分类特性进行拆分,将关键词归于该分类和不归于该分类的数量进行统计,从而根据不同分类的数量进行差值计算得到关键词的权值,信息增益则是目前认为最能表征文本关键词权值的算法,但是在实际运作中存在着诸多不足之处,主要在于计算量过于判断和文本关键词稀疏的问题,信息增益表示该关键词存在于该类别和不存在于该类别对整个分类结果的影响程度,单纯从定义即可反映该算法的精确性。

2.3 文本表示

文本表示的方式主要采用向量空间模型,向量空间模型假设文本中各个关键词之间是相互独立的关系,如此,可以将文本表示为向量的形式,向量中每个维度通过关键词加以填充,关键词之间是相互独立的关系,预示着向量中各个维度之间是相互正交的关系,如此将抽象的文本资源转换为可以形式化表示的向量形式,从而实现文本之间的比较和其他操作。

向量空间模型是一种比较经典的文本表示模型,除此之外,还有诸如概率模型,布尔模型和语言模型等。值得一提的是布尔模型曾是非常重要的文本表示模型,并且对后来诸如模型的发展起到了非常重要的作用。布尔模型假设关键词在文本中出现则记为1,关键词未出现则记为0,如此可将关键词是否在文本中出现进行形式化表示。现如今流行的向量空间模型和概率模型等多种模型中都是布尔模型的基础上加以修正完善而成。

2.4 文本相似度计算

文本相似度计算是指通过一定的策略用以比较文本之间相似程度,文本相似度计算具有非常重要的应用,常用的方法是采用余弦相似度来表征文本之间的相似程度,余弦相似度通过将文本表示为向量的形式,通过比较两个文本向量之间的向量夹角来反映文本之间的相似程度,夹角越大,说明文本之间的含义偏离越大,反之,两个文本之间含义越接近。

将文本表示为向量的形式,通过文本集合和词项集合构建二维矩阵的形式,具体方式如下所示:

针对两个文本向量,以余弦法计算相似度为例,通过比较两个文本向量之间的夹角来定义文本之间的相似程度,如图1所示。

假设文本D1和文本D2的向量化可以表示为D1=(w11,w12,…w1n)和D2=(w21,w22,…,w2n),则文本D1和文本D2之间的相似度可可表示为公式2所示。

文本之间的相似度比较除了利用经典的余弦相似度外,还有其他的相似度比较方法,诸如采用Jaccard相似度,最小哈希和最小哈希签名等。集合之间的Jaccard相似度等于交集大小与并集大小的比例。适合的应用包括文档文本相似度以及顾客购物习惯的相似度计算等。集合上的最小哈希函数基于全集上的排序转换来定义。给定任意一个排列转换,集合的最小哈希值为在排列转换次序下出现的第一个集合元素。以选出多个排列转换,然后在每个排列转换下计算集合的最小哈希值,这些最小哈希值序列构成集合的最小哈希签名。给定两个集合,产生相同哈希值的排列转换所占的期望比率正好等于集合之间的Jaccard相似度。

2.5 文本聚类

文本聚类针对最初文本的预处理等步骤进行最终的聚类操作,K-means聚类算法处理流程为:首先从n个数据对象任意选择k个对象作为初始聚类中心;而对于所剩下其他对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。k个聚类具有以下特点:各聚类本身尽可能地紧凑,而各聚类之间尽可能地分开。

算法流程如下:

(1)从c个数据对象任意选择k个对象作为初始聚类中心。

(2)循环3到4直到每个聚类不再发生变化为止。

(3)根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分。

(4)重新计算每个(有变化)聚类的均值(中心对象)。

整个的算法流程用伪代码表示如下:

3 结语

描述了当前文本聚类的应用领域,文本聚类已经文本挖掘领域占据着非常重要的地位,针对文本聚类的相关步骤进行论述,包括文本的分词操作、文本关键词权重计算,文本表示和文本相似度计算等。最后结合文本的预处理操作,给出文本聚类的理论支撑和算法流程。

摘要：K-means算法是数据挖掘中非常经典的算法。通过数据之间内在关联性将同类数据组合在一起,这对于大量混乱的数据进行资源整合具有非常重要的意义。就K-means聚类算法在文本处理领域的应用展开研究,分析在文本聚类过程中数据的处理流程,涉及文本中特征项的选取、文本的预处理操作、文本的结构化表示和文本之间相似度计算等步骤。

关键词：K-means算法,文本聚类,文本预处理

参考文献

[1]邱云飞,王琳颍,邵良杉,郭红梅.基于微博短文本的用户兴趣建模方法[J].计算机工程,2014,02:275—279.

[2]邓三鸿,万接喜,王昊,刘喜文.基于特征翻译和潜在语义标引的跨语言文本聚类实验分析[J].现代图书情报技术,2014,01:28—35.

[3]孙玲芳,周加波,徐会,许锋,侯志鲁.基于改进K—means的网络舆情热点事件发现技术[J].计算机与现代化,2014,04:143—147.

K-Means聚类法 篇5

目前针对网络流量异常检测的研究已有很多, 研究者根据异常可能引起不同特征的变化, 提出了不同的检测方法, 如文献[1]从数据流中提取服务请求, 根据服务请求的三个属性:请求类型、请求长度和负载分布计算异常得分;文献[2, 3]利用网络流量异常会引起数据包头部特征 (源/目的IP、源/目的端口等) 的分布发生显著变化, 引入特征熵作为异常检测的数据源。这些方法虽然采用了多个特征以提高检测率, 但是没有融合多个特征进行综合评判, 仅采用简单的选举法或简单的特征组合公式, 而没有任何理论依据。文献[4]基于D-S理论融合多个特征对网络流量进行综合评判, 有效地降低了误报率和漏报率。文献[5]提出了基于聚类的异常检测框架, 首先对训练数据集进行划分, 生成n个簇类, 并根据簇类的大小标记"正常簇"或"异常簇", 然后利用已标志的簇将网络数据划分到距离最近的簇中。文献[6]在文献[5]的基础上提出一种新的方法计算类簇的半径阈值, 并且根据每个类簇偏离整体的程度来区分正常簇和异常簇。

上述方法有些使用多个特征以加大检测范围, 但是没有融合多个特征进行综合评判;聚类算法虽然可以处理多维数据, 但是应用在网络异常检测中存在一些缺陷。针对以上问题, 本文试图采用能从多个角度反映网络流量状态的特征以检测到更多的异常;为了能够融合各维特征的检测信息, 降低误报率, 将各维特征排列成检测向量, 采用由K-means聚类算法产生的检测模型对各维特征进行综合判断。其中, 为了使K-means聚类算法能够保证在实时动态变化的网络流量中检测的准确性, 利用滑动窗口机制计算各维特征的局部均值偏差, 使其能够体现各维特征当前的异常程度。

2 异常流量特征分析

在网络异常检测的特征选择问题上已有学者进行了深入研究, 有些方法[2,3,7]重点关注数据包头部特征 (源/目的IP, 源/目的端口号等) ;有些方法[1,8]使用了数据包应用负载中的特征进行检测, 虽然利用这些特征有助于提高检测率, 但由于应用负载的数据量过大, 使用这些特征往往导致检测算法不能满足高速网络的检测需求。因此应该选择计算量小, 能从多个不同的角度反映网络流量状态的特征。本文重点关注的维度有:源/目的IP、源/目的端口、协议类型以及TCP协议的标志位等。

相关研究[3]表明, 正常情况下, 在给定的时间粒度内, 不同的源/目的IP地址数和不同的源/目的端口数相对稳定, 并且他们之间存在一定的内在关联;当发生异常时, 它们之间的关联将会被打破。文献[3]利用Hellinger距离衡量每个时间窗口内各特征的分布变化, 本文对其本质进行分析, 发现它衡量的是源/目的IP地址数, 源/目的端口数的比例关系是否发生变化, 于是本文将IP维和端口维的测度定义如下:

定义1Dsip, Ddip分别为单位时间内不同的源IP地址数目, 目的IP地址数目, 则Dsip, Ddip之间的比例关系为

定义2Dspt, Ddpt分别为单位时间内不同的源端口号数目, 目的端口号数目, 则Dspt, Ddpt之间的比例关系为

利用Hip和Hport可以检测到能够引起源/目的IP地址数或源/目的端口数发生大幅度变化的异常, 例如, DDo S、蠕虫、端口扫描等;但是它们没有考虑数据包的多少, 因此对各特征元素个数变化不大但是会引起流量突变的异常无能为力, 例如, 某个主机突然向另一主机发送大量的数据包。为了弥补此缺陷, 需要引入其他测度。

Moore等人通过对被攻击者发送的响应包进行分析得出:大多数攻击使用TCP包 (94%以上) , 其次是UDP包 (2%) 和ICMP包 (2%) [9], 也就是说大多数情况下如果发生攻击, TCP、UDP、ICMP包中至少有一种会发生异常。而TCP, UDP和ICMP报文在网络流量中的分布具有很强的规律性。因此可以使用TCP、UDP、ICMP包的比例关系来描述网络运行情况。若发生基于UDP或ICMP协议的洪流攻击, 不同协议报文的分布即会发生明显变化, 但由于TCP报文一般在网络流量中占有较高比例, 发生基于TCP的攻击时, 3种数据包的比例关系与正常情况下基本上是相同的, 因而检测不出基于TCP的攻击[10]。考虑到基于TCP的攻击通常会引起SYN报文和SYN+ACK报文的数量不匹配[1], 因此将SYN/SYN+ACK报文的对称性作为检测基于TCP攻击的测度。如上所述, 协议维和TCP标志位维的检测测度定义如下:

定义3设PTCP, PIP分别表示在单位时间内TCP报文和IP报文的统计数, 则TCP报文所占比例为

定义4设PSYN, PSYN+ACK分别为单位时间内SYN和SYN+ACK的报文数, 则SYN和SYN+ACK对称性为

3 异常检测方法

各维特征度量值的时间序列在正常情况下比较平稳, 当有异常发生时会发生较大的波动, 当超过一定阈值时, 则认为出现异常。但是如何确定各维特征的阈值, 如何根据多维特征的检测结果来判断是否真的发生异常?为此将各维特征量排列成检测向量, 采用K-means聚类算法从大量样本数据中挖掘出正常流量的类簇, 将其作为检测模型, 根据距离判断检测向量是否异常。异常检测流程如图1所示, 整个流程分为两阶段:1) 训练阶段, 从样本数据中提取特征, 对各维度量值进行预处理并构造检测向量, 利用K-means聚类算法对检测向量进行分类, 过滤异常数据并建立正常流量模型;2) 在线检测阶段, 类似地构造检测向量, 利用训练阶段建立的正常流量模型对检测向量进行分类, 如果检测向量不属于任何类簇, 则判断发生异常。

3.1 构造检测向量

由于下一阶段采用的是聚类算法, 数据的度量范围不同会对聚类结果产生影响, 因此在聚类分析之前需要对数据进行标准化处理。

3.1.1 数据预处理

文中所采用的测度均是区间标度变量, 对于这类变量的标准化处理方法有很多, z分数规范化方法[6]是最常用的一种。使用z分数规范化需要计算所有分类数据的均值, 应用在网络流量异常检测中存在以下问题:1) 网络流量是随时间依次到达并且具有无限性, 因此无法计算所有数据的均值;2) 网络流量随时间动态变化, 各维特征的度量值在局部可能表现异常, 但是在全局数据中却表现正常;或者在局部表现正常的数据在全局中表现异常。为了解决以上问题, 考虑到一般情况下网络流量在一定的时间内, 随时间变化较小, 因此可以利用最近a个历史数据的均值作为当前时刻的参考值, 通过计算当前度量值与均值的偏离程度衡量各维特征的异常程度。这里采用滑动窗口保存并更新历史数据。

定义5设滑动窗口的大小为a, xi是特征x当前的度量值, mx和σx分别为特征x此时在滑动窗口中的均值和标准差, 则特征x的局部均值偏差为

z (x) 表示当前度量值偏离均值多少个标准差。由于采用了滑动窗口机制, 会不断地更新历史数据, z (x) 反映的是各维特征的当前异常程度, 因此能够检测到局部异常。

3.1.2 剔除异常点

在网络流量正常的情况下, 每隔一个单位时间, 将最新的度量值加入到滑动窗口并将最旧的数据剔除, 保持滑动窗口长度a不变。在检测到可疑点时, 为了确保后续检测的精度, 计算均值时会剔除可疑点。假设数组T[a]={x1, x2, …, xa}记录前a个时间窗口中特征x的度量值, 对于当前观察值xj, 如果|z (x) |超过阈值l (l通常取值为3) , 则不更新数组T, 否则用xj替换T中最旧的数据。详细过程如下所示:

1) 计算前a个时间窗口中特征x的均值mx和标准方差σx:

5) Else;

6) 不更新数组T;

7) End If。

3.1.3 构造检测向量

在对各维度量值进行预处理后, 可以将其排列成检测向量, 作为下一阶段输入的数据对象。

定义6设z (Hip) , z (Hport) , z (Htcp) , z (Hsyn) 分别为t时刻IP维, 端口维, 协议维和TCP标志位维测度的局部均值偏差, 则可构成四维检测向量

3.2 K-means聚类算法

K-means是一种基于划分的动态聚类算法, 将其用于异常检测主要基于以下2个假设[5]:1) 正常行为数据量要远远超过异常行为数据量;2) 正常行为数据与异常行为数据之间的差异很大。第一个假设为识别正常簇与异常簇提供了依据, 根据第二个假设能够很好地区分正常流量和异常流量。为了后续使用方便, 下面对涉及的概念进行定义。

聚类中对象间的相异度 (或相似度) 通常基于对象间的距离来计算。常用的计算距离的方法包括欧几里得距离、曼哈顿距离以及闵可夫斯基距离等。文中采用欧几里得距离计算相异度。

定义7数据对象i和j的相异度 (或距离) 为

其中i= (xi1, xi2, …, xin) 和j= (xj1, xj2, …, xjn) 是两个n维的数据对象, 在本文中n取4。

定义8设C={C1, C2, …, Ck}是对训练数据集S的一种划分, 类Ci的异常因子OF (Ci) 定义为Ci与其他类间距离的平均值:

异常因子OF (Ci) 度量了Ci与其他类簇间的偏离程度, OF (Ci) 越大, Ci与其他类簇间的偏离程度越大。

定义9设C={C1, C2, …, Ck}是对训练数据集S的一种划分, 类Ci的概要信息S (Ci) ={ceni, ri}, 其中ceni是类Ci的聚类中心, ri是Ci的半径, 即类Ci中的数据对象离质心ceni最远的距离。

3.2.1 K-means基本思想

在训练阶段, 采用经典的K-means聚类算法对数据集S进行划分, 其基本思想如下:

输入:n个四维空间数据对象S={Dt|t=1, 2, …, n}, 聚类中心的个数k;

输出:k个类簇C={C1, C2, …, Ck}。

1) 从n个对象中任意选择k个对象作为初始聚类中心;

2) 根据每个聚类中心, 计算每个对象与这些聚类中心的距离;并根据最小距离重新对相应对象进行划分;

3) 重新计算每个 (有变化) 簇的聚类中心;

4) 循环2) 到3) 直至每个簇不再发生变化为止。

3.2.2 建立检测模型

在聚类之后需要过滤掉异常数据, 建立正常数据模型。其详细描述如下:

1) 将集合C中的簇按异常因子大小升序排序, 使得OF (C1) ≤OF (C2) ≤…≤OF (Ck) ;

2) 寻找最小的x使其满足

3) 标记C1, C2, …, Cx为正常簇;

4) 由正常簇的概要信息构成检测模型。

这里假设训练数据集中正常数据占所有数据的比例为y。

3.2.3 在线检测

此时, 对每个时间窗口中生成的四维检测向量Dt, 可以利用检测模型判断Dt是否是异常向量。首先寻找d (Dt, Cj) ≤rj的Cj;如果Cj存在, 则认为Dt是正常向量, 否则判定Dt为异常向量。

4 实验与结果分析

对异常检测系统的评价主要关注两个指标:检测精度和效率。检测精度可以通过检测率和误报率体现, 效率意味着运行异常检测算法所需要的时间。本文通过与基于熵 (Entropy) 的算法和基于指数加权移动平均 (EWMA) 的算法进行对比实验验证所提方法的精度, 并通过分析所提算法的时间复杂度和单步执行时间验证算法的效率。

4.1 实验数据

实验采用的是NUST Traffic Dataset[11], 该数据集是由Irfan等人采集的校园网数据, 包含3个数据集, 每个数据集持续大约3个小时。在每个数据集中只施放一种攻击 (portscan/Do S/Udp flood) , 每种攻击发生10次, 每次持续5分钟, 并且每种攻击具有5种不同的攻击速率:三种低速率攻击 ({0.1, 1, 10}pkts/sec) 和两种高速率攻击 ({100, 1000}pkts/sec) 。其背景流量的平均速率是3168pkts/sec, 标准偏移是1683pkts/sec。各攻击特征如表1所示。

4.2 检测性能

将含有Do S攻击的数据作为训练数据, 以1min时间间隔统计各维特征量。假设训练数据被分成n个时间间隔, 则可以得到n*4的矩阵 (n个检测向量) , 用K-means聚类算法对这n个检测向量进行分类。当k取值为10时, 其结果如图2所示。标号为3的簇包含的数据对象最多, 其他簇只有极少的数据对象, 根据标类算法选取标号为3的簇作为检测模型。然后利用检测模型分别对三个数据集进行在线分类。检测结果如图2的 (b) 、 (c) 、 (d) 所示, 图中标号为3的簇代表的是正常簇, -1表示检测到的异常。

为了验证所提算法的准确性, 采用近年来受关注较多的基于熵的检测方法[12]以及基于EWMA流量预测模型的检测方法进行对比实验, 实验结果如图3所示。图3是3个方法分别对低速率攻击和高速率攻击的检测结果。从图3中可以看到, 不论是对低速率攻击还是高速率攻击, 所提算法在大部分情况下相对于其他2种方法具有更高的精度, 而EWMA方法的检测精度最差。主要原因分析如下:1) 流量大小在时间序列上存在较大的波动, 因此基于EWMA的算法的误报率较高, 而本文所采用的特征序列在无异常时相对平稳, 并且采用K-means算法综合各维特征的检测信息, 因此误报率更低;2) 在计算局部均值偏差时剔除了异常数据, 使其能够检测到多个连续的异常, 因而检测率更高。另外, 在低速率攻击中, 三种方法的检测率相对较低的原因是低速率攻击的网络行为已经非常接近正常流量的网络行为, 并未对整体流量产生较大的偏移。通过调整阈值, 虽然可以提高检测率, 但是误报率会相应上升。

4.3 实验效率分析

通过对算法的仔细分析发现进行异常检测所需要的时间主要消耗在特征量的统计上, 在流量较大的网络上, 统计特征量对算法的效率影响较大。在算法实现时, 利用哈希表记录已出现的特征元素, 并用链地址法解决冲突问题。K-means聚类算法在训练阶段的时间复杂度是O (nkt) , 其中n是对象个数, k为聚类个数, t为迭代次数;建立检测模型阶段需要计算各个类簇的异常因子并对其进行升序排序, 时间复杂度为O (m·k2) , 其中m是检测向量的维度;在线检测阶段的时间复杂度为O (m·x) , 其中x是正常簇的个数。

在配置为1.9GHz的CPU、1GB内存的计算机上, 对以上实验数据集应用所提方法, 单步执行时间如图4所示。对其进行分析, 发现在正常情况下所提方法的单步执行时间不超过1s, 在发生大规模网络攻击时单步执行时间不超过20s, 具有较好的实时性。

5 结束语

针对网络流量检测领域检测率较低, 误报率较高两个问题, 提出基于K-means聚类的异常检测方法。文中根据常见异常在IP、端口、协议以及TCP标志位这四个维度上的变化情况, 采用了四个检测测度, 然后对各维测度进行预处理并构造检测向量, 最后采用由K-means算法产生的检测模型对检测向量分类, 判断是否发生异常。该方法能够融合多维特征进行综合判断, 有效地减低了误报率和漏报率。另外, 文中利用滑动窗口计算各维特征的局部均值偏差, 并剔除了异常数据, 使其能够保证在实时动态变化的网络中的检测准确度。实验结果表明, 该方法能有效地检测出多种异常, 而且误报率相对较低。

参考文献

[1]Krugel C, Toth T, Kirda E.Service specific anomaly detection for network intrusion detection[C]//Proceedings of the 2002 ACM Symposium on Applied Computing.New York:ACM Press, 2002:201~208.

[2]郑黎明, 邹鹏, 韩伟红, 等.基于Filter-ary-Sketch数据结构的骨干网异常检测研究[J].通信学报, 2011, 32 (12) :151-160.

[3]Sengar H, Wang X, Wang H, et al.Online detection of network traffic anomalies using behavioral distance[C]//Proceedings of 2009 17th International Workshop on Quality of Service.New York:IEEE, 2009:1-9.

[4]诸葛建伟, 王大为, 陈昱, 等.基于D-S证据理论的网络异常检测方法[J].软件学报, 2006, 17 (3) :463-471.

[5]Portnoy L, Eskin E, Stolfo J.Intrusion detection with unlabeled data using clustering[C]//Proceedings of 2001ACM CSS Workshop on Data Mining Applied to Security.Philadelphia:ACM Press, 2001:5-8.

[6]Jiang Shengyi, Song Xiaoyu, Wang Hui, et al.A clustering-based method for unsupervised intrusion detections[J].Pattern Recognition Letters, 2006, 27 (7) :802-810.

[7]Kind A, Stoecklin M, Dimitropoulos X.Histogram-based traffic anomaly detection[J].IEEE Transactions on Network and Service Management, 2009, 6 (2) :110-121.

[8]Hareesh I, Prasanna S, Vijayalakshmi M, et al.Anomaly detection system based on analysis of packet header and payload histograms[C]//Proceedings of International Conference on Recent Trends in Information Technology.Piscataway:IEEE Computer Society, 2011:412-416.

[9]Moore D, Voelker G M, Savage S.Inferring internet denial-of-service activity[C]//Proceedings of the 2001USENIX Security Symposium.Washington, DC, 2001:15.

[10]龚俭, 彭艳兵, 杨望, 等.基于Bloom Filter的大规模异常TCP连接参数再现方法[J].软件学报, 2006, 17 (3) :434-444.

[11]Irfan U H, Sardar A, Hassan K, et al.NUST Traffic Dataset[EB/OL].[2012-12-10].http://wisnet.seecs.nust.edu.pk/projects/ENS/DataSets.html.

K-Means聚类法 篇6

K-Means算法是聚类分析中使用最为广泛的算法之一, 该算法简单、计算速度快、资源耗费少, 尤其对大型数据集的处理效率较高, 在网络信息处理领域有着广泛的应用[1]。

K-Means算法是以随机选取的初始聚类中心为前提, 从而该算法有个明显的缺陷[2]:不同的初始聚类中心会导致聚类的结果差别很大, 导致算法容易陷入局部最优解而找不到全局最优解, 这在很大程度上影响其聚类效果。

针对算法K-Means算法随机选取的初始聚类中心的缺陷, 进行改进的方法有很多。文献[3]通过k-dist的差值 (DK) 图分析, 选择主要密度水平曲线上k-dist值最小的点作为初始聚类中心。文献[4]提出基于数据样本分布选取初始聚类中心的改进k-means算法。王丽娟等人[5]提出了基于随机取样的选择性K-means聚类融合算法 (RS-KMCE) , 避免了算法陷入局部最优解。王永贵等人[6]提出结合双粒子群和K-means的混合文本聚类算法, 发挥了两者优势, 提高了算法鲁棒性和准确性, 产生了较好的聚类效果。

在研究K-Means算法及其一些改进算法的基础上, 本文提出采用基于最远距离的方法选取初始聚类中心。

1 改进 K-Means 聚类算法

为了避免最终仅得到局部最优结果, 选取最具有代表性的相互距离最远的K个点作为初始聚类中心。

数据对象之间的相似度采用欧氏距离来进行度量, 公式为:

目标函数采用误差平方和准则函数, 公式为:

优化初始聚类中心的K-Means算法描述如下:

输入包含n个数据对象的数据集

输出聚类结果

(1) 在数据集里随机取一数据点xa, 计算距离xa最远的数据点xb, 然后计算距离数据点xb最远的数据点xc, 若Dab>=Dbc, 则xa、xb为距离最远的两个数据点;若Dab

(2) 将距离最远的两个数据点作为最初的两个初始聚类中心;

(3) 在数据集中寻找下一个聚类中心xk, 其必须满足

(4) 将n-k个数据对象按照最近距离划分到k个聚类中心, 计算目标函数值E, 若Ek>=Ek+1, 则输出k个聚类结果;若Ek

2 实验分析

2.1 实验一

为验证上述算法, 选用UCI数据库上的Iris数据作为测试数据。UCI数据库是加州大学欧文分校提出的用于测试机器学习、数据挖掘算法的数据库, 库中的数据都有确定的分类, 因此可以用准确率直观地表示聚类的质量。

传统K-Means算法进行5次运算和本文改进K-Means算法最终运算结果如表1所示, 通过表1说明了改进K-Means算法的准确率优于传统K-Means算法。

2.2 实验二

实验选择数据集KDD cup 1999作为测试数据, 该数据集是网络入侵检测的标准, 这些数据全部采用tcpdump格式, 每条记录包涵34个数字型字段和7个非数值型字段, 并带有Normal, Probe, Do S, R2L, U2L五种标签。Normal, Probe, Do S, R2L, U2L五种标签。

为了更好的说明算法的改进效果, 实验过程中对数据进行了筛选, 只从数据集中选择出10000条数据记录, 其中Norma记录9500条, Do S记录300条, Probe记录100条, R2L记录50条, U2L记录50条。除此之外, 对数据记录中对实验结果影响不大的属性除去, 只取其中12种关键属性, 包括3个离散型属性和9个连续型属性。

对选择好的数据集同时运用传统K-Means算法和改进K-Means算法进行聚类, 得到的初始聚类中心类型以及聚类结果如表2和表3所示。

从表2和表3中可以看出, 按数据所占比例来看, 传统K-Means算法得到的5个聚类结果中Normal数据占有较高的比例, 因此5个聚类都为Normal聚类。虽然对数据进行了一定的划分且有较高的准确率, 但该聚类结果未能有效标记出异常的攻击数据。而改进K-Means算法除了聚类1、聚类3和聚类5为Normal数据聚类外, 还得到了两个异常聚类:聚类2和聚类4。在聚类2中Do S中类型的数据占记录总数的绝大多数, 因此可以记为Do S聚类;而在聚类4中Probe类型的数据占记录总数的绝大多数, 因此可以记为Probe聚类。与传统K-Means算法相比, 改进K-Means算法对数据进行了有效划分, 且提高了算法的准确率。

3 结束语

针对K-Means算法由于随机选取初始聚类中心和而造成聚类精度及效率降低等问题, 提出了一种改进的K-Means算法。实验验证, 相对于传统K-Means算法, 改进K-Means算法能够获得更好的聚类效果。在实际应用中, 将改进的K-Means算法运用到僵尸网络检测系统, 对于提高僵尸网络的检测率将发挥更好的作用。

摘要：针对K-Means算法所存在的问题, 提出了一种改进的K-Means算法, 该方法通过选取相互距离最远的数据点作为初始聚类中心, 能够很好地排除随机选取初始聚类中心点的影响。通过实验验证, 相对于传统K-Means算法, 改进K-Means算法能够获得更好的聚类效果。

关键词：K-Means算法,距离最远,初始聚类中心

参考文献

[1]杜强, 孙敏.基于改进聚类分析算法的入侵检测系统研究[J].计算机工程与应用, 2011, 47 (11) :106-108, 181.

[2]孙吉贵, 刘杰, 赵连宇.聚类算法研究[J].软件学报, 2008, 19 (1) :48-61.

[3]郑丹, 王潜平.K-Means初始聚类中心的选择算法[J].计算机应用, 2012, 32 (8) :2186-2188, 2192.

[4]仝雪娇, 孟凡荣, 王志晓.对k-means初始聚类中心的优化[J].计算机工程与设计, 2011, 32 (8) :2721-2723, 2788.

[5]王丽娟, 郝志峰, 蔡瑞初等.基于随机取样的选择性K-means聚类融合算法, 计算机应用, 2013, 33 (7) :1969-1972.

K-Means聚类法 篇7

K-means算法是一种应用非常广泛的聚类分析方法,具有简洁、高效、可伸缩性强等优点,一般用簇内数据对象的均值表示K-means算法每个簇的中心[1]。 但传统Kmeans算法存在诸多不足之处。例如,传统K-means算法对初始聚类中心敏感、算法需要指定参数K的值、输入的不同K值随目标准则函数进行不同次数的迭代、聚类结果波动大、容易陷入局部最优[2]。遗传算法具有很强的鲁棒性和适应性,在解决大空间、多峰值、非线性、全局寻优能力等问题上具有优势,但也存在着前期过早收敛和后期收敛过慢的缺点。

基于改进遗传算法的K-means算法能够有效解决算法对初始值K的依赖性,自动生成类K;同时严格选取初始中心点,加大各中心点之间的距离,避免初始聚类中心会选到一个类上,一定程度上克服了算法陷入局部最优状态[3,4,5,6]。

本文基于改进遗传算法进行学生成绩的K-means聚类分析,将学生的考试成绩按照不同科目分成不同的类簇,利用改进遗传算法解决初始聚类中心问题,从而在整体上归纳分析该门课程所具有的特点属性,以及每门课程之间的联系性和差异性,以提高算法效率和准确性。并且,通过选择运算、交叉运算和变异运算来加快算法的收敛性。

1 K-means聚类算法

1.1 传统K-means聚类算法

传统K-means算法随机选择聚类中心,其核心思想为:给出n个数据点,找出k个聚类中心,利用欧氏距离式计算每个数据点与最近聚类中心的距离平方和最小值,依据最近原则把各数据点分到各个簇,利用式(1)计算每簇中数据对象的均值,采用目标准则函数(2)进行迭代运算,直到簇心的移动距离小于某个给定的值。

传统K-means算法描述如下:

输入:n个数据集D,数据聚类个数k。

输出:平方误差准则最小的k个簇的集合。

具体步骤如下:(1)从数据集D中,输入聚类个数k和包含n个数据对象的数据库;(2)随机选择k个对象作为初始聚类中心;(3)根据簇中它们与聚类中心的相似度,将每个对象划分到相似的簇;(4)重复(1)-(3);(5)更新簇的平均值,根据每个簇中对象的平均值,重新划分相应的对象;(6)计算目标准则函数;(7)直到每个目标准则函数不再发生变化,即方差评价函数开始收敛为止。

传统K-means算法划分方法是根据初始聚类中心来确定数据的初始化[7]。然而k个初始聚类中心的确定对聚类结果影响很大,因为步骤(2)是随机选择k个对象作为初始聚类中心的。每次迭代使簇中剩余的对象根据与簇中心的相似度重新划分到相似的簇。每次完成迭代运算,就会算出新的聚类中心,以及误差平方和准则函数(2)的值。若再进行一次迭代后,误差平方和准则函数的值不发生改变,说明算法已经收敛。在迭代过程中,函数(2)逐渐减少,直到为最少值为止。图1显示了K-means算法的迭代过程。

该算法的时间复杂度为O(tknd),其中t是算法循环的次数,t<<n,k<<n。

1.2 K-means算法存在的问题

传统K-means算法对初始聚类中心很敏感,选取不同的初始聚类中心,会得到不同聚类的结果,而且通常得不到全局最优解。因此,如何找到一组较优的初始中心点,进而获得较好的聚类结果并消除聚类结果的波动性值得研究[8]。

传统K-means算法存在的主要问题如下:

(1)难以估计聚类个数K,一般需预先指定。事先不能确定给定的数据集最适合分为几个类别。有的算法根据类的自动合并和分裂得到较为合理的K值;有的依据方差分析理论,混合统计量来确定最佳K值,并应用模糊划分来验证最佳分类数的正确性;有的则结合全协方差矩阵RPCL算法,逐步删除只包括少量训练数据的类。但是之前的这些改进基本没有具体应用到学生考试成绩系统中。

(2)算法过多依赖于初始值并经常陷入局部极小解。不同的初始值可能造成算法聚类结果的不稳定。Kmeans算法常采用误差平方和准则函数作为聚类准则函数。聚类准则函数往往存在很多个局部极小值,但只有一个是全局最小。因为每次确定的初始聚类中心都会偏离非凸函数曲面的全局最优解的搜索范围,使用迭代运算,聚类准则函数只能达到局部最小,而不能得到全局最小。因此,许多算法利用遗传算法进行初始化,以内部目标函数作为评价指标,但基于遗传的K-means算法(GA-K均值算法)存在前期过早收敛而后期收敛过慢的缺点。

1.3 基于改进遗传算法的K-means聚类算法思想

本文提出了一种基于改进遗传算法的K-means算法,该算法结合K-means算法的高效性和局部搜索能力,以及改进遗传算法的全局优化能力,能够达到较好的聚类结果。

1.3.1 染色体编码选择

由于聚类样本数量大、维数高,本文采用将各聚类的中心坐标d维编码为染色体,其在聚类中心的数目为K,其长度为K*d,编码为{m1,m2,…,mk},其中Xi=[mj1,mj2,…,mj3]。由此类推,每条染色体,随机从m个对象中选择K个对象作为初始的簇中心坐标。染色体编码如图2所示。

1.3.2 适应度函数

区分群体中个体良莠程度的标准是适应度函数值的大小。本算法采用公式(3)表示适应度函数,值越小,则聚类结果越好,个体越优良;适应度函数值越大,则聚类结果越差,个体越劣质。

其中,b是常数,根据具体问题进行取值。

1.3.3 改进的选择算法

根据适应度函数淘汰的个体中,也会有在以后交叉变异操作中产生优良的个体,如果直接淘汰会让算法取得局部优化。因此,本文采取了二次选择的方法:(1)对第一次淘汰的个体先进行一遍交叉和变异操作;(2)根据适应度函数计算的值进行排序,找出适应度值最高的个体;(3)对前两次选取的优良个体再根据适应度值进行降序,最终找出最优良的个体作为下一次操作的新种群。

1.3.4 改进的交叉重组

传统的遗传算法采取固定的交叉概率Pc和变异概率Pm,容易出现早熟现象,后期还会因个体差异减小,出现收敛速度缓慢的现象。采用最邻近法则来实现交叉操作,当种群适应度相对集中时,Pc和Pm增大;当种群适应度相对分散时,Pc和Pm减小。让算法在迭代过程中根据个体的适应度来改变Pc和Pm,不但保证了最优个体而且加速了交叉个体的淘汰速度,增强了算法的全局搜索能力。

1.3.5 算法终止条件与优化

先假定一个最大的迭代次数,当算法的迭代次数超过最大迭代次数,最优结果的次数也连续超过某一个阈值。每次遗传操作后会记录适应度最高的个体,算法结束后,将其作为该聚类问题的最终解,并对所有个体计算以其作为K-means问题初始值的局部最优结果,从而替换之前的个体,优化后的个体再进行下一次优化。这样既提高了遗传聚类算法的局部搜索能力,又有利于提高其收敛速度。

1.3.6 改进的遗传K-means算法流程

改进的遗传K-means算法流程如图3所示。

2 仿真实验结果与分析

2.1 实验平台

为了检测本文提出的改进型遗传K-means聚类算法的有效性,本文在一定的环境下对算法进行了仿真实验。实验环境是P4 2.4 GHz,4GB内存,160G硬盘,Windows2007专业版操作系统。 基于改进遗传算法的Kmeans聚类在Visual C+ +6.0 环境下用C+ + 语言实现。

2.2 实验结果及分析

本实验中的数据来源广西政法管理干部学院教务系统,选用信息工程系的学生作为测试样本集。学生成绩数据集包含150个样本,分为2个不同的专业,分别是司法信息专业和计算机网络专业。每个专业各有50个样本,包括4门专业课程:C语言、VB程序设计语言、Java程序设计语言、VB+SQL应用软件程序设计。表1截取了该数据集的9个样本片段并显示了其所学的专业课程。为了方便数据处理,以下成绩均采取10分制显示。

改进的遗传K-means算法实验参数设置如下:初始种群的大小为150,交叉概率Pc=0.9,变异概率Pm=0.01,最大迭代次数T=100,聚类个数k=2。表2显示了信息工程系学生成绩数据两类算法的聚类结果。

为了更清晰地显示两种算法性能的优劣,根据每一次迭代中的目标函数值,绘出两种算法在本组实验中的收敛曲线,如图4所示。K-means所得的结果不理想,正确率只有64%,而改进遗传聚类算法正确率达到了84%。同时,从收敛效果曲线可以看出,每次迭代,改进遗传聚类算法的目标函数值比K-means算法的目标函数值都要小,这说明收敛效果好于传统K-means算法,同时还得到了更好的聚类结果,具有更好的聚类性能。

3 结语

文中采用改进遗传的K-means算法对高职学生考试成绩进行了聚类分析,弥补了传统划分方法的缺点,科学、公正、合理地反映出学生对此门课程掌握情况以及教师的教学效果。并且,教师还可以根据聚类分析结果,针对性地进行教学设计,提高教学效果。学生也可以制定相应的学习计划,从而达到提高学习效率和学习成绩的目的。

摘要：K-means算法是聚类分析划分方法中的一种常用方法,也是目前在数据分析方法中最有应用前景的方法之一。但K-mean算法对初始聚类中心十分敏感,这对处理学生成绩等数据而言,会导致聚类结果极为不稳定。为此,提出基于改进遗传算法的K-means聚类算法。该算法利用遗传算法解决初始聚类中心,提高聚类结果的稳定性,但存在前期过早收敛和后期收敛过慢的缺点。将改进遗传K-means聚类算法应用于高职高专的学生考试成绩分析中,可以很好地解决传统遗传聚类算法对聚类结果的不稳定性问题,并通过聚类结果对学生考试成绩进行分类评价,利用所获得的数据聚类结果指导教学,从而提高教学质量。

关键词：聚类,K-means算法,遗传算法

参考文献

[1]仝雪姣,孟凡荣,王志晓.对K-means初始聚类中心的优化[J].计算机工程与设计,2011,32(8):2721-2723.

[2]HAN LING-BO,WANG QIANG,JIANG ZHENG FENG.Improved K-means initial clustering center selection algorithm[J].Computer Engineering and Applications,2010,46(17):150-152.

[3]陈敏,李雪峰.一种选择了初始聚类中心的改进K-means算法[C].2010年广播技术和多媒体通信国际会议,2010:48-50.

[4]王康,颜雪松,金建,等.一种改进的遗传算法K-均值聚类算法[J].计算机与数字工程,2010(1):18-20.

[5]胡或,毕晋芝.遗传优化的K均值聚类算法[J].计算机系统应用,2010,19(6):52-55.

[6]王智.改进K-means算法在职高试卷成绩分析中的应用[J].电脑知识与技术,2010,6(6):5048-4049.