k-means算法（共7篇）
k-means算法 篇1
K-means聚类算法是由J.B.Mac Queen在1967年提出的, 之后迅速应用在不同的学科和领域。虽然K-means聚类算法被提出有50多年了, 但目前还是被应用最广泛的算法之一。其容易实施、简单、高效的特征, 以及解决无数成功案例, 仍然使其依旧是被研究的热点。
本人主要是在研究K-Means基本算法的基础上, 总结阐述了改进的K-Means算法。基于向量语义相似度的K-means算法, 针对传统的K-Means算法的不足, 提出通过向量语义相似度的计算自动确定初始聚类中心, 在聚类过程中, 达到语义相似度阈值的网页才使用K-Means算法进行聚类;基于初始聚类中心优化的K-means算法, 通过数据之间距离, 计算密度参数, 保留高密度区域, 删除低密度区域, 找出数据的真实分布。
1 K-Means算法简介
K-means算法, 它是一种基于距离远近的聚类算法, 同时也是一种无监督学习算法, 对以后的算法改进具有很大的影响。该算法的优点是简单易行, 容易理解, 时间复杂性接近线性, 对大规模数据挖掘具有高效性和可伸缩性, 在科研以及实际应用中有着很重要的作用。
按照K-means的基本思想, 可以将K-means聚类算法描述如下:
步骤:
输入:数据集中的n个数据对象, 聚类个数为k;
输出:满足误差平方和准则函数最小的K个聚类;
算法流程:
(1) 从n个数据对象中随机选取k个对象作为初始聚类中心;
(2) 计算数据集中各个数据对象与聚类中心的距离, 并根据最小距离对数据对象进行类群划分;
(3) 在形成的子类群中, 重新计算每个聚类中所包含的数据对象的平均值作为新的聚类中心;
(4) 循环流程 (2) 到 (3) 直到前后两次迭代得到的每个类群的中心点不再高于某个阈值为止。
2 K-Means算法改进
2.1 基于向量语义相似度的K-means算法
针对传统的K-Means算法对网页处理的不足, 以及其在文本聚类中存在的局限性, 提出了基于网页向量语义相似度的改进K-Mean算法。新算法通过向量语义相似度的计算确定初始聚类中心, 在聚类过程中, 达到语义相似度阈值的网页才使用K-Means算法进行聚类。新算法很好地克服了传统K-Means算法随机选取聚类中心以及无法处理语义信息的问题, 提高了聚类的质量。
2.2 基于初始聚类中心优化的K-means算法
传统的算法对初始聚类中心特别敏感, 聚类结果随不同的初始输入而波动, 基于初始聚类中心优化的K-means算法通过计算对象相互之间的距离, 产生密度参数, 很好的排除了低密度区域的脏数据, 从而也优化了传统K-Means算法对脏数据的敏感性。
3 K-means算法的其他改进
在K-means聚类算法中, 每个数据点都被唯一的划分到一个类别中, 这被称为硬聚类算法, 它不易处理聚类不是致密而是壳型的情形。这对这一情况, Dunn等人于1973年提出了模糊K-means聚类算法。Kashima等人于2008年使用L1距离, 最终聚类中心是每一类的中位向量。对于一维数据集X={x1, x2, x3, …, xi, …, xn}而言, 中位数M比均值对异常数据有较强的抗干扰性, 聚类结果受数据中异常值的影响较小。Mao&Jain[4]于1996年提出使用Mahalanobis距离, 但计算代价太大。在应用中, Linde等于1980年提出使用Itakura Saito距离。Banerjee等人2004年提出, 如果使用Bregman差异作为距离度量, 有许多突出优点, 如克服局部最优、类别之间的线性分离、线性时间复杂度等。
4 与经典K-means算法的比较
基于向量语义相似度的K-means算法首先计算网易语义之间的相似度, 只有达到一定阈值时, 才进行聚类, 新算法克服了传统K-Means算法无法处理语义信息的问题, 提高了聚类的质量。基于初始聚类中心优化的K-means算法通过对象相互之间的距离, 产生密度参数, 很好的排出了低密度区域的脏数据, 从而也优化了传统K-Means算法对脏数据的敏感性。
5 结束语
对于K-means算法, 笔者比较感兴趣的是未来K-means算法对于稀疏数据的处理能力。大家都知道, 随着大型互联网公司的发展, 以及商品数量的增多, 数据对象稀疏问题对聚类过程影响很大, 现在已有的处理数据稀疏的技术, 比如平均、平滑等, 笔者不是很满意。我们可以假设数据对象的属性就好比一个人在不同成长阶段的性格, 没必要刻意塑造, 而在于它自己丰富。
参考文献
[1]Meng Jianliang, Shang Hai kun, Bian Ling.The application on intrusion detection based on K-means cluster algorithm[C].International Forum on InformationTechnology and Applications, 2009:150-152.
[2]孙士保, 秦克云.改进的k-Means聚类算法研究[J].计算机工程, 2007 (07) :200-202.
[3]Dunn JC.A fuzzy relative of the isodata process and itsuse in detecting compact well-separated clusters[J].Journal of Cybernetics, 1973 (3) :32-57.
[4]Mao J, Jain A K.A self-organizing network for hyper-ellipsoidal clustering.IEEE Transactions on neural networks, 1996 (7) :16-29.
k-means算法 篇2
聚类的基本任务是为对象集合中所有存在特征相似或接近的对象个体进行类别标记。目前,比较流行的聚类方法有划分法、层次法、密度法、网格法等。在众多的聚类方法中,K-means聚类算法是一种应用广泛的无监督聚类划分方法。K-means聚类算法具有算法简单、时间复杂度低等优点,在数据呈球状分布的领域有着较好的聚类效果。但是,由于K-means聚类算法通过随机的方式来确定初始聚类中心,所以其聚类结果呈现出一定的不稳定性,并容易陷入局部最优解。为了提高K-means聚类稳定性,人们对初始聚类中心进行了各种优化。汪中等[1]提出了通过采用密度敏感的相似性度量来计算对象的密度,以此来启发式地生成样本初始中心的方法。赖玉霞等[2]提出了采取聚类对象分布密度方法来确定初始聚类中心,然后选择相互距离最远的k个处于高密度区域的点作为初始聚类中心的方法。张斌等[3]提出了基于距离估计优化初始聚类中心的K-Means算法。上述三种算法分别从密度分布和距离角度来选择聚类初始中心点,但没有考虑类蔟的规模对聚类结果的影响。曹付元等[4]提出了利用邻域模型中对象邻域耦合度和分离度实现初始聚类中心选择的K-Means算法。Fouad Khan[5]提出了在具有最大对象间隔的特征基础上生成初始聚类中心的K-means算法。上述两种算法直接在对象几何参数上进行选择初始聚类中心,当干扰较大时其聚类效果受影响的概率较大。Juanying Xie等[6]提出了通过全局搜索稳定的对象位置来生成初始聚类中心的K-means算法。该算法在对象规模较大时时间复杂度也较大。Yan Zhu等[7]提出了通过AP算法来生成初始聚类中心的CAK-means算法,该算法在AP生成的所有聚类中心基础上进行K-means聚类,并通过比较最终的聚类效果以选出最佳的初始聚类中心,其聚类效果较好但时间复杂度较高。本文提出了通过近邻传播聚类算法生成若干个初始聚类,然后通过考察初始聚类的规模来确定K-means的初始聚类中心的K-means算法(APK-means)。该算法充分发挥了近邻传播聚类(AP)算法能够快速进行大规模数据聚类的优点,同时规避了其无法确定聚类数量的缺陷,有效提高了聚类的稳定性和有效性。本文第1节分别简述了K-means算法和AP算法,第2节详细介绍了APK-means算法,第3节通过实验验证了APK-means算法的有效性和稳定性。
1 K-means聚类算法和AP算法
1.1 K-means聚类算法
设某对象集对象之间的距离为该对象集的k个类别,k个类别的聚类中心
K-means聚类算法通过迭代计算距离逐渐把对象划分成k个类蔟,使得目标函数最小化。
K-means算法描述如下:
输入:聚类的数目k和包含n个对象的数据集。
输出:满足目标函数值最小的k个类蔟。
step 1:从n个数据对象中任意选择k个对象作为初始聚类中心;
step 2:循环step 3和step 4,直到目标函数E的值在某范围内不再发生变化为止或者迭代次数超过上限;
step 3:计算每个对象与聚类中心的距离,并且根据最小距离重新划分对象到相应的类蔟中;
step 4:重新计算每个类蔟的聚类中心。
1.2 AP算法
AP算法定义了以下几个概念:
(1)相似度
对象间的相似度s(i,j)反映了对象xi,xj之间的相似程度,其定义为1式和2式:
(2)吸引度和吸引度矩阵
对象间的吸引度r(i,j)反映了对象xi以对象xj为聚类中心的可能性,其定义为3式:
吸引度矩阵
(3)归属度和归属度矩阵
对象间的归属度a(i,j)反映了以对象xj为聚类中心的类蔟包含对象xi的可能性,其定义为4式和5式:
吸引度矩阵
AP算法描述如下:
输入:n个对象的数据集。
输出:若干个类蔟。
step 1:计算数据集的相似度矩阵;
step 2:计算吸引度矩阵和归属度矩阵,其中a(i,j)=0;
step 3:循环step 4,直到类蔟不再发生变化或者迭代次数超过上限;
step 4:根据式6、7更新吸引度矩阵和归属度矩阵:
step 5:由式8得到以对象xj为聚类中心的类蔟包含对象xi的聚类结果。
2 APK-means聚类算法
若K-means聚类算法所选择的初始聚类中心远离实际的聚类中心,或者是偏远的噪声干扰点等,则聚类的结果会呈现出不确定的现象,从而不能保证较高质量的聚类效果。因此,通过提高初始聚类中心的选取质量来优化K-means算法的聚类效果是可行的方法之一。
2.1 APK-means聚类思想
AP算法在对象间相似度的基础上定义了吸引度和归属度概念,通过迭代不断更新吸引度和归属度矩阵,逐渐将对象集中相似的对象划分到相同的类蔟中,以最终形成若干个类蔟并获得每个类蔟的聚类中心。本文提出在AP算法聚类结果基础上进行K-means聚类的思想。该思想以AP算法聚类生成的类蔟中心为K-means算法的初始聚类中心,充分利用AP算法快速、稳定的聚类效果,有效提高了K-means算法的初始聚类中心的质量。但是,AP算法的聚类数目受每个对象自身成为聚类中心可能性大小(该值称为偏置参数p,一般采用3式估计其值)的影响,且两者之间的映射关系是不明确的。因此AP算法在进行聚类前无法获知最终的聚类数目。而K-means聚类算法是在已知聚类数目的前提下进行聚类。当AP算法聚类生成的类蔟数目等于K-means算法要求的聚类数目时,直接以AP算法聚类结果为当前聚类结果。当AP算法聚类生成的类蔟数目小于K-means算法要求的聚类数目时,通过调整偏置参数p来增加类蔟数目,使其大于K-means算法要求的聚类数目。
当AP算法聚类生成的类蔟数目大于K-means算法要求的聚类数目时,本文提出选择类蔟中规模较大的类蔟的聚类中心作为K-means算法的初始聚类中心。K-means算法在聚类过程中,规模大的类蔟会不断和规模小的类蔟进行合并,直到完成指定的k个聚类。APK-means聚类从以下两个方面优化了K-means聚类效果:
(1)规模较大的类蔟聚类分布对对象集总体聚类分布的影响意义比规模较小的类蔟相对大些,所以规模较大的类蔟的聚类中心在距离上比随机选择的聚类中心更加接近全局最优类蔟分布的聚类中心,使得APK-means算法的聚类效果会比普通K-means算法好。
(2)由于对象间的相似度在AP算法聚类时是不会变动的,所以AP算法聚类生成的类蔟聚类分布是固定的,使得K-means算法最终的聚类结果会保持稳定。
APK-means算法建立对象相似度、吸引度和归属度共三个规模为N*N的矩阵,其时间复杂度为O(AP)+O(K-means),其空间和时间代价大于一次K-means算法的代价。但是APK-means算法只需运行一次即可获得较好的聚类效果。而K-means算法往往需要运行多次才能获取较好的聚类效果。
2.2 APK-means聚类算法
APK-means算法描述如下:
输入:聚类的数目k和包含n个对象的数据集。
输出:满足目标函数值最小的k个类蔟。
step1:运行AP算法
step2:如果AP算法生成的类蔟数等于k,返回;
step3:如果AP算法生成的类蔟数小于k,偏置参数p增加0.01p,跳转至step 2;
step4:计算所有AP算法生成的聚类类蔟的规模(既类蔟中所包含的对象数量);
step5:选取前k个规模最大类蔟的中心为初始聚类中心;
step6:运行K-means聚类算法;
3 实验结果
3.1 聚类效果指标
本文采用聚类密集性指标对K-means算法和APK-means算法的聚类效果进行评估。聚类密集性指标通过测量聚类内的方差来反映聚类数据同一性的程度,其值越小表明同一性越高,即聚类密集性效果越好。聚类密集性指标定义如下:
设对象集其方差其中为对象之间的距离,为对象集X的均值。设对象集X的k个聚类类蔟为则X的密集性指标为
3.2 仿真数据实验
仿真数据实验采用随机生成的100个分为3类的数据对象集合,分别采用K-means算法和APK-means算法进行聚类。表1所示的是运行5次K-means算法和5次APK-means算法的的聚类密集性指标值。
表2所示的是上述5次K-means算法和5次APK-means算法聚类类蔟的聚类中心坐标。
图(1)和图(2)分别是运行5次K-means算法和1次APK-means算法的聚类效果图,图中使用符号“*”、“+”和“^”分别对三个类蔟中的对象进行标记。
图2(a)中三个红色“+”大符号标记了APK-means生成的三个聚类中心。
该仿真实验结果显示K-means算法聚类结果受到了随机选取的聚类中心的影响,而APK-means算法的5次聚类结果都相同,这表明APK-means算法具有更好的聚类稳定性。K-means算法5次聚类结果的密集性指标普遍低于APK-means算法,表明APK-means算法具有更有更好的聚类有效性。
3.3 UCI数据实验
本文采用UCI数据库中的Iris数据集。该数据集包含150个具有4个属性值的对象,共分为3类。由于该数据集已经提供了分类标签,且按照同分类同组的方式顺序编排,所以聚类效果可以通过计算对象正确分类的正确率进行评估。其实验算法描述如下:
step 1:使用聚类算法进行聚类;
step 2:根据数据集的分类标签统计聚类结果中每个对象所属分类一致的数量;
step 3:将分类一致的对象总数除以数据集中对象的总数,得到聚类正确率。
表3所示的是运行5次K-means算法和5次APK-means算法的的聚类密集性指标值。
该实验结果同样表明APK-means算法比K-means算法具有更好的聚类有效性和稳定性。
4 结束语
本文基于K-means聚类算法和AP算法提出了一种APK-means聚类算法。该算法首先由AP算法生成若干类蔟,当类蔟数量小于聚类数k时,通过调整偏置参数p来提高聚类数k;当类蔟数量大于聚类数k时,以此按类蔟规模大小降序选择其对应的聚类中心为K-means聚类算法的初始聚类中心点,接着进行K-means聚类。APK-means聚类算法充分利用了AP算法能够快速稳定生成类蔟的优点,同时也避免了对所有类蔟聚类中心进行全局搜索,优化了K-means聚类算法的聚类稳定性和有效性,获得了较好的聚类效果。但是APK-means算法的空间复杂度和时间复杂度比K-means聚类算法有了一定的上升,在对象集规模较大时其计算代价较大。
摘要：K-means聚类算法在随机选择的初始聚类中心的基础上进行聚类,其聚类效果会因为初始聚类中心的不确定性而不稳定。为了优化其聚类效果,提出了基于近邻传播算法(AP算法)的K-means聚类优化算法(APK-means)。该算法首先通过近邻传播算法生成若干个初始聚类,然后依序选择k个聚类规模最大的聚类中心作为K-means聚类算法的初始聚类中心,接着运行K-means聚类。算法有效性分析和实验结果验证了该算法有效优化了K-mean算法的聚类稳定性和有效性。
k-means算法 篇3
聚类是指按照事物的某些属性, 将事物聚集成若干类, 使得同一个簇中对象相似度尽量大, 而不同簇中的对象相似度尽量小[1]。通过聚类, 人们能够识别事物分布的不同区域, 发现数据属性间的相互关系, 找到潜在有使用价值的信息, 并为决策提供数据依据[2]。聚类分析已经成为当前非常重要的研究方向, 广泛的应用在模式识别、数据分析、图像处理、市场研究以及生物学等领域[3]。
K-means[4]是一种基于划分的聚类算法, 快速、简洁的特点使得其成为目前应用最为广泛的聚类算法。但原始的k-means算法也存在一些缺陷:算法要求用户事先给定k值, 在实际中由于缺乏经验, k值一般难以确定;对初始聚类中心敏感, 不同的初始聚类中心, 可能会导致不同的聚类结果[5]。本文提出一种基于数据场的k-means改进算法, 该算法利用数据场的势函数来计算对象间的紧密程度, 确定聚类个数k以及k个初始聚类中心, 解决了上述问题。该算法不需要人为输入参数, 仿真实验结果表明, 该算法能准确找到聚类中心, 聚类效果优良。
1 数据场基础
借鉴物理场的思想, 李德毅院士将物质粒子间的相互作用引入抽象的数域空间, 提出数据场。数据场把任意一个数据的状态看作是数域空间中所有数据共同作用的结果[6]。
定义1:给定p维空间, 包含n个对象的数据集D={x1, x2, …, xn}及其产生的数据场, 空间任一点x的势值为:
其中, |x-xi|表示场点与对象之间的范数距离;σ为影响因子;将上述势值计算公式称为势函数, 可以发现其为高斯核函数。
以势值来衡量数据场中单个对象的作用范围, 如图1所示。由高斯函数的“3σ规则”可知:每个对象的影响范围是以该对象为中心、半径等于的邻域空间, 即对象间的相互作用力程为
单个对象数据场影响半径R的性质:1、σ越小, R越小, 即对象间的相互作用力程越小;2、σ越小, 势函数衰减速度越快。
数据场有如下性质:
独立性:每个对象点都以自己为中心, 向外辐射能量而不受外界的影响, 如图2, 对象A与B各自分别以自身为中心向四周辐射能量;
叠加性:每个对象点的势值等于等于该空间中各个点在该点产生的能量总和, 如图2, 位置1、2处的势值分别为对象A、B在此处势值的叠加总和;
衰减性:势值随着距离的增加快速下降, 距离场源越近势值越大, 反之, 势值越小, 当超出一定距离后, 其产生的能量可以忽略不计, 如图1所示。
2 基于数据场的k-means改进算法
本文提出一种基于数据场的k-means改进算法, 该算法通过计算所有数据点的势值和到比它势值更大的数据点之间的最小距离, 根据势值和距离的分布决策图, 将势值较大且与比它势值更大的数据点有较大距离的数据点作为聚类中心, 最后将其它数据点按k-means算法聚类, 得到最终的聚类结果。
算法流程描述如下:
Step 1:计算任意两个数据对象点之间的标准距离dij;
Step 2:影响因子优化σ;
Step 3:计算数据对象点的势值
Step 4:确定k个聚类中心;
Step 5:k-means算法聚类。
2.1 标准距离计算
为解决原始数据各维度量纲不一致, 数据之间没有可操作性等问题, 本文采用min-max标准化, 将原始数据转换成无量纲化指标, 使得数据之间具有可操作性。
定义2:设包含n个对象D={x1, x2, …, xn}的数据集, 标准化后的值如下:
定义3:给定n维空间中任意两点xi, xj, 它们之间的欧式距离:
dij具有下述的三个属性:
(1) 非负性:dij≥0;
2.2 影响因子σ
σ用于控制对象间的相互作用力程, 其取值会影响数据场的空间分布。本文采用淦文燕等提出的基于最小势熵的σ优化算法[7]。
定义4:令对象xi的势值为则势熵为:
其中, 为一个标准化因子。
势熵H取最小值时, 对应的σ即为最优值。即:
此方程为单变量非线性函数的最小化问题, 本文采用初始区间为的线性探查法优化σ。步骤如下:
2.3 确定聚类中心
定义5:对于包含n个对象的数据集, 任一对象点i到比自身势值更大的对象点之间的距离设为势值大于当前对象势值中的距离的最小值。即:
其中, 对于具有最大势值的对象, 将其距离设置为距离的最大值。
定义聚类中心具有这样的特点:它们被很多点围绕, 导致局部势值大, 且与局部势值比自己大的点之间的距离较远, 因此聚类中心是势值与距离都较大的点。如图3 (a) 数据分布图所示, 通过观察得知, 数据点1、6为聚类中心, 21、22为孤立点。在图3 (b) 决策图中, 数据点1、6距离δ与势值φ都比较大, 数据点21、22距离较大, 但势值很小, 其它数据点的距离都较小。
3 仿真实验
为验证本文算法的可行性, 进行了仿真实验, 实验采用表1中的5个数据集进行测试, 前4个数据集来自文献[8], 第五个数据集为UCI数据集。前4个数据集的原始分布如图4所示, 其聚类中心结果展示如图5。
由于k-means算法每次选取的聚类中心不一样, 导致聚类结果有差异, 表2为iris数据集在k-means算法中进行5次试验的准确率及在改进k-means算法中的准确率。实验表明, 在k-means算法中, iris数据集中每次实验的准确率都不同, 5次试验平均准确率为72.52%, 而改进k-means初始聚类中心固定, 准确率为92.6%, 改进k-means算法具有良好的聚类质量。
4 结语
本文提出了一种基于数据场的k-means改进算法, 具有较好的自适应性, 能够对任意形状的数据集找出聚类的个数k以及聚类中心的位置, 提高了k-means算法的准确度。但由于kmeans算法本身存在"球形偏见", 对非球形形状的数据集聚类质量不高。
摘要：针对k-means算法需要人为给出聚类个数k、聚类结果严重依赖初始聚类中心的选等问题, 提出一种基于数据场的k-means改进算法。该算法通过计算每个数据点的势值, 根据聚类中心的势值比周围邻居的势值大, 并与其它聚类中心有相对较大距离的特点, 从而确定k个聚类中心;最后将其它数据点按k-means算法聚类。仿真实验表明, 改进算法在不需要人为设定参数的情况下能准确找出聚类个数k以及初始聚类中心。
关键词：k-means,聚类中心,数据场,聚类
参考文献
[1]郭锋.基于数据场的聚类方法研究[D].哈尔滨工程大学, 2009.
[2]伍育红.聚类算法综述[J].计算机科学, 2015, 42 (s1) .
[3]贺玲, 吴玲达, 蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用研究, 2007 (1) :10-13.
[4]Macqueen J.Some Methods for Classification and Analysis of Multi Variate Observations[C]//Proc.of, Berkeley Symposium on Mathematical Statistics and Probability.1967:281-297.
[5]Rodriguez A, Laio A.Clustering by fast search and find of density peaks.[J].Science, 2014, 344 (6191) :1492-1496.
[6]李德毅, 杜鹢.不确定性人工智能[M].国防工业出版社, 2004.
[7]淦文燕, 李德毅, 王建民.一种基于数据场的层次聚类方法[J].电子学报, 2006, 34 (2) :258-2
k-means算法 篇4
手机恶意软件的危害主要有恶意扣费、窃取账号密码等用户隐私、破坏系统等,其中窃取隐私行为占大多数,一旦有恶意的人获取这些隐私信息,他可以对用户进行诈骗,危害非常大,甚至对国家安全都会造成影响[1]。
另外由于恶意代码使用的技术不断更新,Android系统的恶意软件监测变得越来越困难,Android上的应用在被监测出来之前,已经被用户大量下载了。对Android恶意软件检测十分有必要。但是由于手机内存、运行速度、电池耗电量的限制,Android恶意软件检测在手机上的分析效果不是很理想。因此对Android系统的恶意软件进行高效的检测十分必要。
1 相关工作
Android恶意软件检测目前主要采用静态分析和动态分析两种技术。静态分析技术主要采用分析Android软件的源代码或者二进制代码,找出可疑行为,通过分析Android权限和调用函数等内容,根据特定模型,判定是否为恶意软件。权限分析主要针对Android Manifest.xml文件进行自动化分析,提取per⁃mission、activity、service、receive和provider组件进行特征提取,然后根据特定的类别进行设置[2]。而调用函数分析则通过An⁃droid平台的虚拟机Dalvik指令特点,定义形式化描述语言,描述恶意软件[3,8],或者通过native代码使用lib库文件进行分析,提取函数调用序列,完成软件判定[4,9]。静态恶意代码检测优点是覆盖率高,缺点是无法检测代码混淆、加密,而且无法分辨发短信等在动态执行中才可以判定的恶意行为。
动态分析技术主要采用沙盒技术,通过模拟应用软件的操作过程,自动完成软件的安装,用户操作,用户卸载等操作实现恶意软件判定。动态分析可以分享Android系统的系统调用频率数,根据一些特殊调用在系统恶意代码执行时出现波动的现象进行恶意软件判定,另外还可以使用mokeyrunner等工具模拟用户行为,点击应用程序,模拟运行,根据模拟数据建立用户活动模型,实现恶意行为判定[5,7]。但是这种检测方法工作量大,分析时间长,在手机上运行实时性不高,资源消耗过大。
另外为了提高分析的准确性,还有作者提出来基于静态分析和动态分析相结合的多类特征恶意行为检测系统THEA[7],或者基于权限类别的恶意检测程序[2]。但这些程序对恶意程序检测存在着各种问题,因此本文提出基于k NN算法的Android恶意软件监测算法。
2 特征代码提取
特征代码采用静态与动态分析相结合的方式,选取权限、系统函数调用作为特征代码。使用Android SDK自带的AAPT打包工具,对APK进行解压,提取Android Manifest.xml文件和lib库文件(.so文件)。根据Android Manifest.xml的内容生成特征代码向量P,其中P={permission,activity,service,receiver,pro⁃vider}。对.so文件进行合并后,提取动态符号表中的函数信息,对数据应用程序进行统计,提取最能描述系统功能的函数生成向量L,其中L={open,icocl,read,write,sendmsg,recvfrom,recvmsg,access,chmod,chown}。
动态分析通过模拟器调用APK文件,模拟打电话、发短信等操作,然后使用trace和wireshark工具动态检测系统调用日志、系统API和网络数据,并使用mokeyrunner工具模拟用户行为,获取用户行为数据,生成向量U,其中U={trace,wireshark,mokeyrunner}。
特征码向量采用这几个数据构成,M={P,L,U}T。向量相异度采用欧几里得距离,向量X与Y之间的相异度:
3 相关算法实现
3.1 k NN算法简介
k NN算法又被称为k近邻分类(k-nearest neighbor classifi⁃cation)算法,就是在测试组中找和训练元组向量空间上最接近的k个点中,类别最多的那个分类。由于向量组中部分值由于取值范围大,对距离的影响高,不利于反映真实的相异度,需对属性值进行规格化,将各个属性按比例均映射到[0,1]区间,以平衡各个属性对距离的影响,映射公式为:
这里Xi为向量X的第i个分量。
Android程序被分为2种,正常应用和恶意应用,根据分组,计算Android程序类别,分类结果离待测向量最近的为其所属类别。
在试验过程中,发现恶意程序应用判定中权限向量P和用户行为向量U在恶意程序中异常情况比较突出,而系统功能函数往往只是调用一两次,对异常情况判定影响较小,可以对这种情况设置不同的权值,增加判定的准确率。向量X的属性可以设置为:
αi的取值根据试验设定。
3.2 基于k-means算法的改进
基于k NN算法的Android恶意软件监测实现比较简单,是数据挖掘分类技术中的最简单方法,比较适合对稀有事物进行分类。但是算法如果样本不平衡时,比如现阶段恶意软件数目较少,正常软件类数目较大,导致正常软件样本占大多数,有可能k个邻居中占有概率大,造成无论怎样,目标软件都判定为正常软件。
因此可以对恶意软件类和正常软件类进行初始化数据处理,通过K-means算法分别计算出分类的N个质心。K-means算法是一种非监督实时算法,可以在最新误差函数的基础上将数据划分为预定的类数。通过指定聚类数目N和迭代次数或收敛条件,根据一定的相似性原则,分配相似的质心,形成类,然后以每一类的平均矢量作为新的质心,反复迭代直至收敛或者达到最大迭代数目。
K-means的质心可以采用下面的公式计算:
其中Kj为软件训练类的质心,Vi为训练软件特征向量,为训练矢量与质心的关联程度。其取值只能是0和1,其中0代表空隶属度,1代表着全隶属度,计算公式如下:
εK-means算法的收敛条件可以设置一个阈值ε,γ(k)当误差率低于ε,γ(k)可以终止算法,的定义如下:
其中D为误差方差,公式如下:
K-means算法描述如下:
步骤1:选择误差门限ε;
步骤2:初始化质心,根据公式(6)(7)计算,k=0;
步骤3:k=k+1;
步骤4:使用公式(4)(5)计算;
步骤5:根据公式(6)(7)计算D(k),γ(k),,如果,跳转至步骤3;
步骤6:结束。
3.3 k NN算法描述
在对Android恶意软件判定之前,首先对恶意软件和正常软件的训练集进行K-means初始化,获得这两个集合的质心向量组,作为检测程序的样本向量,根据这些样本向量,运行An⁃droid恶意检测算法,算法描述如下:
步骤1:获取Android程序的特征代码P,L,U;
步骤:根据公式()()计算特征向量;
步骤3:根据公式(1)计算特征向量M与正常应用和恶意应用组的相异度;
步骤4:按照相异度进行递增排序;
步骤5:选取最近的k个特征向量;
步骤6:统计这k个特征向量在正常应用和恶意应用的数目,返回最多的一个;
步骤7:根据返回值判定结果。
4 实验分析
为了评估算法的有效性,本文将算法与近年来的相关工作进行对比,使用相同的测试样本进行判断分析。样例主要是从Google Play或者国内的第三方Android市场上下载,一共179个恶意软件,3021个正常软件,对比结果如下:
从对比表中可以看出,本文算法比单纯的静态或动态检测的方法判定率都高,但是在恶意软件判定率方面比Androdect算法差,有待提高。本文算法实现简单,对系统资源耗费更少,更适合在有限资源的移动系统中实现。实验表明本文算法比Androdect算法更容易在Android系统中实现。
5 总结
本文采用了静态和动态结合的技术获取Android应用程序的特征向量,并在此基础上设计了k NN分类算法和K-means聚类算法相结合恶意软件检测模型,并实现了恶意检测算法。该算法弥补了单纯静态或单纯动态监测的不足,在对大量程序的测试中,算法表现良好。实验结果表明算法的准确率和执行效率上表现良好,优于大部分恶意代码检测工具。下一步将k NN分类算法和K-means聚类算法结合到云计算上面,进一步完善算法,并对恶意软件库进行云存储,提高系统的运行速度和判定准确率。
摘要：目前针对Android恶意应用可以采用静态或者动态分析的方法获取软件的特征,并根据这些特征采用特定的算法进行检测,但单一的分析方法无法充分体现Android应用的多样性。该文首次提出一种分析Android应用权限、调用和动作等特征,使用k NN分类算法识别正常应用和恶意应用。同时为了提高分类的正确性,该文还采用了K-means算法对训练类进行初始化。实验表明本文算法能够充分利用Android多样的特征有效检测恶意应用,并且与相关工作对比,算法在检测效率和执行效率上表现更好。
关键词：kNN,K-means,Android,恶意软件检测
参考文献
[1]边悦,戴航,慕德俊.Android恶意软件特征研究[J].计算机技术与发展,2014,24(11):178-181.
[2]杨欢,张玉清,胡予濮,等.基于权限频繁模式挖掘算法的Android恶意应用检测方法[J].通信学报,2013,34(Z1):106-115.
[3]李挺,董航,袁春阳,等.基于Dalvik指令的Android恶意代码特征描述及验证[J].计算机研究与发展,2014,51(7):1458-1466.
[4]雷灵光,荆继武,王跃武,等.一种基于行为的Android系统资源访问控制方案[J].计算机研究与发展,2014,51(5):1028-1038.
[5]蔡志标,彭新光.基于系统调用的Android恶意软件监测[J].计算机工程与设计,2013,34(11):3757-3761.
[6]杨欢,张玉清,胡予濮,等.基于多类特征Android应用恶意行为检测系统[J].计算机学报,2014,37(1):15-25.
[7]S.Asaf,K.Uri,E.Yuval,et al.Andromaly:A behavioral mal-ware detection framework for Android devices[J].Journal of In-telligent Information Systems.2012,38(1):161-190.
[8]Wu Dong-Jie,Mao Ching-hao,Wei Te-En,et al.Droid Mat:Android malware detection through manifest and API callstracing//Proceedings of the Seventh Asia Joint Conference onInformation Security(Asia JCIS 2012).Tokyo Japan,2012:62-69.
k-means算法 篇5
聚类就是对数据集中的数据分组, 使得组内数据具有高度的相似性, 而组间的数据有较大的相异性。聚类分析是一种重要的数据分析方法, 广泛应用于数据挖掘、模式识别、机器学习等领域。
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算法 篇6
文本聚类作为文本处理领域非常重要的组成部分,可以为自然语言处理、信息检索、搜索引擎和问答系统等领域提供基础支撑,文本聚类已经在当前的文本挖掘领域领域占据着非常的重要的地位。信息检索和搜索引擎系统通过对数据库中无类别文本进行聚类操作将文本转换为规则化可处理文本,问答系统需要对短文本进行聚类操作,将文本转换为有价值的结构化数据,文本聚类具有非常重要的现实意义。
文本聚类主要是依据著名的聚类假设:同类的文档相似度较大,而不同类的文档相似度较小。作为一种无监督的机器学习方法,聚类由于不需要训练过程,以及不需要预先对文档手工标注类别,因此具有一定的灵活性和较高的自动化处理能力,已经成为对文本信息进行有效地组织、摘要和导航的重要手段,为越来越多的研究人员所关注。
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算法 篇7
K-means算法是一种使用广泛的分割聚类算法,它取类中所有样本点的平均值作为类的中心,因此k-means聚类算法易受孤立点数据的影响,导致算法可能收敛于局部最优值。为避免此问题的出现,该文介绍一种优化初始聚类中心的改进k-means算法,它基本消除了孤立点对聚类结果的影响,使聚类准确率获得明显提高。
1基于初始中心优化的k-means算法
传统K-means算法对初始聚类中心具有较强的依赖性,不同的初始中心导致每次的聚类结果有所不同。通常,我们选择相互距离最远的k个数据对象作为中心点,但是如果仅基于距离,容易取到噪声数据,因此在选择初始聚类中心时,我们可以将密度和距离因素都考虑在内。为此,该文提出了基于密度和距离的优化初始中心的k-means算法,优化算法的主要思想是取相距最远的处于高密度区域的k个样本点作为初始聚类中心。下面定义样本点α 所处区域的密度:
其中D为样本点集,r为球体半径, Dis (α,d)为距离测量。样本点 α 所处区域的密度是以 α为中心,r为半径的球体所包含的样本点数。半径r的确定方法如下:
<1> 求解每两个数据对象的距离,然后求出所有距离的均值 λ
<2> 用户根据经验给出一个常数β,半径r = λ * β
求出每个样本点所处区域的密度, 然后将高密度区域中的所有点组成集合ZA,在集合中取Density值最大的样本点作为第一个初始中心c1,然后取离c1最远的高密度样本点作为第二个初始中心c2,然后取满足max(min(d(αi, c1),d(αi,c2))) i=1,2,…,n的样本点αi作为第三个初始中心c3,依次类推,取满足max(min(d(αi,c1),d(αi,c2),… d(αi,cq-1))) i=1,2,…,n的样本点 αi作为cq,最后确定了聚类的k个初始中心。
综上所述,改进算法取距离最远的k个高密度样本点作为聚类的初始中心, 这些中心点基本上是稳定的,进而消除了初始中心选择的随机性,提高了聚类结果的精确度。
2实验
为证明优化算法的高效性,本文采用两种数据集对算法进行测试,分别从初始中心,循环次数,准确度三个方面对传统K-means(KMS) 算法,优化的K-means(PKMA) 算法的实验结果进行比较。其中Iris数据集为160,每个数据有5个属性属性,正确聚类个数为4, glass数据集为220, 每个数据有10个属性,正确聚类个数为5。
由表1可以看出,传统k-means算法平均收敛速度较慢,并且聚类结果的平均正确率较低。相反,改进算法不仅结果平均正确率高于传统k-means算法, 而且收敛速度获得明显提高。从实验结果中还可得出,传统k-means算法的收敛速度有时优于PKMA,但结果正确率低于60%。这表明传统k-means算法的初始聚类中心易受孤立点和噪声数据的影响而使聚类结果收敛于局部最优值, 降低了聚类质量;而PKMA算法的优化初始中心基本符合数据的实际分布,使算法尽快收敛于全局最优值,从而提高了聚类正确率。
3结论