1、第五章 聚類分析2022/7/29 The Institute of Business Intelligence, HFUT2/104內容提綱 1. 分類分析2. 聚類分析3. 關聯分析聚類聚類（Clustering）就是將對象集合分成為多個類（Cluster）的過程。聚類分析是一種重要的人類活動。早在孩提時代，人就通過不斷改進下意識中的聚類模式來學會如何區分貓和狗，動物和植物。2022/7/29 The Institute of Business Intelligence, HFUT3/104聚類分析無處不在如果你是一個淘寶店鋪的老板誰經常光顧店鋪，誰買什么東西，買多少？按消費者的性別、年齡

2、、職業、瀏覽次數、瀏覽時間、購物種類、金額等變量對消費者進行聚類這樣淘寶店鋪可以識別顧客購買模式（如哪些人喜歡周末時一次性大采購）需要針對不同的人群，制定不同的關系管理方式，以提高客戶對公司商業活動的響應率。2022/7/29 The Institute of Business Intelligence, HFUT4/104如果你是銀行的客戶經理利用儲蓄額、刷卡消費金額、刷卡次數、誠信度等變量對客戶聚類，找出誰是銀行信用卡的黃金客戶、誰是容易流失的客戶這樣銀行可以制定更吸引的服務，留住客戶！比如：一定額度和期限的免息透資服務！百盛的貴賓打折卡！在他或她生日的時候送上一個小蛋糕！2022/7/2

3、9 The Institute of Business Intelligence, HFUT5/104聚類分析無處不在如果你是社會性網站的站長把每個用戶想象成圖中的一個節點，如果用戶A對用戶B有互動行為(轉發，評論等)，在用戶A和用戶B之間建立一條有向邊這樣網站可以基于用戶的互動信息，構建用戶興趣的挖掘算法。發現網站中具有相同興趣的用戶群體2022/7/29 The Institute of Business Intelligence, HFUT6/104聚類分析無處不在聚類分析原理引例我們看看以下的例子：有16張牌如何將他們分為一組一組的牌呢？AKQJ2022/7/29 The Instit

4、ute of Business Intelligence, HFUT7/104分成四組每組里花色相同組與組之間花色相異AKQJ花色相同的牌為一副2022/7/29 The Institute of Business Intelligence, HFUT8/104聚類分析原理引例分成四組符號相同的牌為一組AKQJ符號相同的的牌2022/7/29 The Institute of Business Intelligence, HFUT9/104聚類分析原理引例分成兩組顏色相同的牌為一組AKQJ顏色相同的配對2022/7/29 The Institute of Business Intelligen

5、ce, HFUT10/104聚類分析原理引例分成兩組大小相近的牌為一組大配對和小配對AKQJ2022/7/29 The Institute of Business Intelligence, HFUT11/104聚類分析原理引例聚類分析基本過程基本過程選擇合理的相似度計算方法計算個體之間的距離或相似度，構建距離矩陣或相似度矩陣基于相似性，采取某種聚類方法進行聚類對不同類別的對象特征進行分析基本原則類內對象相似性盡可能大，類間對象相似性盡可能小2022/7/29 The Institute of Business Intelligence, HFUT12/1042022/7/29 The Ins

6、titute of Business Intelligence, HFUT13/104聚類分析基本過程顧客id 訂單規模 訂單金額 點擊量c1 11.550c2 16.540c3 1.5225c4 4.57.575c5 48.520c6 5.5930c7 4.58552022/7/29 The Institute of Business Intelligence, HFUT14/104聚類分析基本過程距離計算連續型屬性歐氏距離（Euclidean distance）曼哈頓距離（Manhattan distance）明考斯基距離（Minkowski distance） 2022/7/29 The

7、 Institute of Business Intelligence, HFUT15/104顧客id 訂單規模 訂單金額 點擊量c1 11.550c2 5.5955c3 58.540c4 4.57.575c5 48.520c6 3.5930c7 26.540距離10.0715.0235.0255.0110.0210.422022/7/29 The Institute of Business Intelligence, HFUT16/104距離計算連續型屬性選用的度量單位直接影響聚類分析的結果，因此需要實現度量值的標準化，將原來的值轉化為無單位的值，給定一個變量f的度量值，可使用以下方法進行標

