Python语言PPT14.1聚类的原理及实现.pptx

1、数据挖掘数据挖掘聚类聚类分类分类关联规则挖掘关联规则挖掘聚类概述编号账户余额年龄收入性别子女个数100很低151967男0200高258453男1300中326125女2400低202167男1500低552439女4聚类（clusteringclustering）：实现将对象自动分组的一种方法无监督学习聚类类别所表达的含义通常是未知的，不确定的物以类聚客户基本信息数据表年龄年收入学历消费额365万本科4万1424万5本科4万233万1高中3万5617万本科2万382万大专1万怎样把这些客户划分成不同的类别？根据他们之间的相似度根据他们之间的相似度进行聚类，物以类聚，进行聚类，物以类聚，人以群

2、分人以群分他们之间比较他们之间比较相似，是否可相似，是否可聚成一类聚成一类怎样评价相怎样评价相似度呢？似度呢？聚类分析概述概念：概念：聚类分析是数据挖掘中研究聚类分析是数据挖掘中研究“物以类聚物以类聚”的一的一种方法种方法,属多元统计分析方法属多元统计分析方法.例如：细分市场、消费行为划分例如：细分市场、消费行为划分聚类分析是建立一种分类，是将一批样本聚类分析是建立一种分类，是将一批样本(或变量或变量)按照在性质上的按照在性质上的“亲疏亲疏”程度程度,在在没有先验知识没有先验知识的的情况下自动进行分类的方法情况下自动进行分类的方法.其中其中:类内个体具有较高的相似性类内个体具有较高的相似性,类

3、间的差异性较大类间的差异性较大.两类两类:(A B)(C D E)三类三类:(A B)(C)(D E)l依据平均得分的依据平均得分的差距差距,差距较小的差距较小的为一类为一类.l聚类过程中聚类过程中,没有没有事先指定分类的标事先指定分类的标准准.完全根据样本完全根据样本数据客观产生分类数据客观产生分类结果结果.聚类分析概述簇和聚类簇簇(cluster)(cluster)：数据对象的集合数据对象的集合 同一簇中的对象彼此同一簇中的对象彼此相似相似 不同簇中的对象彼此不同簇中的对象彼此相异相异n聚类：聚类：n将数据对象的集合分组成为由相似对象组成的将数据对象的集合分组成为由相似对象组成的多个类多个

4、类 n聚类分析中要划分的类是未知的，所以聚类分聚类分析中要划分的类是未知的，所以聚类分析属于析属于无监督学习无监督学习或或观察学习观察学习聚类算法的应用举例聚类算法的应用举例车牌识别车牌识别图像分割算法图像分割算法K=2K=2，分割为类似白色和类似蓝色两个类，分割为类似白色和类似蓝色两个类将白色的形状与字符库中的字符作相似性将白色的形状与字符库中的字符作相似性比对，判断属于哪个字符。比对，判断属于哪个字符。在图像分割上的简单应用在图像分割上的简单应用例例1：1.图片：一只遥望大海的小狗；图片：一只遥望大海的小狗；2.此图为此图为100 x 100像素的像素的JPG图片，每个像素可以图片，每个像

5、素可以表示为三维向量（分别对应表示为三维向量（分别对应JPEG图像中的红色、图像中的红色、绿色和蓝色通道）绿色和蓝色通道）；3.将图片分割为合适的背景区域（三个）和前景区将图片分割为合适的背景区域（三个）和前景区域（小狗）；域（小狗）；4.使用使用K-means算法对图像进行分割。算法对图像进行分割。在图像分割上的简单应用在图像分割上的简单应用（续）（续）分割后的效果注：最大迭代次数为20次，需运行多次才有可能得到较好的效果。在人脸识别中的应用在人脸识别中的应用例例2：注：聚类中心个数为5，最大迭代次数为10。聚类分析的主要问题如何度量距离如何度量距离层次聚类法层次聚类法K-meansK-me

