聚類分析算法學習報告課件

聚類分析算法——學習匯報聚類分析算法1聚類分析概述寧夏大學·數(shù)學與計算機學院

1、什么是聚類？

聚類（clustering）是將物理或抽象對象的集合分組成為多個類或簇（cluster）的過程，使得在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。

2、與分類的不同

它要劃分的類是未知的。即聚類是一種無指導學習，它不依賴預(yù)先定義的類和帶類標號的訓練實例。聚類分析概述寧夏大學·數(shù)學與計算機學院2聚類分析的應(yīng)用

聚類分析已經(jīng)廣泛的用在許多應(yīng)用中，包括模式識別、數(shù)據(jù)分析、圖像處理以及市場研究。典型的應(yīng)用：

（1）商業(yè)：幫助市場分析人員從客戶基本庫中發(fā)現(xiàn)不同的客戶群，并且用不同的購買模式描述不同客戶群的特征。

（2）生物學：推導植物或動物的分類，活的對種群固有結(jié)構(gòu)的認識。（3）WEB文檔分類（4）其他：地球觀測數(shù)據(jù)庫中相似地區(qū)的確定各類保險投保人的分組，一個城市中不同類型、價值、地理位置房子的分組等。（5）作為其他數(shù)據(jù)挖掘算法的預(yù)處理：即先進行聚類，然后再進行分類等其他數(shù)據(jù)挖掘

寧夏大學·數(shù)學與計算機學院聚類分析的應(yīng)用聚類分析已經(jīng)廣泛的用在許多應(yīng)用中，包括3聚類分析的要求寧夏大學·數(shù)學與計算機學院可伸縮性處理不同類型屬性的能力發(fā)現(xiàn)任意形狀的聚類

用于決定輸入?yún)?shù)的領(lǐng)域知識最小化

處理噪聲數(shù)據(jù)的能力

對于輸入記錄的順序不敏感高維性基于約束的聚類可解釋性和可用性聚類分析的要求寧夏大學·數(shù)學與計算機學院4聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院

聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:

區(qū)間標度變量二元變量標稱型、序數(shù)型和比例標度型變量混合類型變量聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院聚類分析中5區(qū)間標度變量

寧夏大學·數(shù)學與計算機學院1、

區(qū)間標度變量是一個粗略線性標度的連續(xù)度量。典型的例子包括重量和高度，經(jīng)度和緯度坐標，以及大氣溫度。

2、選擇不同的度量單位（如“米”與英尺、“千克”與“磅”等）將直接影響聚類分析的結(jié)果。

3、為了避免聚類分析對度量單位的依賴性，數(shù)據(jù)需要進行標準化。

4、怎樣將一個變量的數(shù)據(jù)標準化呢？為了實現(xiàn)度量值的標準化，一種方法是將原來的度量值轉(zhuǎn)換為無單位的值。區(qū)間標度變量寧夏大學·數(shù)學與計算機學院1、區(qū)間標度變6度量值的標準化

寧夏大學·數(shù)學與計算機學院

（1）計算平均的絕對偏差（meanabsolutedeviation）:其中：

（2）計算標準化的度量值，或（z-score）:

度量值的標準化寧夏大學·數(shù)學與計算機學院（1）計算平均7對象間的相異度計算歐幾里德距離：曼哈坦距離：明考斯基距離：

寧夏大學·數(shù)學與計算機學院對象間的相異度計算歐幾里德距離：寧夏大學·數(shù)學與計算機學院8聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院

聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:

區(qū)間標度變量二元變量標稱型、序數(shù)型和比例標度型變量混合類型變量聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院聚類分析中9二元變量寧夏大學·數(shù)學與計算機學院

一個二元變量只有兩個狀態(tài)：0或者1，0表示該變量為空，1表示該變量存在。

