bigdata数据挖掘培训3

数据挖掘DataMining闫雷鸣2019/7/30四、数据挖掘技术21.贝叶斯分类2.聚类分析4.1贝叶斯分类:为什么?可能性学习可能性预测贝叶斯定理给定训练数据D,条件h的后验概率MAP假设)()()|()|(DPhPhDPDhP.)()|(maxarg)|(maxarghPhDPHhDhPHhMAPh•MAP极大后验假设学习器在候选假设集合H中寻找给定数据D时可能性最大的假设h，h被称为极大后验假设（MAP）确定MAP的方法是用贝叶斯公式计算每个候选假设的后验概率，计算式如下最后一步，去掉了P(D)，因为它是不依赖于h的常量)()|(maxarg)()()|(maxarg)|(maxarghPhDPDPhPhDPDhPhHhHhHhMAP朴素贝叶斯分类朴素假定:属性独立P(x1,…,xk|C)=P(x1|C)·…·P(xk|C)假如i-th是分类属性:P(xi|C)类C中属性i-th具有值xi假如i-th属性连续的:P(xi|C)通过高斯密度函数来估计两种情况下计算容易打网球实例:估计P(xi|C)OutlookTemperatureHumidityWindyClasssunnyhothighfalseNsunnyhothightrueNovercasthothighfalsePrainmildhighfalsePraincoolnormalfalsePraincoolnormaltrueNovercastcoolnormaltruePsunnymildhighfalseNsunnycoolnormalfalsePrainmildnormalfalsePsunnymildnormaltruePovercastmildhightruePovercasthotnormalfalsePrainmildhightrueNoutlookP(sunny|p)=2/9P(sunny|n)=3/5P(overcast|p)=4/9P(overcast|n)=0P(rain|p)=3/9P(rain|n)=2/5temperatureP(hot|p)=2/9P(hot|n)=2/5P(mild|p)=4/9P(mild|n)=2/5P(cool|p)=3/9P(cool|n)=1/5humidityP(high|p)=3/9P(high|n)=4/5P(normal|p)=6/9P(normal|n)=2/5windyP(true|p)=3/9P(true|n)=3/5P(false|p)=6/9P(false|n)=2/5P(p)=9/14P(n)=5/14打网球实例:分类XX=rain,hot,high,falseP(X|p)·P(p)=P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582P(X|n)·P(n)=P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286样本X通过类n(don’tplay)来分类贝叶斯信念网络(I)贝叶斯信念网络允许在变量的子集间定义类条件独立性提供一种因果关系的图形学习贝叶斯信念网络的几种情况网络结构和变量均给出，容易给出网络结构和部分变量网络结构预先不知道贝叶斯信念网络(II)FamilyHistoryLungCancerPositiveXRaySmokerEmphysemaDyspneaLC~LC(FH,S)(FH,~S)(~FH,S)(~FH,~S)0.80.20.50.50.70.30.10.9贝叶斯信念网络肺癌的条件概率表niYParentsixiPxxPn1))(|(),...,(1国家政策（C）单位政策（U）身体状况差（B）过劳死（D）工作压力大（W）WBP(A)tttfftff0.3350.300.050.00UP(W)tf0.900.05CP(U)tf0.950.01P(C)0.50UP(B)tf0.300.01已知：一个事件e={单位政策U=true,and工作压力大=true}，请近似计算出现过劳死的概率。“Noonecanservetwomasters.Eitherhewillhatetheoneandlovetheother,orhewillbedevotedtotheoneanddespisetheother.YoucannotservebothGodandMoney.”FromMatthew6:24NIV四、数据挖掘技术21.贝叶斯分类2.聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类划分方法层次方法基于密度的方法孤立点分析聚类分析将数据对象的集合分成由相似对象组成的多个类聚类分析中要划分的类是未知的典型的应用作为独立的工具来获得数据分布的情况也可以作为其他算法的预处理步骤同一数据的不同聚类结果Howmanyclusters?SixClustersFourClustersTwoClusters典型的聚类分析应用模式识别数据分析图象处理经济学（特别是在市场分析中）互联网对聚类算法的要求良好的聚类算法首先应该保证簇内对象的良好的相似性簇间对象的良好的相异性聚类算法的质量取决于算法对相似性的判别标准以及算法的具体实现算法的质量还取决于算法发现隐藏着的模式的能力数据挖掘对聚类的典型要求可伸缩性处理不同类型属性的能力发现任意形状的聚类用于决定输入参数的领域知识的最小化处理噪声数据的能力对输入记录的顺序不敏感高维性基于约束的聚类可解释性和可用性4.2聚类分析什么是聚类分析?聚类分析中的数据类型数据结构数据矩阵(二模)相异度矩阵(单模)npx...nfx...n1x...............ipx...ifx...i1x...............1px...1fx...11x0...)2,()1,(:::)2,3()...ndnd0dd(3,10d(2,1)0对象对的相异度聚类分析中的数据类型（1）区间标度变量:重量、高度、经纬度、气温二元变量:只有两种状态得病、未得病；0,1聚类分析中的数据类型（2）分类、序数型和比例标度型变量:分类：红、黄、蓝、绿序数：讲师、副教授、教授混合类型变量:如何计算对象间的相异度？两个对象间的相异度是基于对象间距离来计算的常用的方法包括:明考斯基距离Minkowski:这里i=(xi1,xi2,…,xip)andj=(xj1,xj2,…,xjp)是两个p维的数据对象如果q＝1，那么这个就是曼哈坦距离qqppqqjxixjxixjxixjid)||...|||(|),(2211||...||||),(2211ppjxixjxixjxixjidSimilarityandDissimilarityBetweenObjects(Cont.)如果q＝2，那么就是欧几里的距离:对于距离函数满足如下要求d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)加权也可以用于曼哈坦距离和明考斯基距离)||...|||(|),(2222211ppjxixjxixjxixjid4.2聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类主要的聚类方法划分方法:构建数据的若干个划分层次方法:按某种标准将给定数据对象集合进行层次的分解基于密度的方法:基于连接和密度函数基于网格的方法:基于多层粒度结构基于模型的方法:为每个簇假定一个模型，寻找数据对模型进行最佳拟和划分聚类OriginalPointsAPartitionalClustering簇层次聚类p4p1p3p2p4p1p3p2p4p1p2p3p4p1p2p3TraditionalHierarchicalClusteringNon-traditionalHierarchicalClusteringNon-traditionalDendrogramTraditionalDendrogram簇（Clusters）的类型明显分离的簇基于中心的簇基于邻近的簇基于密度的簇概念簇明显分离的簇3well-separatedclusters基于中心的簇Center-based每个点到簇中心的距离，比到其他簇中心的距离更近4center-basedclusters基于邻近的簇NearestneighborAclusterisasetofpointssuchthatapointinaclusteriscloser(ormoresimilar)tooneormoreotherpointsintheclusterthantoanypointnotinthecluster.8contiguousclusters基于密度的簇Density-basedAclusterisadenseregionofpoints,whichisseparatedbylow-densityregions,fromotherregionsofhighdensity.Usedwhentheclustersareirregularorintertwined,andwhennoiseandoutliersarepresent.6density-basedclusters概念簇SharedPropertyorConceptualClustersFindsclustersthatsharesomecommonpropertyorrepresentaparticularconcept..2OverlappingCircles4.2聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类划分方法划分方法:基本概念划分方法:为包含n个数据对象的数据库生成k个簇给定k值，采用一个划分规则将对象组织成k个划分全局优化:尽可能枚举所有划分启发式方法:k-均值和k-中心点算法k-均值(MacQueen’67):每个簇以其对象平均值作为代表（簇中心，或质心）k-中心点或PAM(Kaufman&Rousseeuw’87):每个簇以其中的某一点代表K-均值方法给定k:1.任意选择k个点作为初始的质心2.repeat3.将每个点指派到最近（相似）的簇集4.重新计算每个簇的均值，即更新质心5.until不再发生变化.K-均值方法例012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910最优与次优聚类结果-2-1.5-1-0.500.511.5200.511.522.53xy-2-1.5-1-0.500.511.5200.511.522.53xySub-optimalClustering-2-1.5-1-0.500.511.5200.511.522.53xyOptimalClusteringOriginalPoints随机选择初始质心（例1）-2-1.5-1-0.500.511.5200.511.522.53xyIteration1-2-1.5-1-0.500.511.5200.511.522.53xyIteration2-2-1.5-1-0.500.511.5200.511.522.53xyIteration3-2-1.5-1-0.500.511.5200.511.522.53xyIteration4-2-1.5-1-0.500.511.5200.511.522.53xyIteration5-2-1.5-1-0.500.51