bigdata数据挖掘培训课件

数据挖掘

DataMining闫雷鸣2022/12/9数据挖掘

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

D,条件h的后验概率MAP假设贝叶斯定理MAP极大后验假设学习器在候选假设集合H中寻找给定数据D时可能性最大的假设h，h被称为极大后验假设（MAP）确定MAP的方法是用贝叶斯公式计算每个候选假设的后验概率，计算式如下 最后一步，去掉了P(D)，因为它是不依赖于h的常量MAP极大后验假设学习器在候选假设集合H中寻找给定数据D时可朴素贝叶斯分类朴素假定:属性独立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)朴素假定:属性类条件独立:大大降低计算开销,只计算类的分布.朴素贝叶斯分类(I)朴素假定:属性类条件独立:朴素贝叶斯分类(II)给定训练集,我们能计算出概率（出去打网球）朴素贝叶斯分类(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打网球实例:估计P(xi|C)outlookP(sunn打网球实例:分类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)来分类打网球实例:分类X贝叶斯信念网络(I)贝叶斯信念网络允许在变量的子集间定义类条件独立性提供一种因果关系的图形学习贝叶斯信念网络的几种情况网络结构和变量均给出，容易给出网络结构和部分变量网络结构预先不知道贝叶斯信念网络(I)贝叶斯信念网络允许在变量的子集间定义类贝叶斯信念网络(II)FamilyHistoryLungCancerPositiveXRaySmokerEmphysemaDyspneaLC~LC(FH,S)(FH,~S)(~FH,S)(~FH,~S)0.10.9贝叶斯信念网络肺癌的条件概率表贝叶斯信念网络(II)FamilyLungCancerPo国家政策（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国家政策单位政策身体状况过劳死工作压力WBP(A)四、数据挖掘技术21.贝叶斯分类2.聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类划分方法层次方法基于密度的方法孤立点分析四、数据挖掘技术21.贝叶斯分类什么是聚类分析?聚类:数据对象的集合同一簇中的对象彼此相似与其他簇中的对象彼此相异Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized物以类聚人以群分什么是聚类分析?聚类:数据对象的集合Inter-cluste聚类分析将数据对象的集合分成由相似对象组成的多个类聚类分析中要划分的类是未知的典型的应用作为独立的工具来获得数据分布的情况也可以作为其他算法的预处理步骤

聚类分析同一数据的不同聚类结果Howmanyclusters?SixClusters

同一数据的不同聚类结果Howmanyclusters?SFourClusters

TwoClusters

FourClustersTwoClusters典型的聚类分析应用模式识别数据分析图象处理经济学（特别是在市场分析中）互联网典型的聚类分析应用对聚类算法的要求良好的聚类算法首先应该保证簇内对象的良好的相似性簇间对象的良好的相异性聚类算法的质量取决于算法对相似性的判别标准以及算法的具体实现算法的质量还取决于算法发现隐藏着的模式的能力对聚类算法的要求良好的聚类算法首先应该保证数据挖掘对聚类的典型要求可伸缩性处理不同类型属性的能力发现任意形状的聚类用于决定输入参数的领域知识的最小化处理噪声数据的能力对输入记录的顺序不敏感高维性基于约束的聚类可解释性和可用性数据挖掘对聚类的典型要求可伸缩性4.2聚类分析什么是聚类分析?聚类分析中的数据类型4.2聚类分析什么是聚类分析?数据结构数据矩阵(二模)相异度矩阵(单模)对象对的相异度数据结构数据矩阵对象对的相异度聚类分析中的数据类型（1）区间标度变量:重量、高度、经纬度、气温二元变量:只有两种状态得病、未得病；0,1聚类分析中的数据类型（1）区间标度变量:聚类分析中的数据类型（2）分类、序数型和比例标度型变量:分类：红、黄、蓝、绿序数：讲师、副教授、教授混合类型变量:聚类分析中的数据类型（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)加权也可以用于曼哈坦距离和明考斯基距离SimilarityandDissimilarityB4.2聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类4.2聚类分析什么是聚类分析?主要的聚类方法划分方法:构建数据的若干个划分层次方法:按某种标准将给定数据对象集合进行层次的分解基于密度的方法:基于连接和密度函数基于网格的方法:基于多层粒度结构基于模型的方法:为每个簇假定一个模型，寻找数据对模型进行最佳拟和主要的聚类方法划分方法:构建数据的若干个划分划分聚类OriginalPointsAPartitionalClustering簇划分聚类OriginalPointsAPartition层次聚类TraditionalHierarchicalClusteringNon-traditionalHierarchicalClusteringNon-traditionalDendrogramTraditionalDendrogram层次聚类TraditionalHierarchicalC簇（Clusters）的类型