8、準化：最大-最小值方法z-score方法變量指數法距離計算連續型屬性標準化2022/7/29 The Institute of Business Intelligence, HFUT17/104a=(a-min)/(max-min)連續型屬性標準化最大-最小值方法顧客id 訂單規模 訂單金額 點擊量c1 11.550c2 5.5955c3 58.540c4 4.57.575c5 48.520c6 3.5930c7 26.540Max5.5975Min11.520訂單規模 訂單金額 點擊量0.00 0.00 0.55 1.00 1.00 0.64 0.89 0.93 0.36 0.78 0.80

9、 1.00 0.67 0.93 0.00 0.56 1.00 0.18 0.22 0.67 0.36 2022/7/29 The Institute of Business Intelligence, HFUT18/104距離計算連續型屬性顧客id 訂單規模 訂單金額 點擊量c1 0.00 0.00 0.55 c2 1.00 1.00 0.64 c3 0.89 0.93 0.36 c4 0.78 0.80 1.00 c5 0.67 0.93 0.00 c6 0.56 1.00 0.18 c7 0.22 0.67 0.36 距離1.42 0.30 0.66 1.01 0.22 0.51 距離10

10、.0715.0235.0255.0110.0210.422022/7/29 The Institute of Business Intelligence, HFUT19/104計算均值絕對偏差其中計算標準化的度量值(z-score)連續型屬性標準化z-score方法2022/7/29 The Institute of Business Intelligence, HFUT20/104顧客id 訂單規模 訂單金額 點擊量c1 11.550c2 5.5955c3 58.540c4 4.57.575c5 48.520c6 3.5930c7 26.540mf3.64 7.21 44.29 sf1.27

11、1.8413.47顧客id 訂單規模 訂單金額 點擊量c1 -2.09 -3.11 0.42 c2 1.47 0.97 0.80 c3 1.07 0.70 -0.32 c4 0.68 0.16 2.28 c5 0.28 0.70 -1.80 c6 -0.11 0.97 -1.06 c7 -1.30 -0.39 -0.32 2022/7/29 The Institute of Business Intelligence, HFUT21/104距離計算連續型屬性顧客id 訂單規模 訂單金額 點擊量c1 -2.09 -3.11 0.42 c2 1.47 0.97 0.80 c3 1.07 0.70

12、-0.32 c4 0.68 0.16 2.28 c5 0.28 0.70 -1.80 c6 -0.11 0.97 -1.06 c7 -1.30 -0.39 -0.32 距離5.43 1.21 2.68 4.14 0.88 1.95 距離1.42 0.30 0.66 1.01 0.22 0.51 距離10.0715.0235.0255.0110.0210.422022/7/29 The Institute of Business Intelligence, HFUT22/104變量指數法把屬性值除以該屬性所有取值的均值顧客id 訂單規模 訂單金額 點擊量c1 11.550c2 5.5955c3

13、58.540c4 4.57.575c5 48.520c6 3.5930c7 26.540均值3.64 7.21 44.29 顧客id 訂單規模 訂單金額 點擊量c1 0.27 0.21 1.13 c2 1.51 1.25 1.24 c3 1.37 1.18 0.90 c4 1.24 1.04 1.69 c5 1.10 1.18 0.45 c6 0.96 1.25 0.68 c7 0.55 0.90 0.90 2022/7/29 The Institute of Business Intelligence, HFUT23/104距離計算離散型屬性屬性值的個數是有限的，如性別、學歷、職業等二元變量

14、標稱變量序數變量2022/7/29 The Institute of Business Intelligence, HFUT24/104距離計算離散型屬性二元變量變量取值只有兩種狀態，0或1。二元變量分為對稱二元變量和非對稱二元變量顧客id 性別已婚E71 手機電池 不滿意投訴退貨取消訂單c1 10111010c2 00011010c3 00001100c4 11110000c5 00101110c6 01010001c7 111100002022/7/29 The Institute of Business Intelligence, HFUT25/104二元變量對稱的如果一個二元變量的兩個

15、狀態是同等價值的，且發生具有相似的概率，則可以任取其中一種狀態編碼為1或者0。對于對稱的二元變量，采用簡單匹配系數來評價兩個對象之間的相異度Object id(1,2)=0.5顧客id 性別已婚E71 手機電池 c1 1011c2 0001Object j2022/7/29 The Institute of Business Intelligence, HFUT26/104非對稱的 如果變量的兩個狀態不是同樣重要的，則稱該變量是不對稱的。將比較重要通常也是出現概率比較小的狀態編碼為1，將另一種狀態編碼為0。對于非對稱的二元變量，采用Jaccard系數來評價兩個對象之間的相異度2022/7/29

