商務(wù)智能理論與應(yīng)用6kmeans算法

聚類分析K-means算法 李廣明2023/5/151第一頁，共三十九頁。聚類分析概念聚類與分類的不同在于：分類作為一種監(jiān)督學(xué)習(xí)方法，要求必須事先明確知道各個(gè)類別的信息，并且斷言所有待分類項(xiàng)都有一個(gè)類別與之對應(yīng)。但是很多時(shí)候上述條件得不到滿足，尤其是在處理海量數(shù)據(jù)的時(shí)候，如果通過預(yù)處理使得數(shù)據(jù)滿足分類算法的要求，則代價(jià)非常大，這時(shí)候可以考慮使用聚類算法。聚類屬于無監(jiān)督學(xué)習(xí)，相比于分類，聚類不依賴預(yù)定義的類和類標(biāo)號的訓(xùn)練實(shí)例。聚類分析指將物理或抽象對象的集合分組成為由類似的對象組成的多個(gè)類的分析過程。2023/5/152第二頁，共三十九頁。聚類算法可以用來完成對L維特征向量的分組。對應(yīng)于相同地面類型的點(diǎn)，如水，將其聚類在一起形成一組。一旦這樣分組以后，分析人員就可以通過每一組中的樣本點(diǎn)和地面數(shù)據(jù)的參考信息相聯(lián)系來識別地面類型。2023/5/153第三頁，共三十九頁。聚類分析中的數(shù)據(jù)類型2023/5/154第四頁，共三十九頁。相異度計(jì)算2023/5/155第五頁，共三十九頁。區(qū)間標(biāo)度變量2023/5/156第六頁，共三十九頁。對象間的相似度和相異度對象間的相似度和相異度是基于兩個(gè)對象間的距離來計(jì)算的。標(biāo)量也就是無方向意義的數(shù)字，也叫標(biāo)度變量。現(xiàn)在先考慮元素的所有特征屬性都是標(biāo)量的情況。例如，計(jì)算X={2,1,102}和Y={1,3,2}的相異度。一種很自然的想法是用兩者的歐幾里得距離來作為相異度，歐幾里得距離的定義如下：其意義就是兩個(gè)元素在歐氏空間中的集合距離，因?yàn)槠渲庇^易懂且可解釋性強(qiáng)，被廣泛用于標(biāo)識兩個(gè)標(biāo)量元素的相異度。將上面兩個(gè)示例數(shù)據(jù)代入公式，可得兩者的歐氏距離為：除歐氏距離外，常用作度量標(biāo)量相異度的還有曼哈頓距離和閔可夫斯基距離，兩者定義如下：

曼哈頓距離：

