聚類(lèi)分析中K-means算法綜述

1、攻讀碩士學(xué)位研究生試卷（作業(yè)）封面（ 2015 至 2016 學(xué)年度第一學(xué)期）題 目 論文選讀 科 目 聚類(lèi)分析中K-means算法綜述 姓 名 王苑茹 專(zhuān) 業(yè) 計(jì)算機(jī)技術(shù) 入學(xué)年月 2015年8月 簡(jiǎn)短評(píng)語(yǔ)成績(jī)：授課教師簽字：聚類(lèi)分析中K-means算法綜述摘要:聚類(lèi)分析是數(shù)據(jù)挖掘中一個(gè)極其重要的研究方向，是一個(gè)將數(shù)據(jù)劃分成簇的方法或手段。聚類(lèi)分析可廣泛利用在商務(wù)智能，Web搜索，生物學(xué)以及圖像模式識(shí)別等眾多方面。本文主要敘述聚類(lèi)分析中的K-means聚類(lèi)算法，總結(jié)了K-means聚類(lèi)算法的研究現(xiàn)狀，并針對(duì)K-means算法的相關(guān)改進(jìn)做了綜述。關(guān)鍵詞：K-means聚類(lèi)算法；數(shù)據(jù)子集；聚類(lèi)中

2、心；相似性度量和距離矩陣Overview of K-means algorithm in clustering analysisAbstract:Clustering is major field in data mining which also is an important method of data partition or grouping. Clustering now has been applied into various ways in business intelligence,Web classification,biology,market and so on.In

3、 this paper, we introduce the spatial clustering rules,At the same time, the classical K-means algorithm is describe,And some related improvements to K-means algorithm are summarized.Key words: K-means clustering algorithm; number of clusters K; cluster initialization; distance metric1、引言K-means聚類(lèi)算法

4、是1955年由Steinhaus 、1957年 Lloyed、1965年 Ball & Hall、1967年 McQueen分別在他們各自研究的不同的科學(xué)領(lǐng)域獨(dú)立提出的?？臻g聚類(lèi)分析方法是空間數(shù)據(jù)挖掘理論中一個(gè)重要的領(lǐng)域，是從海量數(shù)據(jù)中發(fā)現(xiàn)知識(shí)的一個(gè)重要手段。k-means算法是空間聚類(lèi)算法中應(yīng)用非常廣泛的算法，同時(shí)它也在聚類(lèi)分析中起著重要作用。日益豐富的空間和非空間數(shù)據(jù)收集存儲(chǔ)于空間數(shù)據(jù)庫(kù)中，隨著空間數(shù)據(jù)的不斷膨脹，海量的空間數(shù)據(jù)的大小、復(fù)雜性都在快速增長(zhǎng)，遠(yuǎn)遠(yuǎn)超出了人們的解譯能力，從這些空間數(shù)據(jù)中發(fā)現(xiàn)鄰域知識(shí)迫切需求產(chǎn)生一個(gè)多學(xué)科、多鄰域綜合交叉的新興研究鄰域，空間數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)

5、而生。雖然k-means聚類(lèi)算法被提出已經(jīng)快60年了，但是目前仍然是應(yīng)用最為廣泛的劃分聚類(lèi)算法之一。容易實(shí)施、簡(jiǎn)單、高效、成功的應(yīng)用案例和經(jīng)驗(yàn)是其仍然流行的主要原因。本文主要敘述聚類(lèi)分析中的K-means聚類(lèi)算法，總結(jié)了K-means聚類(lèi)算法的研究現(xiàn)狀，并針對(duì)K-means算法的相關(guān)改進(jìn)做了綜述。2、經(jīng)典K-means算法2.1 K-means算法 k-means 聚類(lèi)算法是一種基于形心的劃分技術(shù)，是數(shù)據(jù)挖掘領(lǐng)域最為常用的聚類(lèi)方法之一，最初起源于信號(hào)處理領(lǐng)域。它的目標(biāo)是劃分整個(gè)樣本空間為若干個(gè)子空間，每個(gè)子空間中的樣本點(diǎn)距離該空間中心點(diǎn)平均距離最小。因此，k-means是劃分聚類(lèi)的一種。k-m