16、 The Institute of Business Intelligence, HFUT27/104二元變量二元變量的相異度計算gender 是一個對稱的二元變量其它的都是非對稱的二元變量，根據Jaccard系數計算得：NameGenderFeverCoughTest-1Test-2Test-3Test-4JackM101000MaryF101010JimM1100002022/7/29 The Institute of Business Intelligence, HFUT28/104標稱變量（Nominal Variables）標稱變量是二元變量的推廣，它可以具有多于兩個的狀態，比如 變

17、量“學歷”可以有研究生、本科、本科以下等多種狀態。有兩種計算相異度的方法：方法1: 簡單匹配方法m是匹配的數目, p是全部變量的數目方法2: 使用二元變量為每一個狀態創建一個新的二元變量，可以用非對稱的二元變量來編碼標稱變量。2022/7/29 The Institute of Business Intelligence, HFUT29/104顧客id 學歷職業 城市c1 本科公務員合肥c2 研究生公務員合肥c3 本科教師六安c4 本科以下程序員安慶c5 研究生教師六安c6 本科程序員安慶c7 研究生程序員蚌埠d(1,2)=1/3d(2,3)=3/32022/7/29 The Institut

18、e of Business Intelligence, HFUT30/104標稱變量（Nominal Variables）顧客id 學歷職業 城市c1 本科公務員合肥c2 研究生公務員合肥c3 本科教師六安顧客id 本科研究生 公務員教師合肥六安c1 101010c2 011010c3 1001012022/7/29 The Institute of Business Intelligence, HFUT31/104標稱變量（Nominal Variables）相似度計算交易ID產品1相機包，手機屏幕貼膜，濾鏡2鍵盤保護膜，遙控器，濾鏡相機包手機屏幕貼膜濾鏡鍵盤保護膜遙控器X111100X20

19、01112022/7/29 The Institute of Business Intelligence, HFUT32/104聚類算法1. 劃分聚類方法2. 層次聚類方法3. 密度聚類方法2022/7/29 The Institute of Business Intelligence, HFUT33/104實例顏色體形毛型類別1黑大卷毛危險2棕大光滑危險3棕中卷毛不危險4黑小卷毛不危險5棕中光滑危險6黑大光滑危險7棕小卷毛危險8棕小光滑不危險9棕大卷毛危險10黑中卷毛不危險11黑中光滑不危險12黑小光滑不危險實例顏色體形毛型1黑大卷毛2棕大光滑3棕中卷毛4黑小卷毛5棕中光滑6黑大光滑7棕小卷

20、毛8棕小光滑9棕大卷毛10黑中卷毛11黑中光滑12黑小光滑2022/7/29 The Institute of Business Intelligence, HFUT34/104劃分聚類方法給定一個有n個對象的數據集X，劃分聚類技術將構造k個類，k n，這k個類滿足下列條件：每一個類至少包含一個對象。所有類的并集等于X。任意兩個類的交集為空。每一個對象屬于且僅屬于一個類。最經典的劃分算法：k-mean算法2022/7/29 The Institute of Business Intelligence, HFUT35/104k-means算法，也被稱為k-平均或k-均值算法，是一種使用最廣泛的聚

21、類算法。根據個體到每個類中心的距離進行劃分，而類的中心用類中所有個體的均值來度量。1. Set k as an integer. 2. Select k distinct records as initial means, each representing a cluster.3. For each record in data, calculate the squared Euclidean distances between it and the means. Assign the record to the cluster whose mean is the nearest to th

22、e record.4. After all records are assigned to a cluster, calculate the new mean for each cluster as the average of all records in the cluster.5. If the new means equal to the previous means, stop, otherwise, go to Step 2.K-means算法2022/7/29 The Institute of Business Intelligence, HFUT36/104K-means聚類示

23、例2022/7/29 The Institute of Business Intelligence, HFUT37/104輸入：類的數目k和包含n個對象的數據庫。輸出：k個類，使平方誤差準則最小。(1)assign initial value for means; /*任意選擇k個對象作為初始的類中心*/(2) REPEAT(3) FOR j=1 to n DO assign each xj to the closest clusters;(4) FOR i=1 to k DO / *更新類平均值*/ Compute /*計算準則函數E*/(6) UNTIL E不再明顯地發生變化。k-mean

