數據挖掘：概念和技術-聚類分析

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

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

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

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

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

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

0d(i,i)

=0d(i,j)

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

d(i,k)

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

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

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

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

AeBtorAe-Bt

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

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

缺失（即對象i或對象j沒有變量f的值），或者xif

=xjf

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

是二元變量或標稱變量:ifxif

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

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

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

是序數型或比例標度型計算秩rif

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