數(shù)據(jù)挖掘聚類分析課件

數(shù)據(jù)挖掘中的聚類分析算法研究數(shù)據(jù)挖掘聚類分析課件結構一、聚類分析二、聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型三、聚類分析算法分類結構一、聚類分析1.1聚類分析聚類分析（clusteringanalysis）

聚類是把一組個體按照相似性劃分成若干個類別，跟平常說的“物以類聚”相似。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異。在許多應用中，可以將一個簇中的數(shù)據(jù)對象作為一個整體來對待。

1.1聚類分析聚類分析（clusteringanalys1.2聚類分析與其他分類或預測的不同聚類與其他分類或預測的不同（1）大多數(shù)分類方法都是演繹的，即人們事先確定某種事物分類的準則或各類別的標準，分類的過程就是比較分類的要素與各類別標準，然后將各要素劃歸于各類別中。確定事物的分類準則或各類別的標準或多或少帶有主觀色彩。（2）聚類分析是歸納的，不需要事先確定分類的準則來分析數(shù)據(jù)對象，不考慮己知的類標記。一般情況下，訓練數(shù)據(jù)中不提供類標記，聚類的目標就是通過聚類算法產(chǎn)生這種標記。1.2聚類分析與其他分類或預測的不同聚類與其他分類或預測的不數(shù)據(jù)挖掘對聚類的典型要求（1）可伸縮性可伸縮性是指算法不論對于小數(shù)據(jù)集還是對于大數(shù)據(jù)集,都應是有效的。（2）處理不同字段類型的能力算法不僅要能處理數(shù)值型數(shù)據(jù)，還要有處理其它類型字段的能力，包括分類/標稱類型(categorical/nominal)，序數(shù)型(ordinal)，二元類型(binary)，或者這些數(shù)據(jù)類型的混合。1.3數(shù)據(jù)挖掘對聚類的典型要求數(shù)據(jù)挖掘對聚類的典型要求1.3數(shù)據(jù)挖掘對聚類的典型要求（3）能夠發(fā)現(xiàn)任意形狀的聚類有些簇具有規(guī)則的形狀，如矩形和球形。但是，更一般地，簇可以具有任意形狀。（4）用于決定輸入?yún)?shù)的領域知識最小化在聚類分析當中，許多聚類算法要求用戶輸入一定的參數(shù)，如希望簇的數(shù)目。聚類結果對于輸入?yún)?shù)很敏感，通常參數(shù)較難確定，尤其是對于含有高維對象的數(shù)據(jù)集更是如此。（5）處理高維數(shù)據(jù)的能力既可處理屬性較少的數(shù)據(jù)，又能處理屬性較多的數(shù)據(jù)。很多聚類算法擅長處理低維數(shù)據(jù)，一般只涉及兩到三維，通常最多再加二維的情況下能夠很好地判斷聚類的質量。1.3數(shù)據(jù)挖掘對聚類的典型要求（3）能夠發(fā)現(xiàn)任意形狀的聚類1.3數(shù)據(jù)挖掘對聚類的典型要求

（6）能夠處理噪聲數(shù)據(jù)

現(xiàn)實世界中的數(shù)據(jù)庫常常包含了孤立點、空缺、未知數(shù)據(jù)或有錯誤的數(shù)據(jù)。一些聚類算法對于這樣的數(shù)據(jù)敏感,可能導致低質量的聚類結果。所以我們希望算法可以在聚類過程中檢測代表噪聲和離群的點，然后刪除它們或者消除它們的負面影響。

（7）結果對于輸入記錄順序不敏感

一些聚類算法對于輸入數(shù)據(jù)的順序是敏感的。對于同一個數(shù)據(jù)集合，以不同的順序提交給同一個算法時，可能產(chǎn)生差別很大的聚類結果，這是我們不希望的。

1.3數(shù)據(jù)挖掘對聚類的典型要求

（6）能夠處理噪聲數(shù)據(jù)

現(xiàn)實世界中的數(shù)據(jù)庫（8）基于約束的聚類在實際應用當中可能需要在各種約束條件下進行聚類。找到既要滿足特定的約束，又要具有良好聚類特性的數(shù)據(jù)分組是一項具有挑戰(zhàn)性的任務。我們希望聚類算法可以在考慮這些限制的情況下，仍具有較好的表現(xiàn)。（9）可解釋性和可用性聚類的結果最終都是要面向用戶的，用戶期望聚類得到的信息是可理解和可應用的。1.3數(shù)據(jù)挖掘對聚類的典型要求（8）基于約束的聚類1.3數(shù)據(jù)挖掘對聚類的典型要求聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型（1）數(shù)據(jù)結構許多基于內(nèi)存的少類算法選擇如下兩種有代表性的數(shù)據(jù)結構。1）數(shù)據(jù)矩陣（對象-變量結構）數(shù)據(jù)矩陣是一張關系表的形式,每列代表對象的一個屬性,每個元組代表一個數(shù)據(jù)對象。