24、s算法偽代碼2022/7/29 The Institute of Business Intelligence, HFUT38/104實例根據下表數據實施k-means (k=2)聚類個體12345678屬性112124545屬性2112233442022/7/29 The Institute of Business Intelligence, HFUT39/104迭代 平均值平均值 產生的新類新平均值 新平均值次數 （類1） （類2）（類1） （類2）1 （1，1） （1，2）234個體12345678屬性112124545屬性2112233442022/7/29 The Institute

25、of Business Intelligence, HFUT40/104根據下表數據實施k-means (k=2)聚類實例迭代 平均值 平均值 產生的新類 新平均值 新平均值次數 （類1） （類2） （類1） （類2）1 （1，1） （1，2） 1，2，3，4，5，6，7，8 （1.5，1） （3.5，3）第一次迭代：假定隨機選擇的兩個對象，如序號1和序號3當作初始點，分別找到離兩點最近的對象，并產生兩個類1，2和3，4，5，6，7，8。對于產生的類分別計算平均值，得到平均值點。對于1，2，平均值點為（1.5，1）；對于3，4，5，6，7，8，平均值點為（3.5，3）。實例第二次迭代：通過平均

26、值調整對象的所在的類，重新聚類，即將所有點按離平均值點（1.5，1）、（3.5，3）最近的原則重新分配。得到兩個新的類：1，2，3，4和5，6，7，8。重新計算類平均值點，得到新的平均值點為（1.5，1.5）和（4.5，3.5）。實例迭代 平均值 平均值 產生的新類 新平均值 新平均值次數 （類1） （類2） （類1） （類2）1 （1，1） （1，2） 1，2，3，4，5，6，7，8 （1.5，1） （3.5，3）2 （1.5，1） （3.5，3） 1，2，3，4，5，6，7，8 （1.5，1.5） （4.5，3.5）第三次迭代：將所有點按離平均值點（1.5，1.5）和（4.5，3.5）最近

27、的原則重新分配，調整對象，類仍然為1，2，3，4和5，6，7，8，發現沒有出現重新分配，而且準則函數收斂，程序結束。實例迭代 平均值 平均值 產生的新類 新平均值 新平均值次數 （類1） （類2） （類1） （類2）1 （1，1） （1，2） 1，2，3，4，5，6，7，8 （1.5，1） （3.5，3） （1.5，1） （3.5，3） 1，2，3，4，5，6，7，8 （1.5，1.5） （4.5，3.5）3 （1.5，1.5）（4.5，3.5） 1，2，3，4，5，6，7，8 （1.5，1.5） （4.5，3.5）2022/7/29 The Institute of Business Int

28、elligence, HFUT44/104實例2022/7/29 The Institute of Business Intelligence, HFUT45/104練 習 Suppose that the data mining task is to cluster the following eight points (with (x, y) representing location) into three clusters: A1(2, 10), A2(2, 5), A3(8, 4), B1(5, 8), B2(7, 5), B3(6, 4), C1(1, 2), C2(4, 9):

29、The distance function is Euclidean distance. Suppose initially we assign A1, B1, and C1as the center of each cluster, respectively. Use the k-means algorithm to show only (a) The three cluster centers after the first round execution (b) The final three clustersk-means算法的性能分析主要優點：是解決聚類問題的一種經典算法，簡單、快速

30、。對處理大數據集，該算法是相對可伸縮和高效率的。當數據比較密集時，它的效果較好。主要缺點：在類的平均值被定義的情況下才能使用，可能不適用于某些應用。必須事先給出k（要生成的類的數目），而且對初值敏感，對于不同的初始值，可能會導致不同結果。不適合于發現非凸面形狀的類或者大小差別很大的類。而且，它對于“躁聲”和孤立點數據是敏感的。2022/7/29 The Institute of Business Intelligence, HFUT46/104k-means算法局限非球形的類2022/7/29 The Institute of Business Intelligence, HFUT47/104

31、2022/7/29 The Institute of Business Intelligence, HFUT48/104k-means算法局限k-means算法的幾種改進方法k-mode 算法：實現對離散數據的快速聚類，保留了k-means算法的效率同時將k-means的應用范圍擴大到離散數據。k-prototype算法：可以對離散與數值屬性兩種混合的數據進行聚類，在k-prototype中定義了一個對數值與離散屬性都計算的相異性度量標準。2022/7/29 The Institute of Business Intelligence, HFUT49/104k-modes算法 k-modes算