如果假設(shè)所有的二元變量有相同的權(quán)重，則得到一個兩行兩列的可能性表。在下面這個表中，a是對于對象i和j值都為1的變量的數(shù)目，b是對于對象I值為1而對象j的值為0的變量數(shù)目，s是對于對象c值為0而在對于對象j值為1的變量數(shù)目，d是對于對象i和j的值都為0的變量的數(shù)目。變量的總數(shù)是p，p=a+b+c+d。ObjectjObjecti二元變量寧夏大學·數(shù)學與計算機學院一個二元變量只有10

基于對稱二元變量的相似度稱為恒定的相似度，即當一些或者全部二元變量編碼改變時，計算結(jié)果不會發(fā)生變化。

如果二元變量的兩個狀態(tài)的輸出不是同樣重要，則該二元變量是不對稱的?；谶@樣變量的相似度被稱為非恒定的相似度。

二元變量相似度的計算寧夏大學·數(shù)學與計算機學院基于對稱二元變量的相似度稱為恒定的相似度，即當11聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院

聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:

區(qū)間標度變量二元變量標稱型、序數(shù)型和比例標度型變量混合類型變量聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院聚類分析中121、標稱型變量標稱變量（nominal）是二元變量的推廣，它可以具有多于兩個的狀態(tài)值。例如，map-color是一個標稱變量，它可能有五個狀態(tài)：紅色，黃色，綠色，粉紅色和藍色。兩個對象Ｉ和j之間的相異度可以用兩種方法來計算：

（1）簡單匹配方法M是匹配的數(shù)目，P是全部變量的數(shù)目（2）使用二元變量為每一個狀態(tài)創(chuàng)建一個新的二元變量，可以用非對稱的二元變量來編碼標稱變量。標稱型變量寧夏大學·數(shù)學與計算機學院1、標稱型變量標稱型變量寧夏大學·數(shù)學與計算機13

一個離散的序數(shù)（ordinal）型變量類似于標稱變量，除了序數(shù)型變量的Ｍ個狀態(tài)是以有意義的序列排序的。在計算對象的相異度時，序數(shù)型變量的處理與區(qū)間標度變量非常類似。

（1）將xif用它對應(yīng)的秩代替。（2）將每個變量的值域映射到[0.0，1.0]上，使得每個變量都有相同的權(quán)重。這通過用zif來替代rif來實現(xiàn)。

（3）用前面所述的區(qū)間標度變量的任一種距離計算方法來計算。序數(shù)型變量寧夏大學·數(shù)學與計算機學院一個離散的序數(shù)（ordinal）型變量類似于標稱變量，14

用比例標度型變量描述對象之間相異度有以下三種方法：（1）采用與處理區(qū)間標度變量相同的方法。（2）對比例標度型變量進行對數(shù)變換，如：

yif=log(xif)然后再對變換得到的值按區(qū)間標度的值處理。（3）將其作為連續(xù)的序數(shù)型數(shù)據(jù)，將其秩作為區(qū)間標度的值來對待。比例標度型變量寧夏大學·數(shù)學與計算機學院用比例標度型變量描述對象之間相異度有以下三種方法：比例15聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院

聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:

區(qū)間標度變量二元變量標稱型、序數(shù)型和比例標度型變量混合類型變量聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院聚類分析中16

