2基本概念及k-Means算法

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