K-means-聚類算法研究綜述

K-means聚類算法研究綜述摘要:總結(jié)評述了K-means聚類算法的研究現(xiàn)狀，指出K-means聚類算法是一個NP難優(yōu)化問題，無法獲得全局最優(yōu)。介紹了K-means聚類算法的目標函數(shù)，算法流程，并列舉了一個實例，指出了數(shù)據(jù)子集的數(shù)目K，初始聚類中心選取，相似性度量和距離矩陣為K-means聚類算法的3個根本參數(shù)?？偨Y(jié)了K-means聚類算法存在的問題及其改良算法，指出了K-means聚類的進一步研究方向。關(guān)鍵詞：K-means聚類算法；NP難優(yōu)化問題；數(shù)據(jù)子集的數(shù)目K；初始聚類中心選??；相似性度量和距離矩陣ReviewofK-meansclusteringalgorithmAbstract:K-meansclusteringalgorithmisreviewed.K-meansclusteringalgorithmisaNPhardoptimalproblemandglobaloptimalresultcannotbereached.Thegoal，mainstepsandexampleofK-meansclusteringalgorithmareintroduced.K-meansalgorithmrequiresthreeuser-specifiedparameters:numberofclustersK，clusterinitialization，anddistancemetric.ProblemsandimprovementofK-meansclusteringalgorithmaresummarizedthen.FurtherstudydirectionsofK-meansclusteringalgorithmarepointedatlast.Keywords:K-meansclusteringalgorithm;NPhardoptimalproblem;numberofclustersK;clusterinitialization;distancemetricK-means聚類算法是由Steinhaus1955年、Lloyed1957年、Ball&Hall1965年、McQueen1967年分別在各自的不同的科學研究領(lǐng)域獨立的提出。K-means聚類算法被提出來后，在不同的學科領(lǐng)域被廣泛研究和應(yīng)用，并開展出大量不同的改良算法。雖然K-means聚類算法被提出已經(jīng)超過50年了，但目前仍然是應(yīng)用最廣泛的劃分聚類算法之一[1]。容易實施、簡單、高效、成功的應(yīng)用案例和經(jīng)驗是其仍然流行的主要原因。文中總結(jié)評述了K-means聚類算法的研究現(xiàn)狀，指出K-means聚類算法是一個NP難優(yōu)化問題，無法獲得全局最優(yōu)。介紹了K-means聚類算法的目標函數(shù)、算法流程，并列舉了一個實例，指出了數(shù)據(jù)子集的數(shù)目K、初始聚類中心選取、相似性度量和距離矩陣為K-means聚類算法的3個根本參數(shù)。總結(jié)了K-means聚類算法存在的問題及其改良算法，指出了K-means聚類的進一步研究方向。1經(jīng)典K-means聚類算法簡介K-means聚類算法的目標函數(shù)對于給定的一個包含n個d維數(shù)據(jù)點的數(shù)據(jù)集，其中，以及要生成的數(shù)據(jù)子集的數(shù)目K，K-means聚類算法將數(shù)據(jù)對象組織為K個劃分。每個劃分代表一個類，每個類有一個類別中心。選取歐氏距離作為相似性和距離判斷準那么，計算該類內(nèi)各點到聚類中心的距離平方和〔1〕聚類目標是使各類總的距離平方和最小。〔2〕其中，，顯然，根據(jù)最小二乘法和拉格朗日原理，聚類中心應(yīng)該取為類別類各數(shù)據(jù)點的平均值。K-means聚類算法從一個初始的K類別劃分開始，然后將各數(shù)據(jù)點指派到各個類別中，以減小總的距離平方和。因為K-means聚類算法中總的距離平方和隨著類別個數(shù)K的增加而趨向于減小〔當時，〕。因此，總的距離平方和只能在某個確定的類別個數(shù)K下，取得最小值。1.2K-means算法的算法流程K-means算法是一個反復(fù)迭代過程,目的是使聚類域中所有的樣品到聚類中心距離的平方和最小，算法流程包括4個步驟[1]，具體流程圖如圖1所示。11)選定數(shù)據(jù)空間中K個對象作為初始聚類中心，每個對象代表一個類別的中心2)對于樣品中的數(shù)據(jù)對象，那么根據(jù)它們與這些聚類中心的歐氏距離，按距離最近的準那么分別將它們分配給與其最相似的聚類中心所代表的類3)計算每個類別中所有對象的均值作為該類別的新聚類中心，計算所有樣本到其所在類別聚類中心的距離平方和，即值4)聚類中心和值發(fā)生改變？聚類結(jié)束是否圖1K-means聚類算法流程圖Fig.1StepsofK-meansclusteringalgorithmK-means聚類算法實例圖2顯示的是K-means算法將一個2維數(shù)據(jù)集聚成3類的過程示意圖。K-means聚類算法是一個NP難優(yōu)化問題K-means聚類算法是一個NP難優(yōu)化問題嗎？在某個確定的類別個數(shù)K下，在多項式時間內(nèi)，最小的總距離平方和值和對應(yīng)的聚類劃分能否得到？目前，不同的學者有不同的答案。AristidisLikas等人[2]認為在多項式時間內(nèi)最小的值和對應(yīng)的聚類劃分能夠得到，并于2002年提出了全局最優(yōu)的K-means聚類算法。但給出的“TheglobalK-meansclusteringalgorithm〞只有初始聚類中心選取的算法步驟，而缺乏理論證明。很快，pierreHansen等人[3]就提出“TheglobalK-meansclusteringalgorithm〞不過是一個啟發(fā)式增量算法，并不能保證得到全局最優(yōu)，文章最后還給出了反例。很多學者指出，如果數(shù)據(jù)點的維數(shù)，最小的總距離平方和值和對應(yīng)的聚類劃分能夠在時間內(nèi)使用動態(tài)規(guī)劃獲得，例如BellmanandDreyfus[4]。PierreHansen等人[3]認為,K-means聚類算法時間復(fù)雜度未知。但是，更多的學者認為，對于一般的數(shù)據(jù)維數(shù)d和類別個數(shù)K，K-means聚類算法是一個NP難優(yōu)化問題[5]。SanjoyDasgupta等人認為即使在類別個數(shù)K=2的情況下，K-means聚類算法也是一個NP難優(yōu)化問題。MeenaMahajan等人[6]認為即使在數(shù)據(jù)點的維數(shù)下，對于平面的K-means聚類問題，也是NP難的。本研究也認為，對于一般的數(shù)據(jù)維數(shù)d和類別個數(shù)K，K-means聚類算法是一個NP難優(yōu)化問題。K-means聚類算法是一個貪心算法，在多項式時間內(nèi)，僅能獲得局部最優(yōu)，而不可能獲得全局最優(yōu)。(a)將被分成3類的2維原始輸入數(shù)據(jù)(b)選擇3個種子數(shù)據(jù)點作為3個類的初始聚類中心(a)two-dimensionalinputdatawiththreeclusters(b)Threeseedpointsselectedasclustercentersandinitialassignmentofthedatapointstoclusters(c)更新聚類類別和類別中心的第二次迭代過程(d)更新聚類類別和類別中心的第3次的迭代過程(e)K-means聚類算法收斂所獲得的最終聚類結(jié)果(c)steptwoofintermediateliterationsupdating(d)Stepthreeofintermediateiterationsupdating(e)finalclusteringobtainedbyK-meansalgorithmclusterlabelsandtheircentersclusterlabelsandtheircentersatconvergence圖2K-means算法示意圖Fig.2IllustrationofK-meansalgorithm3K-means聚類算法的參數(shù)及其改良K-means聚類算法需要用戶指定3個參數(shù)：類別個數(shù)K，初始聚類中心、相似性和距離度量。針對這3個參數(shù)，K-means聚類算法出現(xiàn)了不同的改良和變種。3.1類別個數(shù)KK-means聚類算法最被人所詬病的是類別個數(shù)K的選擇。因為缺少嚴格的數(shù)學準那么，學者們提出了大量的啟發(fā)式和貪婪準那么來選擇類別個數(shù)K。最有代表性的是，令K逐漸增加，如，因為K-means聚類算法中總的距離平方和J隨著類別個數(shù)K的增加而單調(diào)減少。最初由于K較小，類型的分裂〔增加〕會使J值迅速減小，但當K增加到一定數(shù)值時，J值減小速度會減慢，直到當K等于總樣本數(shù)N時，，這時意味著每類樣本自成一類，每個樣本就是聚類中心。如圖3所示，曲線的拐點A對應(yīng)著接近最優(yōu)的K值，最優(yōu)K值是對J值減小量、計算量以及分類效果等進行權(quán)衡得出的結(jié)果。而在實際應(yīng)用中，經(jīng)常對同一數(shù)據(jù)集，取不同的K值，獨立運行K-means聚類算法，然后由領(lǐng)域?qū)＜疫x取最有意義的聚類劃分結(jié)果。圖3J-K關(guān)系曲線Fig.3RelationshipcurvebetweenJandK并非所有的情況都容易找到J-K關(guān)系曲線的拐點，此時K值將無法確定。對類別個數(shù)K的選擇改良的算法是Ball&Hall[7]于1965年提出的迭代自組織的數(shù)據(jù)分析算法〔IterativeSelf-organizingDataAnalysisTechniqueAlgorithm,ISODATA〕，該算法在運算的過程中聚類中心的數(shù)目不是固定不變的，而是反復(fù)進行修改，以得到較合理的類別數(shù)K，這種修改通過模式類的合并和分裂來實現(xiàn)，合并與分裂在一組預(yù)先選定的參數(shù)指導(dǎo)下進行。3.2初始聚類中心的選取越來越多的學者傾向于認為最小化總距離平方和值和對應(yīng)的聚類劃分是一個ＮＰ難優(yōu)化問題。因此，K-means聚類算法是一個貪心算法，在多項式時間內(nèi)，僅能獲得局部最優(yōu)。而不同的初始聚類中心選取方法得到的最終局部最優(yōu)結(jié)果不同。因此，大量的初始聚類中心選取方案被提出。經(jīng)典的K-means聚類算法的初始聚類中心是隨機選取的。SelimSZ,Al-SultanKS于1991年提出的隨機重啟動K-means聚類算法是目前工程中應(yīng)用最廣泛的初始聚類中心選取方法，其過程如圖4所示。王成等人提出使用最大最小原那么來選取初始聚類中心[8]，與其它方法不同的是，該過程是一個確定性過程。模擬退火、生物遺傳等優(yōu)化搜索算法也被用于K-means聚類算法初始聚類中心的選取。四種初始聚類中心選取方法的比擬可見文獻[9]。自從AristidisLikas等人[2]提出“TheglobalK-meansclusteringalgorithm〞，對其的批評[3]、討論和改良就沒有停止過[10]。用戶指定重啟動次數(shù)用戶指定重啟動次數(shù)N，初始化計數(shù)隨機選擇初始聚類中心K-means聚類計數(shù)次數(shù)加1選擇J值最小的聚類方案聚類結(jié)束否是圖4屢次重啟動K-means聚類算法流程圖Fig.4StepsofmultiplerestartsK-meansclusteringalgorithm3.3相似性度量和距離矩陣K-means聚類算法使用歐式距離作為相似性度量和距離矩陣，計算各數(shù)據(jù)點到其類別中心的距離平方和。因此，K-means聚類算法劃分出來的類別店鋪是類球形的。實際上，歐式距離是Minkowski距離在時的特例，即距離。在采用距離進行K-means聚類時，最終類中心應(yīng)是每一類的m中心向量。Kashima等人于2023年使用距離，最終聚類中心使每一類的中位向量。對于一維數(shù)據(jù)而言，中位數(shù)M比均值x對異常數(shù)據(jù)有較強的抗干擾性，聚類結(jié)果受數(shù)據(jù)中異常值的影響較小。Mao&Jain[11]于1996年提出使用Mahalanobis距離，但計算代價太大。在應(yīng)用中，Linde等。于1980年提出使用Itakura-Saito距離。Banerjee等人2004年提出，如果使用Bregman差異作為距離度量，有許多突出優(yōu)點，如克服局部最優(yōu)、類別之間的線性別離、線性時間復(fù)雜度等。4K-means聚類算法的其他改良在K-means聚類算法中，每個數(shù)據(jù)點都被唯一的劃分到一個類別中，這被稱為硬聚類算法，它不易處理聚類不是致密而是殼形的情形。模糊聚類算法能擺脫這些限制，這些方法是過去20年間集中研究的課題。在模糊方法中，數(shù)據(jù)點可以同時屬于多個聚類，Dunn等人[12]于1973年提出了模糊K-means聚類算法。5結(jié)束語筆者也相信K-means聚類是一個NP難優(yōu)化問題，但這需要更加嚴格的數(shù)學理論證明。因此K-means聚類算法是一個貪心算法，在多項式時間內(nèi)，僅能獲得局部最優(yōu)，對K-means聚類算法的研究也將繼續(xù)。但是對K-means聚類算法的研究和改良應(yīng)注意以下幾點：1〕筆者感興趣的是現(xiàn)實世界問題的實際解決方案，模式分析算法必須能處理非常大的數(shù)據(jù)集。所以，只在小規(guī)模的例子上運行良好是不夠的；我們要求他的性能按比例延伸到大的數(shù)據(jù)集上，也就是高效算法〔efficientalgorithm〕。2〕在現(xiàn)實生活應(yīng)用中數(shù)據(jù)里經(jīng)?；煊杏捎谌藶檎`差而引起的噪聲。我們要求算法能夠處理混有噪聲的數(shù)據(jù)，并識別近似模式。只要噪聲不過多地影響輸出，這些算法應(yīng)能容忍少量的噪聲，稱為算法的健壯性〔robust〕。相對于距離，距離有較強的健壯性。但相似性度量和距離矩陣的選取，不是一個理論問題，而是一個應(yīng)用問題，需要根據(jù)問題和應(yīng)用需要需求，假定適宜的模型。例如，采用不同的距離，K-means聚類的結(jié)果一般是不同的。3〕統(tǒng)計穩(wěn)定性即算法識別的模式確實是數(shù)據(jù)源的真實模式，而不只是出現(xiàn)在有限訓(xùn)練集內(nèi)的偶然關(guān)系。如果我們在來自同一數(shù)據(jù)源的新樣本上重新運行算法，它應(yīng)該識別出相似的模式，從這個意義上講，可以把這個性質(zhì)看作輸出在統(tǒng)計上的健壯性。樣本讀入次序不同，一些聚類算法獲得的模式完全不同，而另一些聚類算法對樣本讀入次序不敏感。從這個角度來講，最大最小原那么比隨機重啟動、模擬退火、生物遺傳在初始聚類中心選取上要好。4〕K-means聚類算法的很多變種引入了許多由用戶指定的新參數(shù)，對這些參數(shù)又如何自動尋優(yōu)確定，是一個不斷深入和開展的過程。5〕K-means還存在一個類別自動合并問題[1]，在聚類過程中產(chǎn)生某一類中無對象的情況，使得得到的類別數(shù)少于用戶指定的類別數(shù)，從而產(chǎn)生錯誤，能影響分類結(jié)果。其原因需要在理論上深入探討,但這方面的論文和研究很少。聚類的意義，這也是所有的聚類算法都面臨的問題，需要在數(shù)學理論和應(yīng)用兩方面開展研究。參考文獻：[1]AnilKJ.Dataclustering:50yearsbeyondK-Means[J].PatternRecognitionLetters,2023,31(8):651-666.[2]LikasA,VlassisM,VerbeekJ.TheglobalK-meansclusteringalgorithm[J].PatternRecognition,2003,36(2):451-461.[3]SelimSZ，Al-SultanKS.AnalysisofglobalK-means，anincrementalheuristicforminimumsum-of-squaresclustering[J].JournalofClassification，2005(2):287-310.[4]BellmanR,DreyfusS.Applieddynamicprogramming[M].NewJersey:PrincetonUniversityPress,1962.[5]AloiseD,DeshpandeA,HansenP,etal.NP-hardnessofeuclideansum-of-squaresclustering[J].MachineLearning,2023,75(2):245-248.[6]MahajanM,NimborP,VaradarajanK.TheplanarK-meansproblemisNP-hard[J].LectureNotesinComputerScience,2023(5431):274-285.[7]BallG,HallD.ISODATA,anovelmethodofdataanalysisandpatternclassification[M].California:Technicalrept.NTISAD69961