人工智能算法與實(shí)踐-第11章 K-Means算法

11.4算法總結(jié)11.1算法概述11.2算法原理11.3算法案例目錄第十一章K-Means算法人工智能算法與實(shí)踐—1

—

01算法概述PartTHREE—2

—

K-Means算法是一種基于距離的聚類(lèi)算法。因?yàn)樵撍惴ň哂蟹诸?lèi)速度快、分類(lèi)準(zhǔn)確率高等優(yōu)點(diǎn)，至今仍有許多人使用和改進(jìn)它，K-Means算法在聚類(lèi)算法中始終占據(jù)著非常重要的地位。K-Means算法是一種聚類(lèi)算法。提到聚類(lèi)，首先想到的是一個(gè)與之相似的概念，那就是分類(lèi)。那么分類(lèi)和聚類(lèi)是否為同一個(gè)概念呢？答案顯然是否定的。聚類(lèi)是指事先沒(méi)有“標(biāo)簽”而通過(guò)某種分析找出事物之間存在聚集性原因的過(guò)程，而分類(lèi)是按照某種標(biāo)準(zhǔn)給對(duì)象貼標(biāo)簽，再根據(jù)標(biāo)簽來(lái)區(qū)分歸類(lèi)。通俗地講，聚類(lèi)就是將相似的事物放在一起，而分類(lèi)更像是給事物分配標(biāo)簽。11.1算法概述—3

—

11.1算法概述—4

—

分類(lèi)和聚類(lèi)的區(qū)別02算法原理PartTWO—5

—

K-Means算法中的K代表的是K個(gè)簇，Means意為均值，即代表著每個(gè)簇中都選取各個(gè)數(shù)據(jù)的均值作為該簇的質(zhì)心，代表著整個(gè)簇。該算法的思想就是輸入簇?cái)?shù)K和包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集，最終輸出結(jié)果為K個(gè)簇，每個(gè)簇都滿足方差最小標(biāo)準(zhǔn)。劃分后的每個(gè)簇內(nèi)各個(gè)數(shù)據(jù)的相似性較高，而不同簇的各個(gè)數(shù)據(jù)之間的相似性較低。算法的定義如下：給定樣本集D={x1,x2,…,xi,…,xn}，xi代表一個(gè)數(shù)據(jù)樣本，其中每個(gè)數(shù)據(jù)樣本由m個(gè)屬性構(gòu)成。聚類(lèi)就是為了將所有樣本集劃分為一定數(shù)量的簇，簇用字母G表示，簇的個(gè)數(shù)用K表示。每個(gè)簇都有一個(gè)中心點(diǎn)即質(zhì)心，用μk表示。因此K-Means算法的原理就是將D={x1,x2,...xi,…,xn}通過(guò)聚類(lèi)劃分為G={G1,G2,…,Gu,…,Gk}的過(guò)程。11.2算法原理—6

—

誤差平方和（SumofSquaredError,SSE）是簇內(nèi)樣本相似性大小的代表，劃分好的某個(gè)簇Gu的誤差平方和越小，說(shuō)明該簇內(nèi)的樣本相似性越大；相反，Gu的誤差平方和越大，說(shuō)明該簇內(nèi)的樣本相似性越小。誤差平方和的計(jì)算公式如下：評(píng)價(jià)指標(biāo)—7

—

11.2算法原理（1）選擇合適的K值。（2）在樣本集D中隨機(jī)地選擇K個(gè)數(shù)據(jù)點(diǎn)，作為K個(gè)簇各自的質(zhì)心。（3）計(jì)算D中每個(gè)樣本到步驟（2）中選取的各個(gè)質(zhì)心的距離，選出每個(gè)樣本和所有質(zhì)心的距離中的最小值，并將該樣本歸類(lèi)到該質(zhì)心所代表的簇中去。（4）根據(jù)步驟（3）中所得的聚類(lèi)結(jié)果，重新計(jì)算K個(gè)簇各自的質(zhì)心，計(jì)算方法是計(jì)算每個(gè)簇中所有元素的平均值。（5）比較前后兩次SSE的差值和設(shè)定的閾值，若大于閾值，則重復(fù)步驟（3）和步驟（4）。（6）如果前后兩次的SSE的差值小于設(shè)定的閾值，則說(shuō)明聚類(lèi)完成。算法流程—8