具有p個屬性的n個對象（例如，人可以用年齡，身高，體重，性別，種族等來描述）可以看成如下n×p(n個對象×p個屬性)的矩陣。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)

2）相異度矩陣（對象-對象結構）它存儲n個對象兩兩之間的差異性，表現(xiàn)形式是n×n維的矩陣。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型其中d(i，j)是對象i和對象j之間相異性的量化表示，通常為非負數(shù)，且d(i，j)=d(j，i)，d(i，i)=。對象i和對象j越相似，則d(i，j)越接近于0，對象i和對象j的差異越大，則d(i，j)越大。相異度矩陣通常用距離公式計算得到。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型（2）數(shù)據(jù)類型聚類分析起源于統(tǒng)計學，傳統(tǒng)的分析方法大多是在數(shù)值類型數(shù)據(jù)的基礎上研究的。然而數(shù)據(jù)挖掘的對象復雜多樣，要求聚類分析的方法不僅能夠對屬性為數(shù)值類型的數(shù)據(jù)進行，而且要適應數(shù)據(jù)類型的變化。1）區(qū)間標度變量區(qū)間標度變量是一個粗略線性標度的連續(xù)度量。典型的例子則包括重量和高度，經(jīng)度和緯度坐標，以及攝氏或華氏溫度等。

數(shù)據(jù)之間純在差異性，同時多個屬性肯那個有不同的度量單位，所以在計算數(shù)據(jù)相似性之前要進行數(shù)據(jù)的標準化。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型（2）數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型數(shù)據(jù)標準化處理以后就可以進行屬性值的相似性測量，通常是計算對象間的距離。對于n維向量xi和xj，有以下幾種距離函數(shù)：歐氏距離曼哈頓距離2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型數(shù)據(jù)標準化處理以后就可以進行屬性值的概化的明考斯基（Minkowski）距離當m=2時，明考斯基D2即為歐氏距離；當m=1時，明考斯基D1即為曼哈頓距離。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型概化的明考斯基（Minkowski）距離2.聚類分析中的數(shù)據(jù)2）二元變量二元變量只有兩個狀態(tài)：0和1。其中二元變量又分為對稱的二元變量和不對稱的二元變量。前者是指變量的兩個狀態(tài)不具有優(yōu)先權，后者對于不同的狀態(tài)其重要性是不同的。對于二元變量,度量兩個變量的差異度可以由簡單匹配系數(shù)(對稱的情況)和Jaccard系數(shù)(非對稱的情況)決定。設兩個對象xi和xj，q是屬性值在兩個對象中都為1的屬性個數(shù)，r是屬性值在xi中為1而在xj中為0的屬性個數(shù)，s是屬性值在xi中為0而在xj中為1的屬性個數(shù)，t是屬性值在兩個對象中都為0的屬性個數(shù)。則2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2）二元變量2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型簡單匹配系數(shù)：Jaccard系數(shù)2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型簡單匹配系數(shù)：2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型3）標稱型變量標稱變量是二元變量的推廣，它可以有多于兩個狀態(tài)值，狀態(tài)之間是無序的。兩個對象i和j之間的差異度可用簡單匹配法來計算:

其中，m是對象xi和xj中匹配的屬性個數(shù)，而p是全部屬性個數(shù)。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型3）標稱型變量2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型4）序數(shù)型變量序數(shù)型變量類似于標稱型變量，但它的各個狀態(tài)是有意義的序列。序數(shù)型變量值的相對順序是必要的，而其實際的大小則不那么重要。一個序數(shù)型變量的值可以映射為秩。假設一個變量f有m個狀態(tài)，這些有序的狀態(tài)定義了一個序列1，…，m，關于f的相異度計算步驟如下：第i個對象的f值為xif，變量f有m個有序的狀態(tài)，對應于序列1，…，m。用對應的秩rif代替xif，rif∈

