聚類分析算法學習報告.ppt

1、聚類分析算法 學習匯報,聚類分析概述,寧夏大學數(shù)學與計算機學院,1、什么是聚類？ 聚類（clustering）是將物理或抽象對象的集合分組成為多個類或簇（cluster）的過程，使得在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。 2、與分類的不同 它要劃分的類是未知的。即聚類是一種無指導學習，它不依賴預先定義的類和帶類標號的訓練實例。,聚類分析的應用,聚類分析已經(jīng)廣泛的用在許多應用中，包括模式識別、數(shù)據(jù)分析、圖像處理以及市場研究。典型的應用： （1）商業(yè)：幫助市場分析人員從客戶基本庫中發(fā)現(xiàn)不同的客戶群，并且用不同的購買模式描述不同客戶群的特征。 （2）生物學：推導植物或動物

2、的分類，活的對種群固有結(jié)構(gòu)的認識。 （3）WEB文檔分類 （4）其他：地球觀測數(shù)據(jù)庫中相似地區(qū)的確定各類保險投保人的分組，一個城市中不同類型、價值、地理位置房子的分組等。 （5）作為其他數(shù)據(jù)挖掘算法的預處理：即先進行聚類，然后再進行分類等其他數(shù)據(jù)挖掘,寧夏大學數(shù)學與計算機學院,聚類分析的要求,寧夏大學數(shù)學與計算機學院,可伸縮性 處理不同類型屬性的能力 發(fā)現(xiàn)任意形狀的聚類 用于決定輸入?yún)?shù)的領(lǐng)域知識最小化 處理噪聲數(shù)據(jù)的能力 對于輸入記錄的順序不敏感 高維性 基于約束的聚類 可解釋性和可用性,聚類分析中的數(shù)據(jù)類型,寧夏大學數(shù)學與計算機學院,聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型

3、: 區(qū)間標度變量 二元變量 標稱型、序數(shù)型和比例標度型變量 混合類型變量,區(qū)間標度變量,寧夏大學數(shù)學與計算機學院,1、 區(qū)間標度變量是一個粗略線性標度的連續(xù)度量。典型的例子包括重量和高度，經(jīng)度和緯度坐標，以及大氣溫度。2、選擇不同的度量單位（如“米”與英尺、“千克”與“磅”等）將直接影響聚類分析的結(jié)果。 3、為了避免聚類分析對度量單位的依賴性，數(shù)據(jù)需要進行標準化。 4、怎樣將一個變量的數(shù)據(jù)標準化呢？為了實現(xiàn)度量值的標準化，一種方法是將原來的度量值轉(zhuǎn)換為無單位的值。,度量值的標準化,寧夏大學數(shù)學與計算機學院,（1）計算平均的絕對偏差（mean absolute deviation）: 其中： （

4、2）計算標準化的度量值，或（z-score）:,對象間的相異度計算,歐幾里德距離： 曼哈坦距離： 明考斯基距離：,寧夏大學數(shù)學與計算機學院,聚類分析中的數(shù)據(jù)類型,寧夏大學數(shù)學與計算機學院,聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型: 區(qū)間標度變量 二元變量 標稱型、序數(shù)型和比例標度型變量 混合類型變量,二元變量,寧夏大學數(shù)學與計算機學院,一個二元變量只有兩個狀態(tài)：0或者1，0表示該變量為空，1表示該變量存在。 如果假設所有的二元變量有相同的權(quán)重，則得到一個兩行兩列的可能性表。在下面這個表中，a是對于對象i和j值都為1的變量的數(shù)目，b是對于對象I值為1而對象j的值為0的變量數(shù)目，s

5、是對于對象c值為0而在對于對象j值為1的變量數(shù)目，d是對于對象i和j的值都為0的變量的數(shù)目。變量的總數(shù)是p，p=a+b+c+d。,Object j,Object i,基于對稱二元變量的相似度稱為恒定的相似度，即當一些或者全部二元變量編碼改變時，計算結(jié)果不會發(fā)生變化。 如果二元變量的兩個狀態(tài)的輸出不是同樣重要，則該二元變量是不對稱的。基于這樣變量的相似度被稱為非恒定的相似度。,二元變量相似度的計算,寧夏大學數(shù)學與計算機學院,聚類分析中的數(shù)據(jù)類型,寧夏大學數(shù)學與計算機學院,聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型: 區(qū)間標度變量 二元變量 標稱型、序數(shù)型和比例標度型變量 混合類型變

