適用于新媒體事件聚類模型的混合算法研究

孫玲芳，李金海

（江蘇科技大學(xué) 經(jīng)濟(jì)管理學(xué)院，江蘇 鎮(zhèn)江 212003）

0 引 言

從2003年的SARS事件開始，新媒體事件逐步呈現(xiàn)在公眾的視野中，并在近幾年里爆發(fā)頻率不斷提高，使得人們認(rèn)識到了新媒體事件的嚴(yán)重性，對新媒體事件的預(yù)警研究也成為網(wǎng)絡(luò)安全領(lǐng)域的熱點。對新媒體事件的預(yù)警就是在新的新媒體事件未爆發(fā)之前，依據(jù)某種策略對它進(jìn)行分類，分在不同類中的新媒體事件有著不同的處理措施，確保新媒體事件的及時發(fā)現(xiàn)以及妥善的處理。

目前常用的聚類方法有：層次法、劃分法、網(wǎng)格法以及密度法。其中被學(xué)者廣泛認(rèn)可的K＿M(jìn)eans算法是一種基于劃分的聚類算法；而另一種啟發(fā)式全局尋優(yōu)算法即遺傳算法（genetic algorithm，GA）近幾年也被大量學(xué)者研究。文獻(xiàn)［1］采用K＿M(jìn)eans算法作為聚類模型的主要算法，提出了一種運(yùn)算速度快，準(zhǔn)確性高的數(shù)據(jù)挖掘方法［1］；文獻(xiàn)［2］將遺傳算法和最近鄰算法動態(tài)結(jié)合，得到了一種更優(yōu)秀的聚類算法［2］；文獻(xiàn)［3］發(fā)現(xiàn)遺傳算法與蟻群算法的融合，較單獨(dú)的遺傳算法或蟻群算法，有著更好的聚類效果［3］。可見算法融合已經(jīng)成為構(gòu)建更為優(yōu)秀的聚類算法的方法，為本文的研究提供了理論依據(jù)。

1 聚類分析的原理

聚類分析是將多個樣本對象組成的集合，按相似性分成多個簇，性質(zhì)相近的歸為同一個簇，使得分在同一簇中的對象具有最大的同質(zhì)性，而分在不同簇中的對象具有最大的異質(zhì)性的過程。聚類分析的一般過程如圖1所示。

聚類算法的選擇需要依據(jù)聚類的目的以及樣本表示的數(shù)據(jù)類型來判斷，而且在有些聚類問題中單個算法已不能滿足算法的精度要求，這時就需要將兩個或兩個以上的算法相結(jié)合以達(dá)到更佳的效果。

圖1 聚類分析的一般過程

1.1 K＿M(jìn)eans的原理

聚類算法有動態(tài)與靜態(tài)之分，動態(tài)聚類算法與靜態(tài)聚類算法的主要區(qū)別在于通過不斷的迭代來完成聚類，且在迭代過程中允許樣本從一個簇中轉(zhuǎn)移到另一個簇中。K＿M(jìn)eans算法就屬于動態(tài)聚類法，因此它也具有動態(tài)聚類法的迭代特點［4］。動態(tài)聚類法過程如圖2所示。

圖2 動態(tài)聚類法過程

K＿M(jìn)eans算法是一種基于劃分的常見的聚類算法，一般采用誤差平方（均方差）作為標(biāo)準(zhǔn)測度函數(shù)。具體算法描述為：

Data［n］，k；

（1）C［1］＝data［1］，c［2］＝data［2］…c［k］＝data［k］；／隨機(jī)選取k個初始中心；

（2）對于data［1］，data［2］…data［n］，分 別 與c［1］，c［2］…c［k］比較，若與c［i］差值最小，就標(biāo)記為i；

（3）對于所有標(biāo)記為i的樣本，重新計算c［i］＝｛∑所有標(biāo)記為i的data／標(biāo)記為i的個數(shù)｝；

（4）重復(fù)（2）、（3），直到所有c［i］值的變化小于給定閥值。

標(biāo)準(zhǔn)測度函數(shù)為

式中：Di——c［i］中的Xk與相應(yīng)的聚類中心的度量即歐幾里德距離［5］。D——?dú)W幾里德距離之和，聚類的目的是使得非相似性（或距離）指標(biāo)的目標(biāo)函數(shù)達(dá)到最小，即D最小。

雖然K＿M(jìn)eans算法應(yīng)用廣泛，但該算法也有一定的局限性，該方法最終結(jié)果受初始值影響較大，結(jié)果較易陷入局部最優(yōu)，且對孤立點敏感。