在許多現(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是二元變量或標稱變量:ifxif=xjfdij(f)=0,elsedij(f)=1

（3）f是區(qū)間標度變量：dij(f)=|xif-xjf|/maxhxhf-minhxhf（4）f是序數(shù)型或比例標度型：計算秩rif 計算zif并將其作為區(qū)間標度變量值對待混合類型變量寧夏大學·數(shù)學與計算機學院在許多現(xiàn)實的數(shù)據(jù)庫中，對象是被混合類型的變量描述的。一17基于劃分的方法基于層次的方法基于密度的方法基于網(wǎng)格的方法基于模型的方法

主要聚類分析方法寧夏大學·數(shù)學與計算機學院主要聚類分析方法寧夏大學·數(shù)學與計算機學院18

劃分方法（partitioningmethod）的基本思想是：給定一個n個對象或元組的數(shù)據(jù)庫，一個劃分方法構(gòu)建數(shù)據(jù)的k個劃分，每個劃分表示一個聚簇，并且k<n。也就是說，它將數(shù)據(jù)劃分成為k個組，同時滿足如下要求：每個組至少包括一個對象；每個對象必須屬于且只屬于一個組?；趧澐值木垲悤蟾F舉所有可能的劃分。實際上，絕大多數(shù)應(yīng)用采用了以下兩個比較流行的啟發(fā)式方式：（1）k-平均算法。在該算法當中，每個簇用該簇中對象的平均值來表示。（2）k-中心點算法。在該算法中每個簇用接近聚類中心的一個對象來表示。

基于劃分的方法寧夏大學·數(shù)學與計算機學院劃分方法（partitioningmet19

層次方法（hierarchicalmethod）的基本思想是：對給定數(shù)據(jù)對象集合進行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以分為凝聚的和分裂的。

（1）凝聚的方法：又稱為自底向上的方法，一開始將每個對象作為單獨的一個組，然后根據(jù)一些規(guī)則相繼地合并相近的對象或者組，將它們聚合成越來越大的類，直到所有的組合并為一個，或者達到一個預(yù)先設(shè)定的終止條件。

基于層次的方法寧夏大學·數(shù)學與計算機學院層次方法（hierarchicalmethod）的基20（2）分裂的方法：又稱為自頂向下的方法，是一個與凝聚的方式相反的過程。即開始時將所有的對象置于一個簇中。在迭代的每一步中，一個簇被分裂為更小的簇，直到最終每個對象在單獨的一個簇中，或者達到一個終止條件（例如：類的數(shù)目到了預(yù)定值，最近的兩個類之間的最小距離大于設(shè)定值等）。

基于層次的方法寧夏大學·數(shù)學與計算機學院基于層次的方法寧夏大學·數(shù)學與計算機學院21絕大多數(shù)劃分方法基于對象之間的距離進行聚類。這樣的方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難。隨之提出了基于密度的聚類方法（density-basedmethod）?；舅枷胧牵褐灰R近區(qū)域的密度（對象或數(shù)據(jù)點的數(shù)目）超過某個值，就繼續(xù)聚類。也就是說，對給定類中的每個數(shù)據(jù)點，在一個給定范圍的區(qū)域中必須至少包含某個數(shù)目點。這樣的方法可以用來過濾“噪聲”孤立點數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇?；诿芏鹊姆椒▽幭拇髮W·數(shù)學與計算機學院絕大多數(shù)劃分方法基于對象之間的距離進行聚類。這樣的22

基于網(wǎng)格的方法（grid-basedmethod）的基本思想是：對象空間量化為有限數(shù)目的單元，形成了一個網(wǎng)格結(jié)構(gòu)。所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)上進行。這種方法的主要優(yōu)點是它的處理速度較快，其處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維單元數(shù)目有關(guān)。基于網(wǎng)格的方法寧夏大學·數(shù)學與計算機學院基于網(wǎng)格的方法寧夏大學·數(shù)學與計算機學院23

基本思想是：為每個簇假定了一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合。一個基于模型的算法可能通過構(gòu)建反映數(shù)據(jù)點空間分布的密度函數(shù)來定位聚類。它也是基于標準的統(tǒng)計數(shù)字自動決定聚類的數(shù)目，考慮“噪聲”數(shù)據(jù)或孤立點，從而產(chǎn)生健壯的聚類方法?；谀Ｐ偷姆椒▽幭拇髮W·數(shù)學與計算機學院基于模型的方法寧夏大學·數(shù)學與計算機學院24

k-means算法，也被稱為k-平均或k-均值，是一種得到最廣泛使用的聚類算法。它是將各個聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點，算法的主要思想是通過迭代過程把數(shù)據(jù)集劃分為不同的類別，使得評價聚類性能的準則函數(shù)達到最優(yōu)，從而使生成的每個聚類內(nèi)緊湊，類間獨立。