6、量,1、標稱型變量 標稱變量（nominal）是二元變量的推廣，它可以具有多于兩個的狀態(tài)值。例如，map-color是一個標稱變量，它可能有五個狀態(tài)：紅色，黃色，綠色，粉紅色和藍色。兩個對象和j之間的相異度可以用兩種方法來計算： （1）簡單匹配方法 M是匹配的數(shù)目，P是全部變量的數(shù)目 （2）使用二元變量 為每一個狀態(tài)創(chuàng)建一個新的二元變量，可以用非對稱的二元變量來編碼標稱變量。,標稱型變量,寧夏大學數(shù)學與計算機學院,一個離散的序數(shù)（ordinal）型變量類似于標稱變量，除了序數(shù)型變量的個狀態(tài)是以有意義的序列排序的。在計算對象的相異度時，序數(shù)型變量的處理與區(qū)間標度變量非常類似。（1）將xif 用它

7、對應的秩代替。 （2）將每個變量的值域映射到0.0，1.0上，使得每個變量都有相同的權(quán)重。這通過用zif來替代rif來實現(xiàn)。 （3）用前面所述的區(qū)間標度變量的任一種距離計算方法來計算。,序數(shù)型變量,寧夏大學數(shù)學與計算機學院,用比例標度型變量描述對象之間相異度有以下三種方法： （1）采用與處理區(qū)間標度變量相同的方法。 （2）對比例標度型變量進行對數(shù)變換，如： yif = log(xif) 然后再對變換得到的值按區(qū)間標度的值處理。 （3）將其作為連續(xù)的序數(shù)型數(shù)據(jù)，將其秩作為區(qū)間標度的值來對待。,比例標度型變量,寧夏大學數(shù)學與計算機學院,聚類分析中的數(shù)據(jù)類型,寧夏大學數(shù)學與計算機學院,聚類分析中數(shù)據(jù)

8、類型用于度量對象間的相異度，常用的數(shù)據(jù)類型: 區(qū)間標度變量 二元變量 標稱型、序數(shù)型和比例標度型變量 混合類型變量,在許多現(xiàn)實的數(shù)據(jù)庫中，對象是被混合類型的變量描述的。一般來說，一個數(shù)據(jù)庫可能包含上面列出的全部六種變量類型。用以下的公式計算i和j的相異度： 其中，p為對象中的變量個數(shù) （1）如果xif或xjf缺失（即對象i或?qū)ο骿沒有變量f的值），或者xif = xjf =0，且變量f是不對稱的二元變量，則指示項ij(f)=0；否則ij(f)=1。 （2）f 是二元變量或標稱變量: if xif = xjf dij(f) = 0, else dij(f) = 1 （3）f是區(qū)間標度變量：dij

9、(f) = | xif-xjf |/maxhxhf-minhxhf （4）f 是序數(shù)型或比例標度型： 計算秩rif 計算zif并將其作為區(qū)間標度變量值對待,混合類型變量,寧夏大學數(shù)學與計算機學院,基于劃分的方法 基于層次的方法 基于密度的方法 基于網(wǎng)格的方法 基于模型的方法,主要聚類分析方法,寧夏大學數(shù)學與計算機學院,劃分方法（partitioning method）的基本思想是：給定一個n個對象或元組的數(shù)據(jù)庫，一個劃分方法構(gòu)建數(shù)據(jù)的k個劃分，每個劃分表示一個聚簇，并且kn。也就是說，它將數(shù)據(jù)劃分成為k個組，同時滿足如下要求： 每個組至少包括一個對象； 每個對象必須屬于且只屬于一個組。 基于劃

10、分的聚類會要求窮舉所有可能的劃分。實際上，絕大多數(shù)應用采用了以下兩個比較流行的啟發(fā)式方式： （1）k-平均算法。在該算法當中，每個簇用該簇中對象的平均值來表示。 （2）k-中心點算法。在該算法中每個簇用接近聚類中心的一個對象來表示。,基于劃分的方法,寧夏大學數(shù)學與計算機學院,層次方法（hierarchical method）的基本思想是：對給定數(shù)據(jù)對象集合進行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以分為凝聚的和分裂的。 （1）凝聚的方法：又稱為自底向上的方法，一開始將每個對象作為單獨的一個組，然后根據(jù)一些規(guī)則相繼地合并相近的對象或者組，將它們聚合成越來越大的類，直到所有的組合并為一個