1.2 遺傳算法的原理

在預(yù)警系統(tǒng)中，新媒體信息來源廣泛、內(nèi)容繁多，一般的聚類算法不能較好的處理，通過研習(xí)大量的文獻(xiàn)發(fā)現(xiàn)，遺傳算法適合新媒體事件的聚類分析。早在20世紀(jì)70年代就有人提出了遺傳算法，算法原理是模擬自然界生物的遺傳變異的進(jìn)化過程，通過遺傳算子來體現(xiàn)遺傳算法的思想，是一種啟發(fā)式全局尋優(yōu)算法［6］。遺傳算法的思想是基于遺傳規(guī)律與自然選擇。

遺傳算法處理的對象是染色體，每條染色體都是問題的一個解，算法的最終目的是選出最適應(yīng)環(huán)境的染色體，即最優(yōu)解。遺傳算法中的樣本組成了群體，個體對環(huán)境的適應(yīng)程度稱為適應(yīng)度。在執(zhí)行遺傳算法前，需要進(jìn)行編碼操作：把搜索空間中的數(shù)據(jù)轉(zhuǎn)換成遺傳空間中的染色體；在執(zhí)行遺傳算法后，需要進(jìn)行譯碼操作：把染色體轉(zhuǎn)換為問題原來的數(shù)據(jù)類型。

雖然遺傳算法具有很好的處理約束，能很好的跳出局部最優(yōu)，最終得到全局最優(yōu)解以及全局搜索能力強(qiáng)等諸多優(yōu)點；但遺傳算法全局搜索的特點也使得算法時間復(fù)雜度較大，不符合新媒體事件預(yù)警系統(tǒng)的及時性。

2 聚類算法的改進(jìn)

在分析K＿M(jìn)eans與遺傳算法的基礎(chǔ)上，發(fā)現(xiàn)K ＿M(jìn)eans算法以及遺傳算法都較適用于新媒體事件的聚類模型構(gòu)建，而它們各自存在的不足也正好被另一種算法所填補(bǔ)，若能將二者合理的結(jié)合，克服各自的劣勢，發(fā)揮各自的優(yōu)勢，必是一個優(yōu)秀的適應(yīng)新媒體事件聚類的算法?；诖耍疚奶岢隽嘶旌螷均值遺傳算法（genetic algorithm with K＿M(jìn)eans，GAWKM）的概念。此算法是基于K＿M(jìn)eans算法和遺傳算法原理的設(shè)想，結(jié)合K－Means算法的局部搜索能力與遺傳算法的全局搜索能力，最終得到全局最優(yōu)解，并且算法的時間復(fù)雜度在規(guī)定范圍之內(nèi)。

2.1 混合K均值遺傳算法的原理

在混合K均值遺傳算法中，選擇過程通過輪盤賭算法實現(xiàn)，并采用最優(yōu)保存策略保留上代中個體適應(yīng)度達(dá)種群平均適應(yīng)度1.5倍或以上（若種群規(guī)模較大，可適當(dāng)增大倍數(shù)，可加快算法的收斂速度）的個體進(jìn)入下一代的父代，缺少的子代則以隨機(jī)方式產(chǎn)生，最大程度保證了混合K均值遺傳算法的收斂［7］。交叉操作則采用單點交叉。通過仿真實驗發(fā)現(xiàn)，變異是遺傳算法能跳出局部最優(yōu)的關(guān)鍵操作，而變異概率決定著變異的效果，因此，讓變異概率隨著群體的平均適應(yīng)度不斷向最優(yōu)個體的適應(yīng)度接近時，就自適應(yīng)地動態(tài)增大。

2.2 混合K均值遺傳算法的具體流程

混合K均值遺傳算法的具體流程如下：

設(shè)樣本總數(shù)為n；聚類簇即聚類中心數(shù)為k（2≤k≤n－1）；交叉概率Pc，變異概率Pm，最大遺傳代數(shù)genmax，已迭代數(shù)gen，適應(yīng)度閥值F。

（1）選擇編碼策略：在混合K均值遺傳聚類算法中，每一條染色體都必須表示所有個體應(yīng)屬于哪類，所以染色體采用自然數(shù)編碼為佳［8］；設(shè)染色體Y＝（G1，G2，…，Gn），Y為1×n維向量，Gi為Y 上第i位的基因，其中：

RandomGi，

／基因Gi為k類中的某類