k-means算法寧夏大學·數(shù)學與計算機學院k-means算法寧夏大學·數(shù)學與計算機學院25（1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量例如歐式距離：（2）選擇評價聚類性能的準則函數(shù)誤差平方和準則函數(shù)為：（3）相似度的計算根據(jù)一個簇中對象的平均值來進行。k-means算法三個要點寧夏大學·數(shù)學與計算機學院k-means算法三個要點寧夏大學·數(shù)學與計算機學院26輸入：簇的數(shù)目k和包含n個對象的數(shù)據(jù)庫。輸出：k個簇，使平方誤差準則最小。算法步驟：1.為每個聚類確定一個初始聚類中心，這樣就有K個初始聚類中心。2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類3.使用每個聚類中的樣本均值作為新的聚類中心。4.重復(fù)步驟2.3步直到聚類中心不再變化。5.結(jié)束，得到K個聚類

k-means算法流程寧夏大學·數(shù)學與計算機學院k-means算法流程寧夏大學·數(shù)學與計算機學院27主要優(yōu)點：是解決聚類問題的一種經(jīng)典算法，簡單、快速。對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。因為它的復(fù)雜度是0(nkt),其中,n是所有對象的數(shù)目,k是簇的數(shù)目,t是迭代的次數(shù)。通常k<<n且t<<n。當結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時,它的效果較好。k-means算法性能分析寧夏大學·數(shù)學與計算機學院k-means算法性能分析寧夏大學·數(shù)學與計算機學院28主要缺點在簇的平均值被定義的情況下才能使用，這對于處理符號屬性的數(shù)據(jù)不適用。必須事先給出k（要生成的簇的數(shù)目），而且對初值敏感，對于不同的初始值，可能會導致不同結(jié)果。它對于“躁聲”和孤立點數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。k-means算法性能分析寧夏大學·數(shù)學與計算機學院k-means算法性能分析寧夏大學·數(shù)學與計算機學院29

k-means算法對某類簇中所有的樣本點維度求平均值，即獲得該類簇質(zhì)點的維度。當聚類的樣本點中有“噪聲”（離群點）時，在計算類簇質(zhì)點的過程中會受到噪聲異常維度的干擾，造成所得質(zhì)點和實際質(zhì)點位置偏差過大，從而使類簇發(fā)生“畸變”。為了解決該問題，K中心點算法（K-medoids）提出了新的質(zhì)點選取方式，而不是簡單像k-means算法采用均值計算法。在K中心點算法中，每次迭代后的質(zhì)點都是從聚類的樣本點中選取，而選取的標準就是當該樣本點成為新的質(zhì)點后能提高類簇的聚類質(zhì)量，使得類簇更緊湊。該算法使用絕對誤差標準來定義一個類簇的緊湊程度。

K-中心點算法寧夏大學·數(shù)學與計算機學院k-means算法對某類簇中所有的樣本點維度求平均值，30輸入：結(jié)果簇的數(shù)目K，包含N個對象的數(shù)據(jù)庫。輸出：K個簇，使得所有對象與其最近中心點的相異度總和最小。方法：隨機選擇K個對象作為初始的中心點。REPEAT指派每個剩余的對象給離它最近的中心點所代表的簇。隨機地選擇一個非中心點對象Orandom；計算用Orandom代替Oj的總代價S；ifS<0,thenOrandom代替Oj,形成新的K個中心點的集合；until不發(fā)生變化；

K-中心點算法寧夏大學·數(shù)學與計算機學院K-中心點算法寧夏大學·數(shù)學與計算機學院31聚類分析算法——學習匯報聚類分析算法32聚類分析概述寧夏大學·數(shù)學與計算機學院

1、什么是聚類？

聚類（clustering）是將物理或抽象對象的集合分組成為多個類或簇（cluster）的過程，使得在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。

