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

有效

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

1.一種基于密度子圖估計的快速聚類方法，其特征在于，包括以下步驟：

S1：獲取樣本，所述樣本包括圖片樣本和real world數(shù)據(jù)集樣本；對所述樣本進行預(yù)處理后組成數(shù)據(jù)集；其中，對圖片樣本進行預(yù)處理的具體步驟包括：將圖片樣本轉(zhuǎn)化為5維數(shù)組，其中數(shù)組中每個元素分別由圖片樣本中對應(yīng)的像素點的位置坐標(biāo)和對應(yīng)的RGB通道值組成；

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

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

S4：計算所述候選集中每個樣本的重要值；

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

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

2.根據(jù)權(quán)利要求1所述的基于密度子圖估計的快速聚類方法，其特征在于：所述S2步驟中，其具體步驟如下：

S21：對所述數(shù)據(jù)集中各個樣本進行密度值估計計算，得到每個樣本的密度值；

S22：根據(jù)預(yù)設(shè)的密度閾值對每個樣本的密度值進行判斷：若當(dāng)前樣本的密度值大于預(yù)設(shè)的密度閾值時，則執(zhí)行S23步驟；否則判定當(dāng)前樣本不加入密度子圖中，然后對下一樣本執(zhí)行本步驟的判斷；

S23：判斷當(dāng)前樣本是否與密度子圖集合中任一子集連通：若是，則將當(dāng)前樣本添加至連通的子集中，并進一步判斷連通的子集是否與密度子圖集合中任一其他子集相交，若是，則將相交的子集進行合并；若否，則創(chuàng)建新的子集，并將當(dāng)前樣本添加至新的子集中；然后對下一樣本執(zhí)行S22步驟的密度值判斷，至所有樣本完成判斷，得到密度子圖集合。

3.根據(jù)權(quán)利要求2所述的基于密度子圖估計的快速聚類方法，其特征在于：所述S21步驟中，對所述數(shù)據(jù)集中各個樣本采用k-NN密度估計方法進行密度值估計計算；其計算公式如下：

其中，f_k(x)表示樣本x的密度值；k為近鄰數(shù)，n為數(shù)據(jù)集中樣本總數(shù)，v_d為d維空間中單位球的體積，r_k(x)表示樣本x到第k個近鄰的距離。

4.根據(jù)權(quán)利要求3所述的基于密度子圖估計的快速聚類方法，其特征在于：所述S4步驟中，計算所述候選集中每個樣本的重要值的具體步驟包括：

S41：對所述候選集中的樣本，計算各個樣本的權(quán)重值w_i；

S42：將所述候選集中各個樣本的密度值f_k(x_i)及其權(quán)重值w_i相乘，得到對應(yīng)樣本的重要值。

5.根據(jù)權(quán)利要求4所述的基于密度子圖估計的快速聚類方法，其特征在于：所述候選集中每個樣本的權(quán)重值w_i的計算步驟如下：

判斷候選集X_H中是否存在比當(dāng)前樣本x_i密度值更高的樣本x_h：若是，則其權(quán)重值w_i的計算公式如下：

否則，其權(quán)重值w_i的計算公式如下：

6.根據(jù)權(quán)利要求1所述的基于密度子圖估計的快速聚類方法，其特征在于：所述S6步驟中，對所述候選集中非質(zhì)心的樣本進行歸類的具體步驟包括：

對所述候選集中非質(zhì)心的樣本按照最近-密度更高的原則，將當(dāng)前樣本歸類到其最近的且密度值更高的點，直至收斂至某一質(zhì)心；

對非候選集中的樣本，判斷其是否在密度子圖中，若是，則將當(dāng)前樣本歸類至對應(yīng)密度子圖中代表點所在的簇中；否則按照最近-密度更高原則，將當(dāng)前樣本歸類到其最近的且密度值更高的點所在的簇中；

當(dāng)對數(shù)據(jù)集中所有樣本完成歸類后，輸出得到聚類結(jié)果。

7.一種計算機設(shè)備，包括存儲器和處理器，所述存儲器存儲有計算機程序，其特征在于，所述處理器執(zhí)行所述計算機程序時實現(xiàn)權(quán)利要求1至6中任一項所述的基于密度子圖估計的快速聚類方法的步驟。

8.一種計算機可讀存儲介質(zhì)，其上存儲有計算機程序，其特征在于，所述計算機程序被處理器執(zhí)行時實現(xiàn)權(quán)利要求1至6中任一項所述的基于密度子圖估計的快速聚類方法的步驟。