{1，…，m}每個序數(shù)型變量有不同數(shù)目的狀態(tài)，為了使每個變量都有相同的權重,我們將每個變量的值域映射到[0.0,1.0]上:2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型4）序數(shù)型變量2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型其中zif是rif映射后的值。采用zif作為第i個對象的f值，計算相異度，可以采用任意一種距離度量方法。5）比例標度型變量比例標度型變量就是在非線性的標度上所獲得的正測量值。對于此種類型的變量，一般采用以下兩種方法計算相異度。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型對比例標度型變量進行對數(shù)變換，變換得到的值采用區(qū)間標度變量的方法來處理。將比例標度型變量看做連續(xù)的序數(shù)型數(shù)據(jù)，將其秩作為區(qū)間標度的值來對待。6）混合類型的變量以上討論了各種數(shù)據(jù)類型和創(chuàng)門差異度的計算方法，在實際數(shù)據(jù)庫中，數(shù)據(jù)對象是由混合類型的變量描述的。在實際聚類分析中，將不同的類型屬性組合在同一個差異度矩陣中進行計算。設數(shù)據(jù)包含m個不同類型的屬性,對象xi和xj之間的差異度定義為：2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型對比例標度型變量進行對數(shù)變?nèi)绻麑傩詐是序數(shù)型或比例標度型變量：將其轉化為區(qū)間標度變量值對待。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型

聚類分析算法分類聚類分析技術通?？煞譃槲宕箢?，分別是基于劃分的聚類，基于層次的聚類，基于密度的聚類，基于網(wǎng)格的聚類以及基于模型的聚類。3.聚類分析算法分類

聚類分析算法分類3.聚類分析算法分類（1）基于劃分的方法劃分算法的思想是，將給定待挖掘數(shù)據(jù)集中的數(shù)據(jù)對象劃分成K組（k≤N，N代表數(shù)據(jù)集中對象數(shù)目），每一組表示一個聚類的簇。并且要滿足任何一個數(shù)據(jù)對象僅可以屬于一個聚類，每個聚類中至少具有一個數(shù)據(jù)對象。K-medoids和K-means算法是劃分算法中兩個比較經(jīng)典的算法。其他很多劃分算法都是從這兩個算法演變改進而來的。3.聚類分析算法分類（1）基于劃分的方法3.聚類分析算法分類1.K-means（k均值）算法K-means算法的相似度計算根據(jù)一個簇中對象的平均值即簇的質心來進行，它的處理過程如下：首先，隨機地選擇k個對象作為初始的k個簇的質心；然后對剩余的每個對象，根據(jù)其與各個質心的距離，將它賦給最近的簇；再后重新計算每個簇的質心。這個過程不斷重復，直到準則函數(shù)收斂。通常采用的準則函數(shù)為平方誤差和準則函數(shù),即SSE(sumofthesquarederror)，其定義如下：這里的SSE是數(shù)據(jù)庫中所有對象的平方誤差總和，p為數(shù)據(jù)對象，mi是簇Ci的平均值。這個準則函數(shù)使生成的結果盡可能的緊湊和獨立。3.聚類分析算法分類1.K-means（k均值）算法3.聚類分析算法分類K均值算法的形式化描述如下：K-means算法：輸入：具有n個數(shù)據(jù)對象的數(shù)據(jù)集，聚類結果中簇的個數(shù)k。輸出：滿足準則函數(shù)的k個聚類。處理過程：(1)在數(shù)據(jù)集里任意選擇k個對象，然后將每個數(shù)據(jù)對象代表初始聚類的中心；(2)將剩下的數(shù)據(jù)劃分到和數(shù)據(jù)本身相距最近的簇心的簇中；(3)重新計算每個簇的均值得到新的簇心值(4)重復(2)到(3)一直到每個簇不再發(fā)生變化或者目標函數(shù)收斂結束3.聚類分析算法分類K均值算法的形式化描述如下：3.聚類分析算法分類在該算法中，一次迭代中把每一個數(shù)據(jù)對象分到離它最近的聚類中心所在類，這個過程的時間復雜度為O(nkd)，這里的n指的是總的數(shù)據(jù)對象個數(shù)，k指定的聚類數(shù)，d是數(shù)據(jù)對象的維數(shù)；新的分類產(chǎn)生以后需要計算新的聚類中心,這個過程的時間復雜度為O(nd)。因此，這個算法一次迭代需要的總的時間復雜度為O(nkd)。例：假設給定如下要進行聚類的元組：{2,4,10,12,3,20,30,11,25}

假設要求的簇的數(shù)量為k=2。應用K一means算法：第一步：初始時用前兩個數(shù)值作為簇的質心，這兩個簇的質心是：m1=2；m2=4；3.聚類分析算法分類在該算法中，一次迭代中把每一個數(shù)據(jù)對第二步：對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它賦給最近的簇，可得：