明显分离的簇基于中心的簇基于邻近的簇基于密度的簇概念簇簇（Clusters）的类型明显分离的簇明显分离的簇3well-separatedclusters明显分离的簇3well-separatedcluster基于中心的簇Center-based

每个点到簇中心的距离，比到其他簇中心的距离更近4center-basedclusters基于中心的簇Center-based4center-bas基于邻近的簇NearestneighborAclusterisasetofpointssuchthatapointinaclusteriscloser(ormoresimilar)tooneormoreotherpointsintheclusterthantoanypointnotinthecluster.8contiguousclusters基于邻近的簇Nearestneighbor8contig基于密度的簇Density-basedAclusterisadenseregionofpoints,whichisseparatedbylow-densityregions,fromotherregionsofhighdensity.Usedwhentheclustersareirregularorintertwined,andwhennoiseandoutliersarepresent.6density-basedclusters基于密度的簇Density-based6density-b概念簇SharedPropertyorConceptualClustersFindsclustersthatsharesomecommonpropertyorrepresentaparticularconcept..2OverlappingCircles概念簇SharedPropertyorConceptu4.2聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类划分方法4.2聚类分析什么是聚类分析?划分方法:基本概念划分方法:为包含n个数据对象的数据库生成k个簇给定k值，采用一个划分规则将对象组织成k个划分全局优化:尽可能枚举所有划分启发式方法:k-均值和k-中心点算法k-均值

(MacQueen’67):每个簇以其对象平均值作为代表（簇中心，或质心）k-中心点或

