[發明專利]基于MapReduce框架下的海量文本快速聚類的方法

有效

• 申請號: 202011051536.8
• 申請日: 2020-09-29
• 公開（公告）號: CN112463958B
• 公開（公告）日: 2022-07-15
• 發明（設計）人: 程永龍;李美晶
• 申請（專利權）人: 上海海事大學
• 主分類號: G06F16/35
• 分類號: G06F16/35;G06F16/33;G06F40/284;G06K9/62;G06Q40/06
• 代理公司: 上海互順專利代理事務所(普通合伙) 31332
• 代理人: 成秋麗

1.基于MapReduce框架下的海量文本快速聚類的方法，其特征在于，包含以下步驟：

S1、對海量文本數據在Hadoop分布式環境下進行預處理，對每個文本進行分詞，轉化成一組分詞串；

S2、在Hadoop分布式環境下利用TF-IDF方法對文本的分詞串進行特征提取，每條文本形成可供計算機識別的數字向量；

S3、將所述步驟S2得到的所述文本數字向量，在Hadoop分布式環境下利用改進的快速初始化K均值聚類算法得到K個初始的質心向量；

S4、將所述步驟S2中所述文本數字向量與所述步驟S3中所述文本質心向量在Hadoop分布式環境下進行聚類，得到聚類結果；

所述步驟S1進一步包含以下步驟：

S1.1、將待預處理文本作為輸入文件，對輸入文件每一行做一遍映射歸約；所述映射歸約過程如下：

(1)將所述輸入文件按行拆分成多個小文件，該小文件中每一行由文本號和對應內容組成，為每一個小文件分配一個映射任務；

(2)在映射階段，將每行內容進行半角向全角轉化、大寫數字向小寫數字轉化、大寫字母向小寫字母轉化、去除文本中的表情符號，用jieba分詞工具進行分詞處理，jieba分詞是一種中文分詞工具，將得到的分詞串去除停用詞，輸出一個鍵值對，鍵是該文本號，值是去除停用詞后的分詞串；

(3)在歸約階段，直接輸出鍵值對，得到每一行由每篇文本的分詞串組成的分詞串文件；

所述步驟S2進一步包含以下步驟：

S2.1、將分詞串文件作為輸入文件，對輸入文件每一行做一遍映射歸約；所述映射歸約過程如下：

(1)將所述輸入文件按行拆分成多個小文件，該小文件中每一行由文本號和對應分詞串組成，為每一個小文件分配一個映射任務；

(2)在映射階段，將每行分詞串去除重復分詞后的分詞取集合，輸出一個鍵值對，鍵是該文本號，值是取集合后的分詞串；

(3)在歸約階段，將每行分詞串合并在一起，取集合組成詞袋，輸出一個鍵值對，鍵為1，值為分詞串集合組成的詞袋，得到一個詞袋文件；

S2.2、將所述步驟S1.1中分詞串文件與S2.1中的詞袋文件，利用TF-IDF進行特征提取；

TF-IDF特征提取計算公式如下：

式中，N_w是在一條文本中分詞w出現的次數，N是該條文本中分詞串中總分詞數，TF_w是分詞w的詞頻；

其中，Y是文本的總數，Y_w是包含分詞w的文本個數，IDF_w是分詞w的逆文本頻率；

(TF-IDF)_w＝TF_w*IDF_w

其中，(TF-IDF)_w是分詞w的詞頻-逆文本頻率指數；

所述步驟S3文本數字向量為S2.2中分詞串的詞頻-逆文本頻率指數構成；所述步驟S3進一步包含以下步驟：

S3.1將所述步驟S2得到的所述文本數字向量中隨機抽取一部分樣本向量，該樣本向量數量為指定K值的三到五倍，其他海量文本為剩余其他向量；

S3.2將所述S3.1所述樣本向量中任意選取一向量，命名為C1，計算C1與樣本向量中所有剩余樣本向量的余弦相似度；

余弦相似度計算公式如下：

式中，x₁與x₂是兩個需要計算的向量，sim(x₁，x₂)是余弦相似度；

S3.3由所述步驟S3.2的余弦相似度計算結果，找到與所述C1余弦相似度較大的向量，命名Ca，計算Ca與其他所有剩余樣本向量的余弦相似度，找到與所述Ca余弦相似度較大的向量，命名Cmax，與較小的向量，命名Cmin；計算所述Ca與所述Cmin的余弦相似度sim(Ca，Cmin)值對應的余弦角度θ；

余弦角度θ計算如下：

sim(Ca，Cmin)＝cosθ

θ＝arccos(sim(Ca，Cmin))

S3.4將步驟S3.3所述余弦角度θ除以指定K值，得到角度間隔θ₁，得到如下角度區間劃分：

[0，θ₁]，[θ₁，2θ₁]，[2θ₁，3θ₁]，.......,[(k-1)θ₁，kθ₁]，共K個區間；

S3.5選取步驟S3.3所述Cmax向量作為參照向量，分別選取步驟S3.4所述區間進行如下計算：

(1)首先選定首個區間[0，θ₁]，逐個計算Cmax與所述其他所有剩余樣本向量的余弦相似度，直到找到一個向量，命名C₁，滿足：cos(0)sim(Cmax,C₁)＝cos(θ₁),記下向量C₁，停止此輪計算；

