人工智能算法與實踐-第11章 K-Means算法

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

—

01算法概述PartTHREE—2

—

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

—

11.1算法概述—4

—

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

—

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

—

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

—

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

—

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

—

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

—

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

—

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

—

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

—

本實驗采用的數(shù)據(jù)集來自Python的sklearn包中自帶的Iris數(shù)據(jù)集。Iris數(shù)據(jù)集是常用的分類實驗數(shù)據(jù)集，由Fisher，1936收集整理。Iris也稱鳶尾花卉數(shù)據(jù)集，是一類多重變量分析的數(shù)據(jù)集。數(shù)據(jù)集包含150個數(shù)據(jù)樣本，分為3類，每類50個數(shù)據(jù)，每個數(shù)據(jù)包含4個屬性?？赏ㄟ^花萼長度、花萼寬度、花瓣長度、花瓣寬度4個屬性預(yù)測鳶尾花卉屬于3個種類（Setosa、Versicolour、Virginica）中的哪一類。11.3算法案例核心代碼—14

—

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

—

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

—

11.4算法總結(jié)—17

—

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