[發(fā)明專利]基于KD樹和混沌蜉蝣優(yōu)化算法的并行譜聚類方法

在審

• 申請?zhí)枺?/td>: 202110503711.0
• 申請日: 2021-05-10
• 公開（公告）號: CN113128618A
• 公開（公告）日: 2021-07-16
• 發(fā)明（設計）人: 毛伊敏;劉祥敏
• 申請（專利權）人: 江西理工大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/00;G06N7/08
• 代理公司: 重慶天成卓越專利代理事務所(普通合伙) 50240
• 代理人: 王宏松

1.一種基于KD樹和混沌蜉蝣優(yōu)化算法的并行譜聚類方法，其特征在于，包括以下步驟：

S1，采用基于采樣的KD-tree數(shù)據(jù)分區(qū)策略DPS劃分數(shù)據(jù)，得到Map上的數(shù)據(jù)分區(qū)；

S2，在構建稀疏相似矩陣過程中，采用優(yōu)化的分區(qū)分配策略OPA和兩個基于三角不等式的KD樹剪枝策略以進行跨分區(qū)的t近鄰搜索；

S3，采用正規(guī)化定理，通過元素對應相乘的方式代替矩陣相乘以優(yōu)化Laplacian矩陣正規(guī)化過程；

S4，采用混沌蜉蝣優(yōu)化算法CMO得到最佳位置作為初始簇中心，然后，對特征空間進行k-means并行聚類；

S5，得到最終的聚類結果，并輸出。

2.根據(jù)權利要求1所述的一種基于KD樹和混沌蜉蝣優(yōu)化算法的并行譜聚類方法，其特征在于，所述KD-tree數(shù)據(jù)分區(qū)策略DPS包括以下步驟：

S1-1，采樣：對數(shù)據(jù)集D進行隨機采樣，得到采樣數(shù)據(jù)集S；

S1-2，支撐點選擇：首先從采樣數(shù)據(jù)集S中隨機選出第一個點；接著依次選出后續(xù)的支撐點，每次選擇到近期被選出的幾個點距離最大的點，得到候選集，并從候選集中組合出所有的支撐點集合；最后構造評價集，將評價集中的數(shù)據(jù)兩兩組合構成數(shù)據(jù)對，選出能排除最多評價集數(shù)據(jù)對的支撐點組合，即為最優(yōu)的支撐點集合PS＝{PS₁,PS₂,...,PS_q|q＜＜n}；其中PS₁表示第1個支撐點，PS₂表示第2個支撐點，PS_q表示第q個支撐點；＜＜表示遠小于，n表示原始數(shù)據(jù)集D的數(shù)據(jù)個數(shù)，q表示支撐點的總個數(shù)；

S1-3，映射：用選定的支撐點將數(shù)據(jù)映射到q維向量空間；對任一數(shù)據(jù)點v_i，將原始度量空間中的數(shù)據(jù)映射到二維向量空間中的數(shù)據(jù)點上；

S1-4，空間劃分：采用KD樹的劃分方法將整個空間分割成若干個不相干的子空間，使每個子空間都包含同等大小的采樣數(shù)據(jù)；首先選出方差最大的維度，根據(jù)采樣數(shù)據(jù)集S在該維度上的值進行升序排序，選出中位數(shù)作為根節(jié)點，小于根節(jié)點的數(shù)據(jù)分配給左子樹，大于根節(jié)點的數(shù)據(jù)分配給右子樹；令m是需要劃分的分區(qū)數(shù)，此時S被分成了兩個不相交的部分，其大小比例為之后重復此過程，直到將S劃分成大小相等的m個不相交的部分P_i(1≤i≤m)；其中，為向上取整符號，向下取整符號；

S1-5，數(shù)據(jù)劃分：在得到一組不相交的子空間Bound(P_i)后，D中的每個對象都可以根據(jù)Bound(P_i)分配到相應的分區(qū)P_i中；劃分完成后，輸出兩個表，分區(qū)信息表PI和數(shù)據(jù)信息表DI；分區(qū)信息表記錄每個分區(qū)P_i的信息，包括P_i的分區(qū)IDp_id和P_i的最小邊界框MinBound(P_i)；數(shù)據(jù)信息表記錄每個點v_i的信息，包括v_i的IDv_id、對應的分區(qū)IDp_id、v_i的屬性A(v_i)和映射向量φ(v_i)。

3.根據(jù)權利要求1所述的一種基于KD樹和混沌蜉蝣優(yōu)化算法的并行譜聚類方法，其特征在于，所述t近鄰搜索包括：

S2-1，局部t近鄰搜索：并行計算每個Map分區(qū)內部樣本數(shù)據(jù)的t近鄰；

S2-2，跨分區(qū)的t近鄰搜索：提出優(yōu)化的分區(qū)分配策略OPA將合格的數(shù)據(jù)分配給分區(qū)，進行跨分區(qū)的t近鄰搜索，得到各樣本數(shù)據(jù)的t近鄰，同時，搜索過程中設計兩個剪枝策略以快速縮小搜索區(qū)域；

S2-3，計算相似度：計算數(shù)據(jù)間的相似度值并將結果暫時存到combine；

S2-4，合并相似度矩陣：接受combine中的鍵值對，獲得并存儲整個數(shù)據(jù)集的相似度矩陣。

4.根據(jù)權利要求3所述的一種基于KD樹和混沌蜉蝣優(yōu)化算法的并行譜聚類方法，其特征在于，所述S2-2包括OPA策略：

其中，m為分區(qū)個數(shù)，i、j為分區(qū)下標，為向上取整符號。