／基因的取值覆蓋所有聚類號，保證每條染色體都有效

在模型中，運(yùn)用式（1）隨機(jī)產(chǎn)生Gi，運(yùn)用式（2）循環(huán)判斷，若條件式（2）未滿足時，須重置Gi。

（2）定義適應(yīng)度函數(shù)：適應(yīng)度函數(shù)的好壞很大程度上影響遺傳算法的迭代次數(shù)與效果。本文采用“界限構(gòu)造法”［9］

為適應(yīng)度函數(shù)（fitness function）；其中

將求最小極值問題轉(zhuǎn)化為求最大極值問題，可以在選擇操作中直接使用輪盤賭算法。

／保留初始群體中適應(yīng)度最大的個體

（3）用K＿M(jìn)eans算法對每個個體進(jìn)行優(yōu)化gen＋＋；

／每迭代一次，已迭代數(shù)gen加一操作

／Yj為第j條染色體

優(yōu)化后，得到新的Yj＝（G1，G2，…，Gn）。

／a為采用最優(yōu)保存策略保留的進(jìn)入下代個體數(shù)｝通過輪盤賭算法選擇剩下的父代：

／r為0至1的隨機(jī)數(shù)

int c；c＝random（1，n）；

／在染色體中隨機(jī)選擇第c位的基因作為交叉點

在交叉操作中采用“基于最短距離基因匹配的算術(shù)交叉?！保?0］

需要注意的是，在這個學(xué)習(xí)過程中，無論語言也好還是文學(xué)作品也好，其中都包含了很多來自西方國家的價值取向，包括價值觀、人生觀的不同觀念影響，學(xué)生在整體的學(xué)習(xí)過程中很容易將其混淆，形成一種盲目崇拜和向往的思想，進(jìn)而影響到自己對于價值觀、人生觀、世界觀的基礎(chǔ)判斷。因此，在英美文化教學(xué)開展的過程中，融入對于思想政治教育的強(qiáng)調(diào)，使其引領(lǐng)英美文化教學(xué)進(jìn)一步開展是極為必要的[2]。

圖3 傳統(tǒng)交叉操作

而基于最短距離基因匹配的算術(shù)交叉，就能夠彌補(bǔ)傳統(tǒng)交叉操作的這一不足。操作過程如下：

minAj；

／比較出最短距離，并記錄是最短距離的那位基因j

j∈m；

這種交叉方法能夠改進(jìn)遺傳算法的收斂性，防止無意義個體的產(chǎn)生，加快聚類速度。

（6）變異操作（Mutation）

采用單點變異，變異概率Pm隨著群體的平均適應(yīng)度不斷向最優(yōu)個體的適應(yīng)度接近時，就自適應(yīng)地動態(tài)增大［11］，設(shè)定

按新的變異概率Pmi，選擇染色體Yai，在Yai上隨機(jī)選擇一個基因位c，并按式（5）變異

／保留新一代群體中適應(yīng)度最大的個體

（7）判斷算法是否結(jié)束

／達(dá)到最大代數(shù)或滿足適應(yīng)度要求

to（8）；

／執(zhí)行步驟（8）

else continue（3）；

／否則跳到步驟（3）

（8）用K＿M(jìn)eans算法對最優(yōu)個體優(yōu)化

／找出每代最優(yōu)個體中適應(yīng)度最大個體

Y＝（G1，G2，…，Gn），其中Data［n］＝Y(jié)

／Y為fmax對應(yīng)的染色體

優(yōu)化后，得到新的Y＝（G1，G2，…，Gn）

／得到的Y 即為最終的最優(yōu)個體

（9）輸出結(jié)果：Y＝（G1，G2，…，Gn）

／將基因值譯碼成類的編號

3 仿真實驗

我們運(yùn)用MATLAB7.0編譯混合K均值遺傳算法，實驗數(shù)據(jù)選取百度百科收錄的，近幾年（2009、2010、2011年）發(fā)生的新媒體事件50個，作為訓(xùn)練樣本，并按時間順序從1－50進(jìn)行標(biāo)記。具體樣本文件信息如圖4所示。

圖4 樣本文件信息

經(jīng)統(tǒng)計，上述50個新媒體事件的時間分布如表1所示。

表1 時間分布

通過對上述50個以及其它的新媒體事件的分析發(fā)現(xiàn)，新媒體事件大致分為以下四類：

（1）對社會的發(fā)展與穩(wěn)定有利的事件；

（2）屬于廣大網(wǎng)民自娛自樂的事件；

