一種基于K均值的網(wǎng)絡(luò)文本信息挖掘算法設(shè)計(jì)

劉曉敏，張艷麗，聶磊

(佳木斯大學(xué)，黑龍江佳木斯154007)

數(shù)據(jù)庫與信息管理

一種基于K均值的網(wǎng)絡(luò)文本信息挖掘算法設(shè)計(jì)

劉曉敏，張艷麗*，聶磊

(佳木斯大學(xué)，黑龍江佳木斯154007)

隨著大數(shù)據(jù)、云計(jì)算等技術(shù)的發(fā)展和普及，人們已經(jīng)進(jìn)入到共享信息的“互聯(lián)網(wǎng)+”時(shí)代，智能化、自動(dòng)化系統(tǒng)運(yùn)行積累了海量的數(shù)據(jù)資源，比如數(shù)以億計(jì)的文該文檔，這些資源充斥著整個(gè)網(wǎng)絡(luò)，無處不在，給人們的搜索帶來了極大的不便。該文為了解決網(wǎng)絡(luò)文本挖掘速度慢、準(zhǔn)確度低的問題，提出了一種基于K均值的網(wǎng)絡(luò)文本信息挖掘算法，實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的遺傳算法、支持向量機(jī)、BP神經(jīng)網(wǎng)絡(luò)相比，該文算法的準(zhǔn)確度可以顯著提高10.3%，并且不需要先驗(yàn)知識(shí)，更加適用于當(dāng)前互聯(lián)網(wǎng)搜索引擎、專家系統(tǒng)等，具有重要的作用和意義。

K均值；聚類；文本信息挖掘；準(zhǔn)確度

Key words：K mean;clustering;text information mining;accuracy

1 概述

網(wǎng)絡(luò)文本信息挖掘是搜索引擎、專家系統(tǒng)、知識(shí)庫等軟件的核心組成部分，也是當(dāng)前互聯(lián)網(wǎng)應(yīng)用的重要基礎(chǔ)，為電子商務(wù)、智能旅游、在線學(xué)習(xí)、物流倉儲(chǔ)、金融證券等業(yè)務(wù)的推廣提供了強(qiáng)大的支撐[1]。網(wǎng)絡(luò)文本信息挖掘可以從海量的、散亂的、無序的文本數(shù)據(jù)資源中發(fā)現(xiàn)潛在的、有價(jià)值的信息，并且將這些信息分類成為一個(gè)個(gè)的文檔簇，這些文檔簇的內(nèi)部具有高度相似性，簇之間具有高度的相異性。網(wǎng)絡(luò)文本信息通過相關(guān)算法操作之后，提供給人們的結(jié)果是可解釋的和有價(jià)值的，因此可以幫助人們進(jìn)行決策[2]。目前，網(wǎng)絡(luò)文本信息挖掘方法經(jīng)過多年的研究，已經(jīng)誕生了很多有效的挖掘方法，比如BP神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、遺傳算法、貝葉斯網(wǎng)絡(luò)等，本文提出在網(wǎng)絡(luò)文本挖掘中引入K均值算法，并且利用模糊數(shù)學(xué)改進(jìn)K均值算法，滿足大規(guī)模文本數(shù)據(jù)信息的挖掘和操作。

2 背景理論

K均值算法是一種基于距離的聚類算法，其可以將任意兩個(gè)對(duì)象之間的距離作為相似性度量指標(biāo)，利用無監(jiān)督學(xué)習(xí)的思想，將距離最近的兩個(gè)數(shù)據(jù)對(duì)象集成在一起[3]。K均值算法執(zhí)行中不需要任何先驗(yàn)知識(shí)，任何一個(gè)搜索引擎、專家系統(tǒng)都不需要背景知識(shí)即可完成信息挖掘和分類，同時(shí)可以利用文本數(shù)據(jù)挖掘準(zhǔn)確度等指標(biāo)進(jìn)行評(píng)價(jià)，將文本數(shù)據(jù)匯聚在一起，實(shí)現(xiàn)數(shù)據(jù)解釋和操作。K均值算法形式化描述如下：假設(shè)網(wǎng)絡(luò)文本數(shù)據(jù)集包含n個(gè)文檔，使用X={x1,x2,…,xn}表示，每一個(gè)文檔都可以使用m個(gè)特征刻畫，這些特征可以是某些出現(xiàn)頻次較高的單詞，也可以是文檔的風(fēng)格、主題等，則第j個(gè)樣本的特征向量使用則數(shù)據(jù)集可以使用矩陣進(jìn)行描述，如公式(1)所示。

其中，xij表示樣本j的特征i，j=1,2,…n，i=1,2,…m。

在k均值算法處理過程中，為了能夠消除數(shù)據(jù)集m個(gè)特征值之間的量綱差別，需要對(duì)其進(jìn)行歸一化處理，具體處理過程如公式(2)所示。

其中，ximax表示第i個(gè)指標(biāo)特征的最大取值；ximin表示第i個(gè)指標(biāo)特征的最小取值；rij表示歸一化后xij的取值。歸一化之后，數(shù)據(jù)集的描述矩陣X可以使用矩陣R表示，如公式(3)所示。