K1=(2,3}；

K2={4,10,12,20,30,11,25}；數(shù)值3與兩個均值的距離相等，所以任意的選擇K1作為其所屬的簇。第三步：計算新的質心：m1=(2+3)/2=2.5；m2=(4+10+12+20+30+11+25)/7=16；重新對簇中的成員進行分配可得K1={2,3,4}和K2={10,12,20,30,11,25}，3.聚類分析算法分類第二步：對剩余的每個對象，根據(jù)其與各個不斷重復這個過程可得:注意在最后兩步中簇的成員是一致的。由于均值不再變化，所以均值已經(jīng)收斂了。因此，該問題的答案為K1={2,3,4,10,11,12}和K2={20,30,25}。3.聚類分析算法分類3.聚類分析算法分類K-means優(yōu)缺點：此聚類分析算法伸縮性良好，并且針對大型數(shù)據(jù)集效率很高。初始的K-means算法缺點如下：(1)初始聚類中心選擇的好與壞將會對聚類結果的質量產(chǎn)生很大影響；(2)算法很容易陷入局部最優(yōu)解，有時會產(chǎn)生較差的結果；(3)算法開始時要求用戶給出聚類簇的個數(shù)k，而對于K值的選擇還沒有很好的準則可循；(4)對噪聲敏感；(5)只能在可以定義聚類的平均值的條件下才可以應用，即適合處理數(shù)值屬性的數(shù)據(jù)(6)聚類的最終結果也許會出現(xiàn)不平衡現(xiàn)象，不適合發(fā)現(xiàn)那些非凸面形狀的簇或者大小差別非常大的簇。3.聚類分析算法分類K-means優(yōu)缺點：3.聚類分析算法分類

2.K-medoids（中心點）

算法K-means算法對于孤立點敏感，一個極大值的對象可能在相當大的程度上扭曲數(shù)據(jù)的分布。k中心點算法不采用簇中對象的平均值作為簇中心，而選用簇中離平均值最近的對象作為簇中心，此種方法具有很好的抗噪聲的能力。以下是K-medoids算法的形式化描述：K-medoids聚類算法：輸入：具有n個對象的數(shù)據(jù)庫，聚類的簇數(shù)目k輸出：滿足目標函數(shù)的k個簇。3.聚類分析算法分類

2.K-medoids（中心點）算法3.聚類分析算法分類處理過程：(1)從輸入的數(shù)據(jù)集中任意選擇k個數(shù)據(jù)對象，并將每個數(shù)據(jù)對象看做是初始簇的聚類中心；(2)計算剩下的每個數(shù)據(jù)對象到每個簇中心點的距離，并將其指派到離它最近的中心點所代表的簇中；(3)任意選擇一個非中心點的數(shù)據(jù)對象Or；(4)計算用Or代替Oj形成新集合的總代價s；(5)如果s<0，則用Or代替Oj，得到新的k個中心點的集合；(6)重復(2)、(3)、(4)、(5)，直至k個中心點不再改變或目標函數(shù)收斂為止。K-medoids算法在抗噪聲和孤立點的能力方面有了很大的提高，但是K-medoids算法在處理起來花費時間比較長，并且依然需要用戶輸入目標聚類個數(shù)k。

3.聚類分析算法分類處理過程：3.聚類分析算法分類(2)基于層次的聚類算法