11、，或者達到一個預先設定的終止條件。,基于層次的方法,寧夏大學數(shù)學與計算機學院,（2）分裂的方法：又稱為自頂向下的方法，是一個與凝聚的方式相反的過程。即開始時將所有的對象置于一個簇中。在迭代的每一步中，一個簇被分裂為更小的簇，直到最終每個對象在單獨的一個簇中，或者達到一個終止條件（例如：類的數(shù)目到了預定值，最近的兩個類之間的最小距離大于設定值等）。,基于層次的方法,寧夏大學數(shù)學與計算機學院,絕大多數(shù)劃分方法基于對象之間的距離進行聚類。這樣的方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難。隨之提出了基于密度的聚類方法（density-based method）。 基本思想是：只要臨近區(qū)域的

12、密度（對象或數(shù)據(jù)點的數(shù)目）超過某個值，就繼續(xù)聚類。也就是說，對給定類中的每個數(shù)據(jù)點，在一個給定范圍的區(qū)域中必須至少包含某個數(shù)目點。這樣的方法可以用來過濾“噪聲”孤立點數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。,基于密度的方法,寧夏大學數(shù)學與計算機學院,基于網(wǎng)格的方法（grid-based method）的基本思想是：對象空間量化為有限數(shù)目的單元，形成了一個網(wǎng)格結(jié)構(gòu)。所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)上進行。這種方法的主要優(yōu)點是它的處理速度較快，其處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維單元數(shù)目有關(guān)。,基于網(wǎng)格的方法,寧夏大學數(shù)學與計算機學院,基本思想是：為每個簇假定了一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合

13、。一個基于模型的算法可能通過構(gòu)建反映數(shù)據(jù)點空間分布的密度函數(shù)來定位聚類。它也是基于標準的統(tǒng)計數(shù)字自動決定聚類的數(shù)目，考慮“噪聲”數(shù)據(jù)或孤立點，從而產(chǎn)生健壯的聚類方法。,基于模型的方法,寧夏大學數(shù)學與計算機學院,k-means算法，也被稱為k-平均或k-均值，是一種得到最廣泛使用的聚類算法。 它是將各個聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點，算法的主要思想是通過迭代過程把數(shù)據(jù)集劃分為不同的類別，使得評價聚類性能的準則函數(shù)達到最優(yōu)，從而使生成的每個聚類內(nèi)緊湊，類間獨立。,k-means算法,寧夏大學數(shù)學與計算機學院,（1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量 例如歐式距離： （2）選擇

14、評價聚類性能的準則函數(shù) 誤差平方和準則函數(shù)為： （3）相似度的計算根據(jù)一個簇中對象的平均值來進行。,k-means算法三個要點,寧夏大學數(shù)學與計算機學院,輸入：簇的數(shù)目k和包含n個對象的數(shù)據(jù)庫。 輸出：k個簇，使平方誤差準則最小。 算法步驟： 1.為每個聚類確定一個初始聚類中心，這樣就有K 個初始聚類中心。 2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類 3.使用每個聚類中的樣本均值作為新的聚類中心。 4.重復步驟2.3步直到聚類中心不再變化。 5.結(jié)束，得到K個聚類,k-means算法流程,寧夏大學數(shù)學與計算機學院,主要優(yōu)點： 是解決聚類問題的一種經(jīng)典算法，簡單、快速。 對處理大數(shù)據(jù)集

15、，該算法是相對可伸縮和高效率的。因為它的復雜度是0 (n k t ) , 其中, n 是所有對象的數(shù)目, k 是簇的數(shù)目, t 是迭代的次數(shù)。通常k n 且t n 。 當結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時, 它的效果較好。,k-means算法性能分析,寧夏大學數(shù)學與計算機學院,主要缺點 在簇的平均值被定義的情況下才能使用，這對于處理符號屬性的數(shù)據(jù)不適用。 必須事先給出k（要生成的簇的數(shù)目），而且對初值敏感，對于不同的初始值，可能會導致不同結(jié)果。 它對于“躁聲”和孤立點數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。,k-means算法性能分析,寧夏大學數(shù)學與計算機學院,k-means算法對某類簇中所有的樣本點維度求平均值，即獲得該類簇質(zhì)點的維度。當聚類的樣本點中有“噪聲”（離群點）時，在計算類簇質(zhì)點的過程中會受到噪聲異常維度的干擾，造成所得質(zhì)點和實際質(zhì)點位置偏差過大，從而使類簇發(fā)生“畸變”。 為了解決該問題，K中心點算法（K-medoids）提出了新的質(zhì)點選取方式，而不是簡單像k-means算法采用均值計算法。在K中心點算法中，每次迭代后的質(zhì)點都是從聚類的樣本點中選取，而選取的標準就是當該樣本點成為新的質(zhì)點后能提高類簇的聚類質(zhì)量，使得類簇更緊湊。該算法使用絕對誤差標準來定義一個