k-mean聚类算法论文（共7篇）
k-mean聚类算法论文 篇1
引言
聚类的基本任务是为对象集合中所有存在特征相似或接近的对象个体进行类别标记。目前,比较流行的聚类方法有划分法、层次法、密度法、网格法等。在众多的聚类方法中,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,算法,近邻传播算法,聚类中心
k-mean聚类算法论文 篇2
聚类就是对数据集中的数据分组, 使得组内数据具有高度的相似性, 而组间的数据有较大的相异性。聚类分析是一种重要的数据分析方法, 广泛应用于数据挖掘、模式识别、机器学习等领域。
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-mean聚类算法论文 篇3
K-Means算法属于聚类方法中一种基本的划分方法, 常采用误差平方和准则函数作为聚类准则函数, 如下式所示:
针对传统K-Means算法存在的对初始聚类中心选择敏感和分类正确率较低的问题, 笔者通过优选初始聚类中心和引入模糊逻辑, 提出一种改进的模糊K-Means聚类算法, 实验结果表明该算法可以取得较高的稳定性和分类正确率。
1 传统K-Means算法思想
传统K-Means算法基本思想描述如下:
输入:k:簇的数目;
D:包含n个对象的数据集。
输出:k个簇的集合。
方法:从D中任意选择k个对象作为初始簇中心;Repeat;根据簇中对象的均值, 将每个对象分配到最相似的簇;更新簇均值, 即重新计算每个簇中对象的均值;Until不再发生变化。
2 改进的模糊K-Means算法
2.1 优化选择初始聚类中心
笔者采用一种聚类中心点替换方法来实现初始聚类中心的选择。输入一个极小值ε, 令K-Means算法在第m次和m-1次迭代分别产生的第j类的聚类中心分别记为Cj和C'j (j=1 to k, k是聚类个数) , 令二者的差值为D=j||Cj-C'j||, 若Dj<ε, 则定义聚类中心Dj, 为稳定聚类中心, 并在下一次迭代中不计算第j类的新的聚类中心;否则定义其为活动聚类中心, 在下一次迭代中继续计算这个类的新的聚类中心并计算Dj进行判断是否为稳定聚类中心。直到所有聚类中心均为稳定聚类中心, 则得到了优选初始聚类中心{Cj (0) }, j=1 to K。
2.2 模糊K-Means算法
FKM算法步骤描述如下:
(1) 输入:
ε':目标函数J收敛阈值;
P=0:迭代次数。
(2) 根据一组聚类中心SCp, 计算dij (i=1 to N, j=1 to K) 。用下式更新隶属度ui.j。
(3) 计算新的聚类中心如下:
3 实验结果
笔者采用的测试数据集是Iris数据集, 该数据集是检测监督或非监督学习算法性能的一个标准测试集。该数据集包含3类4维样本, 其中, 每类样本数目为50, 且服从正态分布, 三类分别为:Setosa, Versicolor, Virginica (其中, Setosa在特征空间上是明显区别于其他两类的, 而剩余的两类在特征空间上有一定相似度) 。
4 结语
笔者针对传统K-Means算法存在的缺点提出进行初始聚类中心优选的模糊K-Means算法, 通过实验结果表明该算法有较高的分类准确率。
摘要：笔者提出一种改进的模糊K-Means聚类算法, 通过合理选取初始聚类中心, 在提高了分类准确率的同时在一定程度上避免了聚类结果陷入局部最优的现象。实验结果表明, 改进的模糊K-Means算法比传统K-Means算法具有更高的分类准确率。
关键词：模糊K-Means,初始聚类中心,局部最优
参考文献
[1]孙吉贵, 刘杰, 赵连宇.聚类算法研究[J].软件学报, 2008, 19 (1) :48-49.
[2]Douglis F, Ousterhout J.Transparent process migration:Design alternatives and the Sprite implementation[J].Software-Practice and Experience, 1991, 21 (8) :757-786.
[3]张玉芳, 毛嘉莉, 熊忠阳.一种改进的K-means算法[J].计算机应用, 2003, 23 (8) :31.
[4]Carvalho F, Tenório C.Fuzzy K-means clustering algorithms for interval-valued data based on adaptive quadratic distances[J].Fuzzy Sets and Systems, 2010, 16 (1) :2979-2980.
k-mean聚类算法论文 篇4
K-means聚类算法是最为经典的基于划分的聚类算法, 该算法的最大优势在与简洁和快速, 但是该算法聚类效果的好坏取决于初始中心的选择和距离公式。同时, Hierarchical聚类在处理大量数据时, 会生成一个高维的矩阵, 导致时间效率低。
本算法模型正是针对K-means聚类对大量数据进行降维, 以此降低Hierarchical聚类的时间效率, 同时利用Hierarchical提高了K-means的聚类效果并实现k值的选取。
1结合Hierarchical聚类和K-means聚类算法的算法模型
本模型主要分为一下几步:首先对数据进行预估, 预设一个合适的k值 (大于目标类数, 远小于总样本数) , 使用K-means聚类进行聚类操作;然后对k个类的平均中心点进行Hierarchical聚类操作, 生成一棵树;最后通过判断k个类的中心点的拐点, 对这个树进行剪枝, 从而生成newk个子树, 即newk个类。
该模型的算法流程如下:
输入:k, data[m, n];
(1) K-means聚类:
1.选择k个初始中心点, c[k, n];
2.对于data[m, n]中的每一行m, 寻找距离其最近的中心点I (i∈k) , 标记data[m, :]为I;
3.对于所有标记为i的点, 重新计算中心点 (使用所有标记为i的点的平均数)
4.重复2, 3, 直至循环10次;
(2) Hierarchical聚类:
5.对4中生成的k个中心点计算两两间的距离, 生成距离矩阵
6.选择最近的两个中心点, 合并生成新的中心点, 使用两个类中的所有点的平均值代表新的中心点
7.重新生成距离矩阵
8.重复6和7, 直到合并成一个类为止
(3) 剪枝操作:
9.根据8生成的树中每一步合并操作时, 两个子节点之间的距离, 计算拐点
10.根据计算的拐点进行剪枝, 得到newk个子树
2实验评价
本模型中的K-means聚类和Hierarchical聚类使用Python编程实现, 利用了sklearn工具中实现的聚类算法KMeans和hierarchy数据结构。实验机器配置为:Intel Core i7-3537U 2.00GHz CPU, 8.00GB内存;Python 2.7.5 (32 bit) 。
数据样本为900条时:
数据样本为1600:
3结束语
本模型通过结合Hierarchical聚类和K-means聚类算法, 实现了一种新的聚类方式。从实验结果可以看出本方法在处理大量高维数据时效果明显, 时间效率低且聚类效果更好。本算法仍存在不足:需要预设一个合适的较大的k值, 此k值不宜过大, 太大会导致算法效率的降低;另一方面, 此值也不能小于聚类效果最好时的类数, 否则聚类效果不理想。基于此点, 需要在使用前根据数据样本进行预估, 然后给出一个较为合适的k值, 或者进行几次实验进行探索。本算法已经实现了k值的自动选择, 也大大减小了在探索过程中所需的时间和精力。
摘要：为了解决进行K-means聚类时类数的自动选择和Hierarchical聚类在处理大量高维数据时时间效率低的问题, 在Kmeans聚类算法的基础上结合Hierarchical聚类算法, 提出了一种基于集体智慧编程方法的用于处理大量数据时动态选取K值的聚类模型。实验结果表明该算法比K-means聚类具有更好的聚类效果, 同时解决了Hierarchical聚类方法时间效率低的问题。本模型通过K-means聚类生成适量的类簇, 再利用Hierarchical聚类对这些类再进行聚类, 最后经过剪枝得到合适的聚类结果, 以此实现动态选取K值。
关键词：K-means聚类,Hierarchical聚类,降维,剪枝
参考文献
[1]王千, 王成, 冯振元.叶金凤K-means聚类算法研究综述[J].电子设计工程, 2012 (7) .
[2]胡伟.改进的层次K均值聚类算法[J].计算机工程与应用, 2013, 49 (2) .
k-mean聚类算法论文 篇5
关键词：数据挖掘,聚类算法,K-means,入侵检测
0 引 言
聚类分析 是将海量 的数据划 分为有意 义或者有 用的组 (簇 )。在同一 簇中的数 据相似度 较高 ,不同的簇 中数据差别 比较大。 聚类分析 主要基于 距离进行 分析 ,它是一种无 监视的学 习训练方 式。
K - means聚类算法 是基于划 分的经典 算法 , 但存在难以 确定初始 聚类中心 值、受噪声 及孤立点 影响较大 的缺点 [1]。基于此 , 很多学者 研究提出 了不同的 改进Kmeans聚类算法 的方法。 参考文献 [ 2 ] 把相互距 离最远的K个高密度 区域的点 作为初始 聚类中心 点 ; 参考文献 [ 3]利用密度 指针初始 化聚类中 心 ,从而从真 实聚类中 心中选取数 据库初始 化聚类中 心 ; 参考文献 [4] 利用密度 和最近邻的 思想来寻 找初始聚 类中心 ; 参考文献 [5] 基于最优划 分初始聚 类中心 ,该算法首 先对数据 样本进行 划分 , 根据划分 样本的分 布特点确 定初始聚 类中心 ; 参考文献 [6] 利用伪随 机数产生 初始聚类 中心 , 但聚类数 据庞大时 ,聚类效果 不容乐观 。参考文 献[7]通过对样 本数据进行 阈值分层 快速确定K-means算法的聚 类数搜索范 围及其上 限 ,利用新的 聚类有效 性指标评 价聚类后 类内与类间 的相似性 程度 ,从而在聚 类数搜索 范围内获 得最佳聚类 数。
1 聚类分析的相似性度量和准则函数
1 . 1 相 似 性 度 量
聚类分析 是依据对 象两两之 间的相似 (或差异)程度来划分 类的 , 而这相似 程度通常 是用距离 来衡量的 [8]。最广泛使 用的距离 计算公式 是欧氏距 离 :
其中 ,i=(xi1, xi2, … , xip) , j = ( xj1, xj2, … , xjp) 。
1 . 2 准 则 函 数
聚类结果 的质量可 以由聚类 准则函数 来判断 , 若准则函数 选的好 , 质量就会 高 ; 反之 , 质量达不 到要求时 ,则须反复 运行聚类 过程[9]。一般的 聚类准则 函数有以 下3种 : ( 1 ) 误差平方 和准则 ; (2 ) 加权平均 平方距离 和准则 ;( 3 ) 加权类间 距离和准 则。
2 K - means 聚 类算法分析
2 . 1 K - means 算 法 过 程
K - means聚类的算 法流程如 下 :
输入 : 含有n个对象的 数据集X={xi| xi∈Rd, i = 1 , 2 ,… , n } , 聚类的个 数k。
输出 :k个类W1, W2, … , Wk。
(1 ) 从数据集X中随机选 取k个初始聚 类中心c1,c2,… , ck。
( 2 ) 依据初始 聚类中心c1, c2, … , ck对数据集 进行划分 , 划分根据 以下原则 : 若dij( xi, cj) < dim( xi, cm) , 其中dij( xi, cj) 是xi与cj的欧式距 离 ,m=1,2,… ,k,j=1,2,… ,k , j≠m , i = 1 , 2 , … , n , 则将xi划分到类cj。
( 5 ) 输出聚类 结果。
K - means聚类算法 的流程如 图1所示。
2 . 2 K - means 算 法 缺 点
( 1 ) K - means算法需要 首先设定K值 , 而算法运 算中K是一个敏感值 ,不同的K值可能会造成不同的运算结果。
( 2 ) 对于一些 噪声和孤 立的数据 较为敏感 。
( 3 ) 簇的平均 值只有被 定义才能 使用 , 这不利于 处理一些有 特殊属性 的数据。
2 . 3 K - means 算 法 的 改 进
( 1 ) 改进初始 值K , 尽量减少 人工干预
利用类间 相异度与 类内相异 度来确定 最终的K值 ,具体分3步来实现 : 首先 , 选取数据 集合的中 间点即所有 数据集合 的平均值 , 利用欧几 里得距离 计算公式 ,计算出距离 中间点最 远距离的 对象N1,再计算出 与N1距离最远的 对象N2,筛选出初 始聚类中 心。其次 计算剩余数 据对象与 数据中心 集合间的 距离 , 取最小距 离D, 计算聚类中 心之间的 距离 ,找出最小 距离C,如果D<C,则将对象放 入到最小 距离的聚 合中 ,否则将其 纳入初始 聚合中心 , 生成新的 聚合中心 , 后面的数 据依次与 聚合中心间 最小距离 与D对比 , 循环所有 数据 , 最终形成 聚类中心集 。最后 ,采用类间 相异度与 类内相异 度来确定 最终的聚类 个数K值。
类内的相 异程度DOC:
类间相异 度DAC:
改进后的 计算方法 如下 :
输入 : 含有n个对象的 数据集X={xi| xi∈Rd, i = 1 , 2 ,… , n } 。
输出 :k个类W1, W2, … , Wk。
1对聚类中 心进行初 始化 ,获得3个聚类中 心。根据公式计算出第1个聚类中心m0,再根据欧几里得距 离计算出与m0最远的数 据对象作 为第2个聚类中心m1, 最后计算 出与m1距离最远 的数据对 象当成第3个聚类中 心m2。
2根据欧几 里得公式 计算数据 集和聚类 中心的距离 ,归类所有 数据 ,重新计算 聚类中心 。
3计算剩余 数据对象 与聚类中 心的最小 距离D及聚类中心 之间的最 小距离C, 计算出此 时的类内 相异度DOC_old和此时的 类间相异 度DAC_old。
4如果D>C, 则把这个 数据对象 作为新的 聚类中心 ,并且计算 新的类内 相异度DOC_new和新的类 间相异度DAC_new,运行步骤5;否则转到 步骤6。
5如果DOC_new <DOC_old且DAC_new >DAC_old则产生新类 , 转到步骤2重复步骤2~5 ; 否则恢复 状态 ,执行步骤6。
6取下一个 类Wi, 如果没有 新的类 , 则转到步 骤7 ;否则反复 执行步骤2~5。
7输出聚类 结果。
( 2 ) 对噪声和 孤立点处 理能力的 改进
有时孤立 点或噪声 具有入侵 特征 , 容易干扰K means算法的聚 类结果 , 这里改进 原始算法 来消弱噪 声和孤立点 的影响。 对于数据 集中的所 有点i,计算出每 一点与剩余 点的距离 和Si, 同时计算 出距离均 和H , 当Si> H时 , 则点i被当做孤 立点处理 。其中n为样本数据 ,d为数据维 数。计算 如下 :
算法描述 如下 :
1输入数据 集 ,利用上述 公式计算 每一Si和H;
2对于每一 点i,如果Si> H , 则将i作为孤立 点 ;
3删除孤立 点 ,获得新的 数据集。
3 改进算法在入侵检测系统中的应用及仿真分析
针对于入 侵检测系 统的缺陷 , 给出了基 于改进算法 的入侵检 测模型流 程 ,如图2所示。
系统检测的对象是网络日志中的数据。先做标准化处理,再进行聚类分析。通过筛选孤立点和改进聚类中心从而提高聚类的准确性。接着进入决策报警分析系统。根据聚类的结果甄别具有攻击特征的记录,一旦发现潜在威胁马上启动报警系统 ,阻止相关攻击的进一 步操作 ,并报告网络管理 者,与此同时挖掘其他 的潜在特征 ,为以后判断攻击提供必要的依据。若没有发现攻击行为则继续监视网络动态。对网络日志文件进行标准化的同时,也将其存入历史数据库中。并进行标准化处理和特征挖掘,进而数据匹配分类,构建成分类器。在分类器的反复训练下可从这些记录中挖掘出正常和非正常行为, 并存入到规则库中,作为今后判断入侵行为的决策机构。
表1列出的是20条网络连 接记录的 特征数据 。其中 ,count表示目标 主机与当 前连接相 同的次数 ;SY_error表示SYN错误连接 所占的百 分数 ;same_srv表示目标 端口相同连 接的百分 数 ;Dif_srv表示目标 端口不同 连接的百分 数 ;Srv_count表示目标 主机与当 前连接相 同的次数 ;Srv_serror表示SYN连接错误 的百分数 ;Rv_dif_host表示目标 端口不同 连接的百 分数[10]。本文主 要对三维 数组 (count,Srv_serror,Srv_count)进行分析 。三组特 征数据的空 间分布图 如图3所示。
这个三维 数组基本 显示了数 据是否具 有攻击特 征。通过分 析这3个参数可 以区分攻 击行为、异 常行为和 正常行为。 当目标端 口与当前 连接相同 的次数大 于15次 ,并且主机 出现错误SYN连接的百 分数大于85% , 目标端口与 当前连接 相同次数 大于25次时认为 是攻击行为 ; 若目标端 口与当前 连接相同 的次数大 于6次 , 并且主机出 现错误SYN连接的百 分数大于75% , 目标端口与 当前连接 相同次数 大于6次时认为 是异常行 为 ;其他则认为 是正常行 为。
采用传统 的K-means算法聚类 分析3组数据后 将20条数据信 息分为3类 : 记录3为攻击行 为 ( 即图4中圆形区域 );记录4,5,6,12,13,19,20为异常行 为 (即图4中椭圆区 域 ) ; 其余的记 录为正常 行为 ( 即图4中矩形区域 )。根据上 述3种行为的 特征 ,可以将攻 击、异常 和正常行为 区分开来 。传统K-means算法却不 能进一步分 析异常行 为是否有 攻击特征 。传统K-means算法对实验 数据聚类 分析的空 间结果如 图4所示。
改进算法 会分离出 记录3 ( 孤立点 ), 并判断其 为攻击行为 ,如图5中圆形区 域。改进 的K-means算法将剩余 的19条记录聚 类为三部 分 ,记录4,5,6,12,13,19,20为异常行 为(如图5中椭圆区 域),其中5,19接近于攻 击行为(如图5中正方形区域)。其余的记录为正常行为。改进算 法有效地 提高了检 测的准确 率。改进 的K -means算法对实 验数据聚 类分析的 空间结果 如图5所示。
4 总 结
k-mean聚类算法论文 篇6
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.
k-mean聚类算法论文 篇7
关键词：k-means算法,信息熵,最优样本抽取,有效性指标
0 引言
聚类是数据挖掘中重要的三个领域 (关联规则, 聚类和分类) 之一。它按照特定要求, 对待分类的对象进行分类, 要求类内相似度尽可能最大, 同时类间相似度尽可能最小。k-means[1]算法因其简单实用而成为应用和研究最广泛的算法之一。但是该算法需要事先确定k值, 而确定最佳k值一直也是聚类有效性研究的重要课题。一般情况下, 确定最佳k值的基本思想为:在k值取值范围内运行k-means算法, 得到不同的结果, 选择合适的有效性评估指标对结果进行评估, 最终确定最佳k值。近年来, 许多研究人员对于如何确定最佳k值进行了深入的研究。包括聚类有效性指的研究, 如XB (Xie-Beni) [2], KL (Krzanowski-Lai) [3], Sil (Silhouette) [4], DB (Davies - Bouldin) [5], IGP (In - Group Proportion) [6], BWP (Between-Within Proportion) [7]。同时文献[8]研究了k值最优解kopt及其上限kmax的条件, 证明了kmax n 。但是这些研究没有基于海量数据之上, 当数据量急剧扩大时, 以上方法进行确定k值的效率由于数据的急剧扩大而得不偿失。因此, 本文借鉴前人的研究成果, 首先通过引入信息熵对前人的有效性指标进行了改进, 针对海量数据集的数据挖掘, 提出了基于数据抽样的k-mean自动挖掘算法。该算法采用分段抽样策略, 以新指标为有效性验证标准, 通过引入统计最优数据抽样数, 得到抽样数据的k值, 然后将该k值应用到海量数据集上进行聚类, 取得了良好的效果。
1 相关概念和原理
1.1 最优抽样数和抽样策略
衡量抽样效果的两个重要指标分别为样本容量和样本质量[9]。所谓样本容量是指所抽取的样本数, 所谓样本质量是抽样样本的代表性, 是抽样中的一个重要指标。在抽样过程中, 如果样本集的容量越大, 其与原数据集的相似程度也就越好, 因而挖掘出来的结果与从原数据集挖掘结果的一致性也就越好。但是, 抽样后挖掘结果的准确性和效率是一对矛盾体, 样本量大, 准确性高, 效率低;样本量小, 准确性低, 效率高。
另外, 当样本量增加超过一定规模后, 准确性不会有足够的提升, 将在保证结果准确性的情况下, 抽取的最小样本量为最优样本数 (Optimal Sample Size, OSS) , 准确寻找最优样本数非常麻烦, 为此, 本文引入文献[9]中的统计最优样本数来代替OSS。
1.2 基于熵权重的距离度量
为提高算法的性能, 对数据集中计算数据对象距离时采用加权距离, 权重值的计算使用信息熵来确定。数据集中的各维属性对聚类结果的影响程度不同, 并且不同的邻居对该数据的归类也有不同的影响。于是, 本文借鉴文献[10], 引入信息熵的概念度量属性权重的大小, 并进一步求得相邻对相之间的权重系数, 最终求出基于熵权重的距离计算公式。
具体步骤如下:
(1) 设有如下属性值矩阵, 其具有n个对象, m维属性:
(2) 构造属性值属性比重矩阵。为了方便不同的量纲属性值进行比较, 对属性值进行了标准化处理。处理方法为:
式中:rij为对象xi的第j维属性的属性值比重。
(3) 分别计算第j维属性的熵值, 权值:
(4) 计算相邻对象间的权重系数。设对象xj是数据对象xi的某个邻居, 则二者间的权重系数的计算公式如下:
式中:xop表示对象xi的第p维属性值, 对象xo是对象xi的邻居, wp是第p维属性的权值。
从式 (1) 中可以看出, 相邻对象的权重系数是由对象的所有属性, 其所有邻居共同决定, 这样在随后计算距离时就最大限度地考虑了相邻对象之间的相互影响及其所有属性的影响。
那么基于信息熵的距离计算公式为:
利用改进的距离计算公式可以更为准确地计算出各个数据对象之间的差距程度, 在一定程度上提高了聚类的精确度。
1.3 聚类有效性指标
好的聚类划分应使类内尽可能相似, 类间尽可能不相似。目前, 评价聚类结果优劣的指标很多, 前面都提到过, 本文选择BWP指标进行了局部改变, 修改后的指标能更好地评价聚类划分的结果。
设k={X, R}为聚类空间, 其中X= [x1, x2, ..., xn], 需要将样本聚类为c类则修改前的评价有效性指标BWP为:
由于修改前的BWP指标在计算距离时只是使用简单距离公式计算距离, 没有考虑到各属性的权重, 因此, 本文在计算距离时引入信息熵, 使用加权的距离公式, 修改后的指标公式为:
2 基于数据抽样的自动k-means聚类算法
结合以上分析, 提出的具体算法归纳如下:
() 确定最优抽样数;
(2) 在全部数据集中采用简单随机抽样策略抽取OSS个数据进行抽样样本数据聚类;
(3) 选择聚类数的搜索范围[kmin, kmax] , 并且从kmin循环至kmax:
1 调用k-means算法, 距离公式采用式 (2) 对应的距离公式;
2 利用式 (4) 计算单个样本的BWP指标值;
3 计算在该聚类数的平均BWP指标值, 即求所有单个样本BWP的简单算术平均。
(4) 求得平均BWP指标中最大时对应的k为最佳聚类数
(5) 在全部数据集中采用式 (2) 的距离公式, 以上一步求的最佳聚类数k进行聚类。
3 仿真实验与分析
本文实验采用Matlab 2012b开发环境, 在Intel（R）Core（TM）i5 CPU 3.4 GHz, 4 GB内存, Windows XP操作系统上运行。本实验选取UCI机器学习数据库中的Mushroom Database作为实验数据。 该数据库包含8 124 个实例, 23 个属性。在实验前, 需要将stalk-root属性上的空缺值补齐, 然后进行实验。描绘该测试数据集的样本容量和样本质量关系曲线如图1 所示。
设切线斜率阈值为0.2, 计算出本数据集的OSS为604。为了实验, 本文先后抽取了403, 1 005, 1 501 和604 这4 种样本进行抽样聚类, 结果下面会详细分析。针对上述6 组样本进行了本算法的仿真实验, 考虑到k-means算法本身由于初始聚类中心的不确定性, 因此, 本实验进行了10 次实验, 实验结果如表1 所示。从表中可以看出, 第一, 随着样本数的增加, 聚类精度也是提高的, 但是, 精度的提高速度越来越慢, 说明本文引入的抽样方法是最优确定抽样样本数的方法;第二, 从传统的k-means算法和本文算法比较来看, 不论样本数的多寡, 本文的聚类精度都比传统k-means算法精度高。
4 结语
本文通过在传统距离公式中引入信息熵, 并进行加权处理, 并将此改进引入到有效性指标中, 针对大规模数据集的数据挖掘, 提出了基于数据抽样的k-means自动挖掘算法, 该算法采用随机抽样策略, 以新指标为有效性验证标准, 通过引入统计最优数据抽样数, 得到抽样数据的k值, 然后将该k值应用到大规模数据集上进行聚类, 取得了良好的效果。
参考文献
[1]MACQUEEN James.Some methods for classification and analysis of multivariate observations[C]//Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability.California, USA:[s.n.], 1967:281-297.
[2]GAO Xiao-shan, LI Jing, TAO Da-cheng.Fuzziness measurement of fuzzy sets and its application in cluster validity analysis[J].International Journal of Fuzzy Systems, 2007, 9 (4) :188-191.
[3]DUDOIT Sandrine, FRIDLYAND Jane.A prediction-based resampling method for estimating the number of clusters in a dataset[J].Genome biology, 2002, 3 (7) :1-22.
[4]ROUSSEEUW P J.Silhouettes:a graphical aid to the interpretation and validation of cluster analysis[J].Journal of computational and applied mathematics, 1987, 20:53-65.
[5]周世兵, 徐振源, 唐旭清.基于近邻传播算法的最佳聚类数确定方法比较研究[J].计算机科学, 2011, 38 (2) :225-228.
[6]KAPP A V, TIBSHIRANI R.Are clusters found in one dataset present in another dataset?[J].Biostatistics, 2007, 8 (1) :9-31.
[7]周世兵, 徐振源, 唐旭清.k-means算法最佳聚类数确定方法[J].计算机应用, 2010 (8) :1995-1998.
[8]杨善林, 李永森, 胡笑旋, 等.k-means算法中的k值优化问题研究[J].系统工程理论与实践, 2006, 26 (2) :97-101.
[9]于海涛.抽样技术在数据挖掘中的应用研究[D].合肥:合肥工业大学, 2006.