層次的方法按數(shù)據(jù)分層建立簇,形成一棵以簇為節(jié)點的樹。根據(jù)層次如何形成，層次的方法可以分為凝聚的和分裂的。凝聚的方法，也稱自底向上的方法，該方法從數(shù)據(jù)點作為個體簇開始，每一步合并兩個最接近的簇，直到所有的簇合并為一個(層次的最上層)，或者達到一個終止的條件。分裂的方法，也稱為自頂向下的方法，它與凝聚的方法正好相反，該方法從包含所有點的一個簇開始，每一步分裂一個簇，最終每個對象在單獨的一個簇中，或者達到一個終止條件，比如達到某個希望的簇數(shù)目，或者兩個最近的簇之間的距離超過了某個閉值。3.聚類分析算法分類(2)基于層次的聚類算法3.聚類分析算法分類無論是凝聚算法還是分裂算法都要采用一個劃分準則,以便判定簇之間的相似性或相異性,五個廣泛采用的簇間距離度量方法如下:（1）最?。▎捂湥┚嚯x；（2）最大（全鏈）距離；（3）平均值（質心）距離；（4）平均（組平均）距離；（5）中心點距離。3.聚類分析算法分類無論是凝聚算法還是分裂算法都要采用一(3)基于密度的方法目前的研究發(fā)現(xiàn)基于密度的聚類方法在發(fā)現(xiàn)任意形狀的數(shù)據(jù)集方面具有非常有力的效果。簡單來說，基于密度的聚類算法就是將數(shù)據(jù)對象劃分為成被低密度區(qū)分隔開的高密度區(qū)。基于密度的聚類應用本地集群準則，有非常優(yōu)秀的抵抗噪聲的效果，而且在挖掘任意形狀的數(shù)據(jù)集方面的能力也非常優(yōu)秀。雖然基于密度的聚類在發(fā)現(xiàn)任意形狀的簇的方面具有良好的效果，但是他依然需要用戶輸出必要的參數(shù)，并且其可擴展性也具有一定的局限性。典型的基于密度的聚類方法包括DBSCAN和OPTICS。3.聚類分析算法分類(3)基于密度的方法3.聚類分析算法分類（4）基于網(wǎng)格的方法

基于網(wǎng)格算法的基本是思想是把數(shù)據(jù)空間的每個屬性分割成有限個相鄰的單元的網(wǎng)格結構，以單個單元為對象創(chuàng)見網(wǎng)格單元的集合，在此一切都是以劃分的網(wǎng)格單元為對象進行操作。基于網(wǎng)格的算法涉及到兩方面參數(shù)的設定，其一是網(wǎng)格單元的設置，其二是網(wǎng)格單元密度的設定。3.聚類分析算法分類（4）基于網(wǎng)格的方法3.聚類分析算法分類（5）基于模型的聚類分析算法

基于模型的聚類分析算法思想是把給定的數(shù)據(jù)集與某個相應數(shù)學模型相結合，尋找數(shù)據(jù)與模型之間的最佳擬合。在此種算法中，聚類結果的簇的數(shù)目也是通過統(tǒng)計數(shù)字自動所決定的，孤立點和噪聲也是根據(jù)統(tǒng)計數(shù)字進而進行分析的。3.聚類分析算法分類（5）基于模型的聚類分析算法3.聚類分析算法分類數(shù)據(jù)挖掘中的聚類分析算法研究數(shù)據(jù)挖掘聚類分析課件結構一、聚類分析二、聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型三、聚類分析算法分類結構一、聚類分析1.1聚類分析聚類分析（clusteringanalysis）

聚類是把一組個體按照相似性劃分成若干個類別，跟平常說的“物以類聚”相似。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異。在許多應用中，可以將一個簇中的數(shù)據(jù)對象作為一個整體來對待。

1.1聚類分析聚類分析（clusteringanalys1.2聚類分析與其他分類或預測的不同聚類與其他分類或預測的不同（1）大多數(shù)分類方法都是演繹的，即人們事先確定某種事物分類的準則或各類別的標準，分類的過程就是比較分類的要素與各類別標準，然后將各要素劃歸于各類別中。確定事物的分類準則或各類別的標準或多或少帶有主觀色彩。（2）聚類分析是歸納的，不需要事先確定分類的準則來分析數(shù)據(jù)對象，不考慮己知的類標記。一般情況下，訓練數(shù)據(jù)中不提供類標記，聚類的目標就是通過聚類算法產(chǎn)生這種標記。1.2聚類分析與其他分類或預測的不同聚類與其他分類或預測的不數(shù)據(jù)挖掘對聚類的典型要求（1）可伸縮性可伸縮性是指算法不論對于小數(shù)據(jù)集還是對于大數(shù)據(jù)集,都應是有效的。（2）處理不同字段類型的能力算法不僅要能處理數(shù)值型數(shù)據(jù)，還要有處理其它類型字段的能力，包括分類/標稱類型(categorical/nominal)，序數(shù)型(ordinal)，二元類型(binary)，或者這些數(shù)據(jù)類型的混合。1.3數(shù)據(jù)挖掘對聚類的典型要求數(shù)據(jù)挖掘對聚類的典型要求1.3數(shù)據(jù)挖掘對聚類的典型要求（3）能夠發(fā)現(xiàn)任意形狀的聚類有些簇具有規(guī)則的形狀，如矩形和球形。但是，更一般地，簇可以具有任意形狀。（4）用于決定輸入?yún)?shù)的領域知識最小化在聚類分析當中，許多聚類算法要求用戶輸入一定的參數(shù)，如希望簇的數(shù)目。聚類結果對于輸入?yún)?shù)很敏感，通常參數(shù)較難確定，尤其是對于含有高維對象的數(shù)據(jù)集更是如此。（5）處理高維數(shù)據(jù)的能力既可處理屬性較少的數(shù)據(jù)，又能處理屬性較多的數(shù)據(jù)。很多聚類算法擅長處理低維數(shù)據(jù)，一般只涉及兩到三維，通常最多再加二維的情況下能夠很好地判斷聚類的質量。1.3數(shù)據(jù)挖掘對聚類的典型要求（3）能夠發(fā)現(xiàn)任意形狀的聚類1.3數(shù)據(jù)挖掘對聚類的典型要求

