數(shù)據(jù)挖掘：概念和技術(shù)-聚類分析

Chapter8.聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類分析方法分類劃分方法（PartitioningMethods）分層方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚類方法異常分析總結(jié)2023/11/251DataMining:ConceptsandTechniques什么是聚類分析?簇（Cluster）:一個(gè)數(shù)據(jù)對(duì)象的集合在同一個(gè)類中，對(duì)象之間0具有相似性；不同類的對(duì)象之間是相異的。聚類分析把一個(gè)給定的數(shù)據(jù)對(duì)象集合分成不同的簇；聚類是一種無(wú)監(jiān)督分類法:沒(méi)有預(yù)先指定的類別；典型的應(yīng)用作為一個(gè)獨(dú)立的分析工具，用于了解數(shù)據(jù)的分布；作為其它算法的一個(gè)數(shù)據(jù)預(yù)處理步驟；聚類的常規(guī)應(yīng)用模式識(shí)別空間數(shù)據(jù)分析在GIS中，通過(guò)聚類發(fā)現(xiàn)特征空間來(lái)建立主題索引；在空間數(shù)據(jù)挖掘中，檢測(cè)并解釋空間中的簇；圖象處理經(jīng)濟(jì)學(xué)(尤其是市場(chǎng)研究方面)WWW文檔分類分析WEB日志數(shù)據(jù)來(lái)發(fā)現(xiàn)相似的訪問(wèn)模式2023/11/253DataMining:ConceptsandTechniques應(yīng)用聚類分析的例子市場(chǎng)銷售:幫助市場(chǎng)人員發(fā)現(xiàn)客戶中的不同群體，然后用這些知識(shí)來(lái)開(kāi)展一個(gè)目標(biāo)明確的市場(chǎng)計(jì)劃；土地使用:在一個(gè)陸地觀察數(shù)據(jù)庫(kù)中標(biāo)識(shí)那些土地使用相似的地區(qū)；保險(xiǎn):對(duì)購(gòu)買了汽車保險(xiǎn)的客戶，標(biāo)識(shí)那些有較高平均賠償成本的客戶；城市規(guī)劃:根據(jù)類型、價(jià)格、地理位置等來(lái)劃分不同類型的住宅；地震研究:根據(jù)地質(zhì)斷層的特點(diǎn)把已觀察到的地震中心分成不同的類；2023/11/254DataMining:ConceptsandTechniques什么是一個(gè)好的聚類方法?一個(gè)好的聚類方法要能產(chǎn)生高質(zhì)量的聚類結(jié)果——簇，這些簇要具備以下兩個(gè)特點(diǎn)：高的簇內(nèi)相似性低的簇間相似性聚類結(jié)果的好壞取決于該聚類方法采用的相似性評(píng)估方法以及該方法的具體實(shí)現(xiàn)；聚類方法的好壞還取決與該方法是能發(fā)現(xiàn)某些還是所有的隱含模式；2023/11/255DataMining:ConceptsandTechniquesRequirementsofClusteringinDataMining可伸縮性能夠處理不同類型的屬性能發(fā)現(xiàn)任意形狀的簇在決定輸入?yún)?shù)的時(shí)候，盡量不需要特定的領(lǐng)域知識(shí)；能夠處理噪聲和異常對(duì)輸入數(shù)據(jù)對(duì)象的順序不敏感能處理高維數(shù)據(jù)能產(chǎn)生一個(gè)好的、能滿足用戶指定約束的聚類結(jié)果結(jié)果是可解釋的、可理解的和可用的2023/11/256DataMining:ConceptsandTechniquesChapter8.ClusterAnalysis什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類分析方法分類劃分方法（PartitioningMethods）分層方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚類方法異常分析總結(jié)2023/11/257DataMining:ConceptsandTechniques兩種數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)矩陣(twomodes)差異度矩陣(onemode)2023/11/258DataMining:ConceptsandTechniques評(píng)價(jià)聚類質(zhì)量差異度/相似度矩陣:相似度通常用距離函數(shù)來(lái)表示；有一個(gè)單獨(dú)的質(zhì)量評(píng)估函數(shù)來(lái)評(píng)判一個(gè)簇的好壞；對(duì)不同類型的變量，距離函數(shù)的定義通常是不同的，這在下面有詳細(xì)討論；根據(jù)實(shí)際的應(yīng)用和數(shù)據(jù)的語(yǔ)義，在計(jì)算距離的時(shí)候，不同的變量有不同的權(quán)值相聯(lián)系；很難定義“足夠相似了”或者“足夠好了”