2、與分類的不同

它要劃分的類是未知的。即聚類是一種無指導學習，它不依賴預(yù)先定義的類和帶類標號的訓練實例。聚類分析概述寧夏大學·數(shù)學與計算機學院33聚類分析的應(yīng)用

聚類分析已經(jīng)廣泛的用在許多應(yīng)用中，包括模式識別、數(shù)據(jù)分析、圖像處理以及市場研究。典型的應(yīng)用：

（1）商業(yè)：幫助市場分析人員從客戶基本庫中發(fā)現(xiàn)不同的客戶群，并且用不同的購買模式描述不同客戶群的特征。

（2）生物學：推導植物或動物的分類，活的對種群固有結(jié)構(gòu)的認識。（3）WEB文檔分類（4）其他：地球觀測數(shù)據(jù)庫中相似地區(qū)的確定各類保險投保人的分組，一個城市中不同類型、價值、地理位置房子的分組等。（5）作為其他數(shù)據(jù)挖掘算法的預(yù)處理：即先進行聚類，然后再進行分類等其他數(shù)據(jù)挖掘

寧夏大學·數(shù)學與計算機學院聚類分析的應(yīng)用聚類分析已經(jīng)廣泛的用在許多應(yīng)用中，包括34聚類分析的要求寧夏大學·數(shù)學與計算機學院可伸縮性處理不同類型屬性的能力發(fā)現(xiàn)任意形狀的聚類

用于決定輸入?yún)?shù)的領(lǐng)域知識最小化

處理噪聲數(shù)據(jù)的能力

對于輸入記錄的順序不敏感高維性基于約束的聚類可解釋性和可用性聚類分析的要求寧夏大學·數(shù)學與計算機學院35聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院

聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:

區(qū)間標度變量二元變量標稱型、序數(shù)型和比例標度型變量混合類型變量聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院聚類分析中36區(qū)間標度變量

寧夏大學·數(shù)學與計算機學院1、

區(qū)間標度變量是一個粗略線性標度的連續(xù)度量。典型的例子包括重量和高度，經(jīng)度和緯度坐標，以及大氣溫度。

2、選擇不同的度量單位（如“米”與英尺、“千克”與“磅”等）將直接影響聚類分析的結(jié)果。

3、為了避免聚類分析對度量單位的依賴性，數(shù)據(jù)需要進行標準化。

4、怎樣將一個變量的數(shù)據(jù)標準化呢？為了實現(xiàn)度量值的標準化，一種方法是將原來的度量值轉(zhuǎn)換為無單位的值。區(qū)間標度變量寧夏大學·數(shù)學與計算機學院1、區(qū)間標度變37度量值的標準化

寧夏大學·數(shù)學與計算機學院

（1）計算平均的絕對偏差（meanabsolutedeviation）:其中：

（2）計算標準化的度量值，或（z-score）:

度量值的標準化寧夏大學·數(shù)學與計算機學院（1）計算平均38對象間的相異度計算歐幾里德距離：曼哈坦距離：明考斯基距離：

寧夏大學·數(shù)學與計算機學院對象間的相異度計算歐幾里德距離：寧夏大學·數(shù)學與計算機學院39聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院

聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:

區(qū)間標度變量二元變量標稱型、序數(shù)型和比例標度型變量混合類型變量聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院聚類分析中40二元變量寧夏大學·數(shù)學與計算機學院

一個二元變量只有兩個狀態(tài)：0或者1，0表示該變量為空，1表示該變量存在。

如果假設(shè)所有的二元變量有相同的權(quán)重，則得到一個兩行兩列的可能性表。在下面這個表中，a是對于對象i和j值都為1的變量的數(shù)目，b是對于對象I值為1而對象j的值為0的變量數(shù)目，s是對于對象c值為0而在對于對象j值為1的變量數(shù)目，d是對于對象i和j的值都為0的變量的數(shù)目。變量的總數(shù)是p，p=a+b+c+d。ObjectjObjecti二元變量寧夏大學·數(shù)學與計算機學院一個二元變量只有41