（6）能夠處理噪聲數(shù)據(jù)

現(xiàn)實世界中的數(shù)據(jù)庫常常包含了孤立點、空缺、未知數(shù)據(jù)或有錯誤的數(shù)據(jù)。一些聚類算法對于這樣的數(shù)據(jù)敏感,可能導致低質量的聚類結果。所以我們希望算法可以在聚類過程中檢測代表噪聲和離群的點，然后刪除它們或者消除它們的負面影響。

（7）結果對于輸入記錄順序不敏感

一些聚類算法對于輸入數(shù)據(jù)的順序是敏感的。對于同一個數(shù)據(jù)集合，以不同的順序提交給同一個算法時，可能產(chǎn)生差別很大的聚類結果，這是我們不希望的。

1.3數(shù)據(jù)挖掘對聚類的典型要求

（6）能夠處理噪聲數(shù)據(jù)

現(xiàn)實世界中的數(shù)據(jù)庫（8）基于約束的聚類在實際應用當中可能需要在各種約束條件下進行聚類。找到既要滿足特定的約束，又要具有良好聚類特性的數(shù)據(jù)分組是一項具有挑戰(zhàn)性的任務。我們希望聚類算法可以在考慮這些限制的情況下，仍具有較好的表現(xiàn)。（9）可解釋性和可用性聚類的結果最終都是要面向用戶的，用戶期望聚類得到的信息是可理解和可應用的。1.3數(shù)據(jù)挖掘對聚類的典型要求（8）基于約束的聚類1.3數(shù)據(jù)挖掘對聚類的典型要求聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型（1）數(shù)據(jù)結構許多基于內(nèi)存的少類算法選擇如下兩種有代表性的數(shù)據(jù)結構。1）數(shù)據(jù)矩陣（對象-變量結構）數(shù)據(jù)矩陣是一張關系表的形式,每列代表對象的一個屬性,每個元組代表一個數(shù)據(jù)對象。

具有p個屬性的n個對象（例如，人可以用年齡，身高，體重，性別，種族等來描述）可以看成如下n×p(n個對象×p個屬性)的矩陣。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)

2）相異度矩陣（對象-對象結構）它存儲n個對象兩兩之間的差異性，表現(xiàn)形式是n×n維的矩陣。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型其中d(i，j)是對象i和對象j之間相異性的量化表示，通常為非負數(shù)，且d(i，j)=d(j，i)，d(i，i)=。對象i和對象j越相似，則d(i，j)越接近于0，對象i和對象j的差異越大，則d(i，j)越大。相異度矩陣通常用距離公式計算得到。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型（2）數(shù)據(jù)類型聚類分析起源于統(tǒng)計學，傳統(tǒng)的分析方法大多是在數(shù)值類型數(shù)據(jù)的基礎上研究的。然而數(shù)據(jù)挖掘的對象復雜多樣，要求聚類分析的方法不僅能夠對屬性為數(shù)值類型的數(shù)據(jù)進行，而且要適應數(shù)據(jù)類型的變化。1）區(qū)間標度變量區(qū)間標度變量是一個粗略線性標度的連續(xù)度量。典型的例子則包括重量和高度，經(jīng)度和緯度坐標，以及攝氏或華氏溫度等。