32、法把k-means算法擴展到可分類數據，定義了新的度量可分類數據相異度的距離公式，并給出相應的更新聚類中心的方式，能夠迅速處理可分類型數據。與k-means算法的區別k-modes算法改變了k-means算法的相異度測量方法，用一個簡單的相異度測量對數據進行聚類。假設X，Y是數據集中的兩個對象，它們用m維屬性描述，則這兩個對象之間的相異度為： 2022/7/29 The Institute of Business Intelligence, HFUT50/104與k-means算法的區別針對每一個屬性，取每個類別中出現頻率最大的一個屬性值作為該類別中心點的對應屬性值。顧客id年齡收入月消費金額

33、c1老年高低c2青年高低c3青年低中c4中年中中c5中年低中c6青年高高c7中年高高顧客id年齡收入月消費金額c11.00 0.80 0.00 c20.12 0.63 0.40 c30.00 0.00 0.50 c40.47 0.20 0.45 c50.26 0.07 0.55 c60.09 0.57 1.00 c70.38 1.00 0.90 2022/7/29 The Institute of Business Intelligence, HFUT51/104k-modes算法 k-prototypes算法 在實際應用中，數據可能是數值型的，同時也有可分類型的。k-prototypes算法

34、綜合了k-means和k-modes算法，采用新的距離度量方法，能夠快速處理混合類型數據集的聚類問題。k-prototypes算法的聚類中心由數值型數據的聚類中心和可分類數據的聚類中心兩部分加權組成，其中數值型屬性的聚類中心和k-means算法類似，通過計算數值型屬性的平均值得到。而可分類型屬性的中心采用類似k-modes算法聚類中心的更新方式，通過計算可分類屬性值出現的頻率確定。2022/7/29 The Institute of Business Intelligence, HFUT52/104顧客id年齡收入月消費金額學歷職業 c11.00 0.80 0.00 本科公務員c20.12 0

35、.63 0.40 研究生公務員c30.00 0.00 0.50 本科教師c40.47 0.20 0.45 本科以下程序員c50.26 0.07 0.55 研究生教師c60.09 0.57 1.00 本科程序員c70.38 1.00 0.90 研究生程序員2022/7/29 The Institute of Business Intelligence, HFUT53/104k-prototypes算法 k-中心點算法也稱PAM算法（Partitioning Around Medoids） 基于有代表性的數據（中心點），而不是均值代表每個類。思路 1.為每個類隨機選擇一個代表對象(中心點)； 2.

36、剩余的對象根據其與代表對象的距離分配給與其最近的一個類； 3.反復地用非代表對象來替換代表對象，以提高聚類的質量，直至找到最合適的中心點。2022/7/29 The Institute of Business Intelligence, HFUT54/104k-中心點算法 劃分方法仍然基于最小化所有對象與其對應的參考點之間的相異度之和的原則來執行。 通常使用絕對誤差來度量： 2022/7/29 The Institute of Business Intelligence, HFUT55/104 where E is the sum of the absolute error for all o

37、bjects p in the data set, and oi is the representative object of Ci. This is the basis for the k-medoids method, which groups n objects into k clusters by minimizing the absolute errork-中心點算法2022/7/29 The Institute of Business Intelligence, HFUT56/104 為了確定非代表對象Orandom是否是當前對象Oj 的好的替代，對于每一個非代表對象P，考慮如下

38、四種情況：第一種情況： P當前隸屬于代表對象Oj。如果Oj 被Orandom 所取代作為代表對象，并且P 離其他代表對象Oi (i j )最近，則P 重新分配給Oi。第二種情況： P當前隸屬于代表對象Oj。如果Oj 被Orandom 所取代作為代表對象，并且P 離Orandom 最近，則P 重新分配給Orandom。第三種情況： P當前隸屬于代表對象Oi， i j 。如果Oj 被Orandom 所取代作為代表對象，并且P 仍然離Oi 最近，則對象的隸屬不發生變化。第四種情況： P當前隸屬于代表對象Oi， i j 。如果Oj 被Orandom 所取代作為代表對象，并且P 離Orandom 最近，