6、eans 算法接受輸入量 k ；然后將n個(gè)數(shù)據(jù)對(duì)象劃分為 k個(gè)聚類(lèi)以便使得所獲得的聚類(lèi)滿(mǎn)足：同一聚類(lèi)中的對(duì)象相似度較高；而不同聚類(lèi)中的對(duì)象相似度較小。聚類(lèi)相似度是利用各聚類(lèi)中對(duì)象的均值所獲得一個(gè)“中心對(duì)象”（引力中心）來(lái)進(jìn)行計(jì)算的。大體上說(shuō)，k-means 算法的工作過(guò)程說(shuō)明如下：首先從n個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類(lèi)中心；而對(duì)于所剩下其它對(duì)象，則根據(jù)它們與這些聚類(lèi)中心的相似度，分別將它們分配給與其最相似的聚類(lèi)；然后再計(jì)算每個(gè)所獲新聚類(lèi)的聚類(lèi)中心；不斷重復(fù)這一過(guò)程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開(kāi)始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù)。 k個(gè)聚類(lèi)具有以下特點(diǎn)：各聚類(lèi)本身盡可能的緊湊，而各聚類(lèi)

7、之間盡可能的分開(kāi)。假設(shè)數(shù)據(jù)集D包含n個(gè)歐氏空間中的對(duì)象。劃分方法把D中的對(duì)象分配到K個(gè)簇中，使得對(duì)象1i，jk,D且=Ø，一個(gè)目標(biāo)函數(shù)用來(lái)評(píng)估劃分的質(zhì)量，使得簇內(nèi)對(duì)象相互相似，而與其他簇中的對(duì)象相異。也就是說(shuō)，該目標(biāo)函數(shù)以簇內(nèi)高相似性和簇間低相似性為目標(biāo)?；谛涡牡膭澐旨夹g(shù)使用簇的形心代表該簇。對(duì)象s與該簇的代表之差用dist（s，）度量，其中dist（x，y）=sqrt( ()2 ) 這里i=1,2.n。簇的質(zhì)量可以用簇內(nèi)變差度量，它是中所有對(duì)象和形心之間的誤差的平方和，= （1） 其中，是數(shù)據(jù)集中所有對(duì)象的誤差的平方和；s是空間中的點(diǎn)，表示給定的數(shù)據(jù)對(duì)象；是簇的形心。2.2 k-

8、means算法流程k-means算法流程，首先，隨機(jī)的選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)聚類(lèi)的平均值或中心，對(duì)剩下的各個(gè)對(duì)象，根據(jù)其與每個(gè)聚類(lèi)中心的歐氏距離，將它派發(fā)給最相似的聚類(lèi)。之后，應(yīng)用更新之后的均值作為新的聚類(lèi)中心，再重新分配全部對(duì)象。繼續(xù)迭代，一直到分配趨于穩(wěn)定，也就是本輪迭代所形成聚類(lèi)與前一輪形成的聚類(lèi)相同。3、K-means聚類(lèi)算法的參數(shù)及其改進(jìn)k-means聚類(lèi)算法需要用戶(hù)指定 3個(gè)參數(shù)：類(lèi)別個(gè)數(shù)K，初始聚類(lèi)中心、相似性和距離度量。針對(duì)這3個(gè)參數(shù)，k-means聚類(lèi)算法出現(xiàn)了不同的改進(jìn)和變種。3.1 基于K值的改進(jìn) 在 k-means 算法中 k 是事先給定的，這個(gè) k 值