6、ans聚类聚类K-K-中心点聚类中心点聚类基于划分的聚类基于划分的聚类如何度量距离如何度量距离数据的种类定距型数据（数值型）定性型数据（布尔型）定序型数据（有顺序的离散值型、比如优、良、中、及格、不及格）亲疏远程度的衡量指标亲疏远程度的衡量指标距离距离:数据间差异程度的度量数据间差异程度的度量.距离越近距离越近,越越“亲密亲密”,”,聚成一类聚成一类;距离越远距离越远,越越“疏远疏远”,”,分别属分别属于不同的类于不同的类定距型个体间的距离：定距型个体间的距离：把每个个案数据看成是把每个个案数据看成是n n维空间上的点维空间上的点,在点和点在点和点之间定义某种距离之间定义某种距离.欧氏距离欧氏

7、距离(EUCLID)EUCLID)平方欧氏距离平方欧氏距离(SEUCLIDSEUCLID)kiiiyxyxEUCLID12)(),(距离的定义个体间的距离个体间的距离把每个个案数据看成是把每个个案数据看成是n维空间上的点维空间上的点,在点和在点和点之间定义某种距离点之间定义某种距离 21122222211)()()()(pkjkikjpipjijiijxxxxxxxxdx1x2x12x22x11x21x21-x11x22-x12212222112121)()(xxxxdPrinciples and Applications of Business IntelligenceChap 6：聚类分析

8、 17距离公式 If q=1,d is 曼哈顿距离Manhattan distance,L1 If q=2,d is 欧式距离Euclidean distance:L2性质：d(oi,oj)0d(oi,oi)=0d(oi,oj)=d(oj,oi)d(oi,oj)doi,ok)+d(ok,oj)|.|(|),(2222211jmximxjxixjxixjoiod|m|.|),(2211jmxixjxixjxixjoiodPrinciples and Applications of Business IntelligenceChap 6：聚类分析 18品距离矩阵Principles and App

9、lications of Business IntelligenceChap 6：聚类分析 19品pkjkikijxxd1)1(品质型个体距离的度量品质型个体间的距离品质型个体间的距离姓名姓名 授课方式授课方式 上机时间上机时间 选某门课程选某门课程张三张三 1 1 1 李四李四 1 1 0王五王五 0 0 1品质型个体间的距离品质型个体间的距离简单匹配简单匹配(simple matching)simple matching)系数系数:适用二值变适用二值变量。量。dcbacbjid),(个体j个体i 1 01 a b0 c d a a为个体为个体i i与个体与个体j j在所有变量上同时在所有变

10、量上同时取取1 1的个数；的个数；d d为同时取为同时取0 0的个数的个数特点：排除同时拥有或同时不拥有特点：排除同时拥有或同时不拥有某特征的情况；取某特征的情况；取0 0和和1 1地位等价。地位等价。品质型个体间的距离品质型个体间的距离品质型个体间的距离简单匹配简单匹配(simple matching)simple matching)系数系数:适用二值变量。适用二值变量。姓名姓名 授课方式授课方式 上机时间上机时间 选某门课程选某门课程张三张三 1 1 1 李四李四 1 1 0王五王五 0 0 1（张三，李四）：（张三，李四）：a=2 b=1 c=0 d=0 d(x,y)=1/(1+2)=1

11、/3（张三，王五）：张三，王五）：a=1 b=2 c=0 d=0 d(x,y)=2/(1+2)=2/3品质型个体间的距离张三距李四近张三距李四近品质型个体间的距离品质型个体间的距离(雅科比系数雅科比系数)根据临床表现研究病人是否有类似的病根据临床表现研究病人是否有类似的病姓名姓名 性别性别 发烧发烧 咳嗽咳嗽 检查检查1 检查检查2 检查检查3 检查检查4张三张三 男男 1 0 1 0 0 0李四李四 女女 1 0 1 0 1 0王五王五 男男 1 1 0 0 0 0.品质型个体间的距离品质型个体间的距离品质型个体间的距离雅科比（雅科比（JaccardJaccard）系数系数:适用二值变量适用

