[發(fā)明專利]一種基于Hadoop平臺的改進(jìn)并行KNN網(wǎng)絡(luò)輿情分類算法

在審

• 申請?zhí)枺?/td>: 201811594517.2
• 申請日: 2018-12-25
• 公開（公告）號: CN109739984A
• 公開（公告）日: 2019-05-10
• 發(fā)明（設(shè)計(jì)）人: 杜少波;李靜;楊露;袁華
• 申請（專利權(quán)）人: 貴州商學(xué)院
• 主分類號: G06F16/35
• 分類號: G06F16/35
• 代理公司: 貴陽中工知識產(chǎn)權(quán)代理事務(wù)所 52106
• 代理人: 劉安寧

1.一種基于Hadoop平臺的改進(jìn)并行KNN網(wǎng)絡(luò)輿情分類算法，其特征在于，CLARA算法的步驟如下：

S1：進(jìn)行m次迭代，迭代執(zhí)行S2-S6；

S2：從整體數(shù)據(jù)集D中按照隨機(jī)采樣的方法抽取相同數(shù)量r個對象得到樣本數(shù)據(jù)集S_i,S_i＝(s₁,s₂,…,s_r)；

S3：在樣本數(shù)據(jù)集S_i上調(diào)用PAM算法找到樣本數(shù)據(jù)集的最優(yōu)k個中心點(diǎn)集合C_i,C_i＝(c₁,c₂,…,c_k)；

S4：根據(jù)得到的C_i找到整個數(shù)據(jù)集D中的每一個對象O_j∈D在C_i中歐氏距離最近的中心點(diǎn)，將O_j劃分為相應(yīng)的簇中；

S5：根據(jù)公式計(jì)算數(shù)據(jù)集D中的每一個對象O_j∈D的平均相異度，作為評價標(biāo)準(zhǔn)；

S6：返回步驟S1，開始下一次迭代；

S7：所有迭代都完成后以平均相異度作為評價標(biāo)準(zhǔn)衡量聚類效果，平均相異度最小的即是最優(yōu)聚類；

S8：統(tǒng)計(jì)樣本數(shù)據(jù)集與k個聚類的平均相異度，如果Sim(D,O_i)小于給定的閾值則將其從樣本數(shù)據(jù)集中裁剪掉，否則將該簇內(nèi)包含的樣本添加到樣本集中。

2.根據(jù)權(quán)利要求1所述的一種基于Hadoop平臺的改進(jìn)并行KNN網(wǎng)絡(luò)輿情分類算法，其特征在于，KNN并行化MapReduce文本分類算法實(shí)現(xiàn)函數(shù)如下：

(1)Map函數(shù)

Input:訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集、設(shè)定k的值一般取奇數(shù)、給出訓(xùn)練數(shù)據(jù)集的類別；

Output：鍵值對<Key1,Value1>,其中Key1表示測試數(shù)據(jù)集索引值，Value1由字符串相似度S和類別標(biāo)簽C組成；

1:Method map(Key,Value,Key1,Value1)

2:{

3:for each line in Value do

將line中的數(shù)據(jù)分解成<id,x,y>的形式；

計(jì)算相似度S＝Sim(x,y)；

x表示測試向量；y表示訓(xùn)練向量；

Emit(Key1,Value1)；

4：}

(2)Reduce函數(shù)

Input：map函數(shù)的輸出結(jié)果<Key1,Value1>

Output：<Key2,Value2>,其中Key2為Key1的值，Value2表示分類結(jié)果

1:Methodreduce(Key1,Value1,Key2,Value2)

2:{

3:Collection sem＝new ArrayList()；

//聲明一個集合sem用于存放測試數(shù)據(jù)

//集與訓(xùn)練數(shù)//據(jù)集的相似度

4:Collection classify＝new ArrayList()；//聲明一個集合classify用于存放分類標(biāo)簽

5:for each v in Value1 do

構(gòu)建鍵值對＜S,C＞，其中S為相似度，C為類別標(biāo)簽；

將S的值加入到集合sem中，C添加到集合classify中；

6：將集合sem中的值進(jìn)行排序，確定k個最近鄰集合同時得到集合sem數(shù)據(jù)所對應(yīng)的類別；

7：把Key1的值賦值給Key2；

8：Emit(Key2,Value2)；

9：}

通過將KNN算法構(gòu)造成MapReduce程序?qū)崿F(xiàn)算法的并行化處理文本分類，其中Map函數(shù)中key值為測試數(shù)據(jù)集的行號即偏移量，Value代表該行對應(yīng)的訓(xùn)練集數(shù)據(jù)，數(shù)據(jù)集中包括相應(yīng)的屬性字段和類別標(biāo)示，Map階段的輸出Key1表示測試數(shù)據(jù)集的行號，Value1表示計(jì)算出的相似度S和類別標(biāo)簽C。在Reduce階段Key2表示測試數(shù)據(jù)集的行號，Value2代表計(jì)算出的分類結(jié)果。