假設(shè)數(shù)據(jù)集X擁有C個(gè)類別，則數(shù)據(jù)集X的模糊識(shí)別矩陣如公式(4)所示。

水稻種質(zhì)資源耐旱性鑒定與評(píng)價(jià)………… 王寶祥，余劍鋒，徐 波，劉 艷，邢運(yùn)高，孫治廣，遲 銘，石時(shí)來，邊建民，徐大勇（1）

其中，uhj表示數(shù)據(jù)集中的樣本j歸屬于h類的隸屬度，h=1,2,…,C，并 且 滿 足 以 下 約 束 條 件 ：0≤uhj≤1，

假設(shè)類別h的m個(gè)特征值稱為類的聚類中心，則c個(gè)類別的特征值可以使用模糊聚類中心陣表示，如公式(5)所示。

其中，sih表示類別h指標(biāo)i的歸一化特征值，0≤sih≤1。

在模糊聚類執(zhí)行過程中，可以設(shè)置不同的特征權(quán)重，一般能夠優(yōu)化突出較為重要的特征貢獻(xiàn)，特征權(quán)重向量如公式(6)所示。

通過分析，模糊聚類的目標(biāo)函數(shù)如公式(7)所示。

具體地，在實(shí)際應(yīng)用過程中，具體算法可以采用迭代執(zhí)行的過程，求取目標(biāo)函數(shù)的最優(yōu)解。

3 基于K均值的網(wǎng)絡(luò)文本信息挖掘算法設(shè)計(jì)

3.1 算法設(shè)計(jì)

K均值算法引入模糊數(shù)學(xué)，將K均值從傳統(tǒng)的硬劃分改進(jìn)到軟劃分，這樣就可以更好地將每一個(gè)數(shù)據(jù)劃分到類別中，具體的基于模糊數(shù)學(xué)改進(jìn)的K均值算法目標(biāo)函數(shù)如公式(8)所示。

其中，b是一個(gè)模糊數(shù)學(xué)模糊度常數(shù)，其可以有效地控制模糊聚類結(jié)果，通過對(duì)模糊K均值算法的隸屬度進(jìn)行求導(dǎo)數(shù)，可以獲取一個(gè)最優(yōu)解，具體的執(zhí)行過程如公式(9)和公式(10)所示。

模糊K均值算法執(zhí)行過程中，公式(9)和公式(10)可以進(jìn)行有效的迭代執(zhí)行，這樣就可以將所有的數(shù)據(jù)劃分到一個(gè)簇中，標(biāo)注出每一個(gè)文本對(duì)象屬于數(shù)據(jù)集的隸屬度，當(dāng)隸屬度不再改變時(shí)即可完成數(shù)據(jù)的分類。具體地，模糊K均值算法在文本信息挖掘中的具體描述如下：

算法輸入：文本對(duì)象簇?cái)?shù)目K，參數(shù)b，包含N個(gè)文本對(duì)象的數(shù)據(jù)集。

算法輸出：K個(gè)文本對(duì)象簇。

算法步驟：

1)利用隨機(jī)化方法或啟發(fā)式方法劃分文本對(duì)象數(shù)據(jù)集為K個(gè)簇，指定每一個(gè)簇的中心數(shù)據(jù)對(duì)象為mi；

2)計(jì)算文本對(duì)象數(shù)據(jù)集中的每一個(gè)文本信息隸屬函數(shù)，采用的計(jì)算公式為公式(10)；

3)基于步驟2)的隸屬度函數(shù)計(jì)算各個(gè)簇的中心值mi，采用的計(jì)算公式為公式(9)；

4)遍歷文本對(duì)象數(shù)據(jù)集中每一個(gè)文本，當(dāng)隸屬度不再發(fā)生任何變化時(shí)，算法終止；否則返回步驟2)。

3.2 算法實(shí)驗(yàn)結(jié)果及分析

文本數(shù)據(jù)挖掘過程中，本文的主要關(guān)注點(diǎn)是新的算法能否從數(shù)據(jù)集中正確地發(fā)現(xiàn)隱含的模式，以便能夠判斷文本數(shù)據(jù)挖掘的準(zhǔn)確度。因此，在算法運(yùn)行和評(píng)估過程中，本文使用已知類標(biāo)號(hào)的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，便于進(jìn)行準(zhǔn)確度評(píng)估。具體地，本文的數(shù)據(jù)集來源于Lang收集的數(shù)據(jù)集，這個(gè)數(shù)據(jù)集共計(jì)包含2000篇信息文檔，并且分為20個(gè)種類，對(duì)每一件文檔都進(jìn)行了評(píng)論，每個(gè)評(píng)論組均包含100個(gè)用戶，因此評(píng)價(jià)指標(biāo)包括2000個(gè)評(píng)價(jià)得分。本文通過對(duì)2000篇文檔進(jìn)行評(píng)價(jià)，將其分為9個(gè)子數(shù)據(jù)集，每一個(gè)文本數(shù)據(jù)集包含了500篇文檔，每一個(gè)子數(shù)據(jù)集都是從2000篇文檔中隨機(jī)挑選的，具體地，Binary_1,2,3表示擁有兩個(gè)真實(shí)類別的文檔數(shù)據(jù)集；Multi5_1,2,3可以描述擁有五個(gè)真實(shí)類別文檔數(shù)據(jù)集；Multi10_1,2,3可以描述擁有十個(gè)真實(shí)類別文檔數(shù)據(jù)集。