閔可夫斯基距離：2023/5/157第七頁，共三十九頁。規(guī)格化問題上面這樣計(jì)算相異度的方式有一點(diǎn)問題，就是取值范圍大的屬性對距離的影響高于取值范圍小的屬性。例如上述例子中第三個(gè)屬性的取值跨度遠(yuǎn)大于前兩個(gè)，這樣不利于真實(shí)反映真實(shí)的相異度，為了解決這個(gè)問題，一般要對屬性值進(jìn)行規(guī)格化。所謂規(guī)格化就是將各個(gè)屬性值按比例映射到相同的取值區(qū)間，這樣是為了平衡各個(gè)屬性對距離的影響。通常將各個(gè)屬性均映射到[0,1]區(qū)間，映射公式為：其中max(ai)和min(ai)表示所有元素項(xiàng)中第i個(gè)屬性的最大值和最小值。例如，將示例中的元素規(guī)格化到[0,1]區(qū)間后，就變成了X’={1,0,1}，Y’={0,1,0}，重新計(jì)算歐氏距離約為1.732。2023/5/158第八頁，共三十九頁。二元變量2023/5/159第九頁，共三十九頁。二元變量相異度-實(shí)例2023/5/1510第十頁，共三十九頁。分類與序數(shù)變量分類變量是二元變量的推廣，類似于程序中的枚舉變量，但各個(gè)值沒有數(shù)字或序數(shù)意義，如顏色、民族等等，對于分類變量，用“取值不同的同位屬性數(shù)/單個(gè)元素的全部屬性數(shù)”來標(biāo)識其相異度。序數(shù)變量是具有序數(shù)意義的分類變量，通?？梢园凑找欢樞蛞饬x排列，如冠軍、亞軍和季軍。對于序數(shù)變量，一般為每個(gè)值分配一個(gè)數(shù)，叫做這個(gè)值的秩，然后以秩代替原值當(dāng)做標(biāo)量屬性計(jì)算相異度。2023/5/1511第十一頁，共三十九頁。向量對象對于向量，由于它不僅有大小而且有方向，所以閔可夫斯基距離不是度量其相異度的好辦法，一種流行的做法是用兩個(gè)向量的余弦度量，其度量公式為：其中||X||表示X的歐幾里得范數(shù)。要注意，余弦度量度量的不是兩者的相異度，而是相似度！2023/5/1512第十二頁，共三十九頁。聚類分析方法的分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法基于約束的方法2023/5/1513第十三頁，共三十九頁。劃分方法基本思想：給定n個(gè)對象或數(shù)據(jù)元組的數(shù)據(jù)庫，劃分方法構(gòu)建數(shù)據(jù)的k個(gè)劃分，每一個(gè)劃分表示一個(gè)簇，k<=n。劃分方法創(chuàng)建一個(gè)初始劃分，然后采用迭代重定位技術(shù)，嘗試通過對象在組間的移動來改進(jìn)劃分。典型的劃分方法有（1）k均值算法，其中每個(gè)簇都用該簇中對象的均值來表示。（2）k中心點(diǎn)算法，其中每個(gè)簇用接近簇中心的一個(gè)對象來表示。它們的異同點(diǎn)有：k-均值算法和k-中心算法都屬于聚類分析中的劃分方法；k-均值算法是將簇中對象的均值作為簇的中心，可以是一個(gè)虛點(diǎn)，計(jì)算其他點(diǎn)與各個(gè)簇中心距離，歸入距離最近的簇中；k-中心算法是找簇中最中心的點(diǎn)作為簇中心，是一個(gè)實(shí)際存在數(shù)據(jù)點(diǎn)。這只是均值與中心區(qū)別，兩種算法具體流程還是不同的。2023/5/1514第十四頁，共三十九頁。K均值算法的由來k平均聚類發(fā)明于1956年，該算法最常見的形式是采用被稱為勞埃德算法(Lloydalgorithm)的迭代式改進(jìn)探索法。勞埃德算法首先把輸入點(diǎn)分成k個(gè)初始化分組，可以是隨機(jī)的或者使用一些啟發(fā)式數(shù)據(jù)。然后計(jì)算每組的中心點(diǎn)，根據(jù)中心點(diǎn)的位置把對象分到離它最近的中心，重新確定分組。繼續(xù)重復(fù)不斷地計(jì)算中心并重新分組，直到收斂，即對象不再改變分組（中心點(diǎn)位置不再改變）。2023/5/1515第十五頁，共三十九頁。K均值算法（1）K均值算法是基于質(zhì)心的技術(shù)，k均值算法以k為輸入?yún)?shù)，把n個(gè)對象集合分為k個(gè)簇，使得簇內(nèi)的相似度高，簇間的相似度低。簇的相似度是關(guān)于簇中對象的均值度量，可以看作簇的質(zhì)心。K均值算法的處理流程如下，首先，隨機(jī)的選擇k個(gè)對象，每個(gè)對象代表一個(gè)簇的初始均值，對剩余的每個(gè)對象，根據(jù)其與各個(gè)簇均值的距離。將它指派到最相似的簇。然后計(jì)算每個(gè)簇的新均值，這個(gè)過程不斷的重復(fù)，直到準(zhǔn)則函數(shù)收斂。通常采用平方誤差準(zhǔn)則

這里Jc（m）是數(shù)據(jù)庫中所有對象的平方誤差的總和，Xi是空間中的點(diǎn)，表示給定的數(shù)據(jù)對象，Zj是簇Cj的平均值（Xi和Zj都是多維的）。2023/5/1516第十六頁，共三十九頁。K均值算法（2）算法：k均值。用于劃分的k均值算法，每個(gè)簇的中心用簇中對象的均值來表示。輸入：k:簇的數(shù)目，

D:包含n個(gè)對象的數(shù)目集。輸出：k個(gè)簇的集合。方法：從D中任意選擇k個(gè)對象作為初始簇中心；Repeat根據(jù)簇中對象的均值，將每個(gè)對象（再）指派到最相似的簇更新簇均值，即計(jì)算每個(gè)簇中對象的均值Until不再發(fā)生變化2023/5/1517第十七頁，共三十九頁。K均值算法（3）2023/5/1518第十八頁，共三十九頁。K-MEANS示例下面，我們來看看k-means算法一個(gè)有趣的應(yīng)用示例：中國男足近幾年到底在亞洲處于幾流水平？下圖是我采集的亞洲15只球隊(duì)在2005年-2010年間大型杯賽的戰(zhàn)績其中包括兩次世界杯和一次亞洲杯。我提前對數(shù)據(jù)做了如下預(yù)處理：對于世界杯，進(jìn)入決賽圈則取其最終排名，沒有進(jìn)入決賽圈的，打入預(yù)選賽十強(qiáng)賽賦予40，預(yù)選賽小組未出線的賦予50。對于亞洲杯，前四名取其排名，八強(qiáng)賦予5，十六強(qiáng)賦予9，預(yù)選賽沒出現(xiàn)的賦予17。這樣做是為了使得所有數(shù)據(jù)變?yōu)闃?biāo)量，便于后續(xù)聚類。2023/5/1519第十九頁，共三十九頁。2023/5/1520第二十頁，共三十九頁。下面先對數(shù)據(jù)進(jìn)行[0,1]規(guī)格化，下表是規(guī)格化后的數(shù)據(jù)2023/5/1521第二十一頁，共三十九頁。