基于對稱二元變量的相似度稱為恒定的相似度，即當一些或者全部二元變量編碼改變時，計算結(jié)果不會發(fā)生變化。

如果二元變量的兩個狀態(tài)的輸出不是同樣重要，則該二元變量是不對稱的?；谶@樣變量的相似度被稱為非恒定的相似度。

二元變量相似度的計算寧夏大學·數(shù)學與計算機學院基于對稱二元變量的相似度稱為恒定的相似度，即當42聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院

聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:

區(qū)間標度變量二元變量標稱型、序數(shù)型和比例標度型變量混合類型變量聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院聚類分析中431、標稱型變量標稱變量（nominal）是二元變量的推廣，它可以具有多于兩個的狀態(tài)值。例如，map-color是一個標稱變量，它可能有五個狀態(tài)：紅色，黃色，綠色，粉紅色和藍色。兩個對象Ｉ和j之間的相異度可以用兩種方法來計算：

（1）簡單匹配方法M是匹配的數(shù)目，P是全部變量的數(shù)目（2）使用二元變量為每一個狀態(tài)創(chuàng)建一個新的二元變量，可以用非對稱的二元變量來編碼標稱變量。標稱型變量寧夏大學·數(shù)學與計算機學院1、標稱型變量標稱型變量寧夏大學·數(shù)學與計算機44

一個離散的序數(shù)（ordinal）型變量類似于標稱變量，除了序數(shù)型變量的Ｍ個狀態(tài)是以有意義的序列排序的。在計算對象的相異度時，序數(shù)型變量的處理與區(qū)間標度變量非常類似。

（1）將xif用它對應(yīng)的秩代替。（2）將每個變量的值域映射到[0.0，1.0]上，使得每個變量都有相同的權(quán)重。這通過用zif來替代rif來實現(xiàn)。

（3）用前面所述的區(qū)間標度變量的任一種距離計算方法來計算。序數(shù)型變量寧夏大學·數(shù)學與計算機學院一個離散的序數(shù)（ordinal）型變量類似于標稱變量，45

用比例標度型變量描述對象之間相異度有以下三種方法：（1）采用與處理區(qū)間標度變量相同的方法。（2）對比例標度型變量進行對數(shù)變換，如：

yif=log(xif)然后再對變換得到的值按區(qū)間標度的值處理。（3）將其作為連續(xù)的序數(shù)型數(shù)據(jù)，將其秩作為區(qū)間標度的值來對待。比例標度型變量寧夏大學·數(shù)學與計算機學院用比例標度型變量描述對象之間相異度有以下三種方法：比例46聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院

聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:

區(qū)間標度變量二元變量標稱型、序數(shù)型和比例標度型變量混合類型變量聚類分析中的數(shù)據(jù)類型寧夏大學·數(shù)學與計算機學院聚類分析中47

