[發明專利]基于Spark的快速尋找聚類中心的方法和系統

在審

• 申請號: 201710693112.3
• 申請日: 2017-08-14
• 公開（公告）號: CN109389140A
• 公開（公告）日: 2019-02-26
• 發明（設計）人: 李學兵;莊福振;敖翔;何清
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 祁建國;梁揮

1.一種快速尋找聚類中心的方法，其特征在于，包括：

步驟1，基于Spark并行計算框架讀取儲存在分布式文件系統中的數據集，并生成彈性分布式數據集；

步驟2，對該彈性分布式數據集進行并行處理，得到第一數據點到第二數據點之間的第一距離；設定閾值，將該第一距離和該閾值，并行處理得到該第一數據點的密度；將該密度生成廣播變量并分配到計算結點；

步驟3，對該廣播變量和第一距離并行處理，得到近鄰點，以及該第一數據點到該近鄰點的第二距離；

步驟4，根據該密度和該第二距離選出聚類中心，進行類別指定，完成聚類。

2.如權利要求1所述的快速尋找聚類中心的方法，其特征在于，所述步驟1之前還包括：

步驟0，配置Spark參數，包括數據讀取路徑、數據存儲路徑和閾值設置參數，初始化Spark環境。

3.如權利要求1所述的快速尋找聚類中心的方法其特征在于，所述步驟2具體包括：

步驟21，定義該第二數據點為該彈性分布式數據集中，除該第一數據點以外的所有數據點；

步驟22，將所有該第一數據點的該第一距離進行升序排序，并根據該閾值設置參數，選取排序序列中某一該第一距離作為該閾值。

步驟23，該密度其中其中d_ij為該第一距離，d_c為該閾值。

4.如權利要求1或3所述的快速尋找聚類中心的方法，其特征在于，步驟3還包括：

以比該第一數據點的密度大的該第二數據點中，距離該第一數據點最近的數據點為該近鄰點；

以該第一數據點到該近鄰點的距離，為該第二距離；

該第二距離其中ρ_i為第一數據點的密度，ρ_j為第二數據點的密度。

5.如權利要求1所述的快速尋找聚類中心的方法，其特征在于，步驟4具體包括：

步驟41，通過該密度和該第二距離畫出決策圖，并以該決策圖確定聚類中心；

步驟42，將所有數據點按照該密度降序排列后，遍歷該數據集；根據該聚類中心的類別信息進行類別指定，輸出聚類結果。

6.一種快速尋找聚類中心的系統，其特征在于，該系統包括：

數據讀取模塊，用于基于Spark并行計算框架讀取儲存在分布式文件系統中的數據集，并生成彈性分布式數據集。

密度獲取模塊，用于對該彈性分布式數據集進行并行處理，得到第一數據點到第二數據點之間的第一距離；設定閾值，將該第一距離和該閾值，并行處理得到該第一數據點的密度；將該密度生成廣播變量并分配到計算結點；

第二距離獲取模塊，用于通過對該廣播變量和第一距離并行處理，得到近鄰點，以及該第一數據點到該近鄰點的第二距離；

聚類模塊，用于對該密度和該第二距離并行處理，獲得聚類中心，進行類別指定，完成聚類。

7.如權利要求6所述的快速尋找聚類中心的系統，其特征在于，該系統還包括：

初始化模塊，用于配置系統算法參數，包括數據讀取路徑、數據存儲路徑和閾值確定參數，初始化Spark環境。

8.如權利要求6所述的快速尋找聚類中心的系統，其特征在于，所述密度獲取模塊還包括：

第一距離模塊，用于得到得到第一數據點到第二數據點之間的第一距離；

閾值獲取模塊，用于將所有該第一數據點的該第一距離進行升序排序，并根據閾值設置參數，選取排序序列中某一該第一距離作為該閾值。

9.如權利要求6所述的快速尋找聚類中心的系統，其特征在于，所述第二距離獲取模塊還包括：

近鄰點獲取模塊，用于獲取該近鄰點，其中以比該第一數據點的密度大的該第二數據點中，距離該第一數據點最近的數據點為該近鄰點；

第二距離模塊，用于獲取該第二距離，其中以該第一數據點到該近鄰點的距離，為該第二距離。

10.如權利要求6所述的快速尋找聚類中心的系統，其特征在于，所述聚類模塊還包括：

聚類中心獲取模塊，用于通過該密度和該第二距離，畫出決策圖，并以該決策圖確定聚類中心；

類別指定模塊，將所有數據點按照該密度降序排列后，遍歷該數據集；根據該聚類中心的類別信息進行類別指定，輸出聚類結果。