39、則P 重新分配給Orandom。 k-中心點算法2022/7/29 The Institute of Business Intelligence, HFUT57/104 為了確定非代表對象Orandom是否是當前對象Oj 的好的替代，對于每一個非代表對象P，考慮如下四種情況：第一種情況： P當前隸屬于代表對象Oj。如果Oj 被Orandom 所取代作為代表對象，并且P 離其他代表對象Oi (i j )最近，則將P 分配給Oi。第二種情況： P當前隸屬于代表對象Oj。如果Oj 被Orandom 所取代作為代表對象，并且P 離Orandom 最近，則P 重新分配給Orandom。第三種情況： P當

40、前隸屬于代表對象Oi， i j 。如果Oj 被Orandom 所取代作為代表對象，并且P 仍然離Oi 最近，則對象的隸屬不發生變化。第四種情況： P當前隸屬于代表對象Oi， i j 。如果Oj 被Orandom 所取代作為代表對象，并且P 離Orandom 最近，則P 重新分配給Orandom。 OrandomOjP Oi 1.分配給Oi k-中心點算法2022/7/29 The Institute of Business Intelligence, HFUT58/104 為了確定非代表對象Orandom是否是當前對象Oj 的好的替代，對于每一個非代表對象P，考慮如下四種情況：第二種情況： P

41、當前隸屬于代表對象Oj。如果Oj 被Orandom 所取代作為代表對象，并且P 離Orandom 最近，則將P分配給Orandom。第三種情況： P當前隸屬于代表對象Oi， i j 。如果Oj 被Orandom 所取代作為代表對象，并且P 仍然離Oi 最近，則對象的隸屬不發生變化。第四種情況： P當前隸屬于代表對象Oi， i j 。如果Oj 被Orandom 所取代作為代表對象，并且P 離Orandom 最近，則P 重新分配給Orandom。 OrandomOjP Oi 2.分配給Orandom k-中心點算法2022/7/29 The Institute of Business Intell

42、igence, HFUT59/104 為了確定非代表對象Orandom是否是當前對象Oj 的好的替代，對于每一個非代表對象P，考慮如下四種情況：第三種情況： P當前隸屬于代表對象Oi， i j 。如果Oj 被Orandom 所取代作為代表對象，并且P 仍然離Oi 最近，則對象P的隸屬不發生變化。第四種情況： P當前隸屬于代表對象Oi， i j 。如果Oj 被Orandom 所取代作為代表對象，并且P 離Orandom 最近，則P 重新分配給Orandom。 OrandomOjP Oi 3. P隸屬關系不變k-中心點算法2022/7/29 The Institute of Business In

43、telligence, HFUT60/104 為了確定非代表對象Orandom是否是當前對象Oj 的好的替代，對于每一個非代表對象P，考慮如下四種情況：第四種情況： P當前隸屬于代表對象Oi， i j 。如果Oj 被Orandom 所取代作為代表對象，并且P 離Orandom 最近，則將P分配給Orandom。 OrandomOjP Oi 4.將P分配給Orandom 算法: PAM（k-中心點算法）輸入：簇的數目k和包含n個對象的數據庫。輸出：k個簇，使得所有對象與其最近中心點的相異度總和最小。（1） 任意選擇k個對象作為初始的簇中心點；（2） REPEAT（3） 指派每個剩余的對象給離它最

44、近的中心點所代表的簇；（4） REPEAT（5） 選擇一個未被選擇的中心點Oj；（6） REPEAT（7） 選擇一個未被選擇過的非中心點對象Orandom ；（8） 用Orandom代替Oj，并進行調整；（9） 計算用Orandom代替Oj的總代價記錄在S (絕對誤差值的差)中；（10） UNTIL 所有的非中心點都被選擇過；（11） UNTIL 所有的中心點都被選擇過；（12） IF 在S中的所有非中心點代替所有中心點后的計算出的總代價有小于0的存在 THEN 找出S中的用非中心點替代中心點后代價最小的一個，并用該非中心點 替代對應的中心點，形成一個新的k個中心點的集合；（13）UNTIL

45、沒有再發生簇的重新分配，即所有的S都大于0.2022/7/29 The Institute of Business Intelligence, HFUT61/104實例 假如空間中的五個點A、如圖所示，各點之間的距離關系如表所示，根據所給的數據對其運行PAM算法實現劃分聚類（設k=2）。 樣本點間距離如下表所示:樣本點ABCDEA01223B10243C22015D24103E335302022/7/29 The Institute of Business Intelligence, HFUT62/104聚類算法1. 劃分聚類方法2. 層次聚類方法3. 密度聚類方法2022/7/29 The