數(shù)據(jù)之間純在差異性，同時多個屬性肯那個有不同的度量單位，所以在計算數(shù)據(jù)相似性之前要進行數(shù)據(jù)的標準化。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型（2）數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型數(shù)據(jù)標準化處理以后就可以進行屬性值的相似性測量，通常是計算對象間的距離。對于n維向量xi和xj，有以下幾種距離函數(shù)：歐氏距離曼哈頓距離2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型數(shù)據(jù)標準化處理以后就可以進行屬性值的概化的明考斯基（Minkowski）距離當m=2時，明考斯基D2即為歐氏距離；當m=1時，明考斯基D1即為曼哈頓距離。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型概化的明考斯基（Minkowski）距離2.聚類分析中的數(shù)據(jù)2）二元變量二元變量只有兩個狀態(tài)：0和1。其中二元變量又分為對稱的二元變量和不對稱的二元變量。前者是指變量的兩個狀態(tài)不具有優(yōu)先權，后者對于不同的狀態(tài)其重要性是不同的。對于二元變量,度量兩個變量的差異度可以由簡單匹配系數(shù)(對稱的情況)和Jaccard系數(shù)(非對稱的情況)決定。設兩個對象xi和xj，q是屬性值在兩個對象中都為1的屬性個數(shù)，r是屬性值在xi中為1而在xj中為0的屬性個數(shù)，s是屬性值在xi中為0而在xj中為1的屬性個數(shù)，t是屬性值在兩個對象中都為0的屬性個數(shù)。則2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2）二元變量2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型簡單匹配系數(shù)：Jaccard系數(shù)2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型簡單匹配系數(shù)：2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型3）標稱型變量標稱變量是二元變量的推廣，它可以有多于兩個狀態(tài)值，狀態(tài)之間是無序的。兩個對象i和j之間的差異度可用簡單匹配法來計算:

其中，m是對象xi和xj中匹配的屬性個數(shù)，而p是全部屬性個數(shù)。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型3）標稱型變量2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型4）序數(shù)型變量序數(shù)型變量類似于標稱型變量，但它的各個狀態(tài)是有意義的序列。序數(shù)型變量值的相對順序是必要的，而其實際的大小則不那么重要。一個序數(shù)型變量的值可以映射為秩。假設一個變量f有m個狀態(tài)，這些有序的狀態(tài)定義了一個序列1，…，m，關于f的相異度計算步驟如下：第i個對象的f值為xif，變量f有m個有序的狀態(tài)，對應于序列1，…，m。用對應的秩rif代替xif，rif∈

{1，…，m}每個序數(shù)型變量有不同數(shù)目的狀態(tài)，為了使每個變量都有相同的權重,我們將每個變量的值域映射到[0.0,1.0]上:2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型4）序數(shù)型變量2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型其中zif是rif映射后的值。采用zif作為第i個對象的f值，計算相異度，可以采用任意一種距離度量方法。5）比例標度型變量比例標度型變量就是在非線性的標度上所獲得的正測量值。對于此種類型的變量，一般采用以下兩種方法計算相異度。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型對比例標度型變量進行對數(shù)變換，變換得到的值采用區(qū)間標度變量的方法來處理。將比例標度型變量看做連續(xù)的序數(shù)型數(shù)據(jù)，將其秩作為區(qū)間標度的值來對待。6）混合類型的變量以上討論了各種數(shù)據(jù)類型和創(chuàng)門差異度的計算方法，在實際數(shù)據(jù)庫中，數(shù)據(jù)對象是由混合類型的變量描述的。在實際聚類分析中，將不同的類型屬性組合在同一個差異度矩陣中進行計算。設數(shù)據(jù)包含m個不同類型的屬性,對象xi和xj之間的差異度定義為：2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型對比例標度型變量進行對數(shù)變?nèi)绻麑傩詐是序數(shù)型或比例標度型變量：將其轉化為區(qū)間標度變量值對待。2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型2.聚類分析中的數(shù)據(jù)結構和數(shù)據(jù)類型

聚類分析算法分類聚類分析技術通?？煞譃槲宕箢悾謩e是基于劃分的聚類，基于層次的聚類，基于密度的聚類，基于網(wǎng)格的聚類以及基于模型的聚類。3.聚類分析算法分類

