資源描述：
《K-means聚類算法研究綜述.docx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、K-means聚類算法研究綜述摘要:總結(jié)評(píng)述了K-means聚類算法的研究現(xiàn)狀，指出K-means聚類算法是一個(gè)NP難優(yōu)化問題，無法獲得全局最優(yōu)。介紹了K-means聚類算法的目標(biāo)函數(shù)，算法流程，并列舉了一個(gè)實(shí)例，指出了數(shù)據(jù)子集的數(shù)目K，初始聚類中心選取，相似性度量和距離矩陣為K-means聚類算法的3個(gè)基本參數(shù)?？偨Y(jié)了K-means聚類算法存在的問題及其改進(jìn)算法，指出了K-means聚類的進(jìn)一步研究方向。關(guān)鍵詞：K-means聚類算法；NP難優(yōu)化問題；數(shù)據(jù)子集的數(shù)目K；初始聚類中心選取；相似性度
2、量和距離矩陣ReviewofK-meansclusteringalgorithmAbstract:K-meansclusteringalgorithmisreviewed.K-meansclusteringalgorithmisaNPhardoptimalproblemandglobaloptimalresultcannotbereached.Thegoal，mainstepsandexampleofK-meansclusteringalgorithmareintroduced.K-meansal
3、gorithmrequiresthreeuser-specifiedparameters:numberofclustersK，clusterinitialization，anddistancemetric.ProblemsandimprovementofK-meansclusteringalgorithmaresummarizedthen.FurtherstudydirectionsofK-meansclusteringalgorithmarepointedatlast.Keywords:K-me
4、ansclusteringalgorithm;NPhardoptimalproblem;numberofclustersK;clusterinitialization;distancemetricK-means聚類算法是由Steinhaus1955年、Lloyed1957年、Ball&Hall1965年、McQueen1967年分別在各自的不同的科學(xué)研究領(lǐng)域獨(dú)立的提出。K-means聚類算法被提出來后，在不同的學(xué)科領(lǐng)域被廣泛研究和應(yīng)用，并發(fā)展出大量不同的改進(jìn)算法。雖然K-means聚類算法被提出已
5、經(jīng)超過50年了，但目前仍然是應(yīng)用最廣泛的劃分聚類算法之一[1]。容易實(shí)施、簡(jiǎn)單、高效、成功的應(yīng)用案例和經(jīng)驗(yàn)是其仍然流行的主要原因。文中總結(jié)評(píng)述了K-means聚類算法的研究現(xiàn)狀，指出K-means聚類算法是一個(gè)NP難優(yōu)化問題，無法獲得全局最優(yōu)。介紹了K-means聚類算法的目標(biāo)函數(shù)、算法流程，并列舉了一個(gè)實(shí)例，指出了數(shù)據(jù)子集的數(shù)目K、初始聚類中心選取、相似性度量和距離矩陣為K-means聚類算法的3個(gè)基本參數(shù)?？偨Y(jié)了K-means聚類算法存在的問題及其改進(jìn)算法，指出了K-means聚類的進(jìn)一步研究
6、方向。1經(jīng)典K-means聚類算法簡(jiǎn)介1.1K-means聚類算法的目標(biāo)函數(shù)對(duì)于給定的一個(gè)包含n個(gè)d維數(shù)據(jù)點(diǎn)的數(shù)據(jù)集，其中，以及要生成的數(shù)據(jù)子集的數(shù)目K，K-means聚類算法將數(shù)據(jù)對(duì)象組織為K個(gè)劃分。每個(gè)劃分代表一個(gè)類，每個(gè)類有一個(gè)類別中心。選取歐氏距離作為相似性和距離判斷準(zhǔn)則，計(jì)算該類內(nèi)各點(diǎn)到聚類中心的距離平方和（1）聚類目標(biāo)是使各類總的距離平方和最小。（2）其中，，顯然，根據(jù)最小二乘法和拉格朗日原理，聚類中心應(yīng)該取為類別類各數(shù)據(jù)點(diǎn)的平均值。K-means聚類算法從一個(gè)初始的K類別劃分開始，然
7、后將各數(shù)據(jù)點(diǎn)指派到各個(gè)類別中，以減小總的距離平方和。因?yàn)镵-means聚類算法中總的距離平方和隨著類別個(gè)數(shù)K的增加而趨向于減?。ó?dāng)時(shí)，）。因此，總的距離平方和只能在某個(gè)確定的類別個(gè)數(shù)K下，取得最小值。1.2K-means算法的算法流程K-means算法是一個(gè)反復(fù)迭代過程,目的是使聚類域中所有的樣品到聚類中心距離的平方和最小，算法流程包括4個(gè)步驟[1]，具體流程圖如圖1所示。1)選定數(shù)據(jù)空間中K個(gè)對(duì)象作為初始聚類中心，每個(gè)對(duì)象代表一個(gè)類別的中心2)對(duì)于樣品中的數(shù)據(jù)對(duì)象，則根據(jù)它們與這些聚類中心的歐氏
8、距離，按距離最近的準(zhǔn)則分別將它們分配給與其最相似的聚類中心所代表的類3)計(jì)算每個(gè)類別中所有對(duì)象的均值作為該類別的新聚類中心，計(jì)算所有樣本到其所在類別聚類中心的距離平方和，即值4)聚類中心和值發(fā)生改變？聚類結(jié)束是否圖1K-means聚類算法流程圖Fig.1StepsofK-meansclusteringalgorithm1.3K-means聚類算法實(shí)例圖2顯示的是K-means算法將一個(gè)2維數(shù)據(jù)集聚成3類的過程示意圖。2K-means聚類算法是一個(gè)NP難優(yōu)化問題K-means聚類算法
