《基本概念及k-Means算法.ppt》由会员分享，可在线阅读，更多相关《基本概念及k-Means算法.ppt（29页珍藏版）》请在三一办公上搜索。
1、数据挖掘,王成（副教授）华侨大学计算机科学与技术学院,主要内容,实例、特征及特征向量差异度度量k-均值算法,实例,输入数据集中的每一条数据都是一个样本(example)，而我们通常用更专业的术语“实例”(instance)来表示例如，下表中一共有6个实例,注:各个数字代表喜欢的程度，范围是0-10，0表示不喜欢，10表示非常喜欢,特征及特征向量,特征(feature)也称作属性(attribute)每一个单一的、独立的实例是由一组固定的和预先定义的特征或属性作为输入提供给机器学习的实例就好比是数据库表中的行，而属性是列,特征及特征向量,学生B的特征是?,学生B：(4，8，0，1),对零食喜欢程
2、度 对韩剧喜欢程度 对篮球喜欢程度 对游戏喜欢程度,特征值,学生B的特征向量,4维特征向量,特征值的类型,数值(numeric)属性实数或整数值，例如前面学生成绩例子中的学生成绩属性即是一个数值属性。,分类(categorical)属性从一个预先定义的有限的可能值的集合中取值；有时也称作名目(norminal)属性、枚举(enumerated)属性，或离散(discrete)属性。这类属性值是一些独特的符号，作为标签或名字使用。例如，天气属性是一个分类属性，它的值只能是晴、多云、雨等。,布尔(boolean)属性分类属性的一个特例，只有true和false，或yes和no两个可选值。,如何让程
3、序自动对学生分组？,如果两个学生的爱好比较类似，例如都喜欢运动，可以分为一组如果有一种方式来度量两个学生的爱好差异程度，那我们可以将差异小的学生分为同一组，而将差异大的分为不同组,主要内容,实例、特征及特征向量差异度度量k-均值算法,如何度量各个学生的差异程度？,考虑二维的情况,D(0,2),B(4,8),C(0,0),A(8,8),E(1,0),F(6,1),B和D的差异可以用BD之间的距离来表示,如何度量N维特征向量之间的差异？,欧氏距离,欧氏距离(欧几里得距离，Euclidean distance)N维空间内任意两点 x(x1,.xn)和 y(y1,.yn)之间的距离为：,欧氏距离,d(
4、A,B)=d(A,D)=d(C,E)=,?,小练习：,欧氏距离,为什么可以使用欧氏距离来体现学生之间的差异？,用于体现学生数据之间的差异的距离公式需要满足如下条件：,1.计算得到的距离不能为负数2.学生特征数据差异越大，距离也要越大，反之，差异越小，距离也要越小3.当且仅当学生特征数据相同时，距离才为0，否则大于04.学生A和学生B的距离应等于学生B和学生A的距离（对称性）,还有其它度量相异度的方法吗？,曼哈顿距离,闵可夫斯基距离,欧氏距离和曼哈顿距离可以看做是闵可夫斯基距离在p=2和p=1下的特例,主要内容,实例、特征及特征向量差异度度量k-均值算法,k-均值算法(k-Means),C4.5
5、,k-Means,SVM,Apriori,EM,PageRank,AdaBoost,kNN,Nave Bayes,CART,十大数据挖掘算法之一,一种聚类算法，属无监督学习,k-均值算法(k-Means),聚类算法将数据点分为多个簇(cluster)k-menas算法中，簇的中心叫做簇质心或中心点(centroid)，质心不一定是一个真实存在的数据点把每个簇想像成一块有质量的物体，质心即这块物体的质量中心k-means要求事先指定数据要分为几组，例如可指定分为3组，这里的3即算法名称中k的含义，此时 k=3,图:4个簇及其质心,k-均值算法(k-Means),1.随机挑选3个点作为初始簇质心(
6、centroid),指定 k=3(即要将数据点分成3组),2.遍历所有点，各自加入距离最近的簇,3.调整各个簇的的质心,4.回到第2步,中止条件：簇不再发生变化,第2步如何找到最近的簇？,遍历各簇质心，计算欧氏距离，距离最小的即最近的,第3步如何调整质心？,取簇中各点的算术平均值作为新质心的坐标即可,(1,4),(6,0),(3,2),(0,8),(6,4),(8,4),(1,8),(8,7),(6,8),(7,9),(7,8),(1.25,5.5),(6.67,2.67),(5.75,2.5),(0.67,6.67),如何评价聚类结果的质量？,好的聚类结果的簇内数据点比较紧凑，簇间相距大即簇
7、内中各数据点离质心的距离都比较小可使用误差平方和(SSE,Sum of Squared Errors)准则函数来评价一个簇的误差平方和即簇内各点到质心欧式距离的平方和：,其中p表示簇中的点，X是簇内点的集合，distance(p,centroid)即点p到簇质心的距离,聚类结果的SSE即各个簇的SSE之和，其值越小表示聚类质量越好,改进1:归一化,结果被“工资”主导了！,考虑对如下学生兴趣数据进行聚类,改进1:归一化,为什么结果被“工资”主导了？,例如x2,y2的差值很大，而x1,y1等差异很小，则计算得到的欧氏距离几乎就约等于,解决方案:归一化,v为原特征值，v为归一化后的值，vmin为样本
8、最小值，vmax为样本最大值,改进1:归一化,归一化,k-均值算法性能分析,主要优点是解决聚类问题的经典算法，简单、快速结果簇比较密集，簇间区别明显时，效果较好,主要缺点对初始值比较敏感，不同的初始值可能会导致不同的结果对“噪声”和孤立点数据敏感，少量的该类数据能对平均值产生极大的影响在簇的平均值被定义的情况下才能使用，对分类属性不适用必须事先给出k值,初始值选择的改进,如何初始值选的是这两个点会怎么样？,k-means+基本思路:初始的聚类中心之间的相互距离要尽可能的远算法思想:1.随机选择第一个簇质心2.对于数据集中每一个点x，计算它与最近质心的距离D(x)3.选择一个新数据点作为新簇质心
9、，选择原则是:D(x)较大的点，被选取作为聚类中心的概率较大4.重复2和3直到k个簇质心被选出来5.利用这k个初始的簇质心来运行标准的k-Means算法,请课后查阅相关资料了解算法细节,处理孤立点,k-中心点算法(k-medoids)不是简单像k-means算法采用均值计算法，每次迭代后的质心都是从簇的样本点中选取，而选取的标准就是当该样本点成为新的质点后能提高簇的聚类质量，使得类簇更紧凑。算法使用SSE来定义一个簇的紧凑程度。算法步骤:(1)随机选择k个对象作为初始的中心点；(2)重复(3)指派每个剩余的样本点给最近的中心点所代表的簇；(4)随意地选择一个非中心点Orandom；(5)计算用
10、Orandom代替原中心点的总代价S；(6)如果S0(更紧凑了)，则用Orandom替换原中心点；(7)直到不发生变化*其中 S 为替换原中心点后的 SSE 减去替换前的 SSE，S 0 表示替换后 SSE 变小了，即聚类质量更好了,请课后查阅相关资料了解算法细节,总结,样本、实例、特征、特征向量的概念样本差异度的度量:欧氏距离k-均值算法k-均值算法的改进,作业,手工演绎 k-means 的算法流程(下次提问)搜索PPT中提到的 k-means 的其它改进算法资料，将算法基本思路整理成 word 文档发到我邮箱(学号-姓名.docx)，周日晚24点前如果还没有熟悉的编辑语言，请选择一门并学习，并尝试实现 k-means 算法(暂时不上交),扩展阅读,谢谢！,