9、的選定是非常難以估計(jì)的。很多時(shí)候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類(lèi)別才最合適。這也是 k-means 算法的一個(gè)不足。有的算法是通過(guò)類(lèi)的自動(dòng)合并和分裂，得到較為合理的類(lèi)型數(shù)目 K，例如 ISODATA 算法。1) 解決方法-聚類(lèi)有效性函數(shù)根據(jù)聚類(lèi)有效性函數(shù)的方法是非常簡(jiǎn)單的一種解決方法，從2，的區(qū)間內(nèi)逐一選取k值，并利用該函數(shù)評(píng)價(jià)聚類(lèi)的效果，最終得到最優(yōu)的k值。中外有許多學(xué)者也是按照這種思想提出了一系列的解決方法。李永森等提出的距離代價(jià)函數(shù)綜合了類(lèi)際距離和類(lèi)內(nèi)距離兩項(xiàng)距離函數(shù)，類(lèi)際距離為所有聚類(lèi)中心到全域數(shù)據(jù)中心的距離之和。類(lèi)內(nèi)距離即所有類(lèi)中對(duì)象到其聚類(lèi)中心的距離之和。作者證明了當(dāng)距離

10、代價(jià)函數(shù)達(dá)到最小值時(shí)，空間聚類(lèi)結(jié)果為最優(yōu)，此時(shí)對(duì)應(yīng)的k 值為最佳聚類(lèi)數(shù)。 楊善林提出的距離代價(jià)函數(shù)作為空間聚類(lèi)的有效性檢驗(yàn)函數(shù), 就是當(dāng)距離代價(jià)函數(shù)達(dá)到最小值時(shí)侯, 以距離代價(jià)最小準(zhǔn)則實(shí)現(xiàn)了k 值優(yōu)化算法，空間聚類(lèi)結(jié)果為最優(yōu).根據(jù)經(jīng)驗(yàn)規(guī)則計(jì)算和確定最優(yōu)解的上界, 給出了求k值最優(yōu)解kopt及其上界kmax的條件, 并在理論上證明了經(jīng)驗(yàn)規(guī)則kmax的合理性.吳艷文等提出的通過(guò)提供相對(duì)較易得到的k 初值( 大于kopt) ,得k 個(gè)初始聚類(lèi)。分析聚類(lèi)之間相互關(guān)系,判斷那些聚類(lèi)應(yīng)是同一類(lèi),從而得到對(duì)k 值的優(yōu)化。 王朔等提出基于非模糊型集群評(píng)估指標(biāo)（DBI）的概念。該指標(biāo)主要利用幾何原理進(jìn)行運(yùn)算，分

11、別以聚類(lèi)間離散程度及位于同一類(lèi)內(nèi)數(shù)據(jù)對(duì)象的緊密程度為依據(jù)。即不同聚類(lèi)間的相異性高而同一類(lèi)內(nèi)數(shù)據(jù)對(duì)象的相似性高，并以此來(lái)進(jìn)行聚類(lèi)結(jié)果的評(píng)估。當(dāng)類(lèi)內(nèi)各數(shù)據(jù)對(duì)象間距離越小而類(lèi)間距離越大時(shí)指標(biāo)值則越小，代表各聚類(lèi)內(nèi)的數(shù)據(jù)對(duì)象越緊密且聚類(lèi)間的差異大。指標(biāo)值越小，表明此聚類(lèi)數(shù)目下聚類(lèi)結(jié)果越佳。DBI 值越小代表各聚類(lèi)內(nèi)數(shù)據(jù)相似度越大而類(lèi)間的相似度越小，由此得到最佳聚類(lèi)數(shù)目。2） 解決方案-遺傳算法Bandyopadhyay 等提出了GCUK 算法是基于遺傳算法的。此算法的染色體是運(yùn)用字符串方式來(lái)編碼的，也就是將每個(gè)初始的聚類(lèi)中心坐標(biāo)按照順序來(lái)進(jìn)行編碼，符號(hào)“#”來(lái)表示沒(méi)有作為初始聚類(lèi)中心的數(shù)據(jù)點(diǎn)，編碼完成