聚類分析算法分類3.聚類分析算法分類（1）基于劃分的方法劃分算法的思想是，將給定待挖掘數(shù)據(jù)集中的數(shù)據(jù)對象劃分成K組（k≤N，N代表數(shù)據(jù)集中對象數(shù)目），每一組表示一個聚類的簇。并且要滿足任何一個數(shù)據(jù)對象僅可以屬于一個聚類，每個聚類中至少具有一個數(shù)據(jù)對象。K-medoids和K-means算法是劃分算法中兩個比較經(jīng)典的算法。其他很多劃分算法都是從這兩個算法演變改進而來的。3.聚類分析算法分類（1）基于劃分的方法3.聚類分析算法分類1.K-means（k均值）算法K-means算法的相似度計算根據(jù)一個簇中對象的平均值即簇的質心來進行，它的處理過程如下：首先，隨機地選擇k個對象作為初始的k個簇的質心；然后對剩余的每個對象，根據(jù)其與各個質心的距離，將它賦給最近的簇；再后重新計算每個簇的質心。這個過程不斷重復，直到準則函數(shù)收斂。通常采用的準則函數(shù)為平方誤差和準則函數(shù),即SSE(sumofthesquarederror)，其定義如下：這里的SSE是數(shù)據(jù)庫中所有對象的平方誤差總和，p為數(shù)據(jù)對象，mi是簇Ci的平均值。這個準則函數(shù)使生成的結果盡可能的緊湊和獨立。3.聚類分析算法分類1.K-means（k均值）算法3.聚類分析算法分類K均值算法的形式化描述如下：K-means算法：輸入：具有n個數(shù)據(jù)對象的數(shù)據(jù)集，聚類結果中簇的個數(shù)k。輸出：滿足準則函數(shù)的k個聚類。處理過程：(1)在數(shù)據(jù)集里任意選擇k個對象，然后將每個數(shù)據(jù)對象代表初始聚類的中心；(2)將剩下的數(shù)據(jù)劃分到和數(shù)據(jù)本身相距最近的簇心的簇中；(3)重新計算每個簇的均值得到新的簇心值(4)重復(2)到(3)一直到每個簇不再發(fā)生變化或者目標函數(shù)收斂結束3.聚類分析算法分類K均值算法的形式化描述如下：3.聚類分析算法分類在該算法中，一次迭代中把每一個數(shù)據(jù)對象分到離它最近的聚類中心所在類，這個過程的時間復雜度為O(nkd)，這里的n指的是總的數(shù)據(jù)對象個數(shù)，k指定的聚類數(shù)，d是數(shù)據(jù)對象的維數(shù)；新的分類產(chǎn)生以后需要計算新的聚類中心,這個過程的時間復雜度為O(nd)。因此，這個算法一次迭代需要的總的時間復雜度為O(nkd)。例：假設給定如下要進行聚類的元組：{2,4,10,12,3,20,30,11,25}

假設要求的簇的數(shù)量為k=2。應用K一means算法：第一步：初始時用前兩個數(shù)值作為簇的質心，這兩個簇的質心是：m1=2；m2=4；3.聚類分析算法分類在該算法中，一次迭代中把每一個數(shù)據(jù)對第二步：對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它賦給最近的簇，可得：

K1=(2,3}；

K2={4,10,12,20,30,11,25}；數(shù)值3與兩個均值的距離相等，所以任意的選擇K1作為其所屬的簇。第三步：計算新的質心：m1=(2+3)/2=2.5；m2=(4+10+12+20+30+11+25)/7=16；重新對簇中的成員進行分配可得K1={2,3,4}和K2={10,12,20,30,11,25}，3.聚類分析算法分類第二步：對剩余的每個對象，根據(jù)其與各個不斷重復這個過程可得:注意在最后兩步中簇的成員是一致的。由于均值不再變化，所以均值已經(jīng)收斂了。因此，該問題的答案為K1={2,3,4,10,11,12}和K2={20,30,25}。3.聚類分析算法分類3.聚類分析算法分類K-means優(yōu)缺點：此聚類分析算法伸縮性良好，并且針對大型數(shù)據(jù)集效率很高。初始的K-means算法缺點如下：(1)初始聚類中心選擇的好與壞將會對聚類結果的質量產(chǎn)生很大影響；(2)算法很容易陷入局部最優(yōu)解，有時會產(chǎn)生較差的結果；(3)算法開始時要求用戶給出聚類簇的個數(shù)k，而對于K值的選擇還沒有很好的準則可循；(4)對噪聲敏感；(5)只能在可以定義聚類的平均值的條件下才可以應用，即適合處理數(shù)值屬性的數(shù)據(jù)(6)聚類的最終結果也許會出現(xiàn)不平衡現(xiàn)象，不適合發(fā)現(xiàn)那些非凸面形狀的簇或者大小差別非常大的簇。3.聚類分析算法分類K-means優(yōu)缺點：3.聚類分析算法分類

2.K-medoids（中心點）

算法K-means算法對于孤立點敏感，一個極大值的對象可能在相當大的程度上扭曲數(shù)據(jù)的分布。k中心點算法不采用簇中對象的平均值作為簇中心，而選用簇中離平均值最近的對象作為簇中心，此種方法具有很好的抗噪聲的能力。以下是K-medoids算法的形式化描述：K-medoids聚類算法：輸入：具有n個