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

有效

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

1.一種基于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.根據權利要求1所述的一種基于MapReduce的k-means文本聚類方法，其特征在于，步驟(2)所述最大距離法選取初始簇中心的過程包括：

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

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

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

3.根據權利要求1所述的一種基于MapReduce的k-means文本聚類方法，其特征在于，步驟(3)的具體方法為：

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

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

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

4.一種基于MapReduce的k-means文本聚類裝置，其特征在于，包括：

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

初始簇中心選取模塊，用于對剩余的文本使用最大距離法選取初始簇中心；

迭代聚類模塊，用于運用MapReduce函數進行多次迭代，完成文本的聚類過程；

所述離群點刪除模塊包括：

集合定義單元，用于定義四個集合，S1，S2，S3，D1；S1為核心點集，S2為邊界點集，S3為離群點集，D1是文本數據集D的備份；

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

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

5.根據權利要求4所述的一種基于MapReduce的k-means文本聚類裝置，其特征在于，所述初始簇中心選取模塊包括：

第一計算單元，用于計算刪除離群點后剩余文本數據集所包括N個樣本點的兩兩之間的距離；

第一選取單元，用于將距離最遠的2個樣本點作為初始簇中心；

第二計算單元，用于計算剩余的樣本點中，到前面已選取的初始簇中心各自距離乘積；

第二選取單元，用于將乘積最大值的那個樣本點作為下一個初始簇中心；

循環單元，用于將第二計算單元和第二選取單元反復執行，直到找到k個初始簇中心。

6.根據權利要求4所述的一種基于MapReduce的k-means文本聚類裝置，其特征在于，所述迭代聚類模塊包括：

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

質心計算單元，用于運用Reduce函數根據Map函數的中間結果計算出新的初始簇中心；

判斷單元，用于對質心計算單元得到的Reduce結果，判斷得到的聚類初始簇中心和上一輪的初始簇中心之間的變化是否小于閾值，若小于，則聚類結束，否則開始新一輪的MapReduce。