46、Institute of Business Intelligence, HFUT63/104層次聚類方法層次聚類方法對給定的數據集進行層次的分解，直到某種條件滿足為止。具體可分為：凝聚的層次聚類：一種自底向上的策略，首先將每個對象作為一個類，然后合并這些原子類為越來越大的類，直到某個終結條件被滿足。分裂的層次聚類：采用自頂向下的策略，它首先將所有對象置于一個類中，然后逐漸細分為越來越小的類，直到達到了某個終結條件。層次凝聚的代表是AGNES算法，層次分裂的代表是DIANA算法。 2022/7/29 The Institute of Business Intelligence, HFUT64/1

47、042022/7/29 The Institute of Business Intelligence, HFUT65/104層次聚類方法常用類間距離最短距離法最長距離法平均距離法重心法2022/7/29 The Institute of Business Intelligence, HFUT66/104層次凝聚AGNES算法 AGNES (Agglomerative Nesting)算法最初將每個對象作為一個類，然后這些類根據某些準則被一步步地合并。兩個類間的相似度由這兩個不同類中距離最近的數據點對的相似度來確定。聚類的合并過程反復進行直到所有的對象最終滿足類數目。2022/7/29 The

48、Institute of Business Intelligence, HFUT67/104算法 : AGNES（自底向上凝聚算法）輸入：包含n個對象的數據庫，終止條件類的數目k。輸出：k個類，達到終止條件規定類數目。步驟： (1) 將每個對象當成一個初始類； (2) REPEAT (3) 根據兩個類中最近的數據點找到最近的兩個類； (4) 合并兩個類，生成新的類的集合； (5) UNTIL 達到預先定義的類的數目；2022/7/29 The Institute of Business Intelligence, HFUT68/104實 例個體12345678屬性111223344屬性2121

49、245452022/7/29 The Institute of Business Intelligence, HFUT69/104 第1步：根據初始類計算每個類之間的距離，隨機找出距離最小的兩個類，進行合并，最小距離為1，將1，2點合并為一個類。2022/7/29 The Institute of Business Intelligence, HFUT70/104實 例個體12345678屬性111223344屬性212124545步驟 最近的類距離 最近的兩個類 合并后的新類 1 1 1，2 1，2，3，4，5，6，7，8步驟 最近的類距離 最近的兩個類 合并后的新類 1 1 1，2 1，2

50、，3，4，5，6，7，8 2 1 3，4 1，2，3，4，5，6，7，8 第2步：對上一次合并后的類計算類間距離，找出距離最近的兩個類進行合并，合并后3，4點成為一類。2022/7/29 The Institute of Business Intelligence, HFUT71/104個體12345678屬性111223344屬性212124545實 例步驟 最近的類距離 最近的兩個類 合并后的新類 1 1 1，2 1，2，3，4，5，6，7，8 2 1 3，4 1，2，3，4，5，6，7，8 3 1 5，6 1，2，3，4，5，6，7，8 第3步：重復第2步的工作，5，6點成為一類。202

51、2/7/29 The Institute of Business Intelligence, HFUT72/104個體12345678屬性111223344屬性212124545實 例步驟 最近的類距離 最近的兩個類 合并后的新類 1 1 1，2 1，2，3，4，5，6，7，8 2 1 3，4 1，2，3，4，5，6，7，8 3 1 5，6 1，2，3，4，5，6，7，8 4 1 7，8 1，2，3，4，5，6，7，8 第4步：重復第2步的工作，7，8點成為一類。2022/7/29 The Institute of Business Intelligence, HFUT73/104個體1234

52、5678屬性111223344屬性212124545實 例步驟 最近的類距離 最近的兩個類 合并后的新類 1 1 1，2 1，2，3，4，5，6，7，8 2 1 3，4 1，2，3，4，5，6，7，8 3 1 5，6 1，2，3，4，5，6，7，8 4 1 7，8 1，2，3，4，5，6，7，8 5 1 1，2，3，4 1，2，3，4，5，6，7，8 第5步：合并1，2，3，4成為一個包含四個點的類。2022/7/29 The Institute of Business Intelligence, HFUT74/104個體12345678屬性111223344屬性212124545實 例步驟

