[發明專利]基于對稱鄰居關系的改進DPC聚類算法及系統

在審

• 申請號: 201910123429.2
• 申請日: 2019-02-18
• 公開（公告）號: CN109886332A
• 公開（公告）日: 2019-06-14
• 發明（設計）人: 吳春蓉;李佳;顏曉彤;楊小川;楊瑞龍
• 申請（專利權）人: 重慶大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 重慶市前沿專利事務所(普通合伙) 50211
• 代理人: 郭云

本發明公開了一種基于對稱鄰居關系的改進DPC聚類算法及系統，所述基于對稱鄰居關系的改進DPC聚類算法，包含以下步驟：S1，獲取每個樣本點的影響空間；S2，計算樣本點密度和距離的乘積；S3，依據寬度優先遍歷方式進行聚類操作。本發明能夠合理地選取參數，避免“多米勒效應”，提高聚類效果，特別是在密度不均勻的數據集上能夠得到很好的聚類效果。

技術領域

本發明涉及聚類算法領域，特別涉及基于對稱鄰居關系的改進DPC聚類算法及系統。

背景技術

聚類是一種重要的數據挖掘方法，屬于一種描述類的數據挖掘方法。聚類將數據對象劃分成多個組或簇，在同一個組中的對象彼此相似，不同組的對象彼此不相似。與分類不同，聚類是一種無監督的學習方法，不需要先驗知識，也不需要對數據進行標記。聚類算法有多種，包括劃分聚類，層次聚類，基于密度的聚類，基于分布的聚類和譜聚類。DPC算法是一種基于密度的聚類算法，該算法于2014發表在《科學》期刊上。該算法是根據每個樣本點的密度和距離值來找到簇的中心，簇的中心擁有較高的密度值和較大的距離值。該算法由于其簡單、效率高等優點被廣泛研究，也應用到分類上。但與此同時它還存在一些缺陷，例如參數截斷距離d_c的取值很難確定，對聚類的結果產生嚴重的影響；非中心點的分配如果不合理，容易產生“多米勒”效應；它在密度不均勻的數據集中表現出來的聚類結果不理想，特別是流形數據集。

例如，申請公布號為CN107392249A的發明專利申請，公開的一種K近鄰相似度優化的密度峰聚類方法，其利用K近鄰對每個點分配時進行指向點檢測，最后剩余的點分配到指向點所在族類，提高DPC算法的精度與適用范圍，但其把所有點間的距離從小到大排序后，取2％到5％小的距離為截斷距離d_c，仍然存在截斷距離d_c的取值很難確定的問題。

發明內容

本發明的目的在于克服現有技術中所存在的上述不足，提供一種基于對稱鄰居關系的改進DPC聚類算法及系統，以合理地選取參數，避免“多米勒效應”，提高聚類效果。

為了實現上述發明目的，本發明提供了以下技術方案：

一種基于對稱鄰居關系的改進DPC聚類算法，其特征在于，包含以下步驟：

S1：獲取每個樣本點的影響空間；

S2：計算樣本點密度和距離的乘積；

S3：依據寬度優先遍歷方式進行聚類操作。

優選地，步驟S1包含以下步驟：

S11：計算樣本點兩兩之間的距離；

S12：使用KD樹來獲得每個樣本點的k最近鄰居和反向k最近鄰居；

S13：將每個樣本點的k最近鄰居和反向k最近鄰居取交集獲得影響空間。

優選地，步驟S2包含以下步驟：

S21：根據影響空間的作用域，計算每個樣本點的密度和距離；

S22：計算每個樣本點的密度和距離的乘積，且樣本點按照其密度和距離的乘積降序的方式排列。

優選地，步驟S3包含以下步驟：

S31：為每個樣本點設置訪問標記；

S32：選取待訪問的樣本點，定義一個空的集合S，從待訪問的樣本點中選擇一個樣本點放入集合S中；

S33：判斷該樣本點是否被訪問，若已訪問則進入步驟S35；否則，執行步驟S34；

S34：檢查集合中樣本點的影響空間中的所有點，并對影響空間中的所有點做相應處理；檢查完樣本點影響空間中的所有點后，從集合S中刪除該樣本點，直至集合S變為空集，操作結束，執行步驟S35；