12、以后在逐代交叉運(yùn)算中最后得到了最優(yōu)k值。張?jiān)虑俚忍岢隽藘?yōu)化值參數(shù)是基于遺傳算法的。在遺傳算法中, 通過(guò)編碼來(lái)實(shí)現(xiàn)染色體。依據(jù)k-means算法要找到最佳的k值, 染色體的編碼既是對(duì)k值的編碼。在一般情況下，對(duì)于某類(lèi)問(wèn)題,總是有一聚類(lèi)的最大類(lèi)數(shù)MaxClassnum, 這個(gè)值即可由用戶(hù)來(lái)進(jìn)行輸入，也可以是給定的聚類(lèi)樣本個(gè)數(shù)。k是介于1和MaxClassnum之間的整數(shù)，可以使用二進(jìn)制串既染色體來(lái)表示。 胡彧等提出了由遺傳操作中的變異操作來(lái)控制k值的大小。變異操作的本質(zhì)是挖掘群體中個(gè)體的多樣性，同時(shí)提高算法的局部隨機(jī)搜索能力，防止出現(xiàn)未成熟收斂通過(guò)對(duì)個(gè)體適應(yīng)度函數(shù)的求解，決定聚類(lèi)數(shù)k值的變化方向。

13、由于最初所給的聚類(lèi)數(shù)k值并非是最佳聚類(lèi)數(shù)，因此將最初所給種群中具有最大適應(yīng)度值的個(gè)體做為最佳聚類(lèi)數(shù)的榜樣個(gè)體，其它個(gè)體的長(zhǎng)度(即k值)向榜樣個(gè)體的長(zhǎng)度靠擾。3） 其他方法 孫雪等提出了一種基于半監(jiān)督k-means 的k 值全局尋優(yōu)算法。 設(shè)初始少量數(shù)據(jù)集帶標(biāo)記的為監(jiān)督信息, 數(shù)據(jù)集無(wú)標(biāo)記的,監(jiān)督信息數(shù)據(jù)集的標(biāo)記為i和j.設(shè)k =2為初值, 在完整的數(shù)據(jù)集上來(lái)進(jìn)行const rained-k-means 聚類(lèi).當(dāng)k取不同值時(shí), 計(jì)算監(jiān)督信息中被錯(cuò)誤標(biāo)記的數(shù)據(jù)總數(shù)N，公式如下： （1）其中c 表示聚類(lèi)后各簇的標(biāo)號(hào);, 表示在第c簇中標(biāo)記的數(shù)據(jù)所占的比例為i , j .出現(xiàn)空簇的頻率取決于K值上限,

14、 當(dāng)出現(xiàn)空簇的頻率大于50 %時(shí), 則此時(shí)k被認(rèn)為已取得最大值.在k值優(yōu)化的整個(gè)過(guò)程中, 如果某一簇內(nèi)的監(jiān)督信息滿(mǎn)足以下條件, 即 閾值 （2）則該次聚類(lèi)結(jié)果被認(rèn)為是無(wú)效,保留有效的簇中心值,再開(kāi)始新一輪聚類(lèi),在中心點(diǎn)選擇上采取了半增量的迭代方式,提高了算法性能。上式閾值選取可采取重復(fù)實(shí)驗(yàn)的方法,一般當(dāng)與的數(shù)量相差較少時(shí),類(lèi)標(biāo)記為c的簇就為無(wú)效的簇.使N取得最小值的k取值就為k-means聚類(lèi)算法的最佳初值。田森平等提出了根據(jù)所需聚類(lèi)數(shù)據(jù)的分布的屬性，來(lái)計(jì)算他們間的距離，經(jīng)過(guò)這一系列變換，得到最終的聚類(lèi)參數(shù)k值。從需要聚類(lèi)的數(shù)據(jù)之中抽取出一部分樣本數(shù)據(jù)，來(lái)獲取聚類(lèi)參數(shù)的抽樣數(shù)據(jù)；再計(jì)算抽樣數(shù)據(jù)

