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

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

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

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

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

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

0d(i,i)

=0d(i,j)

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

d(i,k)

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

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

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

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

AeBtorAe-Bt

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

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

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

=xjf

=0，且變量f是不對稱的二元變量，則指示項δ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的所有非空缺對象f

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

計算zif并將其作為區(qū)間標(biāo)度變量值對待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