bigdaa数据挖掘培训

数据挖掘

DataMining闫雷鸣2023/1/11四、数据挖掘技术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=4WhenDBSCANWorksWellOriginalPointsClustersResistanttoNoi