通常情況下，文本數(shù)據(jù)挖掘采用準(zhǔn)確度作為算法評(píng)價(jià)運(yùn)行結(jié)果的標(biāo)準(zhǔn)，算法運(yùn)行結(jié)果準(zhǔn)確度評(píng)價(jià)公示如公式(11)所示。

其中，t∈T，其可以描述相關(guān)的數(shù)據(jù)對(duì)象；c∈C，其可以描述相關(guān)的類別號(hào)或簇標(biāo)號(hào)；A1(c,T)可以描述相關(guān)的已經(jīng)正確分配到c中的文檔或元組的數(shù)量；A2(c,T)可以描述相關(guān)的算法不正確的分配到c中的文檔或元組的數(shù)量；A3(c,T)可以描述相關(guān)的不正確的沒有分配到c中的文檔或元組的數(shù)量。

通過觀察可以得知，在9個(gè)數(shù)據(jù)集上，本文算法可以很好地發(fā)現(xiàn)真實(shí)文檔之間存在的模式，更加精準(zhǔn)地尋找到潛在結(jié)構(gòu)和類別，尤其是在兩類文檔中，算法分析的準(zhǔn)確度可以達(dá)到93.94%，能夠?yàn)橛脩敉扑]更符合和滿足用戶需求的文檔數(shù)據(jù)搜索結(jié)果，具有非常重要的意義和價(jià)值，這些搜索數(shù)據(jù)機(jī)結(jié)果可以為百度搜索、搜狗、騰訊、京東等網(wǎng)站進(jìn)行使用，更好地為用戶提供真實(shí)文檔數(shù)據(jù)分析服務(wù)，發(fā)掘潛在的價(jià)值。算法運(yùn)行結(jié)果如表1所示。

表1 三種算法的實(shí)驗(yàn)結(jié)果準(zhǔn)確度對(duì)比

4 結(jié)束語

隨著互聯(lián)網(wǎng)應(yīng)用軟件的誕生，軟件運(yùn)行積累了海量的數(shù)據(jù)資源，尤其是文本文檔數(shù)據(jù)呈現(xiàn)出指數(shù)級(jí)速度上升，因此如何從海量文本數(shù)據(jù)中挖掘潛在的有價(jià)值信息，為人們的工作、生活和學(xué)習(xí)提供決策支撐，具有重要的作用和意義。K均值是一種無監(jiān)督的聚類算法，其在執(zhí)行中不需要任何先驗(yàn)知識(shí)，同時(shí)可以準(zhǔn)確地劃分文本數(shù)據(jù)集，提供一個(gè)準(zhǔn)確的分類，可以大大地提高電子商務(wù)、搜索引擎的運(yùn)行準(zhǔn)確度，具有重要的作用和意義。

[1]張群,王紅軍,王倫文,等.基于詞條屬性聚類的文本特征選擇算法[J].計(jì)算機(jī)應(yīng)用研究,2017(2)：369-372.

[2]徐勇,陳亮.一種基于降維思想的K均值聚類方法[J].湖南城市學(xué)院學(xué)報(bào):自然科學(xué)版,2017,26(1)：54-61.

[3]李曉瑜,俞麗穎,雷航,等.一種K-means改進(jìn)算法的并行化實(shí)現(xiàn)與應(yīng)用[J].電子科技大學(xué)學(xué)報(bào),2017,46(1)：61-68.

Design of Network Text Information Mining Algorithm Based on K Mean

LIU Xiao-min,ZHANG Yan-li★,NIE Lei
(Jiamusi University,Jiamusi 154007,China)

TP311

A

1009-3044(2017)24-0001-02

2017-07-30

佳木斯大學(xué)校級(jí)重點(diǎn)項(xiàng)目《計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)實(shí)施導(dǎo)師制的研究》(項(xiàng)目編號(hào)：2017LGL-009)；佳木斯大學(xué)教研項(xiàng)目(2016JL1015)；佳木斯大學(xué)學(xué)位與研究生教研項(xiàng)目(基于“產(chǎn)、學(xué)、研”的研究生創(chuàng)新能力的培養(yǎng)與實(shí)踐)

劉曉敏(1980—)，女，佳木斯大學(xué)，講師，碩士，主要從事計(jì)算機(jī)專業(yè)的教學(xué)，主要研究方向?yàn)閳D像處理和模式識(shí)別；通訊作者：張艷麗(1974—)，女，佳木斯大學(xué)，講師，博士，主要從事農(nóng)業(yè)電氣化、電氣工程專業(yè)的教學(xué)。