[發明專利]基于對稱鄰居關系的改進DPC聚類算法及系統在審
| 申請號： | 201910123429.2 | 申請日： | 2019-02-18 |
| 公開（公告）號： | CN109886332A | 公開（公告）日： | 2019-06-14 |
| 發明（設計）人： | 吳春蓉;李佳;顏曉彤;楊小川;楊瑞龍 | 申請（專利權）人： | 重慶大學 |
| 主分類號： | G06K9/62 | 分類號： | G06K9/62 |
| 代理公司： | 重慶市前沿專利事務所(普通合伙) 50211 | 代理人： | 郭云 |
| 地址： | 400030 *** | 國省代碼： | 重慶;50 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 聚類算法 鄰居關系 對稱 樣本點 聚類 改進 遍歷方式 聚類操作 寬度優先 米勒效應 影響空間 不均勻 數據集 | ||
1.一種基于對稱鄰居關系的改進DPC聚類算法，其特征在于，包含以下步驟：
S1：獲取每個樣本點的影響空間；
S2：計算樣本點密度和距離的乘積；
S3：依據寬度優先遍歷方式進行聚類操作。
2.根據權利要求1所述的改進DPC聚類算法，其特征在于，步驟S1包含以下步驟：
S11：計算樣本點兩兩之間的距離；
S12：使用KD樹來獲得每個樣本點的k最近鄰居和反向k最近鄰居；
S13：將每個樣本點的k最近鄰居和反向k最近鄰居取交集獲得影響空間。
3.根據權利要求1所述的改進DPC聚類算法，其特征在于，步驟S2包含以下步驟：
S21：根據影響空間的作用域，計算每個樣本點的密度和距離；
S22：計算每個樣本點的密度和距離的乘積，且樣本點按照其密度和距離的乘積降序的方式排列。
4.根據權利要求3所述的基于對稱鄰居關系的改進DPC聚類算法，其特征在于，步驟S3包含以下步驟：
S31：為每個樣本點設置訪問標記；
S32：選取待訪問的樣本點，定義一個空的集合S，從待訪問的樣本點中選擇一個樣本點放入集合S中；
S33：判斷該樣本點是否被訪問，若已訪問則進入步驟S35；否則，執行步驟S34；
S34：檢查集合中樣本點的影響空間中的所有點，并對影響空間中的所有點做相應處理；檢查完樣本點影響空間中的所有點后，從集合S中刪除該樣本點，直至集合S變為空集，操作結束，執行步驟S35；
S35：更換樣本點；
S36：判斷待訪問的樣本點是否訪問完畢，若未訪問完畢，則執行步驟S33；若訪問完畢，則執行步驟S37；
S37：整理數據集中樣本點的所屬簇關系，完善聚類操作，輸出聚類結果。
5.根據權利要求4所述的基于對稱鄰居關系的改進DPC聚類算法，其特征在于，所述步驟S32選取的待訪問的樣本點為，步驟S22降序排列的樣本點序列的前h個樣本點；
所述步驟S37包含以下步驟：
A1：判斷樣本點是否標記完畢；
A2：標記未標記的點，將未標記的點標記到該樣本點所在的影響空間中的所有點所屬簇的概率最大的簇中；
A3：整理數據集中樣本點的所屬簇關系，以每個簇擁有一定數量的樣本點的形式輸出。
6.根據權利要求4所述的基于對稱鄰居關系的改進DPC聚類算法，其特征在于，所述步驟S32選取的待訪問的樣本點為所有樣本點；
所述步驟S37包含以下步驟：
B1：整理數據集中樣本點的所屬簇關系，以每個簇擁有一定數量的樣本點的形式輸出；
B2：劃分小簇和大簇，若簇的個數大于k則劃分為大簇，若小于k則劃分為小簇；
B3：將每個小簇合并到相應的大簇中，將小簇合并到其包含的所有樣本點所在的影響空間中的所有點所屬簇的概率最大的簇中；
B4：重新整理數據集中樣本點的所屬簇關系，以每個簇擁有一定數量的樣本點的形式輸出。
7.根據權利要求3所述的基于對稱鄰居關系的改進DPC聚類算法，其特征在于，所述樣本點的密度基于高斯核函數進行計算，其中，第i個樣本點ni的密度計算公式如(2)所示，其中D(ni,nj)為第i個樣本點ni與第j個樣本點nj之間的歐幾里得距離，公式如下：
所有樣本點的距離與密度有關，如果ni的密度值比nj小，那么此時的距離的計算公式如(3)所示，公式如下：
如果樣本點ni的密度值比nj大，那么此時的距離的計算公式如(4)所示，公式如下：
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于重慶大學，未經重慶大學許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201910123429.2/1.html，轉載請聲明來源鉆瓜專利網。