只能憑主觀確定；2023/11/259DataMining:ConceptsandTechniques聚類分析中的數(shù)據(jù)類型區(qū)間標(biāo)度變量（Interval-scaledvariables）:二元變量（Binaryvariables）:標(biāo)稱型，序數(shù)型和比例型變量（Nominal,ordinal,andratiovariables）:混合類型變量（Variablesofmixedtypes）:2023/11/2510DataMining:ConceptsandTechniques區(qū)間標(biāo)度變量數(shù)據(jù)標(biāo)準(zhǔn)化計(jì)算絕對(duì)偏差的平均值:其中計(jì)算標(biāo)準(zhǔn)度量值(z-score)使用絕對(duì)偏差的平均值比使用標(biāo)準(zhǔn)偏差更健壯（robust）2023/11/2511DataMining:ConceptsandTechniques計(jì)算對(duì)象之間的相異度通常使用距離來(lái)衡量?jī)蓚€(gè)對(duì)象之間的相異度。常用的距離度量方法有:

明考斯基距離（Minkowskidistance）:其中i=(xi1,xi2,…,xip)和

j=(xj1,xj2,…,xjp)是兩個(gè)p維的數(shù)據(jù)對(duì)象,q是一個(gè)正整數(shù)。當(dāng)q=1時(shí),d

稱為曼哈坦距離（Manhattandistance）2023/11/2512DataMining:ConceptsandTechniquesSimilarityandDissimilarityBetweenObjects(Cont.)當(dāng)q=2時(shí),

d就成為歐幾里德距離:距離函數(shù)有如下特性：d(i,j)

0d(i,i)

=0d(i,j)

=d(j,i)d(i,j)

d(i,k)

+d(k,j)可以根據(jù)每個(gè)變量的重要性賦予一個(gè)權(quán)重2023/11/2513DataMining:ConceptsandTechniques二元變量二元變量的可能性表 其中每個(gè)對(duì)象有p個(gè)變量，且 p=a+b+c+dObjectiObjectj2023/11/2514DataMining:ConceptsandTechniques二元變量對(duì)稱的 如果一個(gè)二元變量的兩個(gè)狀態(tài)是同等價(jià)值的，具有相同的權(quán)重。即可以任取其中一種狀態(tài)編碼為1或者0 對(duì)于對(duì)稱的二員變量，采用簡(jiǎn)單匹配系數(shù)來(lái)評(píng)價(jià)兩個(gè)對(duì)象之間的相異度

2023/11/2515DataMining:ConceptsandTechniques二元變量非對(duì)稱的 如果變量的兩個(gè)狀態(tài)不是同樣重要的，則稱該變量是不對(duì)稱的。 根據(jù)慣例，將比較重要通常也是出現(xiàn)概率比較小的狀態(tài)編碼為1，將另一中狀態(tài)編碼為0。 對(duì)于非對(duì)稱的二員變量，采用Jaccard系數(shù)來(lái)評(píng)價(jià)兩個(gè)對(duì)象之間的相異度2023/11/2516DataMining:ConceptsandTechniques二元變量的相異度計(jì)算實(shí)例gender是一個(gè)對(duì)稱的二元變量其它的都是非對(duì)稱的二元變量將值Y和P編碼為1,值N編碼為0，根據(jù)Jaccard系數(shù)計(jì)算得：2023/11/2517DataMining:ConceptsandTechniques標(biāo)稱變量（NominalVariables）標(biāo)稱變量是二元變量的推廣，它可以具有多于兩個(gè)的狀態(tài)，比如變量map_color可以有red,yellow,blue,green四種狀態(tài)。有兩種計(jì)算相異度的方法：方法1:簡(jiǎn)單匹配方法M是匹配的數(shù)目,