12、二值变量cbacbjiJ),(个体j个体i 1 01 a b0 c d a为个体为个体i与个体与个体j在所有变量上同时在所有变量上同时取取1的个数；的个数；d为同时取为同时取0的个数的个数特点：排除特点：排除同时不拥有某特征同时不拥有某特征的情的情况；况；取取1 1的状态比取的状态比取0 0更有意义更有意义(如如:临床检验中的阳性特征临床检验中的阳性特征)；编码方案；编码方案会引起系数的变化会引起系数的变化品质型个体间的距离品质型个体间的距离品质型个体间的距离JaccardJaccard系数举例系数举例:根据临床表现研究病人是否根据临床表现研究病人是否有类似的病有类似的病姓名姓名 性别性别 发

13、烧发烧 咳嗽咳嗽 检查检查1 检查检查2 检查检查3 检查检查4张三张三 男男 1 0 1 0 0 0李四李四 女女 1 0 1 0 1 0王五王五 男男 1 1 0 0 0 0.33.010210),(李四张三d67.010111),(王五张三d75.021121),(王五李四d结论结论:张三和李四最有可能得类似张三和李四最有可能得类似的病的病;李四和王五不太有可能李四和王五不太有可能品质型个体间的距离说明：说明：聚类过程中如果数据在数量级上存在差异时，应进行标准聚类过程中如果数据在数量级上存在差异时，应进行标准化处理。化处理。例如例如:样本的欧氏距离 元十万元（1 1，2 2）265000

14、 26500074.0774.07（1 1，3 3）41600041600080.8680.86（2 2，3 3）151000151000154.56154.56距离的标准化处理SPSS等统计软件中有标准化处理功能数据标准化的方法数据标准化就是用来消除不同量级的影响1）min-max标准化（归一化）新数据=(原数据-最小值)/(最大值-最小值)2）z-score标准化（规范化）新数据=(原数据-均值)/标准差聚类数据预处理举例聚类数据预处理举例二、预处理二、预处理(1)定量化处理。定量化处理。(2)归一化处理。消除计量单位的不同。归一化处理。消除计量单位的不同。聚类算法不能解决的问题聚类算法不

15、能自动发现应该聚成多少个类，聚类的数目只能人为主观确定；不会自动给出一个最佳聚类结果。4.2 4.2 层次聚类法层次聚类法Company Namewww.SucaiF层次聚类法层次聚类法将每个对象归为一类，然后不断迭代，直到所将每个对象归为一类，然后不断迭代，直到所有对象合并成一个大类。有对象合并成一个大类。6个民族的粗死亡率与期望寿命层次聚类的输出进化树层次聚类聚类数目的确定聚类数目的确定聚类数目确定尚无统一标准，一般原则：聚类数目确定尚无统一标准，一般原则：各类所包含的元素都不应过多各类所包含的元素都不应过多分类数目应符合分析的目的分类数目应符合分析的目的层次聚类中可以将层次聚类中可以将类

16、间距离类间距离作为确定类数目的辅助工作为确定类数目的辅助工具具聚类过程中类间距离呈增加趋势聚类过程中类间距离呈增加趋势类间距离小，类的相似性大；距离大，相似性小类间距离小，类的相似性大；距离大，相似性小绘制碎石图（绘制碎石图（X X轴为类距离，轴为类距离，Y Y轴为类数）轴为类数）一一(single-linkage)(single-linkage)（最近邻（最近邻(Nearest Neighbor)(Nearest Neighbor)）：）：基本思想：两个簇之间的距离用从两个簇中抽取基本思想：两个簇之间的距离用从两个簇中抽取的每对样本的最小距离的每对样本的最小距离作为距离度量，一旦最近的两个类的距离超过某作为距离度量，一旦最近的两个类的距离超过某个任意给定的阈值，算法就自动结束。个任意给定的阈值，算法就自动结束。二二三三),(minjiCCD层次聚类层次聚类 23145b7a 先将五个样本都分别看成是一个簇，最靠近的两个簇是先将五个样本都分别看成是一个簇，最靠近的两个簇是3 3和和4 4，因为他们具有最小的簇间距离，因为他们具有最小的簇间距离D D（3 3，4 4）=5.0=5.0。第