一种改进的动态k-均值聚类算法①
胡 伟
(山西财经大学实验教学中心, 太原 030006)
摘 要: 针对经典k-均值聚类方法只能处理静态数据聚类的问题, 本文提出一种能够处理动态数据的改进动态k-均值聚类算法, 称为Dynamical K-means算法. 该方法在经典k-均值方法的基础上, 通过对动态变化的数据集中新加入样本进行分析和处理, 根据聚类目标函数改变的实际情况选择最相似的类别进行局部更新或进行全局经典k-均值聚类, 有效检测发生聚类概念漂移和没有发生聚类概念漂移的情况, 从而实现了动态数据的在线聚类, 避免了经典k-均值方法在动态数据中每次都要对全部数据重新聚类而导致算法速度过慢的问题. 标准数据集和人工社会网络数据集上的实验结果表明, 与经典k-均值聚类方法相比, 本文提出的动态k-均值聚类方法能快速高效地处理动态数据聚类问题, 并有效地检测动态数据聚类过程中所产生的概念漂移问题.
关键词: K-均值聚类; 动态k-均值算法; 动态数据; 概念漂移
Research and Realization of a Web Information Extraction and Knowledge Presentation System HU Wei
(Experimental Teaching Center, Shanxi University of Finance and Economics, Taiyuan 030006, China)
Abstract: This paper presents an improved dynamical k-means clustering model to solve the dynamical problem, called Dynamical K-means algorithm, in order to solve the problem that only solving the constant clustering problems of classical k-means clustering method. Based on classical k-means method, by analysis and solving the new adding samples of dynamical training data set, local renew or global clustering is performed by the changing range of objective function, and the dynamical data are clustered online. The speed of classical k-means algorithm is slow by the reiterative clustering is needed of every online clustering step, but the speed of Dynamical K-means algorithm is accelerated. Simulation results on standard and artificial social network datasets demonstrate that comparing with classical k-means clustering means, the excellent clustering results can be obtained by this method and the concept drifting phenomenon can be monitored efficiently.
Key words: K-means clustering; dynamical K-means algorithm; dynamical data; concept drifting
随着信息技术尤其是数据库技术的不断发展, 人们能够以更快捷、容易、廉价的方式获取和存储数据, 这使得大量的数据在诸多领域存储下来. 有资料显示, 2011年全球数据存储量就达到1.8ZB, 预计2020年将增长50倍[1]. 然而, 人们的各项活动都是基于知识和智慧的, 如果数据没有经过分析、加工、处理和精炼, 那么数据本身没有多大意义. 为了能够从海量数据中提炼出有用的知识, 人们迫切需要一种能够智能地、自动地把数据转换成为有用信息和知识的技术、方法
①收稿时间:2012-10-22;收到修改稿时间:2012-12-01或工具, 这就导致了数据挖掘技术的产生. 聚类作为一种典型的数据挖掘方法, 一直以来都是人工智能领域的一个研究热点, 被广泛地应用于人脸图像识别、股票分析预测、搜索引擎、生物信息学等领域中.
聚类分析, 就是将物理或抽象对象的集合分组成为由类似对象组成的多个簇的过程. 一般地, 在聚类结果中, 同一类别中的对象有较大的相似性, 不同类别的对象有较大的差异性. 聚类分析的目标就是在相似度量的基础上对数据进行划分. 聚类来源于很多学
科领域, 包括: 数学、计算机科学、统计学、生物学和经济学等. 在不同领域中, 都有适用于该领域的聚类技术, 并被用来衡量数据之间的相似性[2].
目前, 常用的聚类方法包括: 划分聚类、层次聚类、密度聚类、网格聚类等. 划分聚类就是对给定的包含n个对象的数据集, 采用划分方法分为k个组(k n
≤), 每组代表一个类, 且每个分组至少包含一个数据纪录, 每一个数据纪录属于且仅属于一个分组. 常见的算法如: K-means算法[3]、K-medois算法[4]和CLARANS算法[5]等. 层次聚类就是对给定的数据集进行层次分解或者合并, 直到所有的记录组成一个分组或者某个条件满足为止, 具体又可分为合并(自底向上)和分解(自顶向下)两种方案, 常见的算法有: Birch 算法、Cure算法等[6,7]. 基于密度的聚类克服了传统基于距离的聚类算法只能发现超球形类的缺点, 该方法的基本思想是只要一个区域中点的密度大于某个阀值, 就把它加到与之相近的聚类中去, 其代表算法有DBSCAN算法[8]、OPTICS算法[9]等. 基于网格的聚类方法把对象空间量化为有限数目的网格单元, 形成一个网格结构, 所有的聚类操作都在这个量化空间进行, 常见的网格聚类算法有STING算法[10]和CLIQUE算法[11]. 此外, 基于模型的聚类[12]和基于谱的聚类[13,14]也被众多学者所研究.
在众多的聚类方法中, k-means方法是一种最经典的应用最为广泛的聚类方法[15,16]. 该方法以各类样本的质心代表该类进行不断迭代, 但该方法只适用于数值型属性数据, 对超球形和凸形数据有较好的聚类效果. 但是, 经典k-means算法只能处理静态数据的聚类问题, 对于数据不断发生变化特别是包含概念漂移现象的动态聚类问题, 当数据集更新时, 经典k-means方法需要重新对更新后的整个数据集进行聚类, 因此, 对于动态数据的聚类问题, 每当数据更新一次时, 算法就相当于在整个工作集上重新执行一次, 其执行效率是比较低的.
针对传统k-means方法不能有效处理动态数据聚类的问题, 本文在经典k-means聚类方法的基础上, 通过对新加入的样本与已进行的聚类之间的关系进行分析, 有效地检测发生聚类概念漂移和未发生聚类概念漂移的情况, 对于少数新加入样本后可能产生聚类概念漂移的样本采用经典k-means聚类方法重新聚类, 而对于大多数未产生聚类概念漂移的样本所属类别只需要一个简单的更新, 而不需要在整个数据集上重新聚类, 大大增加了新加入样本时聚类的执行效率, 并且能够有效检测动态聚类过程中所发生的概念漂移现象.
1经典k-means聚类方法
设数据集{}
1
n
i i
X x
=
=且d
i
x R
∈, k为指定的聚类个数. K-means算法的基本工作过程为: 首先, 从n个数据对象中随机选择k个对象作为初始聚类中心, 其它对象则根据其与已得到的聚类中心的相似度分别分
配到最相似的类中. 计算相似度的公式如下, 假设
j
c
为第j个类的类中心, 则
i
x与第j类的相似度定义为:
(1)
然后, 计算每个更新类的新聚类中心, 假设第j
类中的样本为{
12
,,,
j
j j jn
x x x
???}, 即包含
j
n个样本, 该
类的聚类中心为
1
{}p d
j j p
c c
=
=, 其中, p
j
c为类中心
j
c的第p个属性, 则聚类中心第p个属性分量的求法如下:
(2)
不断循环迭代, 直到标准测度函数收敛为止(从表现形式上看即更新后的聚类中心与更新前一致), 一般采用均方差作为标准测度函数, 其形式为:
(3)
最终得到的聚类结果中聚类内部应当尽可能紧凑, 不同类类间应当尽可能分离.
但是, 经典k-means聚类方法由于需要在每次聚类时衡量所有样本到每个类中心的相似度, 因此算法复杂度较高, 运行速度较慢, 若针对动态数据, 每次都在整个数据集上进行聚类显然是不现实的. 因此, 针对k-means方法不能有效处理动态数据聚类的问题, 本文提出一种能够有效处理动态数据聚类问题的改进的动态k-means聚类方法, 该方法通过不断地衡量新来样本与已经产生的聚类之间的关系, 仅仅对与新样本有关的类别进行简单更新, 而不需要在整个更新后的数据集上重新进行聚类, 从而大幅度地提高了k-means处理动态数据聚类问题的执行效率, 并有效检测动态聚类过程中的概念漂移现象.
1
(,)
(,)
i j
i j
s x Class
d x c
==
1
j
n
p p
j jq j
q
c x n
=
=∑
J=
2 动态k-means 聚类方法
设数据集 且d i x R ∈, k 为指定聚类个
数. 由于经典k-means 方法只能对静态数据集(即数据集本身在聚类过程中不发生变化)的问题进行有效聚类, 而对于动态数据集(如聚类过程中数据逐个增加)的聚类问题, 传统k-means 方法必须每次都重新对更新后的整个数据集重新聚类. 由第二节知, 经典
k-means 聚类方法处理静态数据的复杂度为()O nkl , 其中n 为聚类的样本规模, k 为聚类个数, l 为迭代次数. 采用经典k-means 方法处理动态数据, 其复杂度为
()O nklm , 其中m 为更新的样本数. 若更新较多时, 其
复杂度是非常大的. 针对这个问题, 本文提出了一种改进的动态k-means 聚类方法(Dynamical k-means)用于处理动态数据的聚类问题, 该方法首先对原始的样本集进行初始聚类, 得到一个初始的聚类模式. 当有新样本进入时, 通过衡量该样本与已经得到的不同类之间的相似性关系, 来衡量是否发生聚类概念漂移, 若没有发生概念漂移, 则将其划分到相似度大的类中, 而不需要重新在整个更新的数据集上进行聚类, 否则需要在整个数据集上重新进行聚类, 从而得到更新后的训练结果, 如此反复迭代直到没有新的数据加入或者聚类模式不再发生改变为止.
动态k-means 聚类算法:
Step1: 选择包含n 个数据对象的样本集{}1
n i i X x ==
(其中d
i x R ∈)进行初始的k-means 聚类, 得到初始聚类模式1{}k j j X X =→. 具体方法如下:
Step1.1: 设置初始聚类个数参数k , 初始化聚类目标函数(0)10J =, 初始化聚类中心集C φ=, 随机选择k 个样本作为初始聚类中心;
Step1.2: 根据式(1)计算每个样本i x (1,,i n =???)与所有不同的类(1,,)j Class j k =???之间的相似度, 并将i x 归为与其最相似的类中心所属的类;
Step1.3: 根据式(2)计算样本重新分配后的每个类的中心 ;
Step1.4: 根据式(3)计算当前的目标函数, 并计算
()()(1)111t t t r J J
?=?, 若()1t r 为0或者达到迭代步骤的上限
值时, 则初始聚类结束; 否则更新t 值, 并返回Step1.2反复迭代执行, 直到()1t r 为0时聚类结束, t 就是本次
聚类需要迭代的次数.
Step2: 设第l 次更新数据集时新添加的对象为
n l x +, 对新的数据集进行聚类. 根据式(1)计算n l x +与初始得到的k 个类的相似度(,)n l j s x Class +, 1,2,,j k =???.
Step3: 取 中所对应相似度的最大值, 并根据式(4)将n l x +入该最大值所对应的第j 类当中:
(4) 同时, 根据式(5)计算更新类的新的类心, 其第p 个属性分量为
(5)
Step4: 根据式(3)计算当前的目标函数l J , 并与上次得到的目标函数1l J ?进行比较, 设1l l J J ?Δ=?, 如果εΔ>, 则发生聚类概念漂移, 对新添加后的整个数据集进行经典k-means 聚类; 反之, 若εΔ≤, 则没发生聚类概念漂移, 执行Step5. 在实际问题中, 参数ε可根据情况自行选取.
Step5: 观察是否有样本继续更新, 若有, 则返回Step2继续执行, 若没有, 则输出最终聚类结果.
算法结束.
3 实验结果及分析
为验证本文提出的改进动态k-means 聚类方法的有效性, 在四个标准数据集和一个模拟的社会网络数据集上进行了实验, 并将聚类结果与经典k-means 方法所得到的聚类结果进行了比较. 实验在1台PC 机
(2.66Ghz CPU, 1G 内存)上进行测试, 实验平台是Matlab7.0.
实验采用的标准数据集见表1, 这些数据集可从网站https://www.doczj.com/doc/8e13953646.html,/~mlearn/MLRepository.html 上下载. 实验中, 所有数据集进行10等分(Spambase 数据集第一份比其它份多1个样本, 即第一份包含174个样本), 其中9份用于初始k-means 聚类, 剩余1份用于数据集的动态变化的新增样本集.
表1 标准数据集
数据集
训练集 规模
新增样本 规模
数据维数
ASL 250 25 22 Breast_cancer 1900
190
9 Spambase 1731 173 57 Flare_solar 3330 333
9
设置初始聚类个数均为20, 四个标准数据集分别通过25、200、173、333次数据更新, 参数ε取每次更新前目标函数的1/10, 图1给出了本文提出的动态
{}1
n i i X x ==1
()(1)
j
n p p p j
jq n l j q c x x n +==++∑()1{}t k j j C c =={|(,)(,),}j j n l n l j n l i X X x s x c s x c j i +++=≥≠∪(,)n
l j s x Class +
k-means 聚类方法及经典k-means 聚类方法在ASL 数据集上每一次新样本加入后所需要的J 值和训练时间随着新样本加入而得到的变化趋势图.
(a) J 值
(b) 聚类时间 图1 ASL 数据集
从图1可以看出, 在标准数据集ASL 上, 尽管动态k-means 聚类方法的J 值稍许偏高, 但其聚类时间缩短了很多. 此外, 动态k-means 方法能准确地检测出有
1个新增样本加入时发生了聚类概念漂移. 由于当新增样本没有被检测为聚类概念漂移点时, 只需要简单地把该样本归于最相似的类别, 而不需要进行全局的
k-means 聚类, 因此, 采用动态k-means 的方法多数数据加入时聚类时间均近似为0.
在其他数据集上同样做了相同的实验, 当新增样本较多时, 统计图无法清晰地看出样本变化的情况, 因此采用以下几个指标衡量算法效果. 设新增样本集为X , 每个数据集中实际发生概念漂移的样本集合为
1X , 其规模为1n , 本文方法检测到的聚类概念漂移样本集合为2X , 其规模为2n , 概念漂移样本检测率为1p 、错检率为2p 、传统k-means 方法整个过程的训练时间1t 与动态k-means 方法整个过程的训练时间2t . 其中, 检测率1p 、错检率2p 定义如下:
(6)
(7)
其他标准数据集上的实验结果见表2. 表2 各标准数据集上得到的实验结果
Datasets
1n 2n 1p (%) 2p (%)
1t (s)
2t (s)
ASL 1 1 100 0 83.4 5.65 Breast_cancer
4 7 100 1.58 573 19.3
Spambase 6 8 83.3 1.73 509 24.6 Flare_solar 11 29 100 5.41 134 48.9
从表2中可以看出, 除标准数据集Spambase 之外, 其他标准数据集中实际发生概念漂移的样本点的检测率都为100%, 标准数据集Spambase 的检测率也在
80%以上, 也就是说对于标准数据集Spambase, 本文提出的动态k-means 聚类方法只有一个聚类概念漂移的新增样本没有被检测到; 除标准数据集Flare_solar 之外, 其他标准数据集的概念漂移样本误检率都低于
2%, 尽管标准数据集Flare_solar 的误检率达到了5.41%, 但相对于大规模的新增样本集来说, 发生误检的样本依然是较少的; 由于动态k-means 聚类方法只有少数的被检测为聚类概念漂移的样本进入时, 才对整个数据集进行一次k-means 聚类, 而其他情况下只根据其与已有类别的相似性来进行划分, 因此训练效率得到了大幅度提高.
此外, 本文还将动态k-means 方法应用于人工模拟的网络社团结构数据集中, 并与传统k-means 方法进行了对比. 该人工模拟的网络社团机构数据集包含
100个顶点, 它们被划分成相同大小的4个社团结构, 每个社团结构包含25个顶点, 且所有顶点的度均符合如下条件:
(8) 其中in z 为每个顶点随机指向落在相同社团中顶点的有向边数目, out z 为每个顶点随机指向落在不同社团中顶点的有向边数目. 图2为网络中100个顶点在in z =12, out z =3时被划分成4个社团结构时的示意图. 实验中, 将前70个数据作为初始样本集, 后30个数据作为动态变化的新增样本集. 实验结果所测得到的J 值和训练时间如图3所示.
2122()X X X p X
?=
∩1211X X p n =
∩15in out z z +=
图2人工模拟网络社团结构数据集
(a)J值
(b)训练时间
图3网络社团结构数据集实验结果
从以上实验结果可以看出, 在构造的网络社团结构数据集上, 尽管动态k-means聚类方法的J值稍许偏高, 但其聚类时间缩短了很多. 此外, 动态k-means方法检测了两个新加入的样本发生了聚类概念漂移, 其中第5个样本点是正常概念漂移点, 而第13个样本点是错误检测的概念漂移样本点. 由于当新增样本没有被检测为聚类概念漂移点时, 只需要简单地把该样本归于最相似的类别, 而不需要进行全局的k-means聚类, 因此, 这个过程所耗费的时间忽略不计.
综上可看出, 本文提出的动态k-means方法能够以较高的训练效率处理在线聚类问题, 并有效检测在线学习过程中发生的概念漂移问题, 从而及时地更正模型.
4结语
K-means方法是目前机器学习领域常用的一种有效聚类方法, 本文针对经典k-means聚类方法对动态数据聚类的问题需要每次都进行整个数据集的聚类而导致聚类效率低下的问题, 提出了一种专门用来处理动态数据聚类的动态k-means聚类方法, 该方法通过衡量新添加样本与已有聚类模式之间的关系, 根据目标函数改变情况决定进行简单地选择最相似的类别进行局部更新还是重新进行全局经典k-means聚类, 以大幅度提高算法的执行效率, 并有效检测发生概念漂移的问题. 在未来的工作中, 将进一步探索加速k-means聚类方法的动态聚类机制, 并与PCA等特征选择方法相结合, 使其能够被应用到诸如在线图像自动处理、在线网页自动分类等高维的实际动态聚类问题中.
参考文献
1 https://www.doczj.com/doc/8e13953646.html,/files/mail_con.php?mid=1735,2011, 7.
2 Jain AK,Murty MN,Flynn PJ.Data clustering:a review.ACM Computing Surveys,1999,31(3):264?323.
3 MacQueen J.Some methods for classification and analysis of multivariate observations.Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability,Ber- keley,1967,1:281?297.
4 Kaufman L,Peter JR. Finding groups in data:an introduction to cluster analysis.Washington:John Wiley & Sons,1990.
5 Ng RT,Han JW.Efficient and effective clustering methods for spatial data mining.Proceedings of the 20th International Conference on Very Large Data Bases (VLDB1994),Santiago, 1994:144?145.
6 Cilibrasi RL,Vitányi PM.A fast quartet tree heuristic for hierarchical clustering.Pattern recognition,2011,44(3):662?677.
7 白旭,靳志军. K-中心点聚类算法优化模型的仿真研究.计
算机仿真,2011,28(1):218?221.
8 Ester M,Kriegel HP,Sander J.A density-based algorithm for
discovering clusters in large spatial databases with noise. Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD1996),Portland,Oregon, 1996:125?138.
9 武佳薇,李雄飞,孙涛等.邻域平衡密度聚类算法.计算机研
究与发展,2010,47(6):1044?1052.
10 Su MC,Chou CH.A modified version of the k-means
algorithm with distance based on cluster symmetry.IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001,23(6):674?680.
11 Agrawal R,Gehrke J,Gunopulos D,et al.Automatic subspace
clustering of high dimensional data for data mining applica- tion.Proceedings of the ACM SIGMOD Conference on Management of Data (SIGMOD1998),Seattle,1998:94?104.
(上接第106页)
统定位性能相较于原LANDMARC系统也有很好地改善, 系统算法的复杂度得到了明显的减小. 从而, 验证了本文提出的改进方案以及算法的改进思路是可行的, 并且改进优化后的系统对于定位精度和定位性能有较高需求的应用场景具有现实的应用价值及意义.
参考文献
1 J.Hightower and G.Borriello,A survey and taxonomy of loca- tion sensing systems for ubiquitous computing,CSE 01-08-03, University of Washington,Department of Computer Science and Engineering,Seattle,WA,Aug.2001.
2 Ni L M,Liu Yunhao,Lau Y C,et https://www.doczj.com/doc/8e13953646.html,NDMARC:Indoor Loca-
tion sensing Using Active RFID.Wireless Networks,2004,10
(6):701?710. 12 李凯,李昆仑,崔丽娟. 模糊聚类在集成学习中的应用研究.
计算机研究与发展,2007,44(z2):203?207.
13 王玲,薄列峰,焦李成.密度敏感的半监督谱聚类.软件学报,
2007,18(10):2412?2422.
14 王会青,陈俊杰,郭凯.遗传优化的谱聚类方法研究.计算机
工程与应用,2011,47(14):143?145.
15 Kanungo T,Mount DM.A local search approximation
algorithm for k-means https://www.doczj.com/doc/8e13953646.html,putational Geometry, 2004,28(2/3):89?112.
16 Elkan https://www.doczj.com/doc/8e13953646.html,ing the triangle inequality to accelerate k-means.
Proceedings of the Twentieth International Conference on Machine Learning(ICML-2003),Menlo Park,AAAI Press, 2003:147?153.
3 孙瑜,范平志.射频识别技术及其在定位中的应用.计算机应用,2005,6(5):1205?1208.
4 王远哲,毛陆虹,刘辉,肖基诰.基于参考标签的射频识别定
位算法研究与应用.通信学报,2010,31(2):86?92.
5 邓辉舫,马启平,周尚伟.使用无线射频识别(RFID)技术进行
室内定位.计算机应用,2008,28(7):1858?1865.
6 韩下林,赵卫东,季军,卫岗,柳先辉.基于RFID的室内定位
算法及其改进[A].计算机工程与应用,2008,45(11):47?69.
7 周艳,李海成.基于RSSI无线传感器网络空间定位算法.通
信学报,2009,30(6):75?79.
8 中国射频识别(RFID)技术政策白皮书[P].北京:中华人民共
和国科学技术部等十五部委,2006.
K-means聚类算法 K-means也是聚类算法中最简单的一种了，但是里面包含的思想却是不一般。最早我使用并实现这个算法是在学习韩爷爷那本数据挖掘的书中，那本书比较注重应用。看了Andrew Ng的这个讲义后才有些明白K-means后面包含的EM思想。 聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设 宇宙中的星星可以表示成三维空间中的点集。聚类的目的是找到每个样本x潜在的类别y，并将同类别y的样本x放在一起。比如上面的星星，聚类后结果是一个个星团，星团里面的点相互距离比较近，星团间的星星距离就比较远了。 在聚类问题中，给我们的训练样本是，每个，没有了y。 K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下： 1、随机选取k个聚类质心点（cluster centroids）为。 2、重复下面过程直到收敛 { 对于每一个样例i，计算其应该属于的类 对于每一个类j，重新计算该类的质心 } K是我们事先给定的聚类数，代表样例i与k个类中距离最近的那个类，的值 是1到k中的一个。质心代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距离，然后选取 距离最近的那个星团作为，这样经过第一步每一个星星都有了所属的星团；第二步对于
每一个星团，重新计算它的质心（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。 下图展示了对n个样本点进行K-means聚类的效果，这里k取2。 K-means面对的第一个问题是如何保证收敛，前面的算法中强调结束条件就是收敛，可以证明的是K-means完全可以保证收敛性。下面我们定性的描述一下收敛性，我们定义畸变函数（distortion function）如下： J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当 前J没有达到最小值，那么首先可以固定每个类的质心，调整每个样例的所属的类别来让J函数减少，同样，固定，调整每个类的质心也可以使J减小。这两个过程就是内循环中使J单调递减的过程。当J递减到最小时，和c也同时收敛。（在理论上，可以有多组不同的和c值能够使得J取得最小值，但这种现象实际上很少见）。
实验三 K-Means聚类算法 一、实验目的 1) 加深对非监督学习的理解和认识 2) 掌握动态聚类方法K-Means 算法的设计方法 二、实验环境 1) 具有相关编程软件的PC机 三、实验原理 1) 非监督学习的理论基础 2) 动态聚类分析的思想和理论依据 3) 聚类算法的评价指标 四、算法思想 K-均值算法的主要思想是先在需要分类的数据中寻找K组数据作为初始聚类中心，然后计算其他数据距离这三个聚类中心的距离，将数据归入与其距离最近的聚类中心，之后再对这K个聚类的数据计算均值，作为新的聚类中心，继续以上步骤，直到新的聚类中心与上一次的聚类中心值相等时结束算法。 实验代码 function km(k,A)%函数名里不要出现“-” warning off [n,p]=size(A);%输入数据有n个样本，p个属性 cid=ones(k,p+1);%聚类中心组成k行p列的矩阵,k表示第几类，p是属性 %A(:,p+1)=100; A(:,p+1)=0; for i=1:k %cid(i,:)=A(i,:); %直接取前三个元祖作为聚类中心 m=i*floor(n/k)-floor(rand(1,1)*(n/k)) cid(i,:)=A(m,:); cid; end Asum=0; Csum2=NaN; flags=1; times=1; while flags flags=0; times=times+1; %计算每个向量到聚类中心的欧氏距离 for i=1:n
for j=1:k dist(i,j)=sqrt(sum((A(i,:)-cid(j,:)).^2));%欧氏距离 end %A(i,p+1)=min(dist(i,:));%与中心的最小距离 [x,y]=find(dist(i,:)==min(dist(i,:))); [c,d]=size(find(y==A(i,p+1))); if c==0 %说明聚类中心变了 flags=flags+1; A(i,p+1)=y(1,1); else continue; end end i flags for j=1:k Asum=0; [r,c]=find(A(:,p+1)==j); cid(j,:)=mean(A(r,:),1); for m=1:length(r) Asum=Asum+sqrt(sum((A(r(m),:)-cid(j,:)).^2)); end Csum(1,j)=Asum; end sum(Csum(1,:)) %if sum(Csum(1,:))>Csum2 % break; %end Csum2=sum(Csum(1,:)); Csum; cid; %得到新的聚类中心 end times display('A矩阵，最后一列是所属类别'); A for j=1:k [a,b]=size(find(A(:,p+1)==j)); numK(j)=a; end numK times xlswrite('data.xls',A);
k-means 算法 一．算法简介 k -means 算法，也被称为k -平均或k -均值，是一种得到最广泛使用的聚类算法。 它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。 二．划分聚类方法对数据集进行聚类时包括如下三个要点： （1）选定某种距离作为数据样本间的相似性度量 k-means 聚类算法不适合处理离散型属性，对连续型属性比较适合。因此在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离。下面我给大家具体介绍一下欧式距离。 假设给定的数据集 ，X 中的样本用d 个描述属性A 1,A 2…A d 来表示，并且d 个描述属性都是连续型属性。数据样本x i =(x i1,x i2,…x id ), x j =(x j1,x j2,…x jd )其中，x i1,x i2,…x id 和x j1,x j2,…x jd 分别是样本x i 和x j 对应d 个描述属性A 1,A 2,…A d 的具体取值。样本xi 和xj 之间的相似度通常用它们之间的距离d(x i ,x j )来表示，距离越小，样本x i 和x j 越相似，差异度越小；距离越大，样本x i 和x j 越不相似，差异度越大。 欧式距离公式如下： （2）选择评价聚类性能的准则函数 k-means 聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X ，其中只包含描述属性，不包含类别属性。假设X 包含k 个聚类子集X 1,X 2,…X K ； {} |1,2,...,m X x m total ==() ,i j d x x =
J.B.MacQueen 在 1967 年提出的K-means算法[22]到目前为止用于科学和工业应用的诸多聚类算法中一种极有影响的技术。它是聚类方法中一个基本的划分方法，常常采用误差平方和准则函数作为聚类准则函数，误差平方和准则函数定义为： (3-1)其中，是类中数据对象的均值，即，(j=1,2,…，n)，是K个聚类中心，分别代表K个类。 K-means算法的工作原理：算法首先随机从数据集中选取 K个点作为初始聚类中心，然后计算各个样本到聚类中的距离，把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结束，聚类准则函数已经收敛。本算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确。若不正确，就要调整，在全部样本调整完后，再修改聚类中心，进入下一次迭代。如果在一次迭代算法中，所有的样本被正确分类，则不会有调整，聚类中心也不会有任何变化，这标志着已经收敛，因此算法结束。 算法描述如下： 算法：K-means。划分的 K-means 算法基于类中对象的平均值。 输入：类的数目K和包含N个对象的数据库。 方法： ① 对于数据对象集，任意选取K个对象作为初始的类中心； ② 根据类中对象的平均值，将每个对象重新赋给最相似的类； ③ 更新类的平均值，即计算每个类中对象的平均值； ④ Repeat ②③； ⑤ 直到不再发生变化。 其中，初始聚类中心的选择对聚类结果的影响是很大的，如图3.1，图a是三个类的实际分布，图b是选取了好的初始聚类中心（+字标记的数据对象）得到的结果。图c是选取不好的初始聚类中心得到的结果，从中可以看到，选择初始聚类中心是很关键的。 a b c
K-均值聚类算法 1.初始化：选择c 个代表点,...,,321c p p p p 2.建立c 个空间聚类表：C K K K ...,21 3.按照最小距离法则逐个对样本X 进行分类： ),(),,(min arg J i i K x add p x j ?= 4.计算J 及用各聚类列表计算聚类均值，并用来作为各聚类新的代表点（更新代表点） 5.若J 不变或代表点未发生变化，则停止。否则转2. 6.),(1∑∑=∈=c i K x i i p x J δ 具体代码如下： clear all clc x=[0 1 0 1 2 1 2 3 6 7 8 6 7 8 9 7 8 9 8 9;0 0 1 1 1 2 2 2 6 6 6 7 7 7 7 8 8 8 9 9]; figure(1) plot(x(1,:),x(2,:),'r*') %%第一步选取聚类中心，即令K=2 Z1=[x(1,1);x(2,1)]; Z2=[x(1,2);x(2,2)]; R1=[]; R2=[]; t=1; K=1;%记录迭代的次数 dif1=inf; dif2=inf; %%第二步计算各点与聚类中心的距离 while (dif1>eps&dif2>eps) for i=1:20 dist1=sqrt((x(1,i)-Z1(1)).^2+(x(2,i)-Z1(2)).^2); dist2=sqrt((x(1,i)-Z2(1)).^2+(x(2,i)-Z2(2)).^2); temp=[x(1,i),x(2,i)]'; if dist1 matlab实现Kmeans聚类算法 1.简介： Kmeans和应用于混合高斯模型的受限EM算法是一致的。高斯混合模型广泛用于数据挖掘、模式识别、机器学习、统计分析。Kmeans 的迭代步骤可以看成E步和M步，E：固定参数类别中心向量重新标记样本，M：固定均值只考虑（估计）了均值，而没有估计类别的方差，所以聚类的结构比较适合于特征协方差相等的类别。 Kmeans在某种程度也可以看成Meanshitf的特殊版本，Meanshift 是所以Meanshift可以用于寻找数据的多个模态（类别），利用的是梯度上升法。在06年的一篇CVPR文章上，证明了Meanshift方法是牛顿拉夫逊算法的变种。Kmeans和EM算法相似是指混合密度的形式已知（参数形式已知）情况下，利用迭代方法，在参数空间中搜索解。而Kmeans和Meanshift相似是指都是一种概率密度梯度估计的方法，不过是Kmean选用的是特殊的核函数（uniform kernel），而与混合概率密度形式是否已知无关，是一种梯度求解方式。 k-means是一种聚类算法，这种算法是依赖于点的邻域来决定哪些点应该分在点，也可以对高维的空间（3维，4维，等等）的点进行聚类，任意高维的空间都可以。 上图中的彩色部分是一些二维空间点。上图中已经把这些点分组了，并使用了不同的颜色对各组进行了标记。这就是聚类算法要做的事情。 这个算法的输入是： 1：点的数据（这里并不一定指的是坐标，其实可以说是向量） 2：K，聚类中心的个数（即要把这一堆数据分成几组） 所以，在处理之前，你先要决定将要把这一堆数据分成几组，即聚成几类。但并不是在所有情况下，你都事先就能知道需要把数据聚成几类的。意味着使用k-means就不能处理这种情况，下文中会有讲解。 把相应的输入数据，传入k-means算法后，当k-means算法运行完后，该算法的输出是： 1：标签（每一个点都有一个标签，因为最终任何一个点，总会被分到某个类，类的id号就是标签） 2：每个类的中心点。 标签，是表示某个点是被分到哪个类了。例如，在上图中，实际上有4中“标签”，每个“标签”使用不同的颜色来表示。所有黄色点我们可以用标签以看出，有3个类离的比较远，有两个类离得比较近，几乎要混合在一起了。 当然，数据集不一定是坐标，假如你要对彩色图像进行聚类，那么你的向量就可以是(b,g,r)，如果使用的是hsv颜色空间，那还可以使用(h,s,v),当然肯定可以有不同的组合例如(b*b,g*r,r*b) ，(h*b,s*g,v*v)等等。 在本文中，初始的类的中心点是随机产生的。如上图的红色点所示，是本文随机产生的初始点。注意观察那两个离得比较近的类，它们几乎要混合在一起，看看算法是如何将它们分开的。 类的初始中心点是随机产生的。算法会不断迭代来矫正这些中心点，并最终得到比较靠5个中心点的距离,选出一个距离最小的(例如该点与第2个中心点的距离是5个距离中最小的),那么该点就归属于该类.上图是点的归类结果示意图. 经过步骤3后,每一个中心center(i)点都有它的”管辖范围”,由于这个中心点不一定是这个管辖范围的真正中心点,所以要重新计算中心点,计算的方法有很多种,最简单的一种是,直接计算该管辖范围内所有点的均值,做为心的中心点new_center(i). 如果重新计算的中心点new_center(i)与原来的中心点center(i)的距离大于一定的阈值（该阈值可以设定），那么认为算法尚未收敛，使用new_center(i)代替center(i)（如图，中心点从红色点 K-均值分类算法实例 第一步：取K=2，并选 z 1(1)=x 1=(0 0)T z 2(1)=x 2=(1 0)T 第二步：因)1()1(2111z x z x -<-，故)1(11S x ∈ 因)1()1(2212z x z x ->-，故)1(22S x ∈ 因)1()1(2313z x z x -<-，故)1(13S x ∈ …… 得到： S 1(1)={x 1, x 3} S 2(1)={x 2, x 4, x 5, …, x 20} 第三步：计算新的聚类中心 ∑∈??? ? ??=+==)1(311115.00.0)(211)2(S x x x x N z ∑∈???? ??=+++==)1(20422 2233.567.5)(1811)2(S x x x x x N z 第四步：因)1()2(j j z z ≠，j=1,2，返回第二步； 第二步（返回1）：由新的聚类中心，得到： 8,,2,1,)2()2(21 =-<-l z x z x l l 20,,10,9,)2()2(21 =->-l z x z x l l 因此 S 1(2)={x 1, x 2, …, x 8} S 2(2)={x 9, x 10, …, x 20} 第三步（返回1）：计算聚类中心 ∑∈??? ? ??=+++==)2(82111113.125.1)(811)3(S x x x x x N z ∑∈??? ? ??=+++==)2(2010922233.767.7)(1211 )3(S x x x x x N z 第四步（返回1）：因)2()3(j j z z ≠，j=1,2，返回第二步； 第二步（返回2）：分类结果与前一次迭代的结果相同，即S 1(4)=S 1(3)， S 2(4)= S 2(3)； 第三步（返回2）：聚类中心与前一次迭代的结果相同； 第四步（返回2）：因)3()4(j j z z =，j=1,2，算法收敛，得到最终的聚 类中心。 ??? ? ??=13.125.11z ???? ??=33.767.72z 2.K-MEANS算法 k-means 算法接受输入量k ；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较低。簇的相似度是关于簇中对象的均值度量，可以看作簇的质心(centriod)或重心(center of gravity)。 k-means 算法的工作过程说明如下：首先从n个数据对象任意选择k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数.，其定义如下： ∑=∈- = E k i C p i i m p 1 2 | | （1） 其中，E是数据集中所有对象的平方误差和，p是空间中的点，表示给定对象， i m是簇i C的均值（p和i m都是多维的）。换句话说，对于每个簇中的每个对象，求对象到其簇中心距离的平方，然后求和。这个准则试图使生成的k个结果簇尽可能的紧凑和独立。 K均值算法试图确定最小化平方误差的k个划分。当结果簇是紧凑的，并且簇与簇之间明显分离时，它的效果较好。对处理大数据集，该算法是相对可伸缩的和有效率的，因为它的计算复杂度是O（nkt），其中n是对象的总数，k是簇的个数，t 是迭代的次数。通常地，k< 1案例题目： 选取一组点（三维或二维），在空间内绘制出来，之后根据K均值聚类，把这组点分为n类。 此例中选取的三维空间内的点由均值分别为(0,0,0),(4,4,4),(-4,4,-4)， 协方差分别为 300 030 003 ?? ?? ?? ?? ?? ， 000 030 003 ?? ?? ?? ?? ?? ， 300 030 003 ?? ?? ?? ?? ?? 的150个由mvnrnd函数随机 生成。 2原理运用与解析： 2.1聚类分析的基本思想 聚类分析是根据“物以类聚”的道理，对样本或指标进行分类的一种多元统计分析方法，它们讨论的对象是大量的样本，要求能合理地按各自的特性进行合理的分类。对于所选定的属性或特征，每组内的模式都是相似的，而与其他组的模式差别大。一类主要方法是根据各个待分类模式的属性或特征相似程度进行分类，相似的归为一类，由此将待分类的模式集分成若干个互不重叠的子集，另一类主要方法是定义适当的准则函数运用有关的数学工具进行分类。由于在分类中不需要用训练样本进行学习和训练，故此类方法称为无监督分类。 聚类的目的是使得不同类别的个体之间的差别尽可能的大，而同类别的个体之间的差别尽可能的小。聚类又被称为非监督分类，因为和分类学习相比，分类学习的对象或例子有类别标记，而要聚类的例子没有标记，需要由聚类分析算法来自动确定，即把所有样本作为未知样本进行聚类。因此，分类问题和聚类问题根本不同点为：在分类问题中，知道训练样本例的分类属性值，而在聚类问题中，需要在训练样例中找到这个分类属性值。 聚类分析的基本思想是认为研究的样本或变量之间存在着程度不同的相似性（亲疏关系）。研究样本或变量的亲疏程度的数量指标有两种：一种叫相似系数，性质越接近的样本或变量，它们的相似系数越接近1或-1，而彼此无关的变量或样本它们的相似系数越接近0，相似的为一类，不相似的为不同类。另一种叫距离，它是将每一个样本看做p维空间的一个点，并用某种度量测量点与点之 浙江大学算法研究实验报告 数据挖掘 题目：K-means 目录 一、实验内容 (5) 二、实验目的 (7) 三、实验方法 (7) 3.1软、硬件环境说明 (7) 3.2实验数据说明 (7) 图3-1 (7) 3.3实验参数说明/软件正确性测试 (7) 四、算法描述 (9) 图4-1 (10) 五、算法实现 (11) 5.1主要数据结构描述 (11) 图5-1 (11) 5.2核心代码与关键技术说明 (11) 5.3算法流程图 (14) 六、实验结果 (15) 6.1实验结果说明 (15) 6.2实验结果比较 (21) 七、总结 (23) 一、 实验内容 实现K-means 算法，其中该算法介绍如下： k-means 算法是根据聚类中的均值进行聚类划分的聚类算法。 输入：聚类个数k ，以及包含n 个数据对象的数据。 输出：满足方差最小标准的k 个聚类。 处理流程： Step 1. 从n 个数据对象任意选择k 个对象作为初始聚类中心； Step 2. 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分； Step 3. 重新计算每个（有变化）聚类的均值（中心对象） Step 4. 循环Step 2到Step 3直到每个聚类不再发生变化为止； k-means 算法的工作过程说明如下：首先从n 个数据对象任意选择k 个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下： 21∑∑=∈-=k i i i E C p m p (1) 其中E 为数据库中所有对象的均方差之和，p 为代表对象的空间中的一个点，m i 为聚类C i 的均值(p 和m i 均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 重点要求：用于聚类的测试级不能仅为单独的一类属性，至少有两种属性值参与聚类。 基于Matlab环境下的K均值聚类算法 摘要：为了将模式识别方法与图像处理技术相结合，掌握利用均值聚类算法进行图行处理，往往能得到比较好的处理结果，本文在matlab环境下，对有效图像点进行K均值聚类算法，与传统K近邻聚类方法比照，得出了比较好的实验效果。 关键词：K均值聚类算法matlab 图像 引言 k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。 1、K-均值聚类的分析 K-均值聚类的目的是将数据拆成K个不同的群组，该算法的特点是运算结果受到所选择的聚类中心数目、初始位置、模式样本的几何性质以及读入次序的影响。 具体的算法如下： 1、在n维空间中随机生成K个中心点 2、将每个数据项分配给与其距离最近的中心点。 3、将中心点位置移动到所有分配给它的数据项的中心。如果中心点位置没有改变，则结束算法，否则回到第二步。 2、K均值聚类算法与K近邻算法的区别 K近邻算法的基本思想是是使体积为数据的函数，而不是样本N的函数。K-最近邻也是一种用来进行预测的算法。它的工作原理是接受一个用以进行数值预测的新数据项，然后将它与一组已经赋过值的数据项进行比较。算法会从中找出与待预测数据最为接近的K项，并且这K项其求均值以得到最终的结果。优点：能利用复杂函数进行数值预测，又简单易懂，并且我们可以很容易在算法中实现查看用哪些近邻进行预测。缺点：每次进行预测，它都会使用所有的样本，这会导致效率的低下。因此，寻找缩放因子是一种很乏味的事情。 3、K均值聚类法分为如下几个步骤 function y=kMeansCluster(m,k,isRand) %%%%%%%%%%%%%%%% % % kMeansCluster - Simple k means clustering algorithm % Author: Kardi Teknomo, Ph.D. % % Purpose: classify the objects in data matrix based on the attributes % Criteria: minimize Euclidean distance between centroids and object points % For more explanation of the algorithm, see https://www.doczj.com/doc/8e13953646.html,/kardi/tutorial/kMean/index.html % Output: matrix data plus an additional column represent the group of each object % % Example: m = [ 1 1; 2 1; 4 3; 5 4] or in a nice form % m = [ 1 1; % 2 1; % 4 3; % 5 4] % k = 2 % kMeansCluster(m,k) produces m = [ 1 1 1; % 2 1 1; % 4 3 2; % 5 4 2] % Input: % m - required, matrix data: objects in rows and attributes in columns % k - optional, number of groups (default = 1) % isRand - optional, if using random initialization isRand=1, otherwise input any number (default) % it will assign the first k data as initial centroids % % Local Variables % f - row number of data that belong to group i % c - centroid coordinate size (1:k, 1:maxCol) % g - current iteration group matrix size (1:maxRow) % i - scalar iterator % maxCol - scalar number of rows in the data matrix m = number of attributes % maxRow - scalar number of columns in the data matrix m = number of objects % temp - previous iteration group matrix size (1:maxRow) % z - minimum value (not needed) K-m e a n s聚类算法基 本思想 精品文档 K-means聚类算法基本思想 聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。K-means也是聚类算法中最简单的一种。以星团划分为例，，首先随机选取k个宇宙中的点（或者k个星星）作为k 个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距离，然后选取距离最近的那个星团作为 ，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心（对里面所有的 星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。 K-means也是聚类算法中最简单的一种了，但是里面包含的思想却是不一般。最早我使用并实现这个算法是在学习韩爷爷那本数据挖掘的书中，那本书比较注重应用。看了Andrew Ng的这个讲义后才有些明白K-means后面包含的EM思想。 聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设宇宙中的星星可以表示成三维空间中的点集。 聚类的目的是找到每个样本x潜在的类别y，并将同类别y的样本x放在一起。比如上面的星星，聚类后结果是一个个星团，星团里面的点相互距离比较近，星团间的星星距离就比较远了。 在聚类问题中，给我们的训练样本是，每个，没有了y。 K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下： 1、随机选取k个聚类质心点（cluster centroids）为。 2、重复下面过程直到收敛 { 对于每一个样例i，计算其应该属于的类 对于每一个类j，重新计算该类的质心 } K是我们事先给定的聚类数，代表样例i与k个类中距离最近的那个类，的值是1到k中的一个。质心 代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距 离，然后选取距离最近的那个星团作为，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。 下图展示了对n个样本点进行K-means聚类的效果，这里k取2。 收集于网络，如有侵权请联系管理员删除 k均值算法是模式识别的聚分类问题，这是用C#实现其算法 以下是程序源代码： using System; using System.Drawing; using System.Collections; using https://www.doczj.com/doc/8e13953646.html,ponentModel; using System.Windows.Forms; using System.Data; namespace KMean_win { /// /// Form1 的摘要说明。 /// public class Form1 : System.Windows.Forms.Form { /// /// 必需的设计器变量。 /// private https://www.doczj.com/doc/8e13953646.html,ponentModel.Container components = null; private static int k = 2; //类数，此例题为2类 private static int total = 20; //点个数 private int test = 0; private PointF[] unknown = new PointF[total]; //点数组 private int[] type = new int[total]; //每个点暂时的类 public PointF[] z = new PointF[k]; //保存新的聚类中心 public PointF[] z0 = new PointF[k]; //保存上一次的聚类中心private PointF sum; private int temp = 0; private System.Windows.Forms.TextBox textBox1; private int l = 0; //迭代次数 //构造函数，初始化 public Form1() { unknown[0]=new Point(0,0); unknown[1]=new Point(1,0); unknown[2]=new Point(0,1); unknown[3]=new Point(1,1); unknown[4]=new Point(2,1); unknown[5]=new Point(1,2); unknown[6]=new Point(2,2); unknown[7]=new Point(3,2); unknown[8]=new Point(6,6); unknown[9]=new Point(7,6); unknown[10]=new Point(8,6); 在数据挖掘中，k-Means 算法是一种cluster analysis的算法，其主要是来计算数据聚集的算法，主要通过不断地取离种子点最近均值的算法。 问题 K-Means算法主要解决的问题如下图所示。我们可以看到，在图的左边有一些点，我们用肉眼可以看出来有四个点群，但是我们怎么通过计算机程序找出这几个点群来呢？于是就出现了我们的K-Means算法（Wikipedia链接） 这个算法其实很简单，如下图所示： K-Means 算法概要 从上图中，我们可以看到，A, B, C, D, E 是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有两个种子点，所以K=2。 然后，K-Means的算法如下： 1.随机在图中取K（这里K=2）个种子点。 2.然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（上图中，我们可以看到A,B属于上面的种子点，C,D,E属于下面中部的种子点） 3.接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步） 4.然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了A,B,C，下面的种子点聚合了D，E）。 这个算法很简单，但是有些细节我要提一下，求距离的公式我不说了，大家有初中毕业水平的人都应该知道怎么算的。我重点想说一下“求点群中心的算法” 求点群中心的算法 一般来说，求点群中心点的算法你可以很简的使用各个点的X/Y坐标的平均值。不过，我这里想告诉大家另三个求中心点的的公式： 1）Minkowski Distance 公式——λ 可以随意取值，可以是负数，也可以是正数，或是无穷大。 2）Euclidean Distance 公式——也就是第一个公式λ=2 的情况 3）CityBlock Distance 公式——也就是第一个公式λ=1 的情况 这三个公式的求中心点有一些不一样的地方，我们看下图（对于第一个λ 在0-1之间）。 （1）Minkowski Distance （2）Euclidean Distance （3） CityBlock Distance K-Means算法 k-means 算法接受参数k ；然后将事先输入的n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 假设要把样本集分为c个类别，算法描述如下： （1）适当选择c个类的初始中心； （2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类； （3）利用均值等方法更新该类的中心值； （4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。 #include 题目：matlab实现Kmeans聚类算法 姓名 学号 背景知识 1.简介： Kmeans算法是一种经典的聚类算法，在模式识别中得到了广泛的应用，基于Kmeans的变种算法也有很多，模糊Kmeans、分层Kmeans 等。 Kmeans和应用于混合高斯模型的受限EM算法是一致的。高斯混合模型广泛用于数据挖掘、模式识别、机器学习、统计分析。Kmeans 的迭代步骤可以看成E步和M步，E：固定参数类别中心向量重新标记样本，M：固定标记样本调整类别中心向量。K均值只考虑（估计）了均值，而没有估计类别的方差，所以聚类的结构比较适合于特征协方差相等的类别。 Kmeans在某种程度也可以看成Meanshitf的特殊版本，Meanshift 是一种概率密度梯度估计方法（优点：无需求解出具体的概率密度，直接求解概率密度梯度。），所以Meanshift可以用于寻找数据的多个模态（类别），利用的是梯度上升法。在06年的一篇CVPR文章上，证明了Meanshift方法是牛顿拉夫逊算法的变种。Kmeans 和EM算法相似是指混合密度的形式已知（参数形式已知）情况下，利用迭代方法，在参数空间中搜索解。而Kmeans和Meanshift相似是指都是一种概率密度梯度估计的方法，不过是Kmean选用的是特殊的核函数（uniform kernel），而与混合概率密度形式是否已知无关，是一种梯度求解方式。 k-means是一种聚类算法，这种算法是依赖于点的邻域来决定哪些 点应该分在一个组中。当一堆点都靠的比较近，那这堆点应该是分到同一组。使用k-means，可以找到每一组的中心点。 当然，聚类算法并不局限于2维的点，也可以对高维的空间（3维，4维，等等）的点进行聚类，任意高维的空间都可以。 上图中的彩色部分是一些二维空间点。上图中已经把这些点分组了，并使用了不同的颜色对各组进行了标记。这就是聚类算法要做的事情。 这个算法的输入是： 1：点的数据（这里并不一定指的是坐标，其实可以说是向量） 2：K，聚类中心的个数（即要把这一堆数据分成几组） 所以，在处理之前，你先要决定将要把这一堆数据分成几组，即聚成几类。但并不是在所有情况下，你都事先就能知道需要把数据聚成几类的。但这也并不意味着使用k-means就不能处理这种情况，下文中会有讲解。 把相应的输入数据，传入k-means算法后，当k-means算法运行完后，该算法的输出是： 1：标签（每一个点都有一个标签，因为最终任何一个点，总会被分到某个类，类的id号就是标签） 2：每个类的中心点。 标签，是表示某个点是被分到哪个类了。例如，在上图中，实际上 K-means聚类算法 一、K-means聚类原理 1.1 聚类算法的原理 我们经常接触到的聚类分析，一般都是数值聚类，一种常见的做法是同时提取N 种特征，将它们放在一起组成一个N 维向量，从而得到一个从原始数据集合到N 维向量空间的映射——总是需要显式地或者隐式地完成这样一个过程，然后基于某种规则进行分类，在该规则下，同组分类具有最大的相似性。 聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y 的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设宇宙中的星星可以表示成三维空间中的点集。聚类的目的是找到每个样本x潜在的类别y，并将同类别y的样本x放在一起。比如上 面的星星，聚类后结果是一个个星团，星团里面的点相互距离比较近，星团间的星星距离就比较远了。 1.2 K-means聚类原理 假设我们提取到原始数据的集合为(x 1, x 2 , …, x n)，并且每个x i为d维 的向量（d维向量由原始数据的d个特征组成），K-means聚类的目的就是，在给定分类组数k（k≤n）值的条件下，将原始数据分成k类 S = {S1, S2, …,S k}， 1.3 K-means聚类步骤 算法步骤一般如下： 1、从D中随机取k个元素，作为k个簇的各自的中心。 2、分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。 3、根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。 4、将D中全部元素按照新的中心重新聚类。 5、重复第4步，直到每个簇的中心基本不再变化。 6、将结果输出。 1.4 K-means聚类简单实例 对数据点进行聚类，详细步骤如下所示： 首先3 个中心点被随机初始化，所有的数据点都还没有进行聚类，默认全部都标记为红色，如下图所示： 然后进入第一次迭代：按照初始的中心点位置为每个数据点着上颜色，重新计算3 个中心点，结果如下图所示： K-means聚类算法综述 摘要：空间数据挖掘是当今计算机及GIS研究的热点之一。空间聚类是空间数据挖掘的一个重要功能。K-means聚类算法是空间聚类的重要算法。本综述在介绍了空间聚类规则的基础上，叙述了经典的K-means算法，并总结了一些针对K-means算法的改进。 关键词：空间数据挖掘，空间聚类，K-means，K值 1、引言 现代社会是一个信息社会，空间信息已经与人们的生活已经密不可分。日益丰富的空间和非空间数据收集存储于空间数据库中，随着空间数据的不断膨胀，海量的空间数据的大小、复杂性都在快速增长，远远超出了人们的解译能力，从这些空间数据中发现邻域知识迫切需求产生一个多学科、多邻域综合交叉的新兴研究邻域，空间数据挖掘技术应运而生。空间聚类分析方法是空间数据挖掘理论中一个重要的领域，是从海量数据中发现知识的一个重要手段。K-means算法是空间聚类算法中应用广泛的算法，在聚类分析中起着重要作用。 2、空间聚类 空间聚类是空间数据挖掘的一个重要组成部分。作为数据挖掘的一个功能，空间聚类可以作为一个单独的工具用于获取数据的分布情况，观察每个聚类的特征，关注一个特定的聚类集合以深入分析。空间聚类也可以作为其它算法的预处理步骤，比如分类和特征描述，这些算法将在已发现的聚类上运行。 空间聚类规则是把特征相近的空间实体数据划分到不同的组中，组间的差别尽可能大，组内的差别尽可能小。空间聚类规则与分类规则不同，它不顾及已知的类标记，在聚类前并不知道将要划分成几类和什么样的类别，也不知道根据哪些空间区分规则来定义类。（1）因而，在聚类中没有训练或测试数据的概念，这就是将聚类称为是无指导学习（unsupervised learning）的原因。（2） 在多维空间属性中，框定聚类问题是很方便的。给定m个变量描述的n个数据对象，每个对象可以表示为m维空间中的一个点，这时聚类可以简化为从一组非均匀分布点中确定高密度的点群。在多维空间中搜索潜在的群组则需要首先选择合理的相似性标准。（2）已经提出的空间聚类的方法很多，目前，主要分为以下4种主要的聚类分析方法（3）: ①基于划分的方法 包括K—平均法、K—中心点法和EM聚类法。它们都是采用一种迭代的重定位技术,尝试通过对象在划分间移动来改进聚类效果。由于这类方法适用于发现大小相近的球状簇,故常用在设施选址等应用中。 ②基于层次的方法 此法只是对对象集合进行分解。根据层次的分解方式,这类方法可分为凝聚和分裂两种, Birch, Cure 和Chameleon是上述方法的改进。 ③基于密度的方法 对给定类中的每个数据点,在一个给定范围的区域中必须包含超过某个阈值的数据点,才继续聚类。它可以用来发现任意形状的簇,过滤“噪声”。代表性的方法有:DBscan,Optics和Denclue。 ④基于栅格的方法 把对象空间划为有限的数据单元,形成一个网格结构。该方法处理速度快,处理时间独立于数据对象的数目。常用的方法有STING、WaveCluster以及CLIQUE等。 在这些方法中，K-means（k—均值）算法是一种应用十分广泛的聚类分析方法。 3、经典的K-Means算法 K-means聚类问题的假设是有一组N个数据的集合X={x1，x2，x3，…，x n}待聚类。Kmatlab实现Kmeans聚类算法
第二章(K均值算法实例)
K均值算法的一些介绍和基础知识
K均值聚类分析.doc
数据挖掘关于Kmeans算法的研究(含数据集)
基于Matlab环境下的K均值聚类算法
K均值算法matlab代码
K-means聚类算法基本思想讲解学习
K均值聚类算法
K均值算法
K-Means聚类算法及实现代码
(完整版)matlab实现Kmeans聚类算法
K-means算法原理及功能介绍
K-Means聚类算法
相关主题
文本预览