《数据挖掘基础》课件 第3章 聚类.pdf

数据拾掘基础大数据应用人才培养系列教材第三章聚类3.1 聚类概述3.2 聚合分析方法3.3 聚类在实际场景中的应用案例3.4 聚类的实现例子 习题3.1聚类概述第三章聚类聚类的过程把相似数据归并到一类的过程，形成同类对象具有共同特征,不同类对 象之间的有显著区别，直到所有数据的归类都完成。特征性描述:对象的共同特征31*4 3 区别性描述:不同类对象之间的区别：概念描述:特征性描述和区别性描述3.1聚类概述第三章聚类 聚类的目的通过数据间的相似性把数据归类，并根据数据的概念描述，来制定对应 的策略。电商例子在电子商务领域，电商可以对有相似浏览行为的客户进行归类，从而找 出他们的共同特征，达到充分理解客户需求的目的，并提供相适应的客 户服务。3.1聚类概述第三章聚类 聚类技术主要包括传统的模式识别方法和数学分类学聚类的评价标准 Purity RI3.1聚类概述第三章聚类 Purity1purity(Q,C)=-2L 胃 X 13k n CjQ=3 k是聚类(cluster)的集合,3 k表示第k个聚类的集合；C=Q,c2.cj是数据对象类型(class)的集合,Cj表示第j个数据对象类型集；N表示数据对象总数。3.1聚类概述第三章聚类 Purity 例子cluster 1 cluster 2 cluster 3对象类型(class)包括x,o,口N=17purity=(5+4+3)/N=12/170.71purity是简单透明的方法，它的取值在01之间，数值越大，表示聚类效果越好。3.1聚类概述第三章聚类 RI TP+TNKJ=-TP+FP+FN+TNTP:计算每个聚类中同类对象归类到同一类的组合次数，并累计所有的结果TN:计算每个不同类对象归类到不同类的组合次数，并累计所有的结果FP:计算每个聚类中不同类对象归类到同一类的组合次数，并累计所有的结果FN:计算每个同类对象归类到不同类的组合次数，并累计所有的结果TN=TN+FN-FN=96-24=72TP+FP+FN+TN小加二在)中任选n个的组合数 cluster 1Clusterl:TP=C(2,5)=10/-Cluster2:TP=C(2,4)=6(x X Cluster3:TP=C(2,3)+C(2,2)=4 I x/TP=10+6+4=20TP+FP=C(2,6)+C(2,6)+C(2,5)=15+15+10=40FP=TP+FP-TP=20 x:FN=5+5+5+2=15o:FN=4:FN=3FN=15+4+3=24TN+FN=C(l,6)*C(l,6)+C(l,6)*C(l,5)+C(l,6)*C(l,5)=36+30+30=96duster 2 cluster 30Q3.1聚类概述第三章聚类聚类算法 层次聚类算法(Hierarchical Methods)划分聚类算法(Partitioning Methods)基于密度的聚类算法(Density-based Methods)基于网格的聚类算法(Grid-based Methods)基于模型的聚类算法(Model-Based Methods)3.1聚类概述第三章聚类层次聚类算法对给定的数据集进行层次似的分解，直到某种条件满足为止。通过计算各个对象的相似性，并把相似对象合在一起，由同一的父类代表他们，由此构 成一棵树，父类为根节点,其所代表的对象即构成树的子节点。从树的构造顺序划分，有自底而上、自顶而下两种方式。前者对应的是聚合聚类，后者 对应的是分裂聚类。父类(A,B)子类AB3.1聚类概述第三章聚类划分聚类先预设划分的分类数K,将给定的数据划分成K个非空集合即簇，然后通过调整每个数据在 各簇的分布，使得每个簇的相似度得到进一步提高，而簇之间的相异度加大。不断重复这 个过程即迭代，直到每个簇不再改变。3.1聚类概述第三章聚类划分聚类代表算法:KmeansK-means算法流程图大数据应用人才培养系列教材第三章聚类3.1 聚类概述3.2 聚合分析方法3.3 聚类在实际场景中的应用案例3.4 聚类的实现例子 习题3.2聚合分析方法第三章聚类聚合分析过程聚合分析方法是层次聚类的常用方法，其聚合过程是自底而上的过程。它把所有数据样本分别看作独立的簇；计算簇的相似度，即簇之间的距离。距离最小的即相似度最高。把相似度最高的簇合并成一个簇，并再与剩余的其它簇重新聚合。如此重复迭代以上聚合过程，直到所有数据样本合并为一个簇。在聚类分析中，需要确定数据样本间的相似程度，这个相似度称为数据样本间的距 离。计算距离的方法包括欧氏距离、曼哈顿距离、闵可夫斯基距离、切比雪夫距离 等。本章重点介绍常用的欧氏距离方法。3.2聚合分析方法第三章聚类欧氏距离在一个p维空间中，任一点Xi表示为(Xil,Xi2,.,Xip),它与另一点Xj的欧氏距离d(Xi,Xj)可按如下方法计算：*凶，为)=/_(皿.Xjk-A 例子：Xl=(6,3),X2=(3,7)d(Xlz X2)=q v 2 2S(Xlk-X2k)J*IV(6-3y+(3-7)23.2聚合分析方法第三章聚类聚合分析例子原始数据 第1次计算相似度欧氏距离ABcA0.005.006.71B0.009.06C0.00)6 3 7,2 6 3 1-ABC得到A,B最相似;把A,B合并为一簇,并与剩余的C聚合合并簇的值：这里为简易说明，采用簇的质心的方法，即簇的均值作 为合并簇的值的方法3.2聚合分析方法第三章聚类聚合分析例子A,B簇的质心：(A+B)/2=(4.5,5)第2次计算相似度(A,B)质心A63B37(A,B)4.55欧氏距离A,BCA,B0.007.57C0.00得到(A,B),C最相似把(A,B),C合并为一簇。3.2聚合分析方法第三章聚类聚合分析例子1(A,B),C)簇的质心:(A,B)+C)/2=(8.25.5.5)(A,B),C)质心第3次计算相似度欧氏距离A,B4.55C126(A,B),C8.255.5(A,B),C(A,B),C0.00所有的数据点都合并完。聚合过程完成。3.2聚合分析方法第三章聚类聚类树将前面的每一步的计算结果以树状图的形式展现出来就是层次聚类树。最底层是原始数据点。依 照数据点间的相似度组合为聚类树的第二层。以此类推生成完整的层次聚类树树状图。层次聚类树树状图ABC3.2聚合分析方法第三章聚类聚合分析方法应用例子原始数据聚合数据19.721.420.620.624.924.927.527.526.223.463.363.363.363.343.3第1列是原始数据，后面列是聚合过程数据，其中以质心作合并簇值。在区隔程度阀值T=3时，可以得至U3个簇类(A,B),(C,D),E3.2聚合分析方法第三章聚类聚合分析方法应用例子聚合过程对应的层次聚类树如下：层次聚类树树状图实际上，这里A、B、C、D、E的数值分别表示首尔、香港、北京、上海、东京的GDP值。以3（即3千亿）作为区分标准。通过上面描述的聚合过程，可以把亚洲这5个最发达城市划分成以下3个方阵:第一方阵：东京第二方阵：上海，北京大数据应用人才培养系列教材3二1聚类概述3.2 聚合分析方法3.3 聚类在实际场景中的应用案例3.4 聚类的实现例子 习题3.3聚类在实际场景中的应用案例第三章聚类聚类分析在电网运行中，可以大幅度提高电网业务的安全运行水平。聚类分析在电力用户用电行为分析中，可以大幅度提高售电策略的准确性。聚类分析在电商的应用3.3聚类在实际场景中的应用案例第三章聚类聚类分析在电网运行中，可以大幅度提高电网业务的安全运行水平。通过对电网、调度网等重要生产业务的历史故障和缺陷情况进行故障概率聚类分析，发 掘故障因素关联性、共性规律，从而制定相应的防范对策和措施，在故障和缺陷发生之 前进行预防式防护，达到大幅提升电网运行可靠性的目的。3.3聚类在实际场景中的应用案例第三章聚类聚类分析在电力用户用电行为分析中，可以大幅度提高售电策略的准确性。通过对电力用户用电规模、用电模式作聚类分析，就能把用户划分成不同的类别，并分 别制定相应的售电策略、风险防范策略电力公司通过客户价值细分模型，对客户基本信息、用电负荷、违章历史等方面的用电 行为特征进行聚类分析，把多个用户的用电方式通过聚类分析形成用电属性相似的行业 群体，根据客户对电力公司的贡献度、用电变化趋势、风险程度等情况，将客户细分为 多种类别，推进客户细分管理、欠费和用电风险有效预测、配用电错峰调度，实现个性 化营销和服务，促进服务质量和防范风险能力的不断提升。3.3聚类在实际场景中的应用案例第三章聚类聚类分析在电商的应用电商把交易信息包括消费者购买时间、购买商品、购买数量、支付金额、性别、年龄、地域分布、关联收藏等进行聚类分析，可以了解客户的消费习惯，制定对应的商品营销 推广活动，提高成交转化率和成交率。大数据应用人才培养系列教材3二1聚类概述3.2 聚合分析方法3.3 聚类在实际场景中的应用案例3.4 聚类的实现例子习题3.4聚类的实现例子第三章聚类通过例子展示K-means聚类的实现主节点(master)10.30.216.2从节点(slave。10.30.240.14从节点(slave?)10.30.32.7从节点(slave3)10.30.248.8客户端(client)10.30.224.17图3-10大数据集群节点3.4聚类的实现例子第三章聚类(C 10.30.2162 50070/dfshealth.htmlz?tab-overvie.Overview master:8020,(active)Stsr ted：Tue May 16 16:36:21 CST 2017Version：2.7.1,X15ecc87ccf40228f35af06fc56d*5366co657aCoop lied:2015*06-29TO6:04Z by jenkms fxoa(detached fxoa 15ecc8?)Cluster ID：CII-24269862-fe8c-4080-8752-72f6b31b845 Block Pool ID：BP-693136522-10.30.216.2-1494923771285SummarySecurity is off.S&feaode is off*11 files and directories 1 blocks=12 total object G).Heap Memory used 231.58 MB of 958.5 MB He&p Xe*ory Heap ftenory is 958.5 MB.Non Heap Keozy 3ed 40,71 XB of 40.94 KB Comitcd Kon Heap Meaory,I3x Non Heap Kenoxy 13 130 KB.Confi 0.0 0.0 0.0 0.1 0.1 0.1 0.2 0.2 0.2 9.0 9.0 9.0 9.1 9.1 9.1 9.2 9.2 9.2聚类的目标是把原始数据分成2类，并找出每一类的质心。3.4聚类的实现例子第三章聚类 创建hadoop工作目录/34/in rootslavel hadoop#bin/hadoop fs-mkdir-p/34/in 把需要聚类的数据文件kmeans_data.txt装进hadoop的HDFS分布式文件系统中 rootslavel hadoop#bin/hdfs dfs-put/usr/cstor/spark/data/mllib/kmeans_data.txt/34/in rootslavel hadoop#bin/hadoop fs-cat/34/in/kmeans_data.txt 进入 spark-sheH 接口 scala rootslavel spark#bin/spark-shell master spark:/master:7077 运行 K-means spark 算法3.4聚类的实现例子第三章聚类 实施方法过程如下：从本地连接slavel:c:-$ssh 10.30.240.14 Connecting to 10.30.240.14:22.Connection established.To escape to local shell,press Ctrl+Alt+.查看hadoop工作目录 rootslave1#cd/usr/cstor/hadoop rootslave1 hadoop#Is-I total 28-rw-r-r-1 10021 10021 15429 May 16 16:35 LICENSE.txt-rw-r-r-1 10021 10021 101 May 16 16:35 NOTICE.txt-rw-r-r-1 10021 10021 1366 May 16 16:35 README.txt drwxr-xr-x2 10021 10021 194 Jun 29 2015 bin drwxr-xr-x 4 root root 37 May 16 16:36 cloud drwxr-xr-x 3 10021 10021 20 Jun 29 2015 etcy o o o 设置JAVA_HOME路径 rootslave1#export JAVA_HOME=/usr/local/jdk1.7.0_793.4聚类的实现例子第三章聚类导入所需的包：scala import breeze.linalg.Vector,DenseVector,squaredDistance import breeze.linalg.Vector,DenseVector,squaredDistance scala import org.apache.spark.SparkConf;SparkContext import org.apache.spark.SparkConf SparkContext scala import org.apache.spark.SparkContext.import org.apache.spark.SparkContext._3.4聚类的实现例子第三章聚类定义分析方法和计算最短距离点的方法(method):scala def parseVector(line:String):VectorDouble=|DenseVector(line.split().map(_.toDouble)I)parseVector:(line:String)breeze.linalg.VectorDouble scala def closestPoint(p:VectorDouble,centers:ArrayVectorDouble):Int=|var bestindex=0|var closest=Double.Positiveinfinity|for(i-0 until centers.length)|val tempDist=sq uaredDistance(p,centers(i)|if(tempDist scala val lines=sc.textFile(/34/in/kmeans_data.txt)17/05/17 06:14:50 INFO storage.MemoryStore:Block broadcast_0 stored as values in memory(estimated size 86.5 KB,free 86.5 KB)17/05/17 06:14:50 INFO storage.MemoryStore:Block broadcast_0_piece0 stored as bytes in memory(estimated size 19.4 KB,free 105.9 KB)17/05/17 06:14:50 INFO storage.BlockManagerlnfo:Added broadcast_0_piece0 in memory on 10.30.240.14:42657(size:19.4 KB,free:511.5 MB)17/05/17 06:14:50 INFO spark.SparkContext:Created broadcast 0 from textFile at:32 lines:org.apache.spark.rdd.RDDString=MapPartitionsRDDl at textFile at:32 scala val data=lines.map(parseVector J.cacheQdata:org.apache.spark.rdd.RDDbreeze.linalg.VectorDouble=MapPartitionsRDD2 at map at:363.4聚类的实现例子第三章聚类 定义K的数目：scala val K=2.tolnt K:Int=2 scala val convergeDist=0.1.toDouble convergeDist:Double=0.1 初始化K个簇：scala val kPoints=data.takeSample(withReplacement=false,K,42).toArray kPoints:Arraybreeze.linalg.VectorDouble=Array(DenseVector(0.1z 0.1,0.1),DenseVector(9.2,9.2Z 9.2)3.4聚类的实现例子第三章聚类 计算每个点的距离并调整簇，直到K个簇不再有变动，得到措掘结果:scala var tempDist=1.0 tempDist:Double=1.0 scala while(tempDist convergeDist)|val closest=data.map(p=(closestPoint(p,kPoints),(p,1)|val pointStats=closest.reduceByKeycase(p1,c1),(p2,c2)=(p1+p2,c1+c2)|val newPoints=pointStats.map pair=|(pair._1,pair._2._1*(1.0/pair._2._2).collectAsMap()|tempDist=0.0|for(i|tempDist+=sq uaredDistance(kPoints(i),newPoints(i)I)|for(newP|kPoints(newP._1)=newP._2 I)|println(Finished iteration(delta=+tempDist+)I)3.4聚类的实现例子第三章聚类结果展示 scala kPoints.foreach(println)DenseVector(0.1z 0.1,0.1)DenseVector(9.099999999999998z 9.099999999999998,9.099999999999998)习题:1.请说明聚类的过程。2.请说明2种聚类方法的评价标准。3.请列出3种以上聚类算法。4.K-means算法是层次聚类，还是划分聚类？请说明其算法流程。5.请举例并画出一颗层次聚类树，并说明其作用。6.请举例说明欧氏距离(Euclidean Distance)的计算过程。感谢聆听