商務(wù)智能理論與應(yīng)用6-k-means算法ppt課件

1、聚類分析K-means算法李廣明2022/7/101.聚類分析概念聚類與分類的不同在于：分類作為一種監(jiān)視學(xué)習(xí)方法，要求必需事先明確知道各個類別的信息，并且斷言一切待分類項(xiàng)都有一個類別與之對應(yīng)。但是很多時候上述條件得不到滿足，尤其是在處置海量數(shù)據(jù)的時候，假設(shè)經(jīng)過預(yù)處置使得數(shù)據(jù)滿足分類算法的要求，那么代價非常大，這時候可以思索運(yùn)用聚類算法。聚類屬于無監(jiān)視學(xué)習(xí)，相比于分類，聚類不依賴預(yù)定義的類和類標(biāo)號的訓(xùn)練實(shí)例。 聚類分析指將物理或籠統(tǒng)對象的集合分組成為由類似的對象組成的多個類的分析過程。2022/7/102.聚類算法可以用來完成對l維特征向量的分組。對應(yīng)于一樣地面類型的點(diǎn)，如水，將其聚類在一同構(gòu)成

2、一組。一旦這樣分組以后，分析人員就可以經(jīng)過每一組中的樣本點(diǎn)和地面數(shù)據(jù)的參考信息相聯(lián)絡(luò)來識別地面類型。2022/7/103.聚類分析中的數(shù)據(jù)類型2022/7/104.相異度計(jì)算2022/7/105.區(qū)間標(biāo)度變量2022/7/106.對象間的類似度和相異度對象間的類似度和相異度是基于兩個對象間的間隔來計(jì)算的。標(biāo)量也就是無方向意義的數(shù)字，也叫標(biāo)度變量。如今先思索元素的一切特征屬性都是標(biāo)量的情況。例如，計(jì)算X=2,1,102和Y=1,3,2的相異度。一種很自然的想法是用兩者的歐幾里得間隔來作為相異度，歐幾里得間隔的定義如下：其意義就是兩個元素在歐氏空間中的集合間隔，由于其直觀易懂且可解釋性強(qiáng)，被廣泛用

3、于標(biāo)識兩個標(biāo)量元素的相異度。將上面兩個例如數(shù)據(jù)代入公式，可得兩者的歐氏間隔為： 除歐氏間隔外，常用作度量標(biāo)量相異度的還有曼哈頓間隔和閔可夫斯基間隔，兩者定義如下： 曼哈頓間隔： 閔可夫斯基間隔： 2022/7/107.規(guī)格化問題上面這樣計(jì)算相異度的方式有一點(diǎn)問題，就是取值范圍大的屬性對間隔的影響高于取值范圍小的屬性。例如上述例子中第三個屬性的取值跨度遠(yuǎn)大于前兩個，這樣不利于真實(shí)反映真實(shí)的相異度，為理處理這個問題，普通要對屬性值進(jìn)展規(guī)格化。所謂規(guī)格化就是將各個屬性值按比例映射到一樣的取值區(qū)間，這樣是為了平衡各個屬性對間隔的影響。通常將各個屬性均映射到0,1區(qū)間，映射公式為： 其中max(ai)和

4、min(ai)表示一切元素項(xiàng)中第i個屬性的最大值和最小值。例如，將例如中的元素規(guī)格化到0,1區(qū)間后，就變成了X=1,0,1，Y=0,1,0，重新計(jì)算歐氏間隔約為1.732。 2022/7/108.二元變量2022/7/109.二元變量相異度-實(shí)例2022/7/1010.分類與序數(shù)變量分類變量是二元變量的推行，類似于程序中的枚舉變量，但各個值沒有數(shù)字或序數(shù)意義，如顏色、民族等等，對于分類變量，用“取值不同的同位屬性數(shù)/單個元素的全部屬性數(shù)來標(biāo)識其相異度。 序數(shù)變量是具有序數(shù)意義的分類變量，通?？梢园凑找欢樞蛞饬x陳列，如冠軍、亞軍和季軍。對于序數(shù)變量，普通為每個值分配一個數(shù)，叫做這個值的秩，然后

5、以秩替代原值當(dāng)做標(biāo)量屬性計(jì)算相異度。 2022/7/1011.向量對象對于向量，由于它不僅有大小而且有方向，所以閔可夫斯基間隔不是度量其相異度的好方法，一種流行的做法是用兩個向量的余弦度量，其度量公式為： 其中|X|表示X的歐幾里得范數(shù)。要留意，余弦度量度量的不是兩者的相異度，而是類似度！ 2022/7/1012.聚類分析方法的分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法基于約束的方法2022/7/1013.劃分方法根本思想：給定n個對象或數(shù)據(jù)元組的數(shù)據(jù)庫，劃分方法構(gòu)建數(shù)據(jù)的k個劃分，每一個劃分表示一個簇，k=n。劃分方法創(chuàng)建一個初始劃分，然后采用迭代重定位技術(shù)，嘗試經(jīng)過對象

