作业-2.k-means聚类算法

K-Means聚类算法

k-均值算法的改进

K-中心点聚类算法1.简介K-means聚类算法就是基于距离的聚类算法所谓的基于距离的聚类算法是指采用距离作为相似性度量的评价指标。2.K-means聚类算法原理K-means聚类算法的基本思想：一、指定需要划分的簇的个数k值;二、随机地选择k个初始数据对象点作为初始的聚类中心;三、计算其余的各个数据对象到这k个初始聚类中心的距离，把数据对象划归到距离它最近的那个中心所处在的簇类中;四、调整新类并且重新计算出新类的中心。2.K-means聚类算法原理开始输入聚类的个数

k,n初始化

K

个聚类中心分配各个数据对象到距离最近的类中重新计算各个聚类的中心（均值）是否收敛输出聚类结果否是K-means算法的工作流程

K-means聚类算法原理K-Means算法的工作框架：给出n

个数据样本,令I

1,随机选择K

个初始聚类中心

Z

j

(I

),j

1,2,3,,K

；求解每个数据样本与初始聚类中心的距离

Dxi,Zj

I

,i

1,2,3,,nj

1,2,3,,K

，若满足D

xi

,Z

j

I

minD

xi

,Z

j

I

,i

1,2,,n，那么xi

wk

；1

njjjni1（3）令

I

I

1,计算新聚类中心Z

2

ix

，

j

1,

2,,K

以及误差平方和

2njK

j

c

c准则函数

J

的值：

J

2

k

jx

Z

2

；j

1

k

1（4）判断:如果JcI1

JcI

，那么表示算法结束,反之,I

I

1，重新返回第（2）步执行。2.K-means聚类算法原理K-Means算法的特点就是调整一个数据样本后就修改一次聚类中心以及聚类准则函数的值，当n个数据样本完全被调整完后表示一次迭代完成，这样就会得到新的簇和聚类中心的值。K-Means聚类算法其本质是一个最优化求解的问题。K-Means算法对聚类中心采取的是迭代更新的方法。K-means聚类算法特点及应用K-means聚类算法特点优点：算法简单、快速。对处理大数据集，该算法是相对可伸缩的和高效率的。算法尝试找出使平方误差函数值最小的k个划分。缺点：（1）K-means聚类算法只有在簇的平均值被定义的情况下才能使用。要求用户必须事先给出要生成的簇的数目k。对初值敏感。不适合于发现非凸面形状的簇，或者大小差别很大的簇。对于“噪声”和孤立点数据敏感。3

K-means聚类算法特点及应用3.2

K-means聚类算法应用（1）K-means算法在散货船代货运系统中的应用（2）K-Means算法在客户细分中的应用4小结本章详细地介绍了K-means算法的基本概念、基本原理,并介绍了该算法的特点和存在的缺陷,最后介绍了K-means算法的应用,从中可以看出K-means算法的应用非常广泛。

聚类算法将数据点分为多个簇(cluster)

k-menas算法中，簇的中心叫做簇质心或中心点(centroid)，质心不一定是一个真实存在的数据点

把每个簇想像成一块有质量的物体，质心即这块物体的质量中心

k-means要求事先指定数据要

分为几组，例如可指定分为3组，这里的3即算法名称中k的含义，此时k=3图:4个簇及其质心1.随机挑选3个点作为初始簇质心(centroid)指定k=3(即要将数据点分成3组)遍历所有点，各自加入距离最近的簇调整各个簇的的质心4.回到第2步中止条件：簇不再发生变化第2步如何找到最近的簇？遍历各簇质 算欧氏距离，距离最小的即最近的第3步如何调整质心？取簇中各点的算术平均值作为新质心的坐标即可＋＋(8,7)＋＋＋＋(1,

4)(6,

0)(3,

2)(0,

8)(6,

4)(8,

4)(1,

8)(6,

8)(7,

9)(7,8)(1.25,

5.5)(6.67,

2.67)＋(5.75,

2.5)＋(0.67,

6.67)

好的聚类结果的簇内数据点比较紧凑，簇间相距大

即簇内中各数据点离质心的距离都比较小

可使用误差平方和(SSE,SumofSquaredErrors)准则函数来评价

一个簇的误差平方和即簇内各点到质心欧式距离的平方和：SSE(k)

dis

tan

ce(

p,

centroid)2pX其中p表示簇中的点，X是簇内点的集合，distance(p,centroid)即点p到簇质心的距离

聚类结果的SSE即各个簇的SSE之和，其值越小表示聚类质量越好

K-Means聚类算法

k-均值算法的改进

K-中心点聚类算法学生喜欢吃零食喜欢看韩剧喜欢打篮球喜欢玩工资A88005000B78015100C87015080D88105030E001085010F02985090G12995020H21895040结果被“工资”主导了！考虑对如下学生数据进行聚类