53、最近的類距離 最近的兩個類 合并后的新類 1 1 1，2 1，2，3，4，5，6，7，8 2 1 3，4 1，2，3，4，5，6，7，8 3 1 5，6 1，2，3，4，5，6，7，8 4 1 7，8 1，2，3，4，5，6，7，8 5 1 1，2，3，4 1，2，3，4，5，6，7，8 6 1 5，6，7，8 1，2，3，4，5，6，7，8 結束第6步：合并5，6，7，8，由于合并后的類的數目已經達到了用戶輸入的終止條件程序結束。2022/7/29 The Institute of Business Intelligence, HFUT75/104個體12345678屬性111223344屬

54、性212124545實 例123456786543212022/7/29 The Institute of Business Intelligence, HFUT76/104步驟 最近的類距離 最近的兩個類 合并后的新類 1 1 1，2 1，2，3，4，5，6，7，8 2 1 3，4 1，2，3，4，5，6，7，8 3 1 5，6 1，2，3，4，5，6，7，8 4 1 7，8 1，2，3，4，5，6，7，8 5 1 1，2，3，4 1，2，3，4，5，6，7，8 6 1 5，6，7，8 1，2，3，4，5，6，7，8 結束實 例AGNES算法的性能分析優點AGNES算法比較簡單。問題合并點選

55、擇的困難。假如一旦一組對象被合并，下一步的處理將在新生成的類上進行。 已做處理不能撤消，聚類之間也不能交換對象。不具有很好的可伸縮性，因為合并的決定需要檢查和估算大量的對象或類。2022/7/29 The Institute of Business Intelligence, HFUT77/104DIANA算法 DIANA (Divisive Analysis)算法是典型的分裂聚類方法。 在聚類中，用戶定義希望得到的類數目作為一個結束條件。同時，它使用下面兩種測度方法：類的直徑：Max類中的任意兩個數據點的距離。平均相異度（平均距離）： 2022/7/29 The Institute of B

56、usiness Intelligence, HFUT78/104算法： DIANA（自頂向下分裂算法）輸入：包含n個對象的數據庫，終止條件類的數目k。輸出：k個類，達到終止條件規定類數目。步驟：（1）將所有對象整個當成一個初始類；（2） FOR （i=1; ik; i+) DO BEGIN（3） 在所有類中挑出具有最大直徑的類C；（4） 找出C中與其它點平均相異度最大的一個點p,并把p放入splinter group，剩余的放在old party中；（5） REPEAT（6） 將old party中滿足下列條件的點加入splinter group： 這些點到splinter group 的距離

57、小于到old party的距離。（7） UNTIL 沒有新的old party的點被分配給splinter group；（8） splinter group和old party為被選中的類分裂成的兩個類，與其它類一起組成新的類集合。（9） END.DIANA算法2022/7/29 The Institute of Business Intelligence, HFUT79/1042022/7/29 The Institute of Business Intelligence, HFUT80/104DIANA算法實 例序號 屬性 1 屬性 2 1 1 1 2 1 2 3 2 1 4 2 2 5

58、3 4 6 3 5 7 4 4 8 4 52022/7/29 The Institute of Business Intelligence, HFUT81/104 第1步：找到具有最大直徑的類，對類中的每個點計算平均相異度（假定采用是歐式距離）。 1的平均距離：（1+1+1.414+3.6+4.24+4.47+5）/7=2.96 2的平均距離為2.526； 3的平均距離為2.68； 4的平均距離為2.18； 5的平均距離為2.18； 6的平均距離為2.68； 7的平均距離為2.526； 8的平均距離為2.96。 2022/7/29 The Institute of Business Intel

59、ligence, HFUT82/104序號 屬性 1 屬性 2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5實 例步驟 具有最大直徑的類splinter group Old party11，2，3，4，5，6，7，8 12，3，4，5，6，7，8 第2步：在old party里找出到splinter group的距離小于到old party的距離的點，將該點放入splinter group中，該點是2。2022/7/29 The Institute of Business Intelligence, HFUT83/104序號 屬性 1 屬性 2

60、 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5實 例步驟 具有最大直徑的類splinter group Old party11，2，3，4，5，6，7，8 12，3，4，5，6，7，821，2，3，4，5，6，7，8 1，23，4，5，6，7，8 第3步：重復第2步的工作，splinter group中放入點3。2022/7/29 The Institute of Business Intelligence, HFUT84/104序號 屬性 1 屬性 2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4