6、在組間的挪動來改良劃分。典型的劃分方法有1k均值算法，其中每個簇都用該簇中對象的均值來表示。2k中心點(diǎn)算法，其中每個簇用接近簇中心的一個對象來表示。它們的異同點(diǎn)有：k-均值算法和k-中心算法都屬于聚類分析中的劃分方法；k-均值算法是將簇中對象的均值作為簇的中心，可以是一個虛點(diǎn)，計(jì)算其他點(diǎn)與各個簇中心間隔，歸入間隔最近的簇中；k-中心算法是找簇中最中心的點(diǎn)作為簇中心，是一個實(shí)踐存在數(shù)據(jù)點(diǎn)。這只是均值與中心區(qū)別，兩種算法詳細(xì)流程還是不同的。 2022/7/1014.K均值算法的由來k平均聚類發(fā)明于1956年， 該算法最常見的方式是采用被稱為勞埃德算法(Lloyd algorithm)的迭代式改良探

7、求法。勞埃德算法首先把輸入點(diǎn)分成k個初始化分組，可以是隨機(jī)的或者運(yùn)用一些啟發(fā)式數(shù)據(jù)。然后計(jì)算每組的中心點(diǎn)，根據(jù)中心點(diǎn)的位置把對象分到離它最近的中心，重新確定分組。繼續(xù)反復(fù)不斷地計(jì)算中心并重新分組，直到收斂，即對象不再改動分組中心點(diǎn)位置不再改動。 2022/7/1015.K均值算法1K均值算法是基于質(zhì)心的技術(shù)，k均值算法以k為輸入?yún)?shù)，把n個對象集合分為k個簇，使得簇內(nèi)的類似度高，簇間的類似度低。簇的類似度是關(guān)于簇中對象的均值度量，可以看作簇的質(zhì)心。K均值算法的處置流程如下，首先，隨機(jī)的選擇k個對象，每個對象代表一個簇的初始均值，對剩余的每個對象，根據(jù)其與各個簇均值的間隔。將它指派到最類似的簇。

8、然后計(jì)算每個簇的新均值，這個過程不斷的反復(fù)，直到準(zhǔn)那么函數(shù)收斂。通常采用平方誤差準(zhǔn)那么 這里Jcm是數(shù)據(jù)庫中一切對象的平方誤差的總和，Xi是空間中的點(diǎn)，表示給定的數(shù)據(jù)對象，Zj是簇Cj的平均值 Xi和Zj都是多維的。 2022/7/1016.K均值算法2算法：k均值。用于劃分的k均值算法，每個簇的中心用簇中對象的均值來表示。輸入：k:簇的數(shù)目， D:包含n個對象的數(shù)目集。輸出：k個簇的集合。方法：從D中恣意選擇k個對象作為初始簇中心；Repeat根據(jù)簇中對象的均值，將每個對象再指派到最類似的簇更新簇均值，即計(jì)算每個簇中對象的均值Until不再發(fā)生變化2022/7/1017.K均值算法32022

9、/7/1018.K-MEANS例如下面，我們來看看k-means算法一個有趣的運(yùn)用例如：中國男足近幾年究竟在亞洲處于幾流程度？以下圖是我采集的亞洲15只球隊(duì)在2005年-2021年間大型杯賽的戰(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ù)聚類。2022/7/1019.2022/7/1020.下面先對數(shù)據(jù)進(jìn)展0,1規(guī)格化，下表是規(guī)格化后的數(shù)據(jù)202

10、2/7/1021. 接著用k-means算法進(jìn)展聚類。設(shè)k=3，即將這15支球隊(duì)分成三個集團(tuán)。現(xiàn)抽取日本、巴林和泰國的值作為三個簇的種子，即初始化三個簇的中心為A：0.3, 0, 0.19，B：0.7, 0.76, 0.5和C：1, 1, 0.5。為什么選這三個呢？下面，計(jì)算一切球隊(duì)分別對三個中心點(diǎn)的相異度，這里以歐氏間隔度量。下面是用程序求取的結(jié)果：2022/7/1022.從左到右依次表示各支球隊(duì)到當(dāng)前中心點(diǎn)的歐氏間隔，將每支球隊(duì)分到最近的簇，可對各支球隊(duì)做如下聚類：中國C，日本A，韓國A，伊朗A，沙特A，伊拉克C，卡塔爾C，阿聯(lián)酋C，烏茲別克斯坦B，泰國C，越南C，阿曼C，巴林B，朝鮮B，