(2)依次選定區間[θ₁，2θ₁]，逐個計算Cmax與所述其他所有剩余樣本向量的余弦相似度，直到找到一個向量，命名C₂，滿足：cos(θ₁)sim(Cmax,C₂)＝cos(2θ₁),記下向量C₂，停止此輪計算；

(3)以此類推進行第K次，選定區間[(k-1)θ₁，kθ₁]，逐個計算Cmax與所述其他剩余樣本向量的余弦相似度，直到找到一個向量，命名C_k，滿足：cos((k-1)θ₁)sim(Cmax,C_k)＝cos(kθ₁),記下向量C_k，停止此輪計算；

S3.6根據所述步驟S3.5可得到一組向量{C₁，C₂，.....，C_k}，記為初始質心向量；若出現質心向量個數小于K，則缺少向量從所述步驟S3.1所述剩余其他向量隨機選取；

所述步驟S4中進一步包含以下步驟：

S4.1將所述步驟S2中所述文本數字向量作為輸入文件，所述步驟S3中所述文本質心向量作為質心向量文件，質心向量文件每行由質心向量序號與質心向量組成；對輸入文件的每一行作第一遍映射歸約；所述第一遍映射歸約過程如下：

(1)將所述輸入文件按行拆分成多個小文件，該小文件中每一行為一個樣本的數字向量，為每一個小文件分配一個映射任務；

(2)在映射階段，將小文件中每一行向量與所述質心向量文件中每個質心向量進行余弦相似度計算，找出所計算出的余弦相似度最大值對應的向量，作為此行向量的類質心向量，輸出如下的鍵值對：該類質心向量的序號作為鍵，此行向量作為值；

(3)在歸約階段，將鍵相同的數字向量進行相加求和并除以它們的個數，得到它們的平均值，輸出對應的鍵和所得的平均值；

(4)將歸約階段輸出的內容作為新的質心向量文件，將之前質心向量文件作為舊的質心向量文件，比較新舊兩個質心向量文件是否近似相等，比較方法為：將兩個文件質心向量序號相同的質心向量進行相減，將相減得到的誤差向量，該誤差向量中絕對值最大的向量值作為該誤差向量的誤差值，在所有序號相同向量相減得到的誤差向量的誤差值中，找出最大的誤差值作為質心向量的總誤差W，將W與預先設定的閾值Y比較大小，若W小于閾值Y，則聚類結束，得到最終質心向量文件；若W大于Y，則進行下一遍映射歸約直至W小于閾值Y為止，在每一遍映射歸約中，將上一遍產生的新的質心向量文件作為此次映射歸約的質心向量文件，文本數字向量依舊作為輸入文件；

S4.2將所述步驟S4.1聚類最終得到質心向量文件作為質心向量文件，所述步驟S4.1中所述文本數字向量文件作為輸入文件，進行一遍映射歸約，過程如下：

(1)將所述輸入文件按行拆分成多個小文件，該小文件中每一行為一個樣本的數字向量，為每一個小文件分配一個映射任務；

(2)在映射階段，將小文件中每一行向量與所述質心向量文件中每個質心向量進行余弦相似度計算，找出所計算出的余弦相似度最大值對應的向量，作為此行向量的類質心向量，輸出這樣的鍵值對：該類質心向量的序號作為鍵，此行向量作為值；

(3)在歸約階段，直接輸出鍵值對，鍵則為每個文本向量數據的簇標號，值為行向量；

所述步驟S4.1中聚類方法包含以下步驟：

S4.1-1、所述步驟S4.1所述總誤差W大于所述閾值Y時，進行下一遍映射歸約，所述步驟S4.1輸入文件依然作為輸入文件，所述步驟S4.1新的質心向量文件作為質心向量文件，第二遍映射歸約過程如下：

(1)將所述輸入文件按行拆分成多個小文件，該小文件中每一行為一個樣本的數字向量，為每一個小文件分配一個映射任務；

(2)在映射階段，將小文件中每一行向量與所述質心向量文件中每個質心向量進行余弦相似度計算，找出所計算出的余弦相似度最大值對應的向量，作為此行向量的類質心向量，輸出這樣的鍵值對：該類質心向量的序號作為鍵，此行向量作為值；

(3)在歸約階段，將鍵相同的數字向量進行相加求和并除以它們的個數，得到它們的平均值，輸出對應的鍵和所求的平均值；

(4)將歸約階段輸出的內容作為新的質心向量文件，將之前質心向量文件作為舊的質心向量文件，比較新舊兩個質心向量文件是否近似相等，比較方法為：將兩個文件質心向量序號相同的質心向量進行相減，將相減得到的誤差向量，該誤差向量中絕對值最大的向量值作為該誤差向量的誤差值，在所有序號相同向量相減得到的誤差向量的誤差值中，找出最大的誤差值作為質心向量的總誤差W，將W與預先設定的閾值Y比較大小，若W小于閾值Y，則聚類結束，得到最終質心向量文件；若W大于Y，則再次進行下一遍映射歸約，直至W小于閾值Y為止。