接著用k-means算法進(jìn)行聚類。設(shè)k=3，即將這15支球隊(duì)分成三個(gè)集團(tuán)?，F(xiàn)抽取日本、巴林和泰國的值作為三個(gè)簇的種子，即初始化三個(gè)簇的中心為A：{0.3,0,0.19}，B：{0.7,0.76,0.5}和C：{1,1,0.5}。（為什么選這三個(gè)呢？）下面，計(jì)算所有球隊(duì)分別對三個(gè)中心點(diǎn)的相異度，這里以歐氏距離度量。下面是用程序求取的結(jié)果：2023/5/1522第二十二頁，共三十九頁。

從左到右依次表示各支球隊(duì)到當(dāng)前中心點(diǎn)的歐氏距離，將每支球隊(duì)分到最近的簇，可對各支球隊(duì)做如下聚類：中國C，日本A，韓國A，伊朗A，沙特A，伊拉克C，卡塔爾C，阿聯(lián)酋C，烏茲別克斯坦B，泰國C，越南C，阿曼C，巴林B，朝鮮B，印尼C。第一次聚類結(jié)果：A：日本，韓國，伊朗，沙特；B：烏茲別克斯坦，巴林，朝鮮；C：中國，伊拉克，卡塔爾，阿聯(lián)酋，泰國，越南，阿曼，印尼。2023/5/1523第二十三頁，共三十九頁。下面根據(jù)第一次聚類結(jié)果，調(diào)整各個(gè)簇的中心點(diǎn)。A簇的新中心點(diǎn)為：{(0.3+0+0.24+0.3)/4=0.21,(0+0.15+0.76+0.76)/4=0.4175,(0.19+0.13+0.25+0.06)/4=0.1575}={0.21,0.4175,0.1575}（取簇中所有元素各自維度的算術(shù)平均數(shù)。）用同樣的方法計(jì)算得到B和C簇的新中心點(diǎn)分別為{0.7,0.7333,0.4167}，{1,0.94,0.40625}。2023/5/1524第二十四頁，共三十九頁。

