攻读硕士学位研究生试卷（作业）封面（2015 至2016 学年度第一学期）
题目论文选读
科目聚类分析中K-means算法综述
姓名王苑茹
专业计算机技术
入学年月2015年8月
简短评语
成绩：授课教师签字：
聚类分析中K-means算法综述
摘要:聚类分析是数据挖掘中一个极其重要的研究方向，是一个将数据划分成簇的方法或手段。聚类分析可广泛利用在商务智能，Web搜索，生物学以及图像模式识别等众多方面。本文主要叙述聚类分析中的K-means聚类算法，总结了K-means聚类算法的研究现状，并针对K-means算法的相关改进做了综述。
关键词：K-means聚类算法；数据子集；聚类中心；相似性度量和距离矩阵
Overview of K-means algorithm in
clustering analysis
Abstract:Clustering is major field in data mining which also is an important method of data partition or grouping. Clustering now has been applied into various ways in business intelligence,Web classification,biology,market and so on.In this paper, we introduce the spatial clustering rules,At the same time, the classical K-means algorithm is describe,And some related improvements to K-means algorithm are summarized.
Key words: K-means clustering algorithm; number of clusters K; cluster initialization; distance metric
1、引言
K-means聚类算法是1955年由Steinhaus、1957年Lloyed、1965年Ball & Hall、1967年McQueen分别在他们各自研究的不同的科学领域独立提出的。空间聚类分析方法是空间数据挖掘理论中一个重要的领域，是从海量数据中发现知识的一个重要手段。k-means算法是空间聚类算法中应用非常广泛的算法，同时它也在聚类分析中起着重要作用。日益丰富的空间和非空间数据收集存储于空间数据库中，随着空间数据的不断膨胀，海量的空间数据的大小、复杂性都在快速增长，远远超出了人们的解译能力，从这些空间数据中发现邻域知识迫切需求产生一个多学科、多邻域综合交叉的新兴研究邻域，空间数据挖掘技术应运而生。虽然k-means聚类算法被提出已经快60年了，但是目前仍然是应用最为广泛的划分聚类算法之一]1[。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。
本文主要叙述聚类分析中的K-means聚类算法，总结了K-means聚类算法的研究现状，并针对K-means算法的相关改进做了综述。
2、经典K-means算法
2.1 K-means算法
k-means 聚类算法是一种基于形心的划分技术，是数据挖掘领域最为常用的聚类方法之一，最初起源于信号处理领域。它的目标是划分整个样本空间为若干个子空间，每个子空间中的样本点距离该空间中心点平均距离最小。因此，k-means 是划分聚类的一种。
k-means 算法接受输入量k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
大体上说，k-means 算法的工作过程说明如下：首先从n个数据对象任意选择k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度，分别将它们分配给与其最相似的聚类；然后再计算每个所获新聚类的聚类中心；不断重复这一过程直到标准测度函数开始收敛为止。一般都采
用均方差作为标准测度函数。 k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
假设数据集D 包含n 个欧氏空间中的对象。划分方法把D 中的对象分配到K 个簇j C C ,...,1中，使得对象1≦i ，j ≤k,i C ?D 且i C ?j C =?，一个目标函数用来评估划分的质量，使得簇内对象相互相似，而与其他簇中的对象相异。也就是说，该目标函数以簇内高相似性和簇间低相似性为目标。
基于形心的划分i C 技术使用簇的形心代表该簇。对象s ∈i C 与该簇的代表i c 之差用dist （s ，i c ）度量，其中dist （x ，y ）=sqrt( ∑(21i i y x -)^2 ) 这里i=1,2..n 。
簇i C 的质量可以用簇内变差度量，它是i C 中所有对象和形心i c 之间的误差的平
方和，
α=21),(i c p k
i c s dist i ∈=∑∑ （1） 其中，α是数据集中所有对象的误差的平方和；s 是空间中的点，表示给定的数据对象；i c 是簇i C 的形心]2[。
2.2 k-means 算法流程
k-means 算法流程，首先，随机的选择k 个对象，每个对象初始地代表了一个聚类的平均值或中心，对剩下的各个对象，根据其与每个聚类中心的欧氏距离，将它派发给最相似的聚类。之后，应用更新之后的均值作为新的聚类中心，再重新分配全部对象。继续迭代，一直到分配趋于稳定，也就是本轮迭代所形成聚类与前一轮形成的聚类相同。
3、K-means 聚类算法的参数及其改进
k -means 聚类算法需要用户指定 3个参数：类别个数K ，初始聚类中心、相似性和距离度量。针对这3个参数，k -means 聚类算法出现了不同的改进和变种。
3.1 基于K 值的改进
在 k-means 算法中 k 是事先给定的，这个 k 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 k-means 算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目 K ，例如 ISODATA 算法。
1) 解决方法-聚类有效性函数
根据聚类有效性函数的方法是非常简单的一种解决方法，从［2，N］的区间内逐一选取k值，并利用该函数评价聚类的效果，最终得到最优的k值。
中外有许多学者也是按照这种思想提出了一系列的解决方法。
李永森等]3[提出的距离代价函数综合了类际距离和类内距离两项距离函数，类际距离为所有聚类中心到全域数据中心的距离之和。类内距离即所有类中对象到其聚类中心的距离之和。作者证明了当距离代价函数达到最小值时，空间聚类结果为最优，此时对应的k 值为最佳聚类数。
杨善林]4[提出的距离代价函数作为空间聚类的有效性检验函数, 就是当距离代价函数达到最小值时侯, 以距离代价最小准则实现了k 值优化算法，空间聚类结果为最优.根据经验规则计算和确定最优解的上界, 给出了求k值最优解kopt及其上界kmax的条件, 并在理论上证明了经验规则kmax≤n的合理性.
吴艳文等]5[提出的通过提供相对较易得到的k 初值( 大于kopt) ,得k 个初始聚类。分析聚类之间相互关系,判断那些聚类应是同一类,从而得到对k值的优化。
王朔等]6[提出基于非模糊型集群评估指标（DBI）的概念。该指标主要利用几何原理进行运算，分别以聚类间离散程度及位于同一类内数据对象的紧密程度为依据。即不同聚类间的相异性高而同一类内数据对象的相似性高，并以此来进行聚类结果的评估。当类内各数据对象间距离越小而类间距离越大时指标值则越小，代表各聚类内的数据对象越紧密且聚类间的差异大。指标值越小，表明此聚类数目下聚类结果越佳。DBI 值越小代表各聚类内数据相似度越大而类间的相似度越小，由此得到最佳聚类数目。
2）解决方案-遗传算法
Bandyopadhyay等]7[提出了GCUK 算法是基于遗传算法的。此算法的染色体是运用字符串方式来编码的，也就是将每个初始的聚类中心坐标按照顺序来进行编码，符号“#”来表示没有作为初始聚类中心的数据点，编码完成以后在逐代交叉运算中最后得到了最优k值。
张月琴等]8[提出了优化值参数是基于遗传算法的。在遗传算法中, 通过编码来实现染色体。依据k-means算法要找到最佳的k值, 染色体的编码既是对k值的编码。在一般情况下，对于某类问题,总是有一聚类的最大类数MaxClassnum, 这个值即可由用户来进行输入，也可以是给定的聚类样本个数。k是介于1和MaxClassnum之间的整数，可以使用二进制串既染色体来表示。
胡彧等]9[提出了由遗传操作中的变异操作来控制k 值的大小。变异操作的本质是挖掘群体中个体的多样性，同时提高算法的局部随机搜索能力，防止出现未成熟收敛通过对个体适应度函数的求解，决定聚类数k 值的变化方向。由于最初所给的聚类数k 值并非是最佳聚类数，因此将最初所给种群中具有最大适应度值的个体做为最佳聚类数的榜样个体，其它个体的长度(即k 值)向榜样个体的长度靠扰。
3）其他方法
孙雪等]10[提出了一种基于半监督k-means 的k 值全局寻优算法。
设初始少量数据集带标记的为监督信息, 数据集无标记的,监督信息数据集的标记为i 和j .设k =2为初值, 在完整的数据集上来进行const rained-k-means 聚类.当k 取不同值时, 计算监督信息中被错误标记的数据总数N ，公式如下：
∑==k
c jc ic n n N 1),min( （1）
其中c 表示聚类后各簇的标号;ic n ,jc n 表示在第c 簇中标记的数据所占的比例为i , j .出现空簇的频率取决于K 值上限, 当出现空簇的频率大于50 %时, 则此时k 被认为已取得最大值.在k 值优化的整个过程中, 如果某一簇内的监督信息满足以下条件, 即 ,max(阈值 （2） 则该次聚类结果被认为是无效,保留有效的簇中心值,再开始新一轮聚类,在中心点选择上采取了半增量的迭代方式,提高了算法性能。上式阈值选取可采取重复实验的方法,一般当ic n 与jc n 的数量相差较少时,类标记为c 的簇就为无效的簇.使N 取得最小值的k 取值就为k-means 聚类算法的最佳初值。 田森平等]10[提出了根据所需聚类数据的分布的属性，来计算他们间的距离，经过这一系列变换，得到最终的聚类参数k 值。从需要聚类的数据之中抽取出一部分样本数据，来获取聚类参数的抽样数据；再计算抽样数据间的距离来得到一沿对角线对称的距离矩阵，从这一距离矩阵之中找出一个大于零的最小距离即为mind(j i x x ,) , 作为高密度半径和簇划分半径的一个项，来保证这两个半径不会太小；对距离矩阵按列求平均值，再对这些平均值求i R 求平均值得到R ，根据|R R i -| / R 的误差来去掉噪声点，在噪声点去除完全后，重新计算R ，根据R 和min d(j i x x ,), 求得了高密度半径R 。再找出min i R ，依据, d(j i x x ,)< min i R 的关系来得到高密度个数的参数Z ；最终根据R 和min d(j i x x ,), 获得簇划分的半径r ，合并簇的中心点之间距离m ，合并簇的边界点之间距离h 。 综上所述的研究可发现，学术界已经提出了许多种K 值的选取方法，并且分别基于不同的解决方法。 3.2 初始聚类中心的选择 k-means 算法是贪心算法，在多项式时间内，只能得到局部最优。初始聚类中心的选择是随机选取的，不同的初始聚类中心选取方法得到的最终局部最优结果也不同。所以可能造成在同一类别的样本被强制当作两个类的初始聚类中心，使得聚类结果最终只能收敛于局部最优解，k-means 算法的聚类效果在很大的程度上依赖于初始聚类中心的选择，因此，大量的初始聚类中心选取方案被提出。 袁方等]11[提出了基于密度的优化初始聚类中心的方法，找到一组能反映数据分布特征的数据对象作为初始聚类中心 首先计算数据对象i x 所处区域的密度，来定义一个密度参数：以i x 为中心，包含了常数Minpts 个数据对象的半径称为对象i x 的密度参数，用ε表示。ε越大，则说明数据对象所处区域的数据密度就越低。反之，ε越小，说明数据对象所处区域的数据密度越高。通过计算每个数据对象的密度参数，就可以发现处于高密度区域的点，从而得到一个高密度点集合D 。在D 中取处于最高密度区域的数据对象作为第1 个聚类中心z 1；取距离z 1最远的一个高密度点作第2个聚 类中心z 2 ；计算D 中各数据对象i x 到z 1,z 2的距离 d ( i x ,z 1 )，d ( i x ,z 2 )，z 3为满足 max(min(d ( i x ,z 1 ), d ( i x ,z 2 )) i =1, 2,…,n 的数据对象i x ；m z 为满足 max(min(d ( i x ,z 1 ), d ( i x ,z 2 ),...,d(i x ,1 m z )) i =1,2,…,n 的数据对象i x ,i x ∈D 。依此得到k 个初始聚类中心。 秦钰等]12[提出了探测数据集中的相对密集区域, 再利用这些密集区域生成初始类中心点。该方法能够很好地排除类边缘点和噪声点的影响, 并且能够适应数据集中各个实际类别密度分布不平衡的情况, 最终获得较好的聚类效果。 利用UPGMA 层次聚类算法初期汇聚效果好的优势, 发现数据集中的密集区域, 避免类边缘点或噪声点成为初始类中心点, 同时, 着重于考虑区域的相对密集程度, 改变UGPMA 算法的停止条件, 使子树的生成停止在不同的聚类层次上, 以适应各个实际类别密度不平衡的数据集。 赖玉霞等]13[提出了根据数据的自然分布来选取初始聚类中心, 找出对象中分布比较密集的区域, 这正是聚类的目的, 从而摆脱了随机选取聚类中心对聚类结果产生的不稳定性, 以及用质心代表一个簇所带来的“噪声”和孤立点数据对聚类结果的影响。 黄敏等]14[提出了在基于高密度点分布的算法基础上，解决了当高密度点分布不只一个时如何选取聚类中心的问题。找到最大者作为聚类中心点，并将与聚类中心的距离小于样本平均距离的点的密度参数从密度参数集合中删除。 周爱武等]15[提出了的算法的改进建立在没有离群点的数据集上,通过求次小距离的样本点的中心，然后求出此中心与一个聚类中心之间的距离，与样本点之间的平均距离进行判断。如果小于样本点之间的平均距离，则将此样本点加入初始化集合中，再求第三距离小的样本点，如果大于样本点之间的平均距离，则求出此中心存入二维数据样本点中心。集合二维数据样本点中心中的个数等于k，初始聚类中心全部找到。 周炜奔等]16[提出了基于密度、中心点的初始化中心算法，首先算出样本数据集之中每个样本密度，得到一个以密度为标准的样本集合。然后在标准样本集合基础上进行初始聚类中心的选取和簇的划分。每划分出一个簇，就从标准样本集合中删除该簇所包括的数据点。 郑丹等]17[提出了基于k-means聚类算法对初始聚类中心敏感的这一特点的改进算法。k-means聚类算法中，数据对象间的相似性是根据欧氏距离衡量的，距离越小则说明越相似。用DK图对k-dist图进行分析，找出对应密度水平的平缓曲线。在不同的密度水平上分别选择一个k-dist值最小即密度相对最大的点作为初始聚类中心。根据上述原理，在总数为k的数据集之中找出q`个密度相对与其它点最大的点来作为初始聚类中心。 相比确定k值，优化算法应用于初始聚类中心的选择更加合适，目前已经提出了许多比较成熟的算法，并且已经有相关的专著问世]18[。 3.3 相似性度量和距离矩阵 k-means聚类算法使用欧式距离作为相似性度量和距离矩阵，计算各数据点到其类别中心的距离平方和。因此，k-means聚类算法划分出来的类别店铺是类 m 时的特例，即2L距离。在球形的。实际上，欧式距离是Minkowski距离在2 L距离进行K-means聚类时，最终类中心应是每一类的m中心向量。Kashima 采用m L距离，最终聚类中心使每一类的中位向量。对于一维数据等人于2008年使用1 12,{x ,x ,x ,,x }i n X =??????而言，中位数M 比均值x 对异常数据有较强的抗干扰性，聚类结果受数据中异常值的影响较小。Mao&Jain 于1996年提出使用Mahalanobis 距离，但计算代价太大。在应用中，Linde 等。于1980年提出使用Itakura-Saito 距离。Banerjee 等人2004年提出，如果使用Bregman 差异作为距离度量，有许多突出优点，如克服局部最优、类别之间的线性分离、线性时间复杂度等。 4、结束语 k-means 聚类算法是一种非常优秀的算法，以其简单的算法思想、较快的聚类速度和良好的聚类效果得到了广泛的应用。对于该算法在聚类过程中暴露出的若干问题，本文对其中k 值确定、初始聚类中心选择等主要问题进行了综述。因此k-means 聚类算法是一个贪心算法，在多项式时间内，仅能获得局部最优，对 k-means 聚类算法的研究也将继续。 参考文献： [1] Anil K J. Data clustering: 50 years beyond K-Means [J]. Pattern Recognition Letters, 2010, 31(8): 651-666. [2]Jiawei han;Micheline Kamber;Jian Pei.Data Mining:Concepts and Techniques,Third Edition[J].2015.7 [3]李永森，杨善林，马溪骏等．空间聚类算法中的K 值优化问题研究［J］．系统仿真学报， 2006,18( 3) : 573 －576． [4]杨善林, 李永森, 胡笑旋, 等.k-means算法中的k值优化问题研究[ J] .系统工程理论与实 践, 2006,(2):97 -101. [5]吴艳文,胡学钢.一种K_means算法的k值优化方案[J].巢湖学院学报.2007,9(6):21-14. [6]王朔顾,进广.基于K值改进的K－means算法在入侵检测中的应用[J].工业控制计算 机,2014,27(7):93-97. [7]Bandyopadhyay S,Maulik U.Genetic Clustering for Automatic Evolution of Clusters and Application to Image Classification［J］．Pattern Recognition，2002，35( 6) : 1197 －1208．[8]张月琴, 刘静.一种改进的聚类算法在入侵检测中的应用[ J] .太原理工大学学报, 2008, 39(专辑):74 -76. [9]孙雪,李昆仑,胡夕坤,赵瑞.基于半监督K -means的K 值全局寻优算法.北京交通大学学 报,2009,33(6):106-109. [10]田森平,吴文亮.自动获取k-means聚类参数k值的算法[J].计算机工程与设 计.2011,32(1):274-276. [11]袁方,周志勇,宋鑫.初始聚类中心优化的k-means 算法.计算机工程.2007,33(3):65-66. [12]秦钰,荆继武,向继,张爱华.基于优化初始类中心点的K-means改进算法.中国科学院研究 生院学报,2007,24(6):771-777. [13]赖玉霞,刘建平.K- means 算法的初始聚类中心的优化.计算机工程与应用,2008, 44( 10):147-149. [14]黄敏,何中市,邢欣来,陈英.一种新的K-means聚类中心选取算法.计算机工程与应 用,2011,47(35):132-134. [15]周爱武,崔丹丹,潘勇.一种优化初始聚类中心的K- means聚类算法.微型机与应用， 2011,30(13):1-4. [16]周炜奔,石跃祥.基于密度的K-means 聚类中心选取的优化算法.计算机应用研究， 2012,29(5):1726-1727. [17]郑丹,王潜平.K-means初始聚类中心的选择算法.计算机应用，2012,32( 8) : 2186-2188,2192. [18]戴文华.基于遗传算法的文本分类及聚类研究［M］．北京: 科学出版社，2008. 聚类分析K-means算法综述 摘要：介绍K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。 关键词：K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势 算法概述 K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含n个数据对象的数据库，输出满足方差最小标准的k个聚类。 评定标准：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。 解释：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。 k-means 算法基本步骤 （1）从n个数据对象任意选择k 个对象作为初始聚类中心 （2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分 （3）重新计算每个（有变化）聚类的均值（中心对象） （4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2） 形式化描述 输入：数据集D，划分簇的个数k 输出：k个簇的集合 （1）从数据集D中任意选择k个对象作为初始簇的中心； （2）Repeat （3）For数据集D中每个对象P do （4）计算对象P到k个簇中心的距离 （5）将对象P指派到与其最近（距离最短）的簇； （6）End For （7）计算每个簇中对象的均值，作为新的簇的中心； （8）Until k个簇的簇中心不再发生变化 对算法已有优化方法的分析 (1)K-means算法中聚类个数K需要预先给定 这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K 值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标：V(k km) = Intra(k) + Inter(k) / Inter(k max)，其中k max是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是：对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。 (2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解 不同的初始值，结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效果的不稳定，并且，K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值，只有一个属于全局最小，由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过迭代运算，目标函数常常达到局部最小，得不到全局最小。对于这个问题的解决，许多算法采用遗传算法(GA)，例如文献中采用遗传算法GA进行初始化，以内部聚类准则作为评价指标。 (3)从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时,算法的时间开销是非常大 所以需要对算法的时间复杂度进行分析，改进提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的候选集，而在文献中，使用的K-meanS算法是对样本数据进行聚类。无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。 基于划分聚类法的文献综述 聚类分析是一种重要的无监替学习方法，作为数据分析的工具，其重要性在各个领域都得到了广泛的认可.聚类分析的目的是寻找数据集中的“口然分组”，即所谓的“簇”.通俗地讲，簇是指相似元素的集合，聚类分析就是一个在数据集中寻找相似元素集合的无监督学习过程.來〔1不同应用领域的数据集具有不同的特点，人们对数据进行聚类分析的目的也不尽相同，聚类分析的方法因数据集而异，因使用目的而异.当前，聚类分析的新方法层岀不穷，纵观各种聚类算法，它们使用的技术互不相同，其理论背景乂彼此交义、重蒂，很难找到一个统一的标准对其进行归类。 聚类分析的方法可分为基于层次的聚类方法、基于划分的聚类方法、基于图论的聚类方法、基于密度和网格的方法等.这些方法虽然从不同角度使用不同的理论方法研究聚类分析，但对于不同的实际问题，聚类分析中的一些基本内容始终是人们关注的焦点。其中，划分法通常是指给定数据库，其中有N个元素，采用分裂法将其构造为K个组，每一个分组就代表一个聚类，K 计算机工程与应用2006.16 引言 聚类分析是数据挖掘领域中的一个重要分支[1],是人们认 和探索事物之间内在联系的有效手段,它既可以用作独立的 据挖掘工具,来发现数据库中数据分布的一些深入信息,也 以作为其他数据挖掘算法的预处理步骤。所谓聚类(clus- ring)就是将数据对象分组成为多个类或簇(cluster),在同一 簇中的对象之间具有较高的相似度,而不同簇中的对象差别大。传统的聚类算法主要分为四类[2,3]:划分方法,层次方法, 于密度方法和基于网格方法。 受生物进化机理的启发,科学家提出许多用以解决复杂优 问题的新方法,如遗传算法、进化策略等。1991年意大利学A.Dorigo等提出蚁群算法,它是一种新型的优化方法[4]。该算不依赖于具体问题的数学描述,具有全局优化能力。随后他 其他学者[5～7]提出一系列有关蚁群的算法并应用于复杂的组优化问题的求解中,如旅行商问题(TSP)、调度问题等,取得 著的成效。后来其他科学家根据自然界真实蚂蚁群堆积尸体分工行为,提出基于蚂蚁的聚类算法[8,9],利用简单的智能体 仿蚂蚁在给定的环境中随意移动。这些算法的基本原理简单懂[10],已经应用到电路设计、文本挖掘等领域。本文详细地讨现有蚁群聚类算法的基本原理与性能,在归纳总结的基础上 出需要完善的地方,以推动蚁群聚类算法在更广阔的领域内 到应用。 2聚类概念及蚁群聚类算法 一个簇是一组数据对象的集合,在同一个簇中的对象彼此 类似,而不同簇中的对象彼此相异。将一组物理或抽象对象分组为类似对象组成的多个簇的过程被称为聚类。它根据数据的内在特性将数据对象划分到不同组(或簇)中。聚类的质量是基于对象相异度来评估的,相异度是根据描述对象的属性值来计算的,距离是经常采用的度量方式。聚类可用数学形式化描述为:设给定数据集X={x 1 ,x 2 ,…,x n },!i∈{1,2,…,n},x i ={x i1 ,x i2 , …,x 西南民族大学学报·自然科学版第37卷5月专辑 Journal of Southwest University for Nationalities ?Natural Science Edition May. 2011___________________________________________________________________ ___________________________ 收稿日期：2011-03-01 作者简介：向培素(1974-), 女, 副教授, 主要研究方向: 计算机应用, 检索技术. 基金项目：本文是“西南民族大学校级科研项目”(09NYB007)的研究成果之一. 文章编号: 1003-2843(2011)05专-0112-03 聚类算法综述 向培素 (西南民族大学电气信息工程学院, 四川成都 610041) 摘 要: 聚类分析是一种基本的数据分析方法,它在数据挖掘,统计学,空间数据库技术,人工智能,生物学研究,机器学习, 模式识别等领域都得到了广泛的应用. 论文介绍了各类主要的聚类算法,并概述了其主要应用领域. 关键词: 聚类算法; 半监督聚类 中图分类号: G642 文献标志码: A doi ：10.3969/j.issn.1003-2483.2011.05专.33 随着信息技术的发展, 人们积累了越来越多的音、视频数据, 以及文本, 图片等数据, 为了从这些海量数据中查找, 提取有用信息, 出现了数据挖掘技术. 聚类作为数据挖掘的重要技术之一, 在机器学习、工程学、神经网络、生物学、统计学、地球科学以及社会科学和经济学等许多领域起着越来越重要的作用. 传统的聚类算法大致分为两类：层次聚类算法, 分割聚类算法. 1 层次聚类算法 层次聚类是对给定的数据对象的集合进行层次的分界, 根据一些指定标准把数据排列成一个树状结构的算法. 根据层次分界的表示方式, 层次聚类方法又可以分为凝聚的和分裂的两种. 凝聚算法先将每个数据作为一个簇, 然后根据一定的规则将簇合并, 凝聚算法又有单连接(single linkage)、全连接(complete linkage)和平均连接(average linkage)方法. 单连接是指当两个簇之间存在互连的边, 并且簇中数据最小距离小于等于给定的阈值, 则认为这两个簇的距离足够小, 可以合并. 全连接和单连接类似, 不过全连接是使用簇中数据的最大距离作为簇间距离. 平均连接使用两簇中数据的两两距离的平均值作为簇间距离. 分裂聚类先将所有数据归在一个簇里, 然后对簇中联系不紧密的数据进行分裂, 分到其他簇里, 分裂聚类有一些简化的算法, 如单元分裂法和多元分裂法. 单元分裂法每一次选取一个变量对簇进行分裂, 和变量相同的数据归为一类, 和变量不同的数据归为另一类. 多元分裂则是选取一个距离其他数据最远的数据构成分离组, 然后计算簇中每一个数据距离分离组的距离并和该数据与簇中其他数据的距离进行比较, 若该数据距离分离组的距离更近, 则将该数据划入分离组. 重复这个过程, 直到找不到这样的数据为止. 2 分割聚类算法 分割聚类法先对所有数据点进行较为粗略的划分, 然后通过重复的迭代算法使某个准则达到最优化来对划分进行修正. 分割聚类法又可以分为基于密度的算法, 基于网格的算法, 基于图论的算法, 基于平方误差的迭代重分配算法. 数据挖掘中聚类分析综述 发表时间：2014-12-03T13:59:11.890Z 来源：《价值工程》2014年第5月下旬供稿作者：张静[导读] 它在处理大数据量尤其是海量数据时有着明显的优势，而且聚类的质量相对较好。 张静ZHANG Jing（六安职业技术学院信息工程系，六安237000）（Department of Information Engineering，Lu'an Vocational Technical College，Lu'an 237000，China）摘要院数据挖掘中的聚类技术是一种非监督分类技术。概述了聚类分析算法中的数据结构和数据类型，分析了聚类分析的意义及研究现状，比较了几种聚类算法的优点及问题，并结合通信领域的应用指出了K-Means 聚类技术的绝对优势。 Abstract: The clustering technology in data mining is a kind of unsupervised classification techniques. The paper analyses the datastructure and data types of clustering analysis algorithm, the significance and resent research of cluster analysis, compares the advantagesand disadvantages of several kinds of clustering algorithm, points out the absolute advantages of K-Means clustering technology combinedwith the application in communication feild.关键词院数据挖掘；聚类分析；K-Means 算法Key words: data mining；clustering analysis；K-Means algorithm中图分类号院TP274 文献标识码院A 文章编号院1006-4311（2014）15-0226-020 引言数据挖掘，也称知识发现数据库(KDD)[1]，就是从实际的大量的、不完全的，含有噪声的数据中去提取出人们事先不知道的、隐含在其中的对人们有用的知识和信息的过程。数据挖掘经常被企业决策者利用，通过挖掘企业中存储的大量数据中的潜在的有价值的信息，从而帮助企业经营者做出正确的决策，为企业创造更多的利益。聚类技术作为数据挖掘的的重要技术之一，也更多的为人们认识和使用。本文分析了几种主要的聚类算法的优点及存在的问题，并指出K-Means[2]聚类技术在通信领域的绝对优势。 1 聚类的定义聚类分析[3]仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相关的，而不同组的对象是不相关的，组内相似度越大，组间差别度越大，聚内效果就越好。聚类分析技术作为强大的辅助工具在科学研究、社会服务、市场营销等多个领域发挥了巨大的作用。因此聚类分析技术研究也成为一个热点课题。 2 聚类分析算法中的数据结构和数据类型2.1 数据结构一般聚类分析中的数据用以下两种数据结构来表示：对象-属性结构组成了数据矩阵。它由n 个对象组成，例如：人；用P 个属性来描述每个对象，例如：身高、体重、出生日期等。可以使用nXP 矩阵或关系表的形式来表示数据矩阵，如式（1）所示。 2.2 数据类型在实际应用中，数据挖掘任务面对的更多的是非数值型数据对象以及复合数据类型，数据复杂且多样化，布尔类型、有序数据类型、分段数值变量、标称型变量、二元、序数型以及混合型组合变量和比例型变量等都是在数据挖掘中常常会遇到的数据类型变量。 3 主要的聚类算法目前，在数据挖掘中聚类的算法主要可分为以下几种：划分算法、层次方法、基于密度的算法、基于模型的方法以及基于网格的方法。下面将详细列出几种算法，并予以简单的介绍和分析。 3.1 划分方法所谓划分方法就是将包含有n 个数据对象的数据集合分为m 个组，其中每个组都是一个聚类，从定义可以看出，这种聚类要满足以下两点：淤每个分组至少要包含一个一个数据对象；于每个数据对象只能归属在一个分组当中，不能出现一个数据对象同时归属几个分组的情况，使用反复迭代的方法进行分组效果会更佳。最终在计算时，使得每次改进后的分组方案较之前一次都更胜一筹，同一分组当中，各个数据对象越近越好，而一些部分的算法应用对于条件于的限制可以适当放宽一些。在聚类算法中，k-平均(k-means)算法和k-中心点(k-medoids)算法是最重要的两种算法，除此之外的其他类型的划分方法都是在它们的基础上演化而来的。 3.2 层次方法层次聚类算法将数据集进行层次分解。分为自下向上凝聚的(agglomerative)层次聚类和自上向下的分裂法(divisive)层次聚类两种。凝聚的层次聚类将每个数据对象单独分成一个组，再逐步合并分组达到终止函数的限制。分裂法层次聚类，先将所有数据对象放到一个分组中，然后再渐渐划分为小的分组，直到达到了某个终止条件。常用的层次聚类方法包括BIRCH，CURE，ROCK，Chameleon 算法等。 3.3 基于密度的方法目前，对于非球形数据集的聚变来说，基于距离的算法是可行的，但对于其他类型的巨变则须另当别论。在基于密度的聚类算法中，密度代替了数据的相似性，根据数据对象的分布密度，将密度聚类分析算法及应用足够大的区域相连结，从而发现任意形状的簇。这类算法除了可以发现任意形状的簇，而且能有效地起到消除噪声的作用。密度算法主要包括DBSCAN，OPTICS，DENCLUE 等。 基于因子分析和聚类分析的客户偏好探究 一文献综述 二十世纪五十年代中期，美国学者温德尔史密斯提出了顾客细分理论。该理论指出，顾客由于其文化观念、收入、消费习俗等方面的不同可以分为不同的消费群体。企业在经营中应该针对不同的顾客提供针对性的服务，这样才能够利用有限资源进行有效的市场竞争。对顾客的细分从方法上讲有根据人口特征和购买历史的细分和根据顾客对企业的价值即基于顾客的消费金额、消费频率的细分。本文的细分是基于购买历史和人口特征的聚类分析。饭店作为一个古老的服务行业，在现阶段的高度竞争市场下的发展趋势最重要的方面便是服务趋于个性化，所以针对饭店的消费群体特征的聚类可以对饭店进行定位，在此基础上通过分析目标客户群体对消费质量评价的最主要影响因素可以达到其服务个性化的目标。波特把顾客的价值定义为买方感知性与购买成本的一种权衡。对顾客的个性化服务增加了买方的感知度从而加大了他们愿意为此付出的成本，于是饭店便可以增加营业额。 聚类分析是把研究对象视作多维空间中的许多点, 并合理地分成若干类，即一种根据变量域之间的相似性而逐步归群成类的方法，它能客观地反映这些变量或区域之间的内在组合关系。1故聚类算法是对顾客进行分析的一个有效方式。在聚类分析的众多算法中因子分析是研究如何以最少的信息丢失, 将众多原始变量浓缩成少数几个因子变量, 以及如何使因子变量具有较强的可解释性的一种多元统计分析方法。2而典型的k-means算法以平方误差准则较好地实现了空间聚类,对于大数据集的处理效率较高。3在对顾客细分相关文献的研究过程中，主要运用的方法有神经网络,分层聚类,因子分析等方法。比如，在关于网络青少年用户的分类中，作者用层次聚类的方法，通过对青少年年龄,性别,民族,网络可得性,父母的观点等变量等变量定义不同的上网动机，在此基础上对其进行了分类。而在研究人寿保险持有者未来购买基金支持寿险可能性的文章中，通过灰度聚类和神经网络利用消费者的基本信息,财产地位信息,风险承受程度将消费者分为了忠实客户和非忠实客户。在对客户忠诚度的聚类中，作者用RFM的商业模型用DBI确定了Kmeans的最优K值，并最终用kmeans对客户忠诚度进行了聚类。 经过综合分析，我们选择了这两种方法处理顾客数据和饭店的基本资料。即，通过 k-means对客户进行聚类后通过因子分析分析不同类别客户的评价影响因素。 为分析每类客户倾向的饭店特征，本文根据客户聚类结果对饭店数据进行筛选。由于饭店部分属性之间具有相关性，本文采用因子分析法挖掘其“根本属性”，之后对饭店数据进 1李蓉, 李宇. 基与主成分分析与聚类分析方法的我国西部区域划分问题的研究. 科技广场, 2李新蕊.主成分分析、因子分析、聚类分析的比较与应用. 山东教育学院学报. 3杨善林.kmeans 算法中的k 值优化问题研究系统工程理论与实践 信息疼术2018年第6期文章编号=1009 -2552 (2018)06 -0092 -03 DOI：10.13274/https://www.doczj.com/doc/d94298123.html,ki.hdzj.2018. 06.019 基于聚类的图像分割方法综述 赵祥宇\陈沫涵2 (1.上海理工大学光电信息与计算机学院，上海200093; 2.上海西南位育中学，上海200093) 摘要：图像分割是图像识别和机器视觉领域中关键的预处理操作。分割理论算法众多，文中 具体介绍基于聚类的分割算法的思想和原理，并将包含的典型算法的优缺点进行介绍和分析。经过比较后，归纳了在具体应用中如何对图像分割算法的抉择问题。近年来传统分割算法不断 被科研工作者优化和组合，相信会有更多的分割新算法井喷而出。 关键词：聚类算法；图像分割；分类 中图分类号：TP391.41 文献标识码：A A survey of image segmentation based on clustering ZHAO Xiang-yu1，CHEN Mo-han2 (1.School of Optical Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai200093，China；2.Shanghai Southwest Weiyu Middle School，Shanghai200093，China) Abstract:Image segmentation is a key preprocessing operation in image recognition and machine vision. There are many existing theoretical methods,and this paper introduces the working principle ol image segmentation algorithm based on clustering.Firstly,the advantages and disadvantages ol several typical algorithms are introduced and analyzed.Alter comparison,the paper summarizes the problem ol the selection ol image segmentation algorithm in practical work.In recent years,the traditional segmentation algorithms were improved and combined by the researchers,it believes that more new algorithms are blown out. Key words:clustering algorithm；image segmentation；classilication 0引百 近年来科学技术的不断发展，计算机视觉和图像 识别发挥着至关重要的作用。在实际应用和科学研 究中图像处理必不可少,进行图像处理必然用到图像 分割方法,根据检测图像中像素不重叠子区域，将感 兴趣目标区域分离出来。传统的图像分割方法:阈值 法[1]、区域法[2]、边缘法[3]等。近年来传统分割算法 不断被研究人员改进和结合，出现了基于超像素的分 割方法[4]，本文主要介绍超像素方法中基于聚类的经 典方法，如Mean Shift算法、K-m eans 算法、Fuzzy C-mean算法、Medoidshilt算法、Turbopixels算法和 SLIC 算法。简要分析各算法的基本思想和分割效果。 1聚类算法 1.1 Mean Shil't算法 1975年,Fukunaga[5]提出一种快速统计迭代算法，即Mean Shilt算法（均值漂移算法）。直到1995 年,Cheng[6]对其进行改进，定义了核函数和权值系 数，在全局优化和聚类等方面的应用，扩大了 Mean shil't算法适用范围。1997至2003年间，Co-maniciu[7-9]提出了基于核密度梯度估计的迭代式 搜索算法,并将该方法应用在图像平滑、分割和视频 跟踪等领域。均值漂移算法的基本思想是通过反复 迭代计算当前点的偏移均值，并挪动被计算点，经过 反复迭代计算和多次挪动，循环判断是否满足条件, 达到后则终止迭代过程[10]。Mean shil't的基本形 式为： 收稿日期：2017-06 -13 基金项目：国家自然科学基金资助项目（81101116) 作者简介：赵祥宇（1992-)，男，硕士研究生，研究方向为数字图像处理。 —92 — 成绩： 西安建筑科技大学 毕业设计 (论文)文献综述 院（系）：信息与控制工程学院 专业班级： 毕业设计论文方向:空间数据挖掘方法的研究与应用 综述题目：空间数据挖掘方法的研究与应用 学生姓名： 学号： 100620114 指导教师：刘培奇 2014年 3 月 21 日 空间数据挖据方法的研究与应用 摘要：空间数据库含有空间数据和非空间数据, 空间数据主要是地表在GIS 中的二维投影, 非空间数据则是除空间数据以外的一切数据。随着对地观测、获取设备的迅速发展, 空间数据资源日益丰富。然而, 数据资源中蕴含的知识远远没有得到充分的挖掘和利用, 导致“数据爆炸但知识贫乏”;同时,要求用户详细分析这些数据并提取感兴趣的知识或特征是不现实的。因此, 从空间数据库中自动地挖掘知识, 寻找数据库中不明确的、隐含的知识、空间关系或其它模式, 即空间数据挖掘技术(Spatial DataMining ,SDM) 越来越重要。空间数据挖掘是在空间数据库的基础上, 综合利用统计学方法、模式识别技术、人工智能方法、神经网络技术、模糊数学、机器学习、专家系统和相关信息技术等, 按照一定的度量值和临界值抽取空间知识及与之相关的预处理、空间抽样和数据变换的一个多步骤相互链接、反复进行的人机交互过程。可以归纳为数据准备(了解应用领域的先验知识、生成目标数据集、数据清理、数据简化与投影) 、数据挖掘和知识发现(数据挖掘功能和算法的选取, 在空间的关联、特征、分类、回归、聚类、函数依赖等特定的规则中搜索感兴趣的知识)以及数据挖掘后处理(知识的解释、评价和应用)。 关键词：数据挖掘，知识发现，关联规则，空间数据库。 1.前言 空间数据挖掘（spatial data mining）是在数据挖掘的基础之上，结合地理信息系统（GIS）、遥感图像处理、全球定位系统（GPS）、模式识别、可视化等相关的研究领域而形成的一个分支学科，也称为空间数据挖掘和知识发现（spatial data mining and knowledge discovery 简称为SDMKD）。 自20世纪60年代数据库系统诞生以来，数据库技术已经得到了飞速的发展，并且己经深入到社会生活的各个方面。现在，数据无处不在，可以存放在不同类型的数据库中，数据仓库技术可以将异构的数据库集成起来进行综合管理，从而提供更好的服务。 K-means聚类算法研究综述 摘要:总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数，算法流程，并列举了一个实例，指出了数据子集的数目K，初始聚类中心选取，相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means 聚类的进一步研究方向。 关键词：K-means聚类算法；NP难优化问题；数据子集的数目K；初始聚类中心选取；相似性度量和距离矩阵 Review of K-means clustering algorithm Abstract: K-means clustering algorithm is reviewed. K-means clustering algorithm is a NP hard optimal problem and global optimal result cannot be reached. The goal，main steps and example of K-means clustering algorithm are introduced. K-means algorithm requires three user-specified parameters: number of clusters K，cluster initialization，and distance metric. Problems and improvement of K-means clustering algorithm are summarized then. Further study directions of K-means clustering algorithm are pointed at last. Key words: K-means clustering algorithm; NP hard optimal problem; number of clusters K; cluster initialization; distance metric K-means聚类算法是由Steinhaus1955年、Lloyed1957年、Ball & Hall1965年、McQueen1967年分别在各自的不同的科学研究领域独立的提出。K-means聚类算法被提出来后，在不同的学科领域被广泛研究和应用，并发展出大量不同的改进算法。虽然K-means聚类算法被提出已经超过50年了，但目前仍然是应用最广泛的划分聚类算法之一[1]。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。 文中总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数、算法流程，并列举了一个实例，指出了数据子集的数目K、初始聚类中心选取、相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means聚类的进一步研究方向。 1经典K-means聚类算法简介 1.1K-means聚类算法的目标函数 对于给定的一个包含n个d维数据点的数据集 12 {x,x,,x,,x} i n X=??????，其中d i x R ∈，以及要生成的数据子集的数目K，K-means聚类算法将数据对象组织为 K个划分{c,i1,2,} k C K ==???。每个划分代表一个类c k，每个类c k有一个类别中心iμ。选取欧氏距离作为相似性和 距离判断准则，计算该类内各点到聚类中心 i μ的距离平方和 2 (c) i i k i k x C J xμ ∈ =- ∑（1） 聚类目标是使各类总的距离平方和 1 (C)(c) K k k J J = =∑最小。 22 1111 (C)(c) i i K K K n k i k ki i k k k x C k i J J x d x μμ ==∈== ==-=- ∑∑∑∑∑ （2）其中， 1 i i ki i i x c d x c ∈ ? =? ? ? 若 若 ，显然，根据最小二乘 法和拉格朗日原理，聚类中心 k μ应该取为类别 k c类各数据点的平均值。 K-means聚类算法从一个初始的K类别划分开始，然 攻读硕士学位研究生试卷（作业）封面（2015 至2016 学年度第一学期） 题目论文选读 科目聚类分析中K-means算法综述 姓名王苑茹 专业计算机技术 入学年月2015年8月 简短评语 成绩：授课教师签字： 聚类分析中K-means算法综述 摘要:聚类分析是数据挖掘中一个极其重要的研究方向，是一个将数据划分成簇的方法或手段。聚类分析可广泛利用在商务智能，Web搜索，生物学以及图像模式识别等众多方面。本文主要叙述聚类分析中的K-means聚类算法，总结了K-means聚类算法的研究现状，并针对K-means算法的相关改进做了综述。 关键词：K-means聚类算法；数据子集；聚类中心；相似性度量和距离矩阵 Overview of K-means algorithm in clustering analysis Abstract:Clustering is major field in data mining which also is an important method of data partition or grouping. Clustering now has been applied into various ways in business intelligence,Web classification,biology,market and so on.In this paper, we introduce the spatial clustering rules,At the same time, the classical K-means algorithm is describe,And some related improvements to K-means algorithm are summarized. Key words: K-means clustering algorithm; number of clusters K; cluster initialization; distance metric 毕业设计(论文)材料之二(2) 本科毕业设计(论文)开题报告题目：聚类分析在股票投资中的应用 课题类型：设计□实验研究□论文√ 学生姓名： 学号： 专业班级： 学院： 指导教师： 开题时间：2012 年03 月17 日 2012 年3月08日 开题报告内容与要求 一、毕业设计（论文）内容及研究意义 主要内容： 聚类分析又称群分析，是根据“物以类聚”的道理，对样品或指标进行分类的一类多元统计方法。本文主要是采用SPSS或SAS统计软件中的聚类分析方法，对于股票市场中某一行业的多个样本股票进行聚类分析，得出结果并对结果进行分析。首先，介绍关于聚类分析的思想以及发展状况。其次，收集相关样本股票的数据，包括总资产，主营业收入，每股净资产，净资产收益率等指标。再次，用SAS软件对数据进行处理，并得出结果，将样本股票进行分类。最后，对结果进行分析，为投资者作出建议。 研究意义： 聚类源于很多领域，包括数学，计算机科学，统计学，生物学和经济学。在不同的应用领域，很多聚类技术都得到了发展，在股票投资中也发挥着这关重要的作用，这些技术方法被用作描述数据，衡量不同数据源间的相似性，以及把数据源分类到不同的簇中。在股市中，对于广大投资者来说，可以开拓投资渠道，扩大投资的选择范围，适应了投资者多样性的投资动机、交易动机和利益的需求，一般来说能为投资者提供较高收益的可能性。但是由于股票价格受到政治，经济，市场等因素的影响，也受到技术和投资者行为因素的影响，因此股票价格经常处于频繁的变动之中，股票价格的频繁变动扩大了股票市场的投机性活动，使股票市场的风险性增大。因此，对股票市场的的股票进行聚类分析显得意义更大。 第２５卷第３期计算机仿真２００８年３月文章编号：１００６—９３４８（２００８）０３—０１２６—０３ 一种基于投票策略的聚类融合算法 李金磊１，朱晓莲２，朱海燕２ （１．中国石化勘探南方分公司研究院，四川成都６１００４１；２．中国地质大学（武汉）计算机学院，湖北武汉４３００７４）摘要：在分类算法和回归模型中，融合方法正得到越来越广泛的应用，但在非监督机器学习领域．由于缺乏数据集的先验知识，则不能直接用于聚类算法。提出并实现了一种基于投票策略的聚类融合算法，该算法利用ｋ—ｍｅｍｓ算法每次随机选取聚类中心而得到不同样本划分的特性，将多次运行得到的聚类结果通过投票的方式合并，从而得到最终的结果。通过一系列真实数据和合成数据集的实验证明，这种方法比单一的聚类算法能更有效地提高聚类的准确率。在此基础上，为了降低高维数据运算的复杂性，将随机划分属性子空间的方法应用到上述聚类融合算法中，实验证明，该方法同时也能够在一个属性子空间上获得好的聚类结果。 关键词：聚类融合；均值算法；投票策略；属性子空间 中图分类号：ＴＰｌ８文献标识码：Ａ ＡＣｌｕｓｔｅｒｉｎｇＥｎｓｅｍｂｌｅｓＡｌｇｏｒｉｔｈｍＢａｓｅｄｏｎＶｏｔｉｎｇＳｔｒａｔｅｇｙ ＬＩＪｉｎ—ｌｅｉｌ，ＺＨＵＸｉａｏ—ｌｉａｎ２，ＺＨＵＨａｉ—ｙａｎ２ （１．ＲｅｓｅａｒｃｈＩｎｓｔｉｔｕｔｅｏｆＥｘｐｌｏｒａｔｉｏｎＳｏｕｔｈｅｍＤｉｖｉｓｉｏｎＣｏｍｐａｎｙ，ＳＩＮＯＰＥＣ，ＣｈｅｎｇｄＯＵＳｉｃｈｕａｎ６１００４１，Ｃｈｉｎａ； ２．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒ，ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＧｅｏｓｃｉｅｎｃｅｓ，ＷｕｈａｎＨｕｂｅｉ４３００７４，Ｃｈｉｎａ） ＡＢＳＴＲＡＣＴ：Ｉｎｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎａｎｄｒｅｇｒｅｓｓｉｏｎａｌｇｏｒｉｔｈｍｓ，ｔｈｅｅｎｓｅｍｂｌｅｍｅｔｈｏｄ帅ｗｉｄｅｌｙｕｓｅｄ，ｂｕｔｉｎｔｈｅＵｎｓＵ?ｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇ，ｉｔｄｉｄｎ’ｔｂｅｕｓｅｄｉｎｔｈｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｄｉｒｅｃｔｌｙｄｕｅｔｏｌａｃｋｏｆｐｒｉｏｒｋｎｏｗｌｅｄｇｅ．Ｔｈｉｓｐａｐｅｒ ｐｒｏｐｏ础ｔａｃｌｕｓｔｅｒｉｎｇｅｎｓｅｍｂｌｅｓａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｖｏｔｉｎｇｓｔｒａｔｅｇｙ，ｉｔｕｓｅｄｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｔｈａｔｔｈｅｋ—ｍｅａｎｓａｌｇｏ－ｒｉｔｈｍｓｅｌｅｃｔｅｄｔｈｅｃｌｕｓｔｅｒｉｎｇｃｅｎｔｅｒｓｒａｎｄｏｍｌｙａｎｄｆｏｕｎｄｔｈｅｄｉｆｆｅｒｅｎｔｐａｒｔｉｔｉｏｎｓｏｆｔｈｅｓａｍｐｌｅ．Ｔｈｅｎ，ｉｔｃｏｍｂｉｎｅｄｔｈｅｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｓｏｆｏｐｅｒａｔｉｎｇｔｈｅｋ—ｍｅａｎｓａｌｇｏｒｉｔｈｍｒｅｐｅａｔｅｄｌｙｔｏａｆｉｎａｌｒｅｓｕｌｔｖｉａｔｈｅｖｏｔｉｎｇｓｔｒａｔｅｇｙ．Ｔｈｒｏｕｇｈｔｈｅｅｘｐｅｒｉｍｅｎｔｏｎｌｏｔｓｏｆｒｅａｌｄａｔａａｎｄａｒｔｉｆｉｃｉａｌｄａｔａ。ｔｈｉｓｍｅｔｈｏｄｃｏｕｌｄｒｅｃｅｉｖｅａｂｅｔｔｅｒｒｅｓｕｌｔｔｈａｎｔｈｅｓｉｎｇｌｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ．Ｍｏｒｅｏｖｅｒ，ｔＯｒｅｓｏｌｖｅｔｈｅｃｏｍｐｌｅｘｉｔｙｏｆｔｈｅｈｉｇｈｄｉｍｅｎｓｉｏｎｄａｔａ，ａｍｅｔｈｏｄｆｏｒｐａｒｔｉｔｉｏｎｉｎｇｔｈｅｆｅａｔｕｒｅｓｐａｃｅｒａｎｄｏｍｌｙｉｎｔｈｅｅｎｓｅｍｂｌｅａｌｇｏｒｉｔｈｍｗａ￥ｕｓｅｄ．Ｉｔｐｒｏｖｅｄｔｈａｔｔｈｉｓｍｅｔｈｏｄｉｓａｂｌｅｔｏｒｅｃｅｉｖｅａｇｏｏｄｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｉｎｔｈｅａｔｔｒｉｂｕｔｅｓｕｂｓｐａｅｅｂｙｔｈｅｅｘｐｅｒｉｍｅｎｔ． ＫＥＹＷＯＲＤＳ：Ｃｌｕｓｔｅｒｉｎｇｅｎｓｅｍｂｌｅｓ；Ｍｅａｎｓａｌｇｏｒｉｔｈｍ；Ｖｏｔｉｎｇｓｔｒａｔｅｇｙ；Ａｔｔｒｉｂｕｔｅｓｕｂｓｐａｃｅ ｌ引言 聚类算法在数值分析、数据挖掘和模式识别领域有着非常广泛的应用，它们通过将数据样本划分成不同的类别来发现和确定数据的结构分布…。文献［２］中介绍了大量的聚类算法，但在现实中还没有一个单一的算法能够识别出任意形态的数据结构分布口１。受到在传感器融合和分类器融合方面的成果的启发【．】，Ｆｒｅｄ和Ｊａｉｎ提出了一系列基于Ｃｏ一鹊一ｓｏｅｉａｔｉｏｎ关系矩阵的聚类融合方法¨Ｊ。Ｊ。随后，Ａ．Ｓｔｒｅｈｌ和Ｊ．Ｇｈｏｓｈ给出了聚类融合的定义并提出了三个基于超图的方法¨１；Ｌ．ＬＫｕｎｃｈｅｖａ等人详细研究了聚类成员的差异性对聚类融合结果的影响和聚类融合的稳定性问题悼。９１。近几年 收稿日期：２００７一０３—０９修回日期：２００７—０３—２０ ．．—．１２６?－—— 的一系列研究和实验表明，聚类融合方法能得到比单一算法更为优越的结果，能够很好地提高聚类算法的鲁棒性和稳定性，并且能够实行并行计算。 本文结合聚类融合的概念，提出了一种基于投票策略的聚类融合算法，该算法不仅计算量较少，而且聚类效果好。在此基础上，为了降低高维数据运算的复杂性，论文尝试采用随机划分属性子空间的方法，在不影响聚类效果的同时更进一步地减少了计算的工作量。 ２聚类融合概述 聚类融合（ＣｌｕｓｔｅｒｉｎｇＥｎｓｅｍｂｌｅｓ）是将多个对一组数据样本进行划分的不同结果合并成一个统一的划分结果‘７１。它的具体表达如下： 假设有ｎ个数据点Ｘ＝｛ｘｌ，也，ｘ３…．．如ｌ，对数据集ｘ 万方数据万方数据 毕业论文文献综述 信息与计算科学 基于数据库的应用研究 一般来说，一个真正的、完整的站点是离不开数据库的，因为实际应用中，需要保存的数据很多，而且这些数据之间往往还有关联，利用数据库来管理这些数据，可以很方便的查询和更新。数据库在网站编辑中占有很大的比重，几乎没有一个网站能脱离数据库的参与。 高等数学是高校很多专业必修的一门基础课程, 对该门课程的学习不仅可以使学生掌握高等数学的基本概念、理论和方法, 而且还能提高学生的抽象思维能力、逻辑推理能力、空间想象能力、运算能力和综合运用所学知识分析问题、解决问题的能力. 但在传统的教学过程中, 学生普遍反应, 高等数学中的许多概念和基本理论非常抽象, 理解和掌握起来很困难, 这极大地影响了学生学习的效果. 而随着计算机及其应用软件技术的发展, 通过建立数学虚拟实验模型来使学生获得对基本概念的感性认识, 以便帮助学生理解高等数学中的基本概念和理论的方法不仅可行, 而且也取得了很好的效果.。 数学实验的概念可以界定为: 为获得某种数学理论, 检验某个数学猜想, 解决某类问题, 实验者运用一定的物质手段, 在数学思维活动的参与下, 在特定的实验环境下进行的探索、研究活动。建立网上数学实验室可以很好的完成数学实验，而不是抽象的去思考问题，更为直观的看待数学问题。 现如今，抽象的数学教学方法即粉笔+黑板的教学方法已经适应不了现在学生的需求，不管是应用方面突出的工科学院或者纯理论的理学院。过去认为数学课是纯理论课，没有实践性教学环节的观念已经被打破，把计算机引入数学课程教学已是不争的事实。对于突出应用和动手能力的高工专学校，利用数学软件进行数学实验不仅是对数学课程改革、对专业课程的改革的要求，也是时代的发展的必然趋势。 想要建立一个完整的网上数学实验室站点，是需要服务器，数据库，网站设计，网站代码编辑等许多方面的配合。数据库知识是网站建设的基础，网站设计是网站建设的设计图，代码编辑就是实现网站能够面向客户的基本。 数据库知识，在文献1中，讲述了数据库在WEB站点中关于存储和更新时间的长短处理以及如何处理存储更新慢的情况，列举的是电子商务系统里用户对店铺的取舍是由点击转的速度来决定的，而点击后转的速度由数据库来决定的。文中提供了多种解决办法，主要是通过缓存和CachePortal加速方法来解决的。该文献1为我们提供了如何解决点击反映慢的问题，加快网页的反应速度，给用户一个更好的体验。聚类分析K-means算法综述
基于划分聚类法的文献综述
蚁群聚类算法综述
聚类算法综述
数据挖掘中聚类分析综述
基于因子分析和聚类分析的客户偏好探究
基于聚类的图像分割方法综述
文献综述--例子
K-means-聚类算法研究综述
聚类中K-means算法综述讲解
关于聚类分析在股票投资中的应用开题报告
一种基于投票策略的聚类融合算法
基于数据库的应用研究【文献综述】
相关主题
文本预览