15、間的距離來(lái)得到一沿對(duì)角線(xiàn)對(duì)稱(chēng)的距離矩陣，從這一距離矩陣之中找出一個(gè)大于零的最小距離即為mind() , 作為高密度半徑和簇劃分半徑的一個(gè)項(xiàng)，來(lái)保證這兩個(gè)半徑不會(huì)太?。粚?duì)距離矩陣按列求平均值，再對(duì)這些平均值求求平均值得到，根據(jù)| / 的誤差來(lái)去掉噪聲點(diǎn)，在噪聲點(diǎn)去除完全后，重新計(jì)算，根據(jù)和min d(), 求得了高密度半徑R。再找出min ，依據(jù), d()< min 的關(guān)系來(lái)得到高密度個(gè)數(shù)的參數(shù)Z；最終根據(jù)R和min d(), 獲得簇劃分的半徑r，合并簇的中心點(diǎn)之間距離m，合并簇的邊界點(diǎn)之間距離h。 綜上所述的研究可發(fā)現(xiàn)，學(xué)術(shù)界已經(jīng)提出了許多種K值的選取方法，并且分別基于不同的解決方法。3

16、.2 初始聚類(lèi)中心的選擇 k-means算法是貪心算法，在多項(xiàng)式時(shí)間內(nèi)，只能得到局部最優(yōu)。初始聚類(lèi)中心的選擇是隨機(jī)選取的，不同的初始聚類(lèi)中心選取方法得到的最終局部最優(yōu)結(jié)果也不同。所以可能造成在同一類(lèi)別的樣本被強(qiáng)制當(dāng)作兩個(gè)類(lèi)的初始聚類(lèi)中心，使得聚類(lèi)結(jié)果最終只能收斂于局部最優(yōu)解，k-means 算法的聚類(lèi)效果在很大的程度上依賴(lài)于初始聚類(lèi)中心的選擇，因此，大量的初始聚類(lèi)中心選取方案被提出。 袁方等提出了基于密度的優(yōu)化初始聚類(lèi)中心的方法，找到一組能反映數(shù)據(jù)分布特征的數(shù)據(jù)對(duì)象作為初始聚類(lèi)中心 首先計(jì)算數(shù)據(jù)對(duì)象所處區(qū)域的密度，來(lái)定義一個(gè)密度參數(shù)：以為中心，包含了常數(shù)Minpts 個(gè)數(shù)據(jù)對(duì)象的半徑稱(chēng)為對(duì)象的