在許多現(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是二元變量或標稱變量:ifxif=xjfdij(f)=0,elsedij(f)=1

（3）f是區(qū)間標度變量：dij(f)=|xif-xjf|/maxhxhf-minhxhf（4）f是序數(shù)型或比例標度型：計算秩rif 計算zif并將其作為區(qū)間標度變量值對待混合類型變量寧夏大學·數(shù)學與計算機學院在許多現(xiàn)實的數(shù)據(jù)庫中，對象是被混合類型的變量描述的。一48基于劃分的方法基于層次的方法基于密度的方法基于網(wǎng)格的方法基于模型的方法

主要聚類分析方法寧夏大學·數(shù)學與計算機學院主要聚類分析方法寧夏大學·數(shù)學與計算機學院49

劃分方法（partitioningmethod）的基本思想是：給定一個n個對象或元組的數(shù)據(jù)庫，一個劃分方法構(gòu)建數(shù)據(jù)的k個劃分，每個劃分表示一個聚簇，并且k<n。也就是說，它將數(shù)據(jù)劃分成為k個組，同時滿足如下要求：每個組至少包括一個對象；每個對象必須屬于且只屬于一個組?；趧澐值木垲悤蟾F舉所有可能的劃分。實際上，絕大多數(shù)應(yīng)用采用了以下兩個比較流行的啟發(fā)式方式：（1）k-平均算法。在該算法當中，每個簇用該簇中對象的平均值來表示。（2）k-中心點算法。在該算法中每個簇用接近聚類中心的一個對象來表示。

基于劃分的方法寧夏大學·數(shù)學與計算機學院劃分方法（partitioningmet50

層次方法（hierarchicalmethod）的基本思想是：對給定數(shù)據(jù)對象集合進行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以分為凝聚的和分裂的。

（1）凝聚的方法：又稱為自底向上的方法，一開始將每個對象作為單獨的一個組，然后根據(jù)一些規(guī)則相繼地合并相近的對象或者組，將它們聚合成越來越大的類，直到所有的組合并為一個，或者達到一個預(yù)先設(shè)定的終止條件。

基于層次的方法寧夏大學·數(shù)學與計算機學院層次方法（hierarchicalmethod）的基51（2）分裂的方法：又稱為自頂向下的方法，是一個與凝聚的方式相反的過程。即開始時將所有的對象置于一個簇中。在迭代的每一步中，一個簇被分裂為更小的簇，直到最終每個對象在單獨的一個簇中，或者達到一個終止條件（例如：類的數(shù)目到了預(yù)定值，最近的兩個類之間的最小距離大于設(shè)定值等）。

基于層次的方法寧夏大學·數(shù)學與計算機學院基于層次的方法寧夏大學·數(shù)學與計算機學院52絕大多數(shù)劃分方法基于對象之間的距離進行聚類。這樣的方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難。隨之提出了基于密度的聚類方法（density-basedmethod）?；舅枷胧牵褐灰R近區(qū)域的密度（對象或數(shù)據(jù)點的數(shù)目）超過某個值，就繼續(xù)聚類。也就是說，對給定類中的每個數(shù)據(jù)點，在一個給定范圍的區(qū)域中必須至少包含某個數(shù)目點。這樣的方法可以用來過濾“噪聲”孤立點數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇?；诿芏鹊姆椒▽幭拇髮W·數(shù)學與計算機學院絕大多數(shù)劃分方法基于對象之間的距離進行聚類。這樣的53

基于網(wǎng)格的方法（grid-basedmethod）的基本思想是：對象空間量化為有限數(shù)目的單元，形成了一個網(wǎng)格結(jié)構(gòu)。所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)上進行。這種方法的主要優(yōu)點是它的處理速度較快，其處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維單元數(shù)目有關(guān)?；诰W(wǎng)格的方法寧夏大學·數(shù)學與計算機學院基于網(wǎng)格的方法寧夏大學·數(shù)學與計算機學院54

基本思想是：為每個簇假定了一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合。一個基于模型的算法可能通過構(gòu)建反映數(shù)據(jù)點空間分布的密度函數(shù)來定位聚類。它也是基于標準的統(tǒng)計數(shù)字自動決定聚類的數(shù)目，考慮“噪聲”數(shù)據(jù)或孤立點，從而產(chǎn)生健壯的聚類方法。基于模型的方法寧夏大學·數(shù)學與計算機學院基于模型的方法寧夏大學·數(shù)學與計算機學院55

k-means算法，也被稱為k-平均或k-均值，是一種得到最廣泛使用的聚類算法。它是將各個聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點，算法的主要思想是通過迭代過程把數(shù)據(jù)集劃分為不同的類別，使得評價聚類性能的準則函數(shù)達到最優(yōu)，從而使生成的每個聚類內(nèi)緊湊，類間獨立。

k-means算法寧夏大學·數(shù)學與計算機學院k-means算法寧夏大學·數(shù)學與計算機學院56（1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量