《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 其他 > 設(shè)計(jì)應(yīng)用 > 一種服務(wù)于K-means的初始中心選取方法
一種服務(wù)于K-means的初始中心選取方法
電子技術(shù)應(yīng)用 2023年3期
李秋云1，劉燕武2
（1.中國運(yùn)載火箭技術(shù)研究院 北京宇航系統(tǒng)工程研究所，北京 100076； 2.中國電子信息產(chǎn)業(yè)集團(tuán)有限公司，廣東 深圳 518000）
摘要： 聚類是數(shù)據(jù)挖掘領(lǐng)域最重要的技術(shù)之一，K-means是其中使用頻率最高的舉足輕重的聚類算法。然而，K-means算法表現(xiàn)嚴(yán)重依賴于初始中心，選取多少個(gè)初始中心以及選擇哪些數(shù)據(jù)點(diǎn)作為初始中心對(duì)K-means算法十分重要?；诖?，提出一種初始中心選取方法DPCC（Density Peak Clustering Centers）。DPCC方法基于密度和距離生成一個(gè)選取決策圖，將數(shù)據(jù)集中所有的密度峰值點(diǎn)凸顯出來。這些密度峰值點(diǎn)即為DPCC方法為K-means算法提供的初始中心。實(shí)驗(yàn)表明，DPCC方法不僅可為K-means提供初始中心數(shù)量，還能有效提高K-means算法的準(zhǔn)確度，并縮減K-means算法的執(zhí)行時(shí)間。
關(guān)鍵詞： 聚類 初始中心 決策圖
中圖分類號(hào)：TP3-0 文獻(xiàn)標(biāo)志碼：A DOI: 10.16157/j.issn.0258-7998.223066
中文引用格式： 李秋云，劉燕武. 一種服務(wù)于K-means的初始中心選取方法[J]. 電子技術(shù)應(yīng)用，2023，49(3)：134-138.
英文引用格式： Li Qiuyun，Liu Yanwu. An initial centers selection method serving K-means[J]. Application of Electronic Technique，2023，49(3)：134-138.
An initial centers selection method serving K-means
Li Qiuyun1，Liu Yanwu2
(1.Beijing Institute of Astronautical Systems Engineering，China Academy of Launch Vehicle Technology， Beijing 100076， China； 2.China Electronics Corporation， Shenzhen 518000， China)
Abstract： Clustering is one of the most important data mining technologies, and K-means is the most famous and commonly used clustering algorithm. However, the performance of K-means depends heavily on the initial centers. It is very important for K-means to select how many initial centers and which data points to choose as the initial centers. Therefore, an initial centers selection method called DPCC (density peak clustering centers) is proposed. DPCC generates a selection decision graph based on density and distance, so as to highlight all density peak points in dataset. These density peak points are the initial centers provided by DPCC for K-means. Experiments show that DPCC not only provides decision support for the number of initial centers, but also improves the accuracy of K-means and reduces the running time of K-means.
Key words : clustering；initial centers；decision graph

0　引言

聚類是一種無監(jiān)督分析方法，其目的是識(shí)別出數(shù)據(jù)集中的所有數(shù)據(jù)簇，并將每個(gè)簇中的數(shù)據(jù)點(diǎn)看作一類。在眾多聚類算法中，K-means[1]是使用頻率最高的舉足輕重的算法之一。K-means算法從數(shù)據(jù)集中選取k個(gè)數(shù)據(jù)點(diǎn)作為初始聚類中心，按照距離最近原則，將其他數(shù)據(jù)點(diǎn)分配給這k個(gè)初始中心得到初始簇，再將處于初始簇中心的數(shù)據(jù)點(diǎn)作為新的聚類中心。重復(fù)上述過程，直到聚類中心不再改變?yōu)橹埂-means算法的原理相對(duì)簡單，這也是其受到廣泛追捧的原因。然而，該算法也存在著明顯缺陷：

（1）分析之前，需要明確k值。在K-means算法中，k值就是簇的數(shù)量。若k被設(shè)置為10，那么K-means算法將識(shí)別出10個(gè)數(shù)據(jù)簇。但聚類是一種無監(jiān)督分析任務(wù)，在聚類之前無法得知數(shù)據(jù)集存在多少簇。顯然，K-means算法的機(jī)理與聚類初衷是相矛盾的。在真實(shí)分析場(chǎng)景中，常常會(huì)出現(xiàn)k值多于或少于真實(shí)簇?cái)?shù)的情況，影響聚類準(zhǔn)確度。

（2）初始中心易聚團(tuán)。K-means算法隨機(jī)將k個(gè)數(shù)據(jù)點(diǎn)確定為初始聚類中心，易造成多個(gè)聚類中心出現(xiàn)在同一簇內(nèi)，導(dǎo)致該簇被分解為多類。

（3）迭代次數(shù)無法控制。K-means算法需要經(jīng)過多次迭代直至聚類中心不再改變?yōu)橹埂ＭǔＧ闆r下，聚類中心最終會(huì)迭代到密度稠密區(qū)。也就是說，初始中心越遠(yuǎn)離密度核心，K-means算法的迭代次數(shù)越多，運(yùn)行時(shí)間越長。又因初始中心是隨機(jī)選取的，致使K-means算法的運(yùn)行時(shí)間無法控制。

針對(duì)上述問題，本文提出一種名為DPCC（Density Peak Clustering Centers）的方法，為K-means算法提供初始中心。DPCC運(yùn)用于K-means算法之前，通過計(jì)算數(shù)據(jù)點(diǎn)密度以及與高密度數(shù)據(jù)點(diǎn)間最近距離生成決策圖，以凸顯數(shù)據(jù)集中所有的密度峰值點(diǎn)。這些密度峰值點(diǎn)即可作為K-means算法的初始中心。



本文詳細(xì)內(nèi)容請(qǐng)下載：http://ihrv.cn/resource/share/2000005243




作者信息：

李秋云1，劉燕武2

（1.中國運(yùn)載火箭技術(shù)研究院 北京宇航系統(tǒng)工程研究所，北京 100076；
2.中國電子信息產(chǎn)業(yè)集團(tuán)有限公司，廣東 深圳 518000）



微信圖片_20210517164139.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。