p是全部變量的數(shù)目方法2:使用二元變量為每一個(gè)狀態(tài)創(chuàng)建一個(gè)新的二元變量，可以用非對(duì)稱的二元變量來(lái)編碼標(biāo)稱變量。2023/11/2518DataMining:ConceptsandTechniques序數(shù)型變量一個(gè)序數(shù)型變量可以是離散的也可以是連續(xù)的離散的序數(shù)型變量類似于標(biāo)稱變量，除了它的M個(gè)狀態(tài)是以有意義的序列排序的，比如職稱連續(xù)的序數(shù)型變量類似于區(qū)間標(biāo)度變量，但是它沒(méi)有單位，值的相對(duì)順序是必要的，而其實(shí)際大小并不重要。2023/11/2519DataMining:ConceptsandTechniques序數(shù)型變量相異度的計(jì)算 與區(qū)間標(biāo)度變量的計(jì)算方法相類似將xif

用它對(duì)應(yīng)的秩代替將每個(gè)變量的值域映射到[0.0，1.0]上，使得每個(gè)變量都有相同的權(quán)重。這通過(guò)用zif來(lái)替代rif來(lái)實(shí)現(xiàn)用前面所述的區(qū)間標(biāo)度變量的任一種距離計(jì)算方法來(lái)計(jì)算2023/11/2520DataMining:ConceptsandTechniques比例標(biāo)度型變量（Ratio-scaledvariable）比例標(biāo)度型變量:總是取正的度量值，有一個(gè)非線性的標(biāo)度，近似的遵循指數(shù)標(biāo)度，比如

AeBtorAe-Bt

計(jì)算相異度的方法:采用與處理區(qū)間標(biāo)度變量相同的方法—不是一個(gè)好的選擇進(jìn)行對(duì)數(shù)變換，對(duì)變換得到的值在采用與處理區(qū)間標(biāo)度變量相同的方法 yif

=log(xif)將其作為連續(xù)的序數(shù)型數(shù)據(jù)，將其秩作為區(qū)間標(biāo)度的值來(lái)對(duì)待。2023/11/2521DataMining:ConceptsandTechniques混合類型的變量一個(gè)數(shù)據(jù)庫(kù)可能包含了所有這6中類型的變量 用以下公式計(jì)算對(duì)象i，j之間的相異度. 其中，p為對(duì)象中的變量個(gè)數(shù) 如果xif或xjf

缺失（即對(duì)象i或?qū)ο骿沒(méi)有變量f的值），或者xif

=xjf

=0，且變量f是不對(duì)稱的二元變量，則指示項(xiàng)δij(f)=0；否則δij(f)=12023/11/2522DataMining:ConceptsandTechniques混合類型的變量f

是二元變量或標(biāo)稱變量:ifxif

=xjfdij(f)=0,elsedij(f)=1f

是區(qū)間標(biāo)度變量: dij(f)=|xif-xjf|/maxhxhf-minhxhf

其中h遍取變量f的所有非空缺對(duì)象f

是序數(shù)型或比例標(biāo)度型計(jì)算秩rif

計(jì)算zif并將其作為區(qū)間標(biāo)度變量值對(duì)待2023/11/2523DataMining:ConceptsandTechniquesChapter8.ClusterAnalysis什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類分析方法分類劃分方法（PartitioningMethods）分層方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚類方法異常分析總結(jié)2023/11/2524DataMining:ConceptsandTechniquesMajorClusteringApproachesPartitioningalgorithms:ConstructvariouspartitionsandthenevaluatethembysomecriterionHierarchyalgorithms:Createahierarchicaldecompositionofthesetofdata(orobjects)usingsomecriterionDensity-based:basedonconnectivityanddensityfunctionsGrid-based:basedonamultiple-levelgranularitystructureModel-bas