—

11.2算法原理K值的選取—9

—

1經(jīng)驗(yàn)法根據(jù)經(jīng)驗(yàn)選擇代表點(diǎn)，然后根據(jù)問(wèn)題的性質(zhì)和數(shù)值的分布以直觀的方式尋找較為合適的K值。2手肘法手肘法的核心指標(biāo)就是SSE的值，思想就是逐步增大K的值，每個(gè)簇內(nèi)的聚合程度也會(huì)大幅度增加，即SSE的值會(huì)大幅度減少。當(dāng)K值逐漸取接近合適的值時(shí)，SSE值的減小幅度會(huì)越來(lái)越小，逐漸趨于平緩。11.2算法原理質(zhì)心的選擇—10

—

1隨機(jī)法多次運(yùn)行，每次運(yùn)行都使用一組不同的隨機(jī)樣本作為初始質(zhì)心，然后選擇具有最小SSE值的簇集。2層次聚類(lèi)法取一個(gè)樣本，并使用層次聚類(lèi)方法對(duì)其進(jìn)行聚類(lèi)。從層次聚類(lèi)中提取K個(gè)簇，并用這些簇的質(zhì)心作為初始的質(zhì)心。3取最遠(yuǎn)點(diǎn)法取所有點(diǎn)的質(zhì)心作為第一個(gè)質(zhì)心。然后，每個(gè)后繼質(zhì)心都選擇離已經(jīng)選擇過(guò)的初始質(zhì)心最遠(yuǎn)的點(diǎn)。11.2算法原理距離的選擇—11

—

1歐式距離2曼哈頓距離3余弦相似度11.2算法原理03算法案例PartTHREE—12

—

數(shù)據(jù)集的選擇—13

—

本實(shí)驗(yàn)采用的數(shù)據(jù)集來(lái)自Python的sklearn包中自帶的Iris數(shù)據(jù)集。Iris數(shù)據(jù)集是常用的分類(lèi)實(shí)驗(yàn)數(shù)據(jù)集，由Fisher，1936收集整理。Iris也稱(chēng)鳶尾花卉數(shù)據(jù)集，是一類(lèi)多重變量分析的數(shù)據(jù)集。數(shù)據(jù)集包含150個(gè)數(shù)據(jù)樣本，分為3類(lèi)，每類(lèi)50個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)包含4個(gè)屬性。可通過(guò)花萼長(zhǎng)度、花萼寬度、花瓣長(zhǎng)度、花瓣寬度4個(gè)屬性預(yù)測(cè)鳶尾花卉屬于3個(gè)種類(lèi)（Setosa、Versicolour、Virginica）中的哪一類(lèi)。11.3算法案例核心代碼—14

—

11.3算法案例1.計(jì)算距離（距離通常使用歐幾里得距離）2.初始化質(zhì)心3．K-Means算法實(shí)現(xiàn)過(guò)程—15

—

觀察圖11-6可以看到聚類(lèi)效果明顯。當(dāng)聚類(lèi)效果不佳時(shí)，可以通過(guò)改變K值的選取方式，如手肘法、輪廓系數(shù)法等，或者改變初始質(zhì)心的選擇方式來(lái)使聚類(lèi)效果更佳，也可以使用二分K-Means聚類(lèi)算法來(lái)加強(qiáng)聚類(lèi)效果11.3算法案例04算法總結(jié)PartFOUR—16

—

11.4算法總結(jié)—17

—

K-Means算法有著原理簡(jiǎn)單、容易實(shí)現(xiàn)、分類(lèi)速度快和分類(lèi)準(zhǔn)確率高等優(yōu)點(diǎn)，但同時(shí)該算法也有如下缺點(diǎn)。（1）K值很難確定。通常需要靠經(jīng)驗(yàn)來(lái)估計(jì)一個(gè)大概的K值，K值的選擇直接決定了聚類(lèi)的結(jié)果。（2）對(duì)噪聲和異常點(diǎn)敏感。K-Means算法很容易受到噪聲以及孤立點(diǎn)的影響，導(dǎo)致下一