17、密度參數(shù)，用表示。越大，則說(shuō)明數(shù)據(jù)對(duì)象所處區(qū)域的數(shù)據(jù)密度就越低。反之，越小，說(shuō)明數(shù)據(jù)對(duì)象所處區(qū)域的數(shù)據(jù)密度越高。通過(guò)計(jì)算每個(gè)數(shù)據(jù)對(duì)象的密度參數(shù)，就可以發(fā)現(xiàn)處于高密度區(qū)域的點(diǎn)，從而得到一個(gè)高密度點(diǎn)集合D。在D中取處于最高密度區(qū)域的數(shù)據(jù)對(duì)象作為第1 個(gè)聚類(lèi)中心z；取距離z最遠(yuǎn)的一個(gè)高密度點(diǎn)作第2個(gè)聚類(lèi)中心z ；計(jì)算D 中各數(shù)據(jù)對(duì)象到z,z的距離 d( ,z )，d( ,z )，z為滿(mǎn)足max(min(d( ,z ), d( ,z ) i =1, 2,n的數(shù)據(jù)對(duì)象 ；為滿(mǎn)足max(min(d( ,z ), d( ,z ),.,d(,) i =1,2,n的數(shù)據(jù)對(duì)象 ,D。依此得到k個(gè)初始聚類(lèi)中心。秦鈺

18、等提出了探測(cè)數(shù)據(jù)集中的相對(duì)密集區(qū)域, 再利用這些密集區(qū)域生成初始類(lèi)中心點(diǎn)。該方法能夠很好地排除類(lèi)邊緣點(diǎn)和噪聲點(diǎn)的影響, 并且能夠適應(yīng)數(shù)據(jù)集中各個(gè)實(shí)際類(lèi)別密度分布不平衡的情況, 最終獲得較好的聚類(lèi)效果。利用UPGMA 層次聚類(lèi)算法初期匯聚效果好的優(yōu)勢(shì), 發(fā)現(xiàn)數(shù)據(jù)集中的密集區(qū)域, 避免類(lèi)邊緣點(diǎn)或噪聲點(diǎn)成為初始類(lèi)中心點(diǎn), 同時(shí), 著重于考慮區(qū)域的相對(duì)密集程度, 改變UGPMA 算法的停止條件, 使子樹(shù)的生成停止在不同的聚類(lèi)層次上, 以適應(yīng)各個(gè)實(shí)際類(lèi)別密度不平衡的數(shù)據(jù)集。 賴(lài)玉霞等提出了根據(jù)數(shù)據(jù)的自然分布來(lái)選取初始聚類(lèi)中心, 找出對(duì)象中分布比較密集的區(qū)域, 這正是聚類(lèi)的目的, 從而擺脫了隨機(jī)選取聚類(lèi)中

19、心對(duì)聚類(lèi)結(jié)果產(chǎn)生的不穩(wěn)定性, 以及用質(zhì)心代表一個(gè)簇所帶來(lái)的“噪聲”和孤立點(diǎn)數(shù)據(jù)對(duì)聚類(lèi)結(jié)果的影響。黃敏等提出了在基于高密度點(diǎn)分布的算法基礎(chǔ)上，解決了當(dāng)高密度點(diǎn)分布不只一個(gè)時(shí)如何選取聚類(lèi)中心的問(wèn)題。找到最大者作為聚類(lèi)中心點(diǎn)，并將與聚類(lèi)中心的距離小于樣本平均距離的點(diǎn)的密度參數(shù)從密度參數(shù)集合中刪除。周愛(ài)武等提出了的算法的改進(jìn)建立在沒(méi)有離群點(diǎn)的數(shù)據(jù)集上,通過(guò)求次小距離的樣本點(diǎn)的中心， 然后求出此中心與一個(gè)聚類(lèi)中心之間的距離， 與樣本點(diǎn)之間的平均距離進(jìn)行判斷。如果小于樣本點(diǎn)之間的平均距離， 則將此樣本點(diǎn)加入初始化集合中， 再求第三距離小的樣本點(diǎn)，如果大于樣本點(diǎn)之間的平均距離， 則求出此中心存入二維數(shù)據(jù)樣本

20、點(diǎn)中心 。集合二維數(shù)據(jù)樣本點(diǎn)中心中的個(gè)數(shù)等于k， 初始聚類(lèi)中心全部找到。 周煒奔等提出了基于密度、中心點(diǎn)的初始化中心算法，首先算出樣本數(shù)據(jù)集之中每個(gè)樣本密度，得到一個(gè)以密度為標(biāo)準(zhǔn)的樣本集合。然后在標(biāo)準(zhǔn)樣本集合基礎(chǔ)上進(jìn)行初始聚類(lèi)中心的選取和簇的劃分。每劃分出一個(gè)簇，就從標(biāo)準(zhǔn)樣本集合中刪除該簇所包括的數(shù)據(jù)點(diǎn)。鄭丹等提出了基于k-means聚類(lèi)算法對(duì)初始聚類(lèi)中心敏感的這一特點(diǎn)的改進(jìn)算法。k-means聚類(lèi)算法中，數(shù)據(jù)對(duì)象間的相似性是根據(jù)歐氏距離衡量的，距離越小則說(shuō)明越相似。用DK圖對(duì)k-dist圖進(jìn)行分析，找出對(duì)應(yīng)密度水平的平緩曲線(xiàn)。在不同的密度水平上分別選擇一個(gè)k-dist值最小即密度相對(duì)最大的點(diǎn)

21、作為初始聚類(lèi)中心。根據(jù)上述原理，在總數(shù)為k的數(shù)據(jù)集之中找出q個(gè)密度相對(duì)與其它點(diǎn)最大的點(diǎn)來(lái)作為初始聚類(lèi)中心。相比確定k值，優(yōu)化算法應(yīng)用于初始聚類(lèi)中心的選擇更加合適，目前已經(jīng)提出了許多比較成熟的算法，并且已經(jīng)有相關(guān)的專(zhuān)著問(wèn)世。3.3 相似性度量和距離矩陣 k-means聚類(lèi)算法使用歐式距離作為相似性度量和距離矩陣，計(jì)算各數(shù)據(jù)點(diǎn)到其類(lèi)別中心的距離平方和。因此，k-means聚類(lèi)算法劃分出來(lái)的類(lèi)別店鋪是類(lèi)球形的。實(shí)際上，歐式距離是Minkowski距離在時(shí)的特例，即距離。在采用距離進(jìn)行K-means聚類(lèi)時(shí)，最終類(lèi)中心應(yīng)是每一類(lèi)的m中心向量。Kashima等人于2008年使用距離，最終聚類(lèi)中心使每一類(lèi)的

22、中位向量。對(duì)于一維數(shù)據(jù)而言，中位數(shù)M比均值x對(duì)異常數(shù)據(jù)有較強(qiáng)的抗干擾性，聚類(lèi)結(jié)果受數(shù)據(jù)中異常值的影響較小。Mao&Jain于1996年提出使用Mahalanobis距離，但計(jì)算代價(jià)太大。在應(yīng)用中，Linde等。于1980年提出使用Itakura-Saito距離。Banerjee等人2004年提出，如果使用Bregman差異作為距離度量，有許多突出優(yōu)點(diǎn)，如克服局部最優(yōu)、類(lèi)別之間的線(xiàn)性分離、線(xiàn)性時(shí)間復(fù)雜度等。4、結(jié)束語(yǔ) k-means聚類(lèi)算法是一種非常優(yōu)秀的算法，以其簡(jiǎn)單的算法思想、較快的聚類(lèi)速度和良好的聚類(lèi)效果得到了廣泛的應(yīng)用。對(duì)于該算法在聚類(lèi)過(guò)程中暴露出的若干問(wèn)題，本文對(duì)其中k值確定、

23、初始聚類(lèi)中心選擇等主要問(wèn)題進(jìn)行了綜述。因此k-means聚類(lèi)算法是一個(gè)貪心算法，在多項(xiàng)式時(shí)間內(nèi)，僅能獲得局部最優(yōu)，對(duì) k-means聚類(lèi)算法的研究也將繼續(xù)。參考文獻(xiàn) ： 1 Anil K J. Data clustering: 50 years beyond K-Means J. Pattern Recognition Letters, 2010, 31(8): 651-666.2Jiawei han;Micheline Kamber;Jian Pei.Data Mining:Concepts and Techniques,Third EditionJ.2015.73李永森，楊善林，馬溪駿等 空間聚類(lèi)算法中的K 值優(yōu)化問(wèn)題研究J系統(tǒng)仿真學(xué)報(bào)，2006,18( 3) : 573 5764楊善林, 李永森, 胡笑旋, 等.k-means算法中的k值優(yōu)化問(wèn)題研究 J .系統(tǒng)工程理論與實(shí)踐, 2006,(2):97 -101.5吳艷文,胡學(xué)鋼.一種K_means算法的k值優(yōu)化方案J.巢湖學(xué)院學(xué)報(bào).2007,9(6):21-14.6王朔顧,進(jìn)廣.基于K 值改進(jìn)的Kmeans 算法在入侵檢測(cè)中的應(yīng)用J.工業(yè)控制計(jì)算機(jī),2014,27(7):93-97.7Bandyopadhyay S,Maulik U.Genetic Cluste