11、印尼C。第一次聚類結(jié)果：A：日本，韓國，伊朗，沙特；B：烏茲別克斯坦，巴林，朝鮮；C：中國，伊拉克，卡塔爾，阿聯(lián)酋，泰國，越南，阿曼，印尼。2022/7/1023.下面根據(jù)第一次聚類結(jié)果，調(diào)整各個簇的中心點(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。202

12、2/7/1024. 用調(diào)整后的中心點(diǎn)再次進(jìn)展聚類，得到：第二次迭代后的結(jié)果為：中國C，日本A，韓國A，伊朗A，沙特A，伊拉克C，卡塔爾C，阿聯(lián)酋C，烏茲別克斯坦B，泰國C，越南C，阿曼C，巴林B，朝鮮B，印尼C。2022/7/1025.結(jié)果無變化，闡明結(jié)果已收斂，于是給出最終聚類結(jié)果：亞洲一流：日本，韓國，伊朗，沙特亞洲二流：烏茲別克斯坦，巴林，朝鮮亞洲三流：中國，伊拉克，卡塔爾，阿聯(lián)酋，泰國，越南，阿曼，印尼看來數(shù)據(jù)通知我們，說國足近幾年處在亞洲三流程度真的是沒有冤枉他們，至少從國際杯賽戰(zhàn)績是這樣的。其實(shí)上面的分析數(shù)據(jù)不僅通知了我們聚類信息，還提供了一些其它有趣的信息，例如從中可以定量分析出

13、各個球隊(duì)之間的差距，例如，在亞洲一流隊(duì)伍中，日本與沙特程度最接近，而伊朗那么相距他們較遠(yuǎn)，這也和近幾年伊朗衰敗的實(shí)踐相符。 2022/7/1026.k均值算法的優(yōu)點(diǎn)假設(shè)變量很大，k均值比層次聚類的計(jì)算速度更快假設(shè)k很小。與層次聚類相比，k均值可以得到更嚴(yán)密的簇，尤其是對于球狀簇。對大數(shù)據(jù)集，是可伸縮和高效率的。算法嘗試找出使平方誤差函數(shù)值最小的k個劃分。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯的時候，效果較好。2022/7/1027.K均值算法的缺陷沒有指明初始化均值的方法。常用的方法是隨機(jī)的選取k個樣本作為均值。產(chǎn)生的結(jié)果依賴于均值的初始值，經(jīng)常發(fā)生得到次優(yōu)劃分的情況。處理方法是多次嘗試不同的

14、初始值。能夠發(fā)生間隔簇中心mi最近的樣本集為空的情況，因此， mi將得不到更新。這是一個必需處置的問題，但我們忽略該問題。結(jié)果依賴于|x- mi|的度量單位。一個常用的處理方法是用規(guī)范差規(guī)范各個變量，雖然這并非總是可取的。結(jié)果還依賴于k值，所以難以比較聚類結(jié)果的優(yōu)劣。不適宜發(fā)現(xiàn)非凸面外形的簇，并對噪聲和離群點(diǎn)數(shù)據(jù)是較敏感的，由于少量的這類數(shù)據(jù)可以對均值產(chǎn)生極大的影響。2022/7/1028.K均值算法的改良改良措施：1樣本數(shù)據(jù)預(yù)處置。計(jì)算樣本對象兩兩之間的間隔，篩掉與其它一切樣本的間隔和最大的m個對象。2初始聚類中心的選擇。如不采用簇中的平均值作為參考點(diǎn)，而選用簇中位置最接近中心的對象。這樣可

15、以防止孤立點(diǎn)的影響。2022/7/1029.K均值算法的變種首先采用層次凝聚算法決議結(jié)果簇的數(shù)目，并找到一個初始聚類，然后用迭代重定位來改良該聚類。K眾數(shù)方法，它擴(kuò)展了k均值方式來聚類分類數(shù)據(jù)，用簇的眾數(shù)來取代簇均值，采用新的相異性度量處置分類對象，采用基于頻率的方法更新簇眾數(shù)。EM期望最大化算法，與k均值算法將每一個對象指派到一個簇相反，在EM算法中，每個對象按照權(quán)重指派到每個簇，其中權(quán)重表示對象的隸屬概率。2022/7/1030.假設(shè)數(shù)據(jù)發(fā)掘的義務(wù)是將如下的八個點(diǎn)用(x,y)代表位置聚類為三個類。A1(2,10),A2(2,5),A3(8,4),B1(5,8),B2(7,5),B3(6,4

16、),C1(1,2),C2(4,9)2022/7/1031.假設(shè)初始我們選擇A1,B1,和C1為每個簇的中心，用k-means算法來給出2022/7/1032.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

17、-5)2+(5-8)2=13 B1-B3:dist=(6-5)2+(4-8)2=172022/7/1033.B1-C2:dist=(4-5)2+(9-8)2=2 C1-A2:dist=(2-1)2+(5-2)2=10 C1-A3:dist=(8-1)2+(4-2)2=53 C1-B2:dist=(7-1)2+(5-2)2=45 C1-B3:dist=(6-1)2+(4-2)2=29 C1-C2:dist=(4-1)2+(9-2)2=582022/7/1034.其他五個結(jié)點(diǎn)選擇與其最近的質(zhì)心，三個簇分別為：B1,C2,B3,B2,A3C1,A2A1計(jì)算這三個簇的質(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。2022/7/1035.在第一次循環(huán)執(zhí)行后的三個簇中心分別為6，6，1.5,3.5，2，10重新指派各個對象到離其最近的質(zhì)心，與上面方面一樣，構(gòu)成的三個簇為A3,B1,B2,B3，C1，A2，A1,C2