[發(fā)明專利]一種基于密度子圖估計(jì)的快速聚類方法、計(jì)算機(jī)設(shè)備及存儲介質(zhì)

有效

• 申請?zhí)枺?/td>: 202011060417.9
• 申請日: 2020-09-30
• 公開（公告）號: CN112163623B
• 公開（公告）日: 2022-03-04
• 發(fā)明（設(shè)計(jì)）人: 楊易揚(yáng);鄭喜臣;任成森;鞏志國;蔡瑞初;郝志峰;陳炳豐
• 申請（專利權(quán)）人: 廣東工業(yè)大學(xué)
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 廣州粵高專利商標(biāo)代理有限公司 44102
• 代理人: 林麗明

本發(fā)明涉及機(jī)器學(xué)習(xí)技術(shù)領(lǐng)域，為克服上述現(xiàn)有技術(shù)所述的不能確定簇的質(zhì)心、計(jì)算成本大、在聚類過程中出現(xiàn)過分割的缺陷，提出一種基于密度子圖估計(jì)的快速聚類方法、計(jì)算機(jī)設(shè)備及存儲介質(zhì)，其中，基于密度子圖估計(jì)的快速聚類方法包括以下步驟：獲取樣本，對樣本進(jìn)行預(yù)處理后組成數(shù)據(jù)集；對數(shù)據(jù)集中各個樣本進(jìn)行密度值估計(jì)，構(gòu)建密度子圖集合；從密度子圖集合中找出每個密度子圖的密度最高點(diǎn)作為該密度子圖的代表點(diǎn)，把代表點(diǎn)對應(yīng)的樣本組成候選集；計(jì)算候選集中每個樣本的重要值；將候選集根據(jù)重要值進(jìn)行降序排序，選擇前K個樣本作為K個簇的質(zhì)心；對候選集中非質(zhì)心的樣本進(jìn)行歸類，輸出得到聚類結(jié)果。

技術(shù)領(lǐng)域

本發(fā)明涉及機(jī)器學(xué)習(xí)技術(shù)領(lǐng)域，更具體地，涉及一種基于密度子圖估計(jì)的快速聚類方法、計(jì)算機(jī)設(shè)備及存儲介質(zhì)。

背景技術(shù)

基于密度的聚類方法是數(shù)據(jù)挖掘中一個經(jīng)典的研究方向，在學(xué)術(shù)界和工業(yè)界都很受歡迎，因?yàn)樗軌虬l(fā)現(xiàn)數(shù)據(jù)集中任意形狀的簇，其主要通過核密度估計(jì)(KDE，kerneldensity estimates)對數(shù)據(jù)集的樣本進(jìn)行密度連接。

傳統(tǒng)的基于密度的聚類方法中，DBSCAN(Density-Based Spatial Clustering ofApplications with Noise)主要通過判斷樣本點(diǎn)之間是否密度可達(dá)來進(jìn)行簇的劃分。然而，DBSCAN不能確定簇的質(zhì)心，而質(zhì)心通常是作為簇的代表點(diǎn)。針對上述問題，MeanShift提出對于每個樣本點(diǎn)，通過核密度估計(jì)不斷地移動，直到最后移動到密度局部最大值點(diǎn)，這個密度最大值點(diǎn)作為簇的質(zhì)心。如果移動到同一個質(zhì)心的數(shù)據(jù)樣本就歸為同一個簇。然而，該方法在移動過程中會不斷產(chǎn)生新的樣本點(diǎn)，這導(dǎo)致了可伸縮性差并且計(jì)算成本非常大。而QuickShift提出通過移動每個樣本點(diǎn)到其τ-radius球半徑范圍中最近的更高密度的樣本點(diǎn)。因此在移動過程中不需要產(chǎn)生新的點(diǎn)，只需要在樣本之間進(jìn)行密度連接，大大降低了相應(yīng)的計(jì)算成本。另一方面，對于尋找密度最高點(diǎn)的方法，包括MeanShift、QuickShift，由于只關(guān)注密度最高點(diǎn)，而忽略了其他點(diǎn)的局部密度結(jié)構(gòu)，導(dǎo)致上述方法均存在過分割的問題。除了過分割問題外，基于密度的聚類的方法不能根據(jù)用戶的需求返回指定數(shù)量的K個簇，雖然在2014年science雜志上提出了一種DPC算法，根據(jù)數(shù)據(jù)集的密度和距離兩個維度來確定K個簇的質(zhì)心，但是DPC算法需要計(jì)算數(shù)據(jù)集中每兩個點(diǎn)之間的距離，得到距離矩陣，這導(dǎo)致算法的復(fù)雜度過高。同時K-Mode和LK-Mode也有類似的問題。

發(fā)明內(nèi)容

本發(fā)明為克服上述現(xiàn)有技術(shù)所述的不能確定簇的質(zhì)心、計(jì)算成本大、在聚類過程中出現(xiàn)過分割的缺陷，提供一種基于密度子圖估計(jì)的快速聚類方法、計(jì)算機(jī)設(shè)備及存儲介質(zhì)。

為解決上述技術(shù)問題，本發(fā)明的技術(shù)方案如下：

一種基于密度子圖估計(jì)的快速聚類方法，包括以下步驟：

S1：獲取樣本，對樣本進(jìn)行預(yù)處理后組成數(shù)據(jù)集；

S2：對數(shù)據(jù)集中各個樣本進(jìn)行密度值估計(jì)，構(gòu)建密度子圖集合；

S3：從密度子圖集合中找出每個密度子圖的密度最高點(diǎn)作為該密度子圖的代表點(diǎn)，把代表點(diǎn)對應(yīng)的樣本組成候選集；

S4：計(jì)算候選集中每個樣本的重要值；

S5：將候選集根據(jù)重要值進(jìn)行降序排序，選擇前K個樣本作為K個簇的質(zhì)心；

S6：對候選集中非質(zhì)心的樣本進(jìn)行歸類，輸出得到聚類結(jié)果。

作為優(yōu)選方案，S1步驟中，樣本包括但不僅限于圖片樣本、real world(真實(shí)的)數(shù)據(jù)集樣本。

作為優(yōu)選方案，S1步驟中，對圖片樣本進(jìn)行預(yù)處理的具體步驟包括：將圖片轉(zhuǎn)化為5維數(shù)組，其中數(shù)組中每個點(diǎn)分別是由圖片樣本中對應(yīng)的像素點(diǎn)的位置坐標(biāo)和對應(yīng)的RGB通道值組成。

作為優(yōu)選方案，S2步驟中，其具體步驟如下：