为什么结果被“工资”主导了？例如x2,y2的差值很大，而x1,y1等差异很小，则计算得到的欧氏距离几乎就约等于

(x2

y2

)2

解决方案:归一化v

vminv'

vmax

vminv为原特征值，v'为归一化后的值，vmin为样本最小值，vmax为样本最大值学生喜欢吃零食喜欢看韩剧喜欢打篮球喜欢玩工资A88005000B78015100C87015080D88105030E001085010F02985090G12995020H21895040归一化学生喜欢吃零食喜欢看韩剧喜欢打篮球喜欢玩工资A11000B0.875100.1111111C10.87500.1111110.8D110.100.3E0010.8888880.1F00.250.90.8888880.9G0.1250.250.910.2H0.250.1250.810.4

主要优点是解决聚类问题的经典算法，简单、快速结果簇比较密集，簇间区别明显时，效果较好

主要缺点对初始值比较敏感，不同的初始值可能会导致不同的结果对“噪声”和孤立点数据敏感，少量的该类数据能对平均值产生极大的影响在簇的平均值被定义的情况下才能使用，对分类属性不适用必须事先给出k值如何初始值选的是这两个点会怎么样？k-means++基本思路:初始的聚类中心之间的相互距离要尽可能的远算法思想:随机选择第一个簇质心对于数据集中每一个点x，计算它与最近质心的距离D(x)选择一个新数据点作为新簇质心，选择原则是:

D(x)较大的点，被选取作为聚类中心的概率较大重复2和3直到k个簇质心被选出来利用这k个初始的簇质心来运行标准的k-Means算法请课后查阅相关资料了解算法细节

K-Means聚类算法

k-均值算法的改进

K-中心点聚类算法k-中心点算法(k-me

ds)不是简单像k-means算法采用均值计算法，每次迭代后的质心都是从簇的样本点中选取，而选取的标准就是当该样本点成为新的质点后能提高簇的聚类质量，使得类簇更紧凑。算法使用SSE来定义一个簇的紧凑程度。算法步骤:随机选择k个对象作为初始的中心点；重复指派每个剩余的样本点给最近的中心点所代表的簇；随意地选择一个非中心点Orandom；计算用Orandom代替原中心点的总代价S；如果S<0(更紧凑了)，则用Orandom替换原中心点；直到不发生变化*其中

S为替换原中心点后的

SSE减去替换前的

SSE，S<0表示替换后

SSE变小了，即聚类质量更好了请课后查阅相关资料了解算法细节1.简介K中心点聚类算法重复迭代，直到每 对象都成为它的簇的实际中心点，或最靠中心的对象。聚类结果的质量用代价函数来评估，该函数用来度量对象与其簇的代表对象之间的平均相异度。2.K-中心点聚类算法原理K-中心点聚类算法的基本思想为：选用簇中位置最中心的对象，试图对n个对象给出k个划分，代表对象也被称为是中心点，其他对象则被称为非代表对象。2.K-中心点聚类算法原理在K-中心点聚类算法中需要计算所有非选中对象与选中对象之间的相异度作为分组的依据．一般情况下，数据对象为数值型，选用曼哈顿距离：d

i,

j

xi1

xj1

xi2

xj

2

xin

xjn此处：i

xi1,

xi

2

,,

xin

和

j

xj1,

xj

2

,,

xjn

是两个n维的数据对象。2.K-中心点聚类算法原理K-中心点聚类算法描述:输入：簇的数目k和包含n个对象的数据库输出：k个簇，使得所有对象与其最近中心点的相异度总和最小任意选择k个对象作为初始的簇中心点,Repeat指派每个剩余对象给离他最近的中心点所表示的簇Repeat选择一个未被选择的中心点Repeat2.K-中心点聚类算法原理K-中心点聚类算法描述:选择一个未被选择过的非中心点对象计算用代替的总代价并记录在S中Until所有非中心点都被选择过Until所有的中心点都被选择过If在S中的所有非中心点代替所有中心点后的计算出总代价有小于0的存在，then找出S中的用非中心点替代中心点后代价最小的一个，并用该非中心点替代对应的中心点，形成一个新的k个中心点的集合；Until没有再发生簇的重新分配，即所有的S都大于0.K-中心点聚类算法特点及应用K-中心点聚类算法特点优势：对噪声点/孤立点不敏感，具有较强的数据鲁棒性；聚类结果与数据对象点输入顺序无关；聚类结果具有数据对象平移和正交变换的不变性等。缺点：在于聚类过程的高耗时性。3.K-中心点聚类算法特点及应用3.2

K-中心点聚类算法应用（1）K-中心点算法在暂住人口分析中的应用（2）K-