[發明專利]一種基于MapReduce的k-means文本聚類的方法及裝置

有效

• 申請號: 201711473670.5
• 申請日: 2017-12-29
• 公開（公告）號: CN108268611B
• 公開（公告）日: 2021-03-26
• 發明（設計）人: 趙偉;武新;崔維力;張浩文
• 申請（專利權）人: 天津南大通用數據技術股份有限公司
• 主分類號: G06F16/35
• 分類號: G06F16/35;G06K9/62
• 代理公司: 天津濱海科緯知識產權代理有限公司 12211
• 代理人: 李成運

本發明提供一種基于MapReduce的k?means文本聚類的方法及裝置。包括，刪除離群點，最大距離法選取初始簇中心，構造迭代中的簇中心計算公式和測度函數，設計基于MapReduce框架的大規模文本并行聚類模型。采用本發明的方法，可以有效解決傳統K?means聚類算法中的局部最優、迭代次數過多、聚類結果不穩定的問題，提高算法的并行能力和可擴展性。

技術領域

本發明屬于文本聚類方法，特別涉及MapReduce編程模型，同時還涉及k-means聚類 方法。

背景技術

隨著互聯網的發展，數據的規模越來越龐大，現有的文本聚類方法并不能適應規模龐 大的數據集，無論從文本聚類效果還是時間性能上都不能達到所要達到的要求。

例如傳統K-means聚類算法中中存在迭代次數過多、聚類結果不穩定的情況，因此算 法的并行能力和可擴展性都不能令人滿意。

發明內容

本發明要解決的問題是提出基于MapReduce的最大距離法選取初始簇中心的k-means 文本聚類方法，從而提高文本聚類效果和時間性能。

為了達到上述目的，本發明采取的技術方案為：一種基于MapReduce的k-means文本 聚類方法，包括：

(1)、對整個文本數據集的離群點進行刪除；

(2)、對剩余的文本使用最大距離法選取初始簇中心；

(3)、運用MapReduce函數進行多次迭代，完成文本的聚類過程。

進一步的，步驟(1)所述刪除離群點的方法包括：

(101)、定義四個集合，S1，S2，S3，D1；S1為核心點集，S2為邊界點集，S3為離群 點集，D1是文本數據集D的備份；

(102)、對于文本數據集D中的任一文本數據點d_x，運用Map函數計算該文本與其他文本之間的距離，得到與d_x的距離不大于距離參數Eps的點集合；

(103)、使用Reduce函數對步驟102得到的點集合進行求和，若值不小于個數參數Minpts，則采用Map函數將其歸類到核心點集S1，再采用Reduce函數將不包含S1的文本 數據集傳入D1文本數據集。

進一步的，步驟(2)所述最大距離法選取初始簇中心的過程包括：

(201)、計算刪除離群點后剩余文本數據集所包括N個樣本點的兩兩之間的距離，并 將距離最遠的2個樣本點作為初始簇中心；

(202)、計算剩余的樣本點中，到前面已選取的初始簇中心各自距離乘積；將乘積最 大值的那個樣本點作為下一個初始簇中心；

(203)、反復執行步驟(202)，直到找到k個初始簇中心，其中k為根據實際需要聚類的數量定義。

進一步的，步驟(3)的具體方法為：

(301)、運用Map函數計算每個文本數據點到各個初始簇中心的距離，并根據距離把 文本數據點歸屬到最近的初始簇中心；

(302)、運用Reduce函數根據Map函數的結果計算出新的初始簇中心；

(303)、對于步驟(302)得到的Reduce結果，判斷得到的聚類初始簇中心和上一輪的初始簇中心之間的變化是否小于閾值，若小于，則聚類結束，否則開始新一輪的MapReduce。

本發明的另一方面，提出了一種基于MapReduce的k-means文本聚類裝置，包括：

離群點刪除模塊，用于對整個文本數據集的離群點進行刪除；