PAM(Kaufman&Rousseeuw’87):每个簇以其中的某一点代表划分方法:基本概念划分方法:为包含n个数据对象的数据库生成K-均值方法给定k:1.任意选择k个点作为初始的质心2.repeat3.将每个点指派到最近（相似）的簇集4.重新计算每个簇的均值，即更新质心5.until不再发生变化.K-均值方法给定k:K-均值方法例K-均值方法例最优与次优聚类结果Sub-optimalClusteringOptimalClusteringOriginalPoints最优与次优聚类结果Sub-optimalClusterin随机选择初始质心（例1）随机选择初始质心（例1）随机选择初始质心（例1）随机选择初始质心（例1）随机选择初始质心（例2）但是，随机选择的初始质心，未必能得到最优的结果随机选择初始质心（例2）但是，随机选择的初始质心，未必能得到随机选择初始质心（例2）随机选择初始质心（例2）k-均值的优点简单、有效可用于各种数据类型（但并非适合所有数据类型）k-均值的优点简单、有效k-均值的局限（缺点）不能处理：不同尺寸的簇不同密度的簇非球形的簇对含离群点的数据聚类时也有问题k-均值的局限（缺点）不能处理：不同尺寸的簇OriginalPointsK-means(3Clusters)不同尺寸的簇OriginalPointsK-means(不同密度的簇OriginalPointsK-means(3Clusters)不同密度的簇OriginalPointsK-means(非球形的簇OriginalPointsK-means(2Clusters)非球形的簇OriginalPointsK-means(2克服K-means的局限OriginalPoints K-meansClusters一种方法是使用更多的簇（较小的簇集）.发现簇集的子簇,但是需要将子簇合并.克服K-means的局限OriginalPoints 克服K-means的局限OriginalPoints K-meansClusters克服K-means的局限OriginalPoints 克服K-means的局限OriginalPoints K-meansClusters克服K-means的局限OriginalPoints K中心点方法在簇集中找到簇中最中心位置的点，也就是中心点PAM(围绕中心点的划分,1987)最初随机选定k个中心点后，反复试图寻找更好的中心点，分析所有可能的对象对。PAM

适合于小数据集，但是在大数据集上效果不佳CLARA(Kaufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):随即抽样K中心点方法在簇集中找到簇中最中心位置的点，也就是中心点对比k-中心与k-均值当存在噪声和离群点时，k-中心法更鲁棒k-中心法的执行代价高于k-均值法对比k-中心与k-均值当存在噪声和离群点时，k-中心法更鲁棒小结与回顾聚类分析同一数据，不同聚类方法可导致不同结果距离的度量基于划分的聚类k-均值法小结与回顾聚类分析K-均值方法给定k:1.任意选择k个点作为初始的质心2.repeat3.将每个点指派到最近（相似）的簇集4.重新计算每个簇的均值，即更新质心5.until不再发生变化.K-均值方法给定k:K-均值方法例K-均值方法例k-均值的优点简单、有效可用于各种数据类型（但并非适合所有数据类型）k-均值的优点简单、有效k-均值的局限（缺点）不能处理：不同尺寸的簇不同密度的簇非球形的簇对含离群点的数据聚类时也有问题k-均值的局限（缺点）不能处理：4.2聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类划分方法层次方法4.2聚类分析什么是聚类分析?层次聚类HierarchicalClustering:NestedClustersDendrogram树状图12345612345层次聚类HierarchicalClustering:Ne层次方法将嵌套定义的簇集组成一棵层次形式的树按照分裂方式可分为：凝聚的把每个点都作为一个簇，开始聚类每一步合并两个最近的簇，直到只剩下一个簇分裂的所有的点看做一个簇每一步，分裂一个簇，直到每个点都是一个簇层次方法将嵌套定义的簇集组成一棵层次形式的树层次聚类方法利用相似度或距离矩阵作为聚类标准.这种方法不需要提供k值，但是必须提供中止条件Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0凝聚的(AGNES)分裂的(DIANA)层次聚类方法利用相似度或距离矩阵作为聚类标准.这种方法不需AGNES(凝聚的层次聚类)KaufmannandRousseeuw(1990)将具有最少相异性的点合并将这些簇合并成越来越大的簇直到所有终结条件被满足AGNES(凝聚的层次聚类)KaufmannandRoDIANA(分裂的层次聚类)KaufmannandRousseeuw(1990)与AGNES刚好相反直到每个对象自成一簇DIANA(分裂的层次聚类)KaufmannandRo基本层次凝聚聚类基本算法简单直接：计算相似度矩阵（或邻近矩阵）以每个点为一个簇Repeat

合并最近的两个簇 更新相似度矩阵Until

仅剩下一个簇

关键操作:计算两个簇间的相似度有多种方法度量距离或者相似度基本层次凝聚聚类基本算法简单直接：简单直接的凝聚聚类初始，每个点都为一个簇集，计算邻近矩阵p1p3p5p4p2p1p2p3p4p5......ProximityMatrix简单直接的凝聚聚类初始，每个点都为一个簇集，计算邻近矩阵p中间过程经若干次合并后C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix中间过程经若干次合并后C1C4C2C5C3C2C1C1C3C中间过程合并C2与C5，更新矩阵C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix中间过程合并C2与C5，更新矩阵C1C4C2C5C3C2C合并后问题：“如何更新矩阵?”C1C4C2UC5C3???? ???C2UC5C1C1C3C4C2UC5C3C4ProximityMatrix合并后问题：“如何更新矩阵?”C1C4C2UC5C3如何度量簇间距离（相似性）

p1p3p5p4p2p1p2p3p4p5......Similarity?最小距离最大距离均值距离中心点间距离其他ProximityMatrix如何度量簇间距离（相似性）p1p3p5p4p2p1p2p3HowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离其他HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离其他HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离其他两个极端折中HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离其他HowtoDefineInter-ClusterSi最近邻聚类与单连接算法最近邻：以最小距离度量簇间距离单连接：最近的簇间距离超过某个阈值聚类就会终止12345最近邻聚类与单连接算法最近邻：以最小距离度量簇间距离1234最近邻聚类:MINNestedClustersDendrogram12345612345最近邻聚类:MINNestedClustersDendrMIN的优点OriginalPointsTwoClusters

能够处理非椭圆形簇集MIN的优点OriginalPointsTwoClustMIN的局限OriginalPointsTwoClusters

对噪声和离群点敏感MIN的局限OriginalPointsTwoClust最远邻聚类与全连接算法最远邻：以最大距离度量簇间距离。（合并最大距离最小的两个簇）全连接：当最近簇间最大距离大于某个阈值时聚类便终止。12345最远邻聚类与全连接算法最远邻：以最大距离度量簇间距离。（合并最远邻聚类:MAXNestedClustersDendrogram12345612534最远邻聚类:MAXNestedClustersDendrMAX的优点OriginalPointsTwoClusters

对噪声和离群点不太敏感MAX的优点OriginalPointsTwoClustMAX的局限OriginalPointsTwoClusters可能分裂大的簇偏好球形簇MAX的局限OriginalPointsTwoClust均值距离或平均距离聚类两个簇间所有点对距离的平均值12345均值距离或平均距离聚类两个簇间所有点对距离的平均值12345均值距离聚类NestedClustersDendrogram12345612534均值距离聚类NestedClustersDendrogra均值距离聚类是对最小和最大距离的一种折中优点对噪声和离群点不敏感不足偏好球形簇均值距离聚类是对最小和最大距离的一种折中层次聚类比较GroupAverageMINMAX123456125341234561253412345612345层次聚类比较GroupAverageMINMAX12345层次聚类的困难合并或分裂点的选择非常关键一旦选定，下一步的处理将针对新的簇进行，已做过的处理不能撤销，簇间也不能交换对象。若一步选择没做好，就可能导致低质量的结果。合并与分裂的计算量较大改进：与其他聚类技术集成，多阶段聚类层次聚类的困难合并或分裂点的选择非常关键CURE(ClusteringUsingREpresentatives)CURE:byGuha,Rastogi&Shim,1998利用固定数目的具有代表性的点来代表一个簇，从而衡量两个簇集之间的距离，合并有最近代表对的两个簇集。CURE(ClusteringUsingREpreseCure:算法抽取随机样本s.将样本分割成一组划分对每个划分局部的聚类删除孤立点通过随机抽样如果一个簇增长的太慢，删除它.对局部的簇集聚类用相应的簇标签来标记数据Cure:算法抽取随机样本s.数据划分和聚类s=50p=2s/p=25xxxyyyyxyxs/pq=5数据划分和聚类s=50xxxyyyyxyxs/pq=Cure:收缩代表点按照某个收缩因子向簇中心收缩代表点.代表点决定了簇集的形状xyxyCure:收缩代表点按照某个收缩因子向簇中心收缩代表点.CURE不能处理不同密度的簇OriginalPointsCURECURE不能处理不同密度的簇OriginalPointsCHAMELEON基于图的CHAMELEON:采用动态模型的算法，byG.Karypis,E.H.HanandV.Kumar’99通过动态模型衡量相似性如果两个簇集的互联性和相似度与簇内部对象间的互联性和相似度高度相关，则合并这两个簇。算法分作两步1.通过一个图划分算法将数据对象聚类成大量相对较小的子聚类2.然后用一个凝聚的层次凝聚算法通过反复地合并子类来找到真正的结果簇CHAMELEON基于图的CHAMELEON:采用动态模型的CHAMELEON算法的大致框架构造稀疏图划分图合并划分最终的簇集DataSetCHAMELEON算法的大致框架构造稀疏图划分图合并划分最终ExperimentalResults:CHAMELEONExperimentalResults:CHAMELEOExperimentalResults:CHAMELEONExperimentalResults:CHAMELEOExperimentalResults:CURE(10clusters)ExperimentalResults:CURE(10ExperimentalResults:CURE(15clusters)ExperimentalResults:CURE(15ExperimentalResults:CHAMELEONExperimentalResults:CHAMELEOExperimentalResults:CURE(9clusters)ExperimentalResults:CURE(9ExperimentalResults:CURE(15clusters)ExperimentalResults:CURE(15小结层次聚类凝聚的和分裂的簇间距离：最小、最大、均值、中心点最近邻与单连接最远邻与全连接CURE，CHAMELEON小结层次聚类4.2聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类划分方法层次方法基于密度的方法4.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)|>=MinPts

pqMinPts=5Eps=1cm基于密度的聚集：背景知识两个参数:pqMinPts=5基于密度的聚集：背景知识(II)密度可达:当存在一个对象链p1,…,pn,p1=q,pn=p

，其中pi+1

是pi直接密度可达的情况下，点p从点q关于Eps,MinPts密度相关点p

和点q

是关于.Eps,MinPts对象相关的，当存在一个点o，使得p

和q

都是从o

关于.Eps和MinPts密度可达的.pqp1pqo基于密度的聚集：背景知识(II)密度可达:pqp1pqoDBSCAN:基于高密度连接区域的密度聚类方法基于密度的簇集:簇被定义为密度相连点的最大集合可以在带有噪声的空间数据库中发现任意形状的聚类。CoreBorderOutlierEps=1cmMinPts=5DBSCAN:基于高密度连接区域的密度聚类方法基于密度的簇DBSCAN:算法随机的选择点p寻找所有从点p

关于EpsandMinPts.密度可达的点如果p

是核心点,那么一个簇集已经生成了如果p只是边缘点,从点p

没有哪一个点是密度可达的，DBSCAN访问数据库中下一个点.重复上述过程知道中止条件满足DBSCAN:算法随机的选择点pDBSCAN:Core,Border,andNoisePointsDBSCAN:Core,Border,andNoisDBSCAN:SensitivetoParametersDBSCAN:SensitivetoParameterDBSCAN:Core,BorderandNoisePointsOriginalPointsPointtypes:core,borderandnoiseEps=10,MinPts=4DBSCAN:Core,BorderandNoiseWhenDBSCANWorksWellOriginalPointsClustersResistanttoNoiseCanhandleclustersofdifferentshapesandsizesWhenDBSCANWorksWellOriginalWhenDBSCANDoesNOTWorkWellOriginalPoints(MinPts=4,Eps=9.75).

(MinPts=4,Eps=9.92)VaryingdensitiesHigh-dimensionaldataWhenDBSCANDoesNOTWorkWell4.2聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类划分方法层次方法基于密度的方法孤立点（离群点）分析4.2聚类分析什么是聚类分析?什么是孤立点?什么是孤立点?与数据的其他部分不同或不一致例如:Sports:MichaelJordon,WayneGretzky,...问题找到前n个孤立点应用:监测信用卡诈骗监测电话诈骗分析收入极高和极低的消费者的行为医疗分析什么是孤立点?什么是孤立点?基于统计的孤立点查询对给定的数据集合假设了一个分布或概率模型进行不一致性检验，根据数据集参数分布参数预期的孤立点数目缺点针对单个属性很多情况下数据分布是未知的。基于统计的孤立点查询对给定的数据集合假设了一个分布或概率模基于距离的孤立点查询为了解决统计学方法的一些限制，引入了基于距离的孤立点概念我们需要在不知道数据分布的情况下处理多位数据.基于距离的孤立点:如果数据集合T中至少有p部分对象与对象O的距离大于d，那么就称O为一个带参数p和d的基于距离的孤立点计语句你的孤立点算法基于索引的算法嵌套循环算法基于单元的算法基于距离的孤立点查询为了解决统计学方法的一些限制，引入了基于基于密度的方法:LOFForeachpoint,computethedensityofitslocalneighborhoodComputelocaloutlierfactor(LOF)ofasamplepastheaverageoftheratiosofthedensityofsamplepandthedensityofitsnearestneighborsOutliersarepointswithlargestLOFvaluep2p1基于密度的方法:LOFForeachpoint,co基于聚类的方法Basicidea:ClusterthedataintogroupsofdifferentdensityChoosepointsinsmallclusterascandidateoutliersComputethedistancebetweencandidatepointsandnon-candidateclusters.Ifcandidatepointsarefarfromallothernon-candidatepoints,theyareoutliers基于聚类的方法Basicidea:基于偏离的孤立点预测通过一组对象的主要特征来识别孤立点与给出描述偏离的对象就被认为是孤立点序列异常技术模仿了人类从一系列的推测类似对象中识别异常对象的方式OLAP数据立方体技术利用在大规模多维数据中采用数据立方体来确定反常区域。基于偏离的孤立点预测通过一组对象的主要特征来识别孤立点数据挖掘

DataMining闫雷鸣2022/12/9数据挖掘

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

D,条件h的后验概率MAP假设贝叶斯定理MAP极大后验假设学习器在候选假设集合H中寻找给定数据D时可能性最大的假设h，h被称为极大后验假设（MAP）确定MAP的方法是用贝叶斯公式计算每个候选假设的后验概率，计算式如下 最后一步，去掉了P(D)，因为它是不依赖于h的常量MAP极大后验假设学习器在候选假设集合H中寻找给定数据D时可朴素贝叶斯分类朴素假定:属性独立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)朴素假定:属性类条件独立:大大降低计算开销,只计算类的分布.朴素贝叶斯分类(I)朴素假定:属性类条件独立:朴素贝叶斯分类(II)给定训练集,我们能计算出概率（出去打网球）朴素贝叶斯分类(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打网球实例:估计P(xi|C)outlookP(sunn打网球实例:分类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)来分类打网球实例:分类X贝叶斯信念网络(I)贝叶斯信念网络允许在变量的子集间定义类条件独立性提供一种因果关系的图形学习贝叶斯信念网络的几种情况网络结构和变量均给出，容易给出网络结构和部分变量网络结构预先不知道贝叶斯信念网络(I)贝叶斯信念网络允许在变量的子集间定义类贝叶斯信念网络(II)FamilyHistoryLungCancerPositiveXRaySmokerEmphysemaDyspneaLC~LC(FH,S)(FH,~S)(~FH,S)(~FH,~S)0.10.9贝叶斯信念网络肺癌的条件概率表贝叶斯信念网络(II)FamilyLungCancerPo国家政策（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国家政策单位政策身体状况过劳死工作压力WBP(A)四、数据挖掘技术21.贝叶斯分类2.聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类划分方法层次方法基于密度的方法孤立点分析四、数据挖掘技术21.贝叶斯分类什么是聚类分析?聚类:数据对象的集合同一簇中的对象彼此相似与其他簇中的对象彼此相异Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized物以类聚人以群分什么是聚类分析?聚类:数据对象的集合Inter-cluste聚类分析将数据对象的集合分成由相似对象组成的多个类聚类分析中要划分的类是未知的典型的应用作为独立的工具来获得数据分布的情况也可以作为其他算法的预处理步骤

聚类分析同一数据的不同聚类结果Howmanyclusters?SixClusters

同一数据的不同聚类结果Howmanyclusters?SFourClusters

TwoClusters

FourClustersTwoClusters典型的聚类分析应用模式识别数据分析图象处理经济学（特别是在市场分析中）互联网典型的聚类分析应用对聚类算法的要求良好的聚类算法首先应该保证簇内对象的良好的相似性簇间对象的良好的相异性聚类算法的质量取决于算法对相似性的判别标准以及算法的具体实现算法的质量还取决于算法发现隐藏着的模式的能力对聚类算法的要求良好的聚类算法首先应该保证数据挖掘对聚类的典型要求可伸缩性处理不同类型属性的能力发现任意形状的聚类用于决定输入参数的领域知识的最小化处理噪声数据的能力对输入记录的顺序不敏感高维性基于约束的聚类可解释性和可用性数据挖掘对聚类的典型要求可伸缩性4.2聚类分析什么是聚类分析?聚类分析中的数据类型4.2聚类分析什么是聚类分析?数据结构数据矩阵(二模)相异度矩阵(单模)对象对的相异度数据结构数据矩阵对象对的相异度聚类分析中的数据类型（1）区间标度变量:重量、高度、经纬度、气温二元变量:只有两种状态得病、未得病；0,1聚类分析中的数据类型（1）区间标度变量:聚类分析中的数据类型（2）分类、序数型和比例标度型变量:分类：红、黄、蓝、绿序数：讲师、副教授、教授混合类型变量:聚类分析中的数据类型（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)加权也可以用于曼哈坦距离和明考斯基距离SimilarityandDissimilarityB4.2聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类4.2聚类分析什么是聚类分析?主要的聚类方法划分方法:构建数据的若干个划分层次方法:按某种标准将给定数据对象集合进行层次的分解基于密度的方法:基于连接和密度函数基于网格的方法:基于多层粒度结构基于模型的方法:为每个簇假定一个模型，寻找数据对模型进行最佳拟和主要的聚类方法划分方法:构建数据的若干个划分划分聚类OriginalPointsAPartitionalClustering簇划分聚类OriginalPointsAPartition层次聚类TraditionalHierarchicalClusteringNon-traditionalHierarchicalClusteringNon-traditionalDendrogramTraditionalDendrogram层次聚类TraditionalHierarchicalC簇（Clusters）的类型

明显分离的簇基于中心的簇基于邻近的簇基于密度的簇概念簇簇（Clusters）的类型明显分离的簇明显分离的簇3well-separatedclusters明显分离的簇3well-separatedcluster基于中心的簇Center-based

每个点到簇中心的距离，比到其他簇中心的距离更近4center-basedclusters基于中心的簇Center-based4center-bas基于邻近的簇NearestneighborAclusterisasetofpointssuchthatapointinaclusteriscloser(ormoresimilar)tooneormoreotherpointsintheclusterthantoanypointnotinthecluster.8contiguousclusters基于邻近的簇Nearestneighbor8contig基于密度的簇Density-basedAclusterisadenseregionofpoints,whichisseparatedbylow-densityregions,fromotherregionsofhighdensity.Usedwhentheclustersareirregularorintertwined,andwhennoiseandoutliersarepresent.6density-basedclusters基于密度的簇Density-based6density-b概念簇SharedPropertyorConceptualClustersFindsclustersthatsharesomecommonpropertyorrepresentaparticularconcept..2OverlappingCircles概念簇SharedPropertyorConceptu4.2聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类划分方法4.2聚类分析什么是聚类分析?划分方法:基本概念划分方法:为包含n个数据对象的数据库生成k个簇给定k值，采用一个划分规则将对象组织成k个划分全局优化:尽可能枚举所有划分启发式方法:k-均值和k-中心点算法k-均值

(MacQueen’67):每个簇以其对象平均值作为代表（簇中心，或质心）k-中心点或

PAM(Kaufman&Rousseeuw’87):每个簇以其中的某一点代表划分方法:基本概念划分方法:为包含n个数据对象的数据库生成K-均值方法给定k:1.任意选择k个点作为初始的质心2.repeat3.将每个点指派到最近（相似）的簇集4.重新计算每个簇的均值，即更新质心5.until不再发生变化.K-均值方法给定k:K-均值方法例K-均值方法例最优与次优聚类结果Sub-optimalClusteringOptimalClusteringOriginalPoints最优与次优聚类结果Sub-optimalClusterin随机选择初始质心（例1）随机选择初始质心（例1）随机选择初始质心（例1）随机选择初始质心（例1）随机选择初始质心（例2）但是，随机选择的初始质心，未必能得到最优的结果随机选择初始质心（例2）但是，随机选择的初始质心，未必能得到随机选择初始质心（例2）随机选择初始质心（例2）k-均值的优点简单、有效可用于各种数据类型（但并非适合所有数据类型）k-均值的优点简单、有效k-均值的局限（缺点）不能处理：不同尺寸的簇不同密度的簇非球形的簇对含离群点的数据聚类时也有问题k-均值的局限（缺点）不能处理：不同尺寸的簇OriginalPointsK-means(3Clusters)不同尺寸的簇OriginalPointsK-means(不同密度的簇OriginalPointsK-means(3Clusters)不同密度的簇OriginalPointsK-means(非球形的簇OriginalPointsK-means(2Clusters)非球形的簇OriginalPointsK-means(2克服K-means的局限OriginalPoints K-meansClusters一种方法是使用更多的簇（较小的簇集）.发现簇集的子簇,但是需要将子簇合并.克服K-means的局限OriginalPoints 克服K-means的局限OriginalPoints K-meansClusters克服K-means的局限OriginalPoints 克服K-means的局限OriginalPoints K-meansClusters克服K-means的局限OriginalPoints K中心点方法在簇集中找到簇中最中心位置的点，也就是中心点PAM(围绕中心点的划分,1987)最初随机选定k个中心点后，反复试图寻找更好的中心点，分析所有可能的对象对。PAM

适合于小数据集，但是在大数据集上效果不佳CLARA(Kaufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):随即抽样K中心点方法在簇集中找到簇中最中心位置的点，也就是中心点对比k-中心与k-均值当存在噪声和离群点时，k-中心法更鲁棒k-中心法的执行代价高于k-均值法对比k-中心与k-均值当存在噪声和离群点时，k-中心法更鲁棒小结与回顾聚类分析同一数据，不同聚类方法可导致不同结果距离的度量基于划分的聚类k-均值法小结与回顾聚类分析K-均值方法给定k:1.任意选择k个点作为初始的质心2.repeat3.将每个点指派到最近（相似）的簇集4.重新计算每个簇的均值，即更新质心5.until不再发生变化.K-均值方法给定k:K-均值方法例K-均值方法例k-均值的优点简单、有效可用于各种数据类型（但并非适合所有数据类型）k-均值的优点简单、有效k-均值的局限（缺点）不能处理：不同尺寸的簇不同密度的簇非球形的簇对含离群点的数据聚类时也有问题k-均值的局限（缺点）不能处理：4.2聚类分析什么是聚类分析?聚类分析中的数据类型主要的聚类方法分类划分方法层次方法4.2聚类分析什么是聚类分析?层次聚类HierarchicalClustering:NestedClustersDendrogram树状图12345612345层次聚类HierarchicalClustering:Ne层次方法将嵌套定义的簇集组成一棵层次形式的树按照分裂方式可分为：凝聚的把每个点都作为一个簇，开始聚类每一步合并两个最近的簇，直到只剩下一个簇分裂的所有的点看做一个簇每一步，分裂一个簇，直到每个点都是一个簇层次方法将嵌套定义的簇集组成一棵层次形式的树层次聚类方法利用相似度或距离矩阵作为聚类标准.这种方法不需要提供k值，但是必须提供中止条件Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0凝聚的(AGNES)分裂的(DIANA)层次聚类方法利用相似度或距离矩阵作为聚类标准.这种方法不需AGNES(凝聚的层次聚类)KaufmannandRousseeuw(1990)将具有最少相异性的点合并将这些簇合并成越来越大的簇直到所有终结条件被满足AGNES(凝聚的层次聚类)KaufmannandRoDIANA(分裂的层次聚类)KaufmannandRousseeuw(1990)与AGNES刚好相反直到每个对象自成一簇DIANA(分裂的层次聚类)KaufmannandRo基本层次凝聚聚类基本算法简单直接：计算相似度矩阵（或邻近矩阵）以每个点为一个簇Repeat

合并最近的两个簇 更新相似度矩阵Until

仅剩下一个簇

关键操作:计算两个簇间的相似度有多种方法度量距离或者相似度基本层次凝聚聚类基本算法简单直接：简单直接的凝聚聚类初始，每个点都为一个簇集，计算邻近矩阵p1p3p5p4p2p1p2p3p4p5......ProximityMatrix简单直接的凝聚聚类初始，每个点都为一个簇集，计算邻近矩阵p中间过程经若干次合并后C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix中间过程经若干次合并后C1C4C2C5C3C2C1C1C3C中间过程合并C2与C5，更新矩阵C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix中间过程合并C2与C5，更新矩阵C1C4C2C5C3C2C合并后问题：“如何更新矩阵?”C1C4C2UC5C3???? ???C2UC5C1C1C3C4C2UC5C3C4ProximityMatrix合并后问题：“如何更新矩阵?”C1C4C2UC5C3如何度量簇间距离（相似性）

p1p3p5p4p2p1p2p3p4p5......Similarity?最小距离最大距离均值距离中心点间距离其他ProximityMatrix如何度量簇间距离（相似性）p1p3p5p4p2p1p2p3HowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离其他HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离其他HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离其他两个极端折中HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距离最大距离均值距离中心点间距离其他HowtoDefineInter-ClusterSi最近邻聚类与单连接算法最近邻：以最小距离度量簇间距离单连接：最近的簇间距离超过某个阈值聚类就会终止12345最近邻聚类与单连接算法最近邻：以最小距离度量簇间距离1234最近邻聚类:MINNestedClustersDendrogram12345612345最近邻聚类:MINNestedClustersDendrMIN的优点OriginalPointsTwoClusters

能够处理非椭圆形簇集MIN的优点OriginalPointsTwoClustMIN的局限OriginalPointsTwoClusters

对噪声和离群点敏感MIN的局限OriginalPointsTwoClust最远邻聚类与全连接算法最远邻：以最大距离度量簇间距离。（合并最大距离最小的两个簇）全连接：当最近簇间最大距离大于某个阈值时聚类便终止。12345最远邻聚类与全连接算法最远邻：以最大距离度量簇间距离。（合并最远邻聚类:MAXNestedClustersDendrogram12345612534最远邻聚类:MAXNestedClustersDendrMAX的优点OriginalPointsTwoClusters

对噪声和离群点不太敏感MAX的优点OriginalPointsTwoClustMAX的局限OriginalPointsTwoClusters可能分裂大的簇偏好球形簇MAX的局限OriginalPointsTwoClust均值距离或平均距离聚类两个簇间所有点对距离的平均值12345均值距离或平均距离聚类两个簇间所有点对距离的平均值12345均值距离聚类NestedClustersDendrogram12345612534均值距离聚类NestedClustersDendrogra均值距离聚类是对最小和最大距离的一种折中优点对噪声和离群点不敏感不足偏好球形簇均值距离聚类是对最小和最大距离的一种折中层次聚类比较GroupAverageMINMAX123456125341234561253412345612345层次聚类比较GroupAverageMINMAX12345层次聚类的困难合并或分裂点的选择非常关键一旦选定，下一步的处理将针对新的簇进行，已做过的处理不能撤销，簇间也不能交换对象。若一步选择没做好，就可能导致低质量的结果。合并与分裂的计算量较大改进：与其他聚类技术集成，多阶段聚类层次聚类的困难合并或分裂点的选择非常关键CURE(ClusteringUsingREpresentatives)CURE:byGuha,Rastogi&Shim,1998利用固定数目的具有代表性的点来代表一个簇，从而衡量两个簇集之间的距离，合并有最近代表对的两个簇集。CURE(ClusteringUsingREpreseCure:算法抽取随机样本s.将样本分割成一组划分对每个划分局部的聚类删除孤立点通过随机抽样如果一个簇增长的太慢，删除它.对局部的簇集聚类用相应的簇标签来标记数据Cure:算法抽取随机样本s.数据划分和聚类s=50p=2s/p=25xxxyyyyxyxs/pq=5数据划分和聚类s=50xxxyyyyxyxs/pq=Cure:收缩代表点按照某个收缩因子向簇中心收缩代表点.代表点决定了簇集的形状xyxyCure:收缩代表点按照某个收缩因子向簇中心收缩代表点.CURE不能处理不同密度的簇OriginalPointsCURECURE不能处理不同密度的簇OriginalPointsCHAMELEON基于图的CHAMELEON:采用动态模型的算法，byG.Karypis,E.H.HanandV.Kumar’99通过动态模型衡量相似性如果两个簇集的互联性和相似度与簇内部对象间的互联性和相似度高度相关，则合并这两个簇。算法分作两步1.通过一个图划分算法将数据对象聚类成大量相对较小的子聚类2.然后用一个凝聚的层次凝聚算法通过反复地合并子类来找到真正的结果簇CHAMELEON基于图的CHAMELEON:采用动态模型的CHAMELEON算法的大致框架构造稀疏图划分图合并划分最终的簇集DataSetCHAMELEON算法的大致框架构造稀疏图划分图合并划分最终ExperimentalResults:CHAMELEONExperimentalResults:CHAMELEOExperimentalResults:CHAMELEONExpe