（3）對社會的發(fā)展與穩(wěn)定有一定負(fù)面影響的事件；

（4）嚴(yán)重影響社會的發(fā)展與穩(wěn)定的事件。

因此本文設(shè)定聚類數(shù)K＝4；樣本總數(shù)n＝50；交叉概率Pc＝0.7，變異概率Pm＝0.01，最大遺傳代數(shù)genmax＝200，已迭代數(shù)gen，適應(yīng)度閥值F＝0.05。

其中新媒體事件的文本信息通過向量空間模型轉(zhuǎn)換為計算機(jī)能夠識別形式［12］，表示為：

其中，X為新媒體事件的影響度值，Ti表示第i個特征項的值，Wi表示特征項Ti的向量權(quán)重，特征項為文本中重要的詞語，向量權(quán)重通過詞頻加權(quán)法計算得來，即某一特征項在文本中出現(xiàn)次數(shù)越多，Wi越大。向量空間模型經(jīng)過特征降維降為5維，這5個特征項是文本中出現(xiàn)次數(shù)最多的5個詞，Ti的具體數(shù)值與它的語義強(qiáng)度直接相關(guān)。有關(guān)轉(zhuǎn)換向量空間模型的具體過程這里不再詳述。50個新媒體事件的影響度在坐標(biāo)軸上的分布如圖5所示。

圖5 樣本分布

橫軸表示樣本的序號，縱軸表示樣本的影響度值。

將算法及樣本數(shù)據(jù)輸入MATLAB7.0，得到最優(yōu)解Y＝（1，3，3，1，4，4，3，4，4，3，4，3，2，3，3，4，2，3，4，4，4，3，2，2，2，2，2，3，2，3，4，3，4，3，3，3，4，2，4，3，3，1，4，2，1，3，4，3，3，3）；

聚類之后的樣本分布圖如圖6所示。

圖6 樣本聚類分布

具體聚類結(jié)果見表2。

表2 聚類結(jié)果

通過對聚類結(jié)果進(jìn)行分析，發(fā)現(xiàn)第6，23，31，36，40，50個新媒體事件的分類結(jié)果，與各大媒體最終對這些新媒體事件的評價有所不同。如分在第三類的40。郭美美事件，本身是一個炫富事件，應(yīng)該說對社會的發(fā)展與穩(wěn)定影響不大，但由于之后關(guān)聯(lián)了紅十字的一系列問題，使得國內(nèi)一時陷入了慈善荒，最終使事件升級為第四類新媒體事件。經(jīng)過試驗后的再次分析，發(fā)現(xiàn)這6個事件的誤判，是由于新媒體事件文本信息的不完善以及語義強(qiáng)度判斷算法還不夠精確所致。

第一類新媒體事件屬于對社會的發(fā)展與穩(wěn)定有利的事件，此類事件不需要有關(guān)部門的刻意引導(dǎo)，適當(dāng)?shù)陌効梢院霌P(yáng)社會風(fēng)氣；第二類新媒體事件屬于廣大網(wǎng)民自娛自樂的事件，一般此類事件不需要特別的關(guān)注，它們會隨著時間的流逝，讓公眾逐漸淡忘；第三類新媒體事件屬于對社會的發(fā)展與穩(wěn)定有一定負(fù)面影響，這類事件就需要有關(guān)部門及時做出正確的引導(dǎo)，防止發(fā)展成為第四類事件；而第四類新媒體事件的爆發(fā)則會嚴(yán)重影響社會的發(fā)展與穩(wěn)定，輕則擾亂社會治安，重則造成人員傷亡，對于這類事件，及時正確的官方引導(dǎo)是重點，而給予那些惡意煽動民意的幕后黑手相應(yīng)的處罰則是輔助措施。經(jīng)過對四類新媒體事件的分析，我們發(fā)現(xiàn)某個事件的從屬關(guān)系，并不是一成不變的，有關(guān)部門及時正確的引導(dǎo)能夠讓事件走向良性的發(fā)展方向，反之亦然。

本次仿真試驗的結(jié)果正確率約為88%，應(yīng)該說還較為理想。而導(dǎo)致誤差的大部分原因?qū)⒃诮窈蟮难芯恐胁粩嗤晟啤?/p>

4 結(jié)束語