用調(diào)整后的中心點(diǎn)再次進(jìn)行聚類，得到：第二次迭代后的結(jié)果為：中國C，日本A，韓國A，伊朗A，沙特A，伊拉克C，卡塔爾C，阿聯(lián)酋C，烏茲別克斯坦B，泰國C，越南C，阿曼C，巴林B，朝鮮B，印尼C。2023/5/1525第二十五頁，共三十九頁。結(jié)果無變化，說明結(jié)果已收斂，于是給出最終聚類結(jié)果：亞洲一流：日本，韓國，伊朗，沙特亞洲二流：烏茲別克斯坦，巴林，朝鮮亞洲三流：中國，伊拉克，卡塔爾，阿聯(lián)酋，泰國，越南，阿曼，印尼看來數(shù)據(jù)告訴我們，說國足近幾年處在亞洲三流水平真的是沒有冤枉他們，至少從國際杯賽戰(zhàn)績是這樣的。其實(shí)上面的分析數(shù)據(jù)不僅告訴了我們聚類信息，還提供了一些其它有趣的信息，例如從中可以定量分析出各個(gè)球隊(duì)之間的差距，例如，在亞洲一流隊(duì)伍中，日本與沙特水平最接近，而伊朗則相距他們較遠(yuǎn)，這也和近幾年伊朗沒落的實(shí)際相符。2023/5/1526第二十六頁，共三十九頁。K均值算法的優(yōu)點(diǎn)如果變量很大，k均值比層次聚類的計(jì)算速度更快（如果k很?。?。與層次聚類相比，k均值可以得到更緊密的簇，尤其是對于球狀簇。對大數(shù)據(jù)集，是可伸縮和高效率的。算法嘗試找出使平方誤差函數(shù)值最小的k個(gè)劃分。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯的時(shí)候，效果較好。2023/5/1527第二十七頁，共三十九頁。K均值算法的缺點(diǎn)沒有指明初始化均值的方法。常用的方法是隨機(jī)的選取k個(gè)樣本作為均值。產(chǎn)生的結(jié)果依賴于均值的初始值，經(jīng)常發(fā)生得到次優(yōu)劃分的情況。解決方法是多次嘗試不同的初始值。可能發(fā)生距離簇中心mi最近的樣本集為空的情況，因此，mi將得不到更新。這是一個(gè)必須處理的問題，但我們忽略該問題。結(jié)果依賴于||x-mi||的度量單位。一個(gè)常用的解決方法是用標(biāo)準(zhǔn)差規(guī)范各個(gè)變量，雖然這并非總是可取的。結(jié)果還依賴于k值，所以難以比較聚類結(jié)果的優(yōu)劣。不適合發(fā)現(xiàn)非凸面形狀的簇，并對噪聲和離群點(diǎn)數(shù)據(jù)是較敏感的，因?yàn)樯倭康倪@類數(shù)據(jù)能夠?qū)诞a(chǎn)生極大的影響。2023/5/1528第二十八頁，共三十九頁。K均值算法的改進(jìn)改進(jìn)措施：（1）樣本數(shù)據(jù)預(yù)處理。計(jì)算樣本對象兩兩之間的距離，篩掉與其它所有樣本的距離和最大的m個(gè)對象。（2）初始聚類中心的選擇。如不采用簇中的平均值作為參考點(diǎn)，而選用簇中位置最靠近中心的對象。這樣可以避免孤立點(diǎn)的影響。2023/5/1529第二十九頁，共三十九頁。K均值算法的變種首先采用層次凝聚算法決定結(jié)果簇的數(shù)目，并找到一個(gè)初始聚類，然后用迭代重定位來改進(jìn)該聚類。K眾數(shù)方法，它擴(kuò)展了k均值模式來聚類分類數(shù)據(jù)，用簇的眾數(shù)來取代簇均值，采用新的相異性度量處理分類對象，采用基于頻率的方法更新簇眾數(shù)。EM（期望最大化）算法，與k均值算法將每一個(gè)對象指派到一個(gè)簇相反，在EM算法中，每個(gè)對象按照權(quán)重指派到每個(gè)簇，其中權(quán)重表示對象的隸屬概率。2023/5/1530第三十頁，共三十九頁。假設(shè)數(shù)據(jù)挖掘的任務(wù)是將如下的八個(gè)點(diǎn)（用(x,y)代表位置）聚類為三個(gè)類。 A1(2,10),A2(2,5),A3(8,4),B1(5,8),B2(7,5),B3(6,4),C1(1,2),C2(4,9)2023/5/1531第三十一頁，共三十九頁。假設(shè)初始我們選擇A1,B1,和C1為每個(gè)簇的中心，用k-means算法來給出2023/5/1532第三十二頁，共三十九頁。A1-A2：dist=(2-2)2+(5-10)2=25;A1-A3:dist=(8-2)2+(4-10)2=72;A1-B2:dist=(7-2)2+(5-10)2=50;A1-B3:dist=(6-2)2+(4-10)2=52;A1-C2:dist=(4-2)2+(9-10)2=5;B1-A2:dist=(2-5)2+(5-8)2=18;B1-A3:dist=(8-5)2+(4-8)2=25;B1-B2:dist=(7-5)2+(5-8)2=13B1-B3:dist=(6-5)2+(4-8)2=172023/5/1533第三十三頁，共三十九頁。B1-C2:dist=(4-5)2+(9-8)2=2C1-A2:dist=(2-1)2+(5-2)2=10C1-A3:dist=(8-1)2+(4-2)2=53C1-B2:dist=(7-1)2+(5-2)2=45C1-B3:dist=(6-1)2+(4-2)2=29C1-C2:dist=(4-1)2+(9-2)2=582023/5/1534第三十四頁，共三十九頁。其他五個(gè)結(jié)點(diǎn)選擇與其最近的質(zhì)心，三個(gè)簇分別為：｛B1,C2,B3,B2,A3｝{C1,A2}{A1}計(jì)算這三個(gè)簇的質(zhì)心：｛B1,C2,B3,B2,A3｝的質(zhì)心為：(（8+5+7+6+4）/5,(4+8+5+4+9)/5)即（6，6）；｛C1,A2｝的質(zhì)心為：（（2+1）/2，（5+2）/2）即為（1.5,3.5）;{A1}的質(zhì)心為（2，10）。2023/5/1535第三十五頁，共三十九頁。在第一次循環(huán)執(zhí)行后的三個(gè)簇中心分別為（6，6），（1.5,3.5），（2，10）重新指派各個(gè)對象到離其最近的質(zhì)心，與上面方面相同，形成的三個(gè)簇為｛A3,B1,B2,B3｝，｛C1，A2｝，｛A1,C2｝三個(gè)簇的質(zhì)心分別為（6.5，5.25），（1.5