bigdaa数据挖掘培训

数据挖掘

DataMining闫雷鸣2023/1/17四、数据挖掘技术21.贝叶斯分类2.聚类分析4.1贝叶斯分类:为什么?可能性学习可能性预测贝叶斯定理给定训练数据

D,条件h的后验概率MAP假设MAP极大后验假设学习器在候选假设集合H中寻找给定数据D时可能性最大的假设h，h被称为极大后验假设（MAP）确定MAP的方法是用贝叶斯公式计算每个候选假设的后验概率，计算式如下 最后一步，去掉了P(D)，因为它是不依赖于h的常量朴素贝叶斯分类朴素假定:属性独立P(x1,…,xk|C)=P(x1|C)·…·P(xk|C)假如i-th是分类属性:

P(xi|C)类C中属性i-th具有值xi假如i-th属性连续的:

P(xi|C)通过高斯密度函数来估计两种情况下计算容易朴素贝叶斯分类(I)朴素假定:属性类条件独立:大大降低计算开销,只计算类的分布.朴素贝叶斯分类(II)给定训练集,我们能计算出概率（出去打网球）打网球实例:估计P(xi|C)outlookP(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打网球实例:分类XX=<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.010582P(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.10.9贝叶斯信念念网络肺癌的条件件概率表国家政策（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四、数据挖挖掘技术21.贝叶斯分类类2.聚类分析什么是聚类类分析?聚类分析中中的数据类类型主要的聚类类方法分类类划分方法层次方法基于密度的的方法孤立点分析析什么是聚类类分析?聚类:数据对象的的集合同一簇中的的对象彼此此相似与其他簇中中的对象彼彼此相异Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized物以类聚人以群分聚类分析将数据对象象的集合分分成由相似似对象组成成的多个类类聚类分析中中要划分的的类是未知的典型的应用用作为独立的工具具来获得数据据分布的情情况也可以作为为其他算法法的预处理步骤骤同一数据的的不同聚类类结果Howmanyclusters?SixClusters

FourClusters

TwoClusters

典型的聚类类分析应用用模式识别数据分析图象处理经济学（特特别是在市市场分析中中）互联网对聚类算法法的要求良好的聚类类算法首先先应该保证证簇内对象的的良好的相相似性簇间对象的的良好的相相异性聚类算法的的质量取决决于算法对对相似性的的判别标准准以及算法法的具体实实现算法的质量量还取决于于算法发现现隐藏着的的模式的能能力数据挖掘对对聚类的典典型要求可伸缩性处理不同类类型属性的的能力发现任意形形状的聚类类用于决定输输入参数的的领域知识识的最小化化处理噪声数数据的能力力对输入记录录的顺序不不敏感高维性基于约束的的聚类可解释性和和可用性4.2聚类分析什么是聚类类分析?聚类分析中中的数据类类型数据结构数据矩阵(二模)相异度矩阵阵(单模)对象对的相相异度聚类分析中中的数据类类型（1）区间标度变变量:重量、高度度、经纬度度、气温二元变量:只有两种状状态得病、未得得病；0,1聚类分析中中的数据类类型（2）分类、序数数型和比例例标度型变变量:分类：红、、黄、蓝、、绿序数：讲师师、副教授授、教授混合类型变变量:如何计算对对象间的相相异度？两个对象间间的相异度度是基于对对象间距离离来计算的的常用的方法法包括:明考斯基距距离Minkowski:这里i=(xi1,xi2,…,xip)andj=(xj1,xj2,…,xjp)是两个p维的数据对对象如果q＝1，那么这个个就是曼哈哈坦距离SimilarityandDissimilarityBetweenObjects(Cont.)如果果q＝2，那那么么就就是是欧欧几几里里的的距距离离:对于于距距离离函函数数满满足足如如下下要要求求d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)加权权也也可可以以用用于于曼曼哈哈坦坦距距离离和和明明考考斯斯基基距距离离4.2聚类类分分析析什么么是是聚聚类类分分析析?聚类类分分析析中中的的数数据据类类型型主要要的的聚聚类类方方法法分分类类主要要的的聚聚类类方方法法划分分方方法法:构建建数数据据的的若若干干个个划划分分层次次方方法法:按某某种种标标准准将将给给定定数数据据对对象象集集合合进进行行层层次次的的分分解解基于于密密度度的的方方法法:基于于连连接接和和密密度度函函数数基于于网网格格的的方方法法:基于于多多层层粒粒度度结结构构基于于模模型型的的方方法法:为每每个个簇簇假假定定一一个个模模型型，，寻寻找找数数据据对对模模型型进进行行最最佳佳拟拟和和划分分聚聚类类OriginalPointsAPartitionalClustering簇层次次聚聚类类TraditionalHierarchicalClusteringNon-traditionalHierarchicalClusteringNon-traditionalDendrogramTraditionalDendrogram簇（（Clusters）的的类类型型明显显分分离离的的簇簇基于于中中心心的的簇簇基于于邻邻近近的的簇簇基于于密密度度的的簇簇概念念簇簇明显显分分离离的的簇簇3well-separatedclusters基于于中中心心的的簇簇Center-based每个个点点到到簇簇中中心心的的距距离离，，比比到到其其他他簇簇中中心心的的距距离离更更近近4center-basedclusters基于于邻邻近近的的簇簇NearestneighborAclusterisasetofpointssuchthatapointinaclusteriscloser(ormoresimilar)tooneormoreotherpointsintheclusterthantoanypointnotinthecluster.8contiguousclusters基于于密密度度的的簇簇Density-basedAclusterisadenseregionofpoints,whichisseparatedbylow-densityregions,fromotherregionsofhighdensity.Usedwhentheclustersareirregularorintertwined,andwhennoiseandoutliersarepresent.6density-basedclusters概念念簇簇SharedPropertyorConceptualClustersFindsclustersthatsharesomecommonpropertyorrepresentaparticularconcept..2OverlappingCircles4.2聚类类分分析析什么么是是聚聚类类分分析析?聚类类分分析析中中的的数数据据类类型型主要要的的聚聚类类方方法法分分类类划分分方方法法划分分方方法法:基本本概概念念划分分方方法法:为包包含含n个数数据据对对象象的的数数据据库库生生成成k个簇簇给定定k值，，采采用用一一个个划划分分规规则则将将对对象象组组织织成成k个划划分分全局局优优化化:尽可可能能枚枚举举所所有有划划分分启发发式式方方法法:k-均值值和k-中心心点点算法法k-均值值(MacQueen’67):每个个簇簇以以其其对对象象平平均均值值作作为为代代表表（（簇簇中中心心，，或或质质心心））k-中心心点点或或PAM(Kaufman&Rousseeuw’87):每个个簇簇以以其其中中的的某某一一点点代代表表K-均值值方方法法给定定k:1.任意意选选择择k个点点作作为为初初始始的的质质心心2.repeat3.将每每个个点点指指派派到到最最近近（（相相似似））的的簇簇集集4.重新新计计算算每每个个簇簇的的均均值值，，即即更更新新质质心心5.until不再再发发生生变变化化.K-均值值方方法法例最优优与与次次优优聚聚类类结结果果Sub-optimalClusteringOptimalClusteringOriginalPoints随机机选选择择初初始始质质心心（（例例1）随机机选选择择初初始始质质心心（（例例1）随机机选选择择初初始始质质心心（（例例2）但是是，，随随机机选选择择的的初初始始质质心心，，未未必必能能得得到到最最优优的的结结果果随机机选选择择初初始始质质心心（（例例2）k-均值值的的优优点点简单单、、有有效效可用用于于各各种种数数据据类类型型（但但并并非非适适合合所所有有数数据据类类型型））k-均值值的的局局限限（（缺缺点点））不能能处处理理：：不同同尺尺寸寸的的簇簇不同同密密度度的的簇簇非球球形形的的簇簇对含含离离群群点点的的数数据据聚聚类类时时也也有有问问题题不同同尺尺寸寸的的簇簇OriginalPointsK-means(3Clusters)不同密度的簇簇OriginalPointsK-means(3Clusters)非球形的簇OriginalPointsK-means(2Clusters)克服K-means的局限OriginalPointsK-meansClusters一种方法是使使用更多的簇簇（较小的簇簇集）.发现簇集的子子簇,但是需要将子子簇合并.克服K-means的局限OriginalPointsK-meansClusters克服K-means的局限OriginalPointsK-meansClustersK中心点方法在簇集中找到到簇中最中心心位置的点，，也就是中心心点PAM(围绕中心点的的划分,1987)最初随机选定定k个中心点后，，反复试图寻寻找更好的中中心点，分析析所有可能的的对象对。PAM适合于小数据据集，但是在在大数据集上上效果不佳CLARA(Kaufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):随即抽样对比k-中心与k-均值当存在噪声和和离群点时，，k-中心法更鲁棒棒k-中心法的执行行代价高于k-均值法小结与回顾聚类分析同一数据，不不同聚类方法法可导致不同同结果距离的度量基于划分的聚聚类k-均值法K-均值方法给定k:1.任意选择k个点作为初始始的质心2.repeat3.将每个点指派派到最近（相相似）的簇集集4.重新计算每个个簇的均值，，即更新质心心5.until不再发生变化化.K-均值方法例k-均值的优点简单、有效可用于各种数数据类型（但并非适合合所有数据类类型）k-均值的局限（（缺点）不能处理：不同尺寸的簇簇不同密度的簇簇非球形的簇对含离群点的的数据聚类时时也有问题4.2聚类分析什么是聚类分分析?聚类分析中的的数据类型主要的聚类方方法分类划分方法层次方法层次聚类HierarchicalClustering:NestedClustersDendrogram树状图12345612345层次方法将嵌套定义的的簇集组成一一棵层次形式式的树按照分裂方式式可分为：凝聚的把每个点都作作为一个簇，，开始聚类每一步合并两两个最近的簇簇，直到只剩剩下一个簇分裂的所有的点看做做一个簇每一步，分裂裂一个簇，直直到每个点点都是一个簇簇层次聚类方法法利用相似度或或距离矩阵作作为聚类标准准.这种方法不需需要提供k值，但是必须须提供中止条条件Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0凝聚的(AGNES)分裂的(DIANA)AGNES(凝聚的层次聚聚类)KaufmannandRousseeuw(1990)将具有最少相相异性的点合合并将这些簇合并并成越来越大大的簇直到所有终结结条件被满足足DIANA(分裂的层次聚聚类)KaufmannandRousseeuw(1990)与AGNES刚好相反直到每个对象象自成一簇基本层次凝聚聚聚类基本算法简单单直接：计算相似度矩矩阵（或邻近近矩阵）以每个点为一一个簇Repeat合并最近的两两个簇更新相似度矩矩阵Until仅剩下一个簇簇关键操作:计算两个簇间间的相似度有多种方法度度量距离或者者相似度简单直接的凝凝聚聚类初始，每个点点都为一个簇簇集，计算邻邻近矩阵p1p3p5p4p2p1p2p3p4p5......ProximityMatrix中间过程经若干次合并并后C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix中间过程合并C2与C5，更新矩阵C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix合并后问题：“如如何更新矩阵阵?”C1C4C2UC5C3???????C2UC5C1C1C3C4C2UC5C3C4ProximityMatrix如何度量簇间间距离（相似似性）p1p3p5p4p2p1p2p3p4p5......Similarity?最小距离最大距离均值距离中心点间距离离其他ProximityMatrixHowtoDefineInter-ClusterSimilarityp1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离离其他HowtoDefineInter-ClusterSimilarityp1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离离其他HowtoDefineInter-ClusterSimilarityp1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离离其他两个极端折中HowtoDefineInter-ClusterSimilarityp1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离离其他最近邻聚类与与单连接算法法最近邻：以最最小距离度量量簇间距离单连接：最近近的簇间距离离超过某个阈阈值聚类就会会终止12345最近邻聚类:MINNestedClustersDendrogram12345612345MIN的优点OriginalPointsTwoClusters能够处理非椭椭圆形簇集MIN的局限OriginalPointsTwoClusters对噪声和离群群点敏感最远邻聚类与与全连接算法法最远邻：以最最大距离度量量簇间距离。。（合并最大大距离最小的的两个簇）全连接：当最最近簇间最大大距离大于某某个阈值时聚聚类便终止。。12345最远邻聚类:MAXNestedClustersDendrogram12345612534MAX的优点OriginalPointsTwoClusters对噪声和离群群点不太敏感感MAX的局限OriginalPointsTwoClusters可能分裂大的的簇偏好球形簇均值距离或平平均距离聚类类两个簇间所有有点对距离的的平均值12345均值距离聚类类NestedClustersDendrogram12345612534均值距离聚类类是对最小和最最大距离的一一种折中优点对噪声和离群群点不敏感不足偏好球形簇层次聚类比较较GroupAverageMINMAX123456125341234561253412345612345层次聚类的困困难合并或分裂点点的选择非常常关键一旦选定，下下一步的处理理将针对新的的簇进行，已已做过的处理理不能撤销，，簇间也不能能交换对象。。若一步选择没没做好，就可可能导致低质质量的结果。。合并与分裂的的计算量较大大改进：与其他他聚类技术集集成，多阶段段聚类CURE(ClusteringUsingREpresentatives)CURE:byGuha,Rastogi&Shim,1998利用固定数目目的具有代表表性的点来代代表一个簇，，从而衡量两两个簇集之间间的距离，合合并有最近代代表对的两个个簇集。Cure:算法抽取随机样本本s.将样本分割成成一组划分对每个划分局局部的聚类删除孤立点通过随机抽样样如果一个簇增增长的太慢，，删除它.对局部的簇集集聚类用相应的簇标标签来标记数数据数据划分和聚聚类s=50p=2s/p=25xxxyyyyxyxs/pq=5Cure:收缩代表点按照某个收缩缩因子向簇中心收收缩代表点.代表点决定了了簇集的形状状xyxyCURE不能处理不同同密度的簇OriginalPointsCURECHAMELEON基于图的CHAMELEON:采用动态模型型的算法，byG.Karypis,E.H.HanandV.Kumar’99通过动态模型型衡量相似性性如果两个簇集集的互联性和和相似度与簇簇内部对象间间的互联性和和相似度高度度相关，则合合并这两个簇簇。算法分作两步步1.通过一个图划划分算法将数数据对象聚类类成大量相对对较小的子聚聚类2.然后用一个凝凝聚的层次凝凝聚算法通过过反复地合并并子类来找到到真正的结果果簇CHAMELEON算法的大致框框架构造稀疏图划分图合并划分最终的簇集DataSetExperimentalResults:CHAMELEONExperimentalResults:CHAMELEONExperimentalResults:CURE(10clusters)ExperimentalResults:CURE(15clusters)ExperimentalResults:CHAMELEONExperimentalResults:CURE(9clusters)ExperimentalResults:CURE(15clusters)小结层次聚类凝聚的和分裂裂的簇间距离：最最小、最大、、均值、中心心点最近邻与单连连接最远邻与全连连接CURE，CHAMELEON4.2聚类分析什么是聚类分分析?聚类分析中的的数据类型主要的聚类方方法分类划分方法层次方法基于密度的方方法基于密度的簇簇集方法主要特征:发现任意形状状的簇集处理噪声单次扫描需要密度参数数作为中止条条件若干相关研究究:DBSCAN:Ester,etal.(KDD’96)OPTICS:Ankerst,etal(SIGMOD’99).DENCLUE:Hinneburg&D.Keim(KDD’98)CLIQUE:Agrawal,etal.(SIGMOD’’98)基于密度的聚聚集：背景知知识两个参数:Eps:邻域半径MinPts:对象领域中至至少包含的最最小对象数目目NEps(p):{q属于D|dist(p,q)<=Eps}直接可达:在下面条件满满足情况下，，我们称点p侍从对象q关于.Eps,MinPts直接可达的1)p属于NEps(q)2)核心对象条件件:|NEps(q)|>=MinPtspqMinPts=5Eps=1cm基于密度的聚聚集：背景知知识(II)密度可达:当存在一个对对象链p1,…,pn,p1=q,pn=p，其中pi+1是pi直接密度可达达的情况下，，点p从点q关于Eps,MinPts密度相关点p和点q是关于.Eps,MinPts对象相关的，，当存在一个个点o，使得p和q都是从o关于.Eps和MinPts密度可达的.pqp1pqoDBSCAN:基于高密度连连接区域的密密度聚类方法法基于密度的簇簇集:簇被定义为密密度相连点的的最大集合可以在带有噪噪声的空间数数据库中发现现任意形状的的聚类。CoreBorderOutlierEps=1cmMinPts=5DBSCAN:算法随机的选择点点p寻找所有从点点p关于EpsandMinPts.密度可达的点点如果p是核心点,那么一个簇集集已经生成了了如果p只是边缘点,从点p没有哪一个点点是密度可达达的，DBSCAN访问数据库中中下一个点.重复上述过程程知道中止条条件满足DBSCAN:Core,Border,andNoisePointsDBSCAN:SensitivetoParametersDBSCAN:Core,BorderandNoisePointsOriginalPointsPointtypes:core,borderandnoiseEps=10,MinPts=4WhenDBSCANWorksWellOriginalPointsClustersResistanttoNoiseCanhandleclustersofdifferentshapesandsizesWhenDBSCANDoesNOTWorkWellOriginalPoints(MinPts=4,Eps=9.75).(MinPts=4,Eps=9.92)VaryingdensitiesHigh-dimensionaldata4.2聚类分析什么是聚类