通過將遺傳算法與K＿M(jìn)eans算法有效結(jié)合，提出了混合K均值遺傳算法，并合理運(yùn)用界限構(gòu)造法、最優(yōu)保存策略、基于最短距離基因匹配的算術(shù)交叉以及變異概率的自適應(yīng)改變等方法，在一定程度上解決了遺傳算法的收斂較慢、不適于處理復(fù)雜數(shù)據(jù)，以及K＿M(jìn)eans算法易于陷入局部最優(yōu)解、對孤立點敏感的不足。通過仿真試驗，發(fā)現(xiàn)試驗結(jié)果正確率較為理想，說明混合K均值遺傳算法適用于新媒體事件的聚類模型構(gòu)建，但此算法在前期的數(shù)據(jù)收集以及文本信息向計算機(jī)能識別的數(shù)據(jù)轉(zhuǎn)換精確度方面還不夠完善，在后期的研究中還有待改善。

［1］ZHOU Lijuan，SHI Qian，GE Xuebin，et al.Cluster－based evaluation in fuzzy－genetic data mining［J］.Computer Engineering and Applications，2010，46（13）：118－121（in Chinese）.［周麗娟，石倩，葛學(xué)彬，等.基于聚類的模糊遺傳挖掘算法的研究［J］.計算機(jī)工程與應(yīng)用，2010，46（13）：118－121.］

［2］LU Linhua.A novel dynamic clustering algorithm based on genetic algorithm［J］.Computer Simulation，2009，26（7）：122－125（in Chinese）.［陸林花.一種新的基于遺傳算法的動態(tài)聚類算法［J］.計算機(jī)仿真，2009，26（7）：122－125.］

［3］ZHU Feng，CHEN Li.Research on clustering algorithm based on fusion of ant colony and genetic algorithm［J］.Journal of Northwest University（Natural Science Edition），2009，39（5）：745－749（in Chinese）.［朱峰，陳莉.蟻群與遺傳算法融合的聚類算法研究［J］.西北大學(xué)學(xué)報（自然科學(xué)版），2009，39（5）：745－749.］

［4］Nazim Dugan，Sakir Erkoc.Genetic algorithm application to the structural properties of si－ge mixed clusters［J］.Materials and Manufacturing Processes，2009，24（3）：250－254.

［5］LIU Hailin.Research of web user clustering model based on genetic algorithm［D］.Tianjin：Tianjin University of Technology，2007：7－14（in Chinese）.［劉海琳.基于遺傳算法的Web用戶聚類模型的研究［D］.天津：天津理工大學(xué)，2007：7－14.］

［6］QIN Junhua，ZHANG Hongwei，ZHAO Shizheng.Fuzzy clustering analysis based on genetic algorithm and its application［J］.Computer Applications，2007，27（1）：52－55（in Chinese）.［覃俊華，張洪偉，趙世政.基于遺傳算法的模糊聚類研究及其應(yīng)用［J］.計算機(jī)應(yīng)用，2007，27（1）：52－55.］

［7］SU Liangyu，SU Liangbi.Cluster analysis based on genetic algorithm［J］.Computer Development and Application，2011，24（2）：7－9（in Chinese）.［蘇良昱，蘇良碧.基于遺傳算法的聚類分析［J］.電腦開發(fā)與應(yīng)用，2011，24（2）：7－9.］

［8］SHENG Weiguo，Allan Tucker，LIU Xiaohui.A niching genetic k－means algorithm and its applications to gene expression data［J］.Soft Computer，2010，14（11）：9－19.

［9］LOU Yuansheng，TAO Zhenhong.Web service composition algorithm for QoS global optimization［J］.Computer Engineering and Applications，2011，47（8）：207－210（in Chinese）.［婁淵勝，陶振宏.Web服務(wù)組合QoS全局優(yōu)化算法［J］.計算機(jī)工程與應(yīng)用，2011，47（8）：207－210.］

［10］LI Long1ong，WANG Mei1i.Research on an adaptive genetic algorithm based on weighted binary tree［J］.Computer Technology and Development，2010，20（11）：95－99（in Chinese）.［李龍龍，王美麗.基于加權(quán)二叉樹的自適應(yīng)遺傳算法研究［J］.計算機(jī)技術(shù)與發(fā)展，2010，20（11）：95－99.］

［11］ZHENG Yu，CHEN Zhuangzhuang，LI Yajuan，et al.New automatic alignment technology for single mode fiberwaveguide based on improved genetic algorithm［J］.Optoelectronics Letters，2009，5（3）：165－168.

［12］JING Liping，Michael K Ng，Joshua Z Huang.Knowledgebased vector space model for text clustering［J］.Knowledge and Information Systems，2010，25（1）：35－55.