蘭慧紅,黃緊德

基于改進(jìn)EMD距離的信息特征單元的聚類(lèi)方法

蘭慧紅,黃緊德

廣西教育學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院, 廣西 南寧 530023

為研究基于改進(jìn)EMD距離的信息特征單元聚類(lèi)方法，本文利用向量空間方法提取信息特征單元，設(shè)置EMD地面距離作為不同信息特征單元間的距離，將信息特征單元比作供貨商與消費(fèi)商。為避免利用EMD距離聚類(lèi)引起的信息特征單元過(guò)分割、正例現(xiàn)象增多以及供貨商無(wú)法供貨問(wèn)題，設(shè)置符合特征相似條件的供貨商增大權(quán)值的相似閾值，利用閾值令運(yùn)輸以低成本的供貨商為主，改進(jìn)EMD距離；利用改進(jìn)EMD距離算法實(shí)現(xiàn)信息特征單元的有效聚類(lèi)。經(jīng)仿真平臺(tái)驗(yàn)證，該方法對(duì)文本、股票等不同類(lèi)型信息特征單元聚類(lèi)精度達(dá)到99%以上，并且聚類(lèi)過(guò)程迭代次數(shù)少，聚類(lèi)性能優(yōu)。

EMD距離; 信息特征單元; 聚類(lèi)方法

近年來(lái)網(wǎng)絡(luò)發(fā)展飛速，人類(lèi)生活已經(jīng)越來(lái)越走進(jìn)信息化[1]。在這種大數(shù)據(jù)環(huán)境下，如何從繁瑣無(wú)規(guī)律的信息中有效尋找自身需要且具有價(jià)值信息是目前急需解決的問(wèn)題[2]。在大數(shù)據(jù)環(huán)境下檢索信息特征單元，并將信息特征單元進(jìn)行分類(lèi)與融合，在數(shù)據(jù)挖掘、知識(shí)管理與數(shù)據(jù)搜索等領(lǐng)域中都具有重要意義[3,4]。

以往信息特征單元聚類(lèi)方法的聚類(lèi)效果都較為粗糙，例如基于GDD算法的聚類(lèi)方法可將大部分信息特征單元聚類(lèi)，但是存在單元過(guò)分割問(wèn)題，聚類(lèi)精度低；基于PCAP算法的聚類(lèi)方法精度可達(dá)到要求，但計(jì)算過(guò)程復(fù)雜，并容易受噪聲影響[5]。本文針對(duì)以上聚類(lèi)方法存在的缺點(diǎn)，提出基于改進(jìn)EMD (Earth Mover's Distance)距離的信息特征單元聚類(lèi)方法，通過(guò)該方法進(jìn)行信息特征單元聚類(lèi)，可有效處理含有噪聲的信息特征單元，解決單元過(guò)分割、正例現(xiàn)象增多等問(wèn)題，使信息特征單元聚類(lèi)結(jié)果更加精確[6]。

1 信息特征單元聚類(lèi)方法分析

1.1 提取信息特征單元

采用向量空間方法提取信息特征單元。設(shè)待提取信息特征單元集為S=(t1,w1;t2,w2;L;t,w)，該特征單元集中，t1表示信息特征單元，w1表示該信息特征單元權(quán)重，利用信息特征單元間相似度衡量信息特征單元相關(guān)程度公式如下：

若向量維數(shù)較高，在利用提取的信息特征單元進(jìn)行聚類(lèi)時(shí)會(huì)增加聚類(lèi)復(fù)雜度并為聚類(lèi)增加干擾，為了解決含有噪聲的信息特征單元，因此需先篩選候選特征信息增益再提取信息特征單元[7]。

利用信息增益衡量提取信息特征單元的度量，待聚類(lèi)特征集的信息增益公式如下：

式中，n表示訓(xùn)練特征集中出現(xiàn)t的數(shù)量，(t)表示待聚類(lèi)特征t的信息增益，(t)公式如下：

特征的條件熵公式如下：

以上公式中，(S|t)為特征t與特征S同時(shí)出現(xiàn)的條件概率。

提取的特征單元信息增益可直接反應(yīng)出信息特征單元聚類(lèi)能力，將所獲取的(t)結(jié)果依據(jù)從大至小順序排序，設(shè)置閾值對(duì)排序結(jié)果進(jìn)行階段，將符合閾值條件的信息特征單元為信息特征單元聚類(lèi)依據(jù)[8]。

1.2 EMD距離

EMD距離是從運(yùn)輸問(wèn)題演化而來(lái)，是一種度量相似性的方法，可實(shí)現(xiàn)信息與信息之間多對(duì)多優(yōu)良匹配，因此很適宜用于信息特征單元聚類(lèi)[9]。因此定義EMD地面距離作為不同信息特征單元間的距離[10]EMD距離具體可描述為：存在多個(gè)供應(yīng)商將自身一定數(shù)量貨物發(fā)送至不同消費(fèi)商，尋找成本最小的貨物傳輸途徑，使貨物可以滿(mǎn)足消費(fèi)商要求進(jìn)行有效的發(fā)送。利用運(yùn)輸問(wèn)題將特征聚類(lèi)問(wèn)題簡(jiǎn)化為線(xiàn)性規(guī)劃問(wèn)題，可以很好的解決信息特征單元聚類(lèi)問(wèn)題。

設(shè)上文中提取不同信息特征單元空間中含有的距離映射用表示，:×?+，則有：

以上公式中，,?為該特征空間中一點(diǎn)，點(diǎn)的權(quán)值用w表示。

設(shè)=[d]為地面距離矩陣，表示點(diǎn)與點(diǎn)間地面距離。設(shè)點(diǎn)p與點(diǎn)q間流用S表示，存在流矩陣=[S]以保證全局代價(jià)函數(shù)為最小，且應(yīng)滿(mǎn)足的約束條件如下：

S≥0，1≤≤，1≤≤(6)

利用以上公式解決EMD距離的運(yùn)輸問(wèn)題，獲取矩陣，可得EMD距離的運(yùn)輸工作規(guī)格化值：

EMD距離中EMD值不會(huì)隨特征分布的微小變化而引起波動(dòng)，因此具有連續(xù)性；EMD距離的特征分布緊湊型與靈活性可避免屬性相似性度量的量化問(wèn)題；有利于特征匹配的平衡。雖然EMD距離具有以上優(yōu)點(diǎn)，但是EMD距離也有著對(duì)精度要求高導(dǎo)致計(jì)算過(guò)于復(fù)雜的缺點(diǎn)，因此在進(jìn)行信息特征單元聚類(lèi)時(shí)需要對(duì)EMD距離進(jìn)行改進(jìn)。

1.3 基于改進(jìn)EMD距離的信息特征單元聚類(lèi)

針對(duì)EMD距離的信息特征單元聚類(lèi)問(wèn)題，可將信息特征單元比作供貨商與消費(fèi)商，設(shè)二者分別為S={x,=1,2,…,}與S={x,=1,2…,}，且滿(mǎn)足x?R，x?R。兩信息特征單元的EMD距離隨權(quán)值w，w與運(yùn)輸成本d改變而改變。信息特征單元間距離相似性用d衡量，具體公式如下：

將現(xiàn)有的信息單元特征值集定義w。對(duì)信息單元特征集以“分割特征數(shù)量與總特征集比值”作為相應(yīng)區(qū)域權(quán)值。通過(guò)特征與質(zhì)心距離計(jì)算信息特征單元集，具體計(jì)算過(guò)程為：

式中，O表示特征S質(zhì)心。

采用未改進(jìn)EMD距離聚類(lèi)信息特征單元時(shí)，會(huì)引起特征單元過(guò)分割、正例現(xiàn)象增多以及供貨商無(wú)法供貨的問(wèn)題，因此需改進(jìn)EMD距離，使信息特征單元聚類(lèi)結(jié)果最優(yōu)。

計(jì)算信息特征單元集S內(nèi)的示例相似性，將小于閾值的特征合并，計(jì)算特征相似性公式如下：

若公式（11）計(jì)算結(jié)果sim(x,x)<，那么對(duì)應(yīng)特征示例可合并為新示例，合并過(guò)程如下：

以上公式中，為|S|內(nèi)與x相似示例數(shù)量。

2 實(shí)驗(yàn)分析

為檢驗(yàn)改進(jìn)EMD距離方法對(duì)信息特征單元的聚類(lèi)效果，在Matlab仿真實(shí)驗(yàn)平臺(tái)中編寫(xiě)本文方法進(jìn)行聚類(lèi)實(shí)驗(yàn)，實(shí)驗(yàn)?zāi)繕?biāo)分別為（1）來(lái)自中國(guó)科學(xué)院計(jì)算技術(shù)研究所文本數(shù)據(jù)；（2）Iris數(shù)據(jù)庫(kù)中選取的信息特征單元；（3）MIL標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)中數(shù)據(jù)集MUSK；（4）中國(guó)財(cái)經(jīng)股票2018年1月1日至12月31日的30支股票數(shù)據(jù)。并將本文方法聚類(lèi)結(jié)果與GDD方法和PCAP方法聚類(lèi)結(jié)果進(jìn)行比較。

2.1 文本特征單元聚類(lèi)結(jié)果

將來(lái)自中國(guó)科學(xué)院計(jì)算技術(shù)研究所文本信息特征單元10000例進(jìn)行分析，利用本文方法、GDD方法和PCAP方法三種方法進(jìn)行聚類(lèi)，結(jié)果見(jiàn)表1。

表1 三種方法聚類(lèi)文本特征單元結(jié)果

三種方法聚類(lèi)文本特征單元結(jié)果準(zhǔn)確率見(jiàn)圖1。

圖1 三種方法聚類(lèi)文本特征單元準(zhǔn)確率

從表1與圖1結(jié)果可以看出，本文方法聚類(lèi)中國(guó)科學(xué)院計(jì)算技術(shù)研究1000例文本信息特征單元結(jié)果準(zhǔn)確率最高，準(zhǔn)確率均在99%以上，說(shuō)明了本文方法的聚類(lèi)有效性。

2.2 Iris數(shù)據(jù)庫(kù)聚類(lèi)結(jié)果

在Iris數(shù)據(jù)庫(kù)中選取鳶尾花特征作為聚類(lèi)信息特征單元，該信息特征共有200例，分為4類(lèi)，每類(lèi)包含50例，各例信息特征單元中含有4個(gè)屬性。三種方法聚類(lèi)結(jié)果見(jiàn)表2。

表2 三種方法聚類(lèi)鳶尾花信息特征單元結(jié)果

表2可以看出，本文方法聚類(lèi)結(jié)果較準(zhǔn)確，正確率在95%以上，而GDD方法正確率僅為80%左右，PCAP方法正確率最高僅為76%，驗(yàn)證了本文方法的聚類(lèi)有效性及準(zhǔn)確性。

2.3 MIL標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)聚類(lèi)結(jié)果

在MIL標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)中選取MUSK數(shù)據(jù)集作為實(shí)驗(yàn)對(duì)象，MUSK數(shù)據(jù)集是來(lái)自麝香分子的樣本，該數(shù)據(jù)集中包括Musk1與Musk2兩個(gè)子信息特征單元，Musk1中包括57例正向信息特征單元與64例負(fù)向特征單元，Musk2中包括162例正向信息特征單元與174例負(fù)向特征單元。三種方法聚類(lèi)實(shí)驗(yàn)結(jié)果見(jiàn)表3。

表3 三種方法聚類(lèi)MUSK信息特征單元結(jié)果

表3結(jié)果可以看出，本文方法聚類(lèi)457例信息特征單元僅有一例聚類(lèi)錯(cuò)誤，正確率為99.8%，而GDD方法和PCAP方法正確率分別為97.8%與97.4%，再次驗(yàn)證了本文方法的聚類(lèi)準(zhǔn)確性。

2.4 迭代次數(shù)統(tǒng)計(jì)

為驗(yàn)證本文方法聚類(lèi)效率，在實(shí)驗(yàn)中統(tǒng)計(jì)了以上三種方法迭代次數(shù)，結(jié)果見(jiàn)圖2。

圖2 三種方法聚類(lèi)迭代次數(shù)

從圖2可以看出，本文方法在聚類(lèi)五個(gè)信息特征單元集時(shí)迭代次數(shù)均在10次以下，而GDD方法在聚類(lèi)依據(jù)風(fēng)險(xiǎn)程度進(jìn)行股票聚類(lèi)時(shí)迭代次數(shù)達(dá)到了160次，PCAP方法在聚類(lèi)依據(jù)上升趨勢(shì)進(jìn)行股票聚類(lèi)時(shí)迭代次數(shù)高達(dá)185次，迭代次數(shù)的增多不僅會(huì)為算法的計(jì)算增加復(fù)雜多，并且影響聚類(lèi)的準(zhǔn)確度，因此可以看出本文方法聚類(lèi)效率最高。

根據(jù)以上實(shí)驗(yàn)分析三種方法對(duì)不同類(lèi)型信息特征單元的聚類(lèi)結(jié)果、聚類(lèi)準(zhǔn)確率以及方法聚類(lèi)迭代次數(shù)可以看出，本文方法聚類(lèi)準(zhǔn)確率明顯高于其它兩種方法，并且迭代次數(shù)最少，不僅節(jié)省了運(yùn)算時(shí)間，也增加了信息特征單元聚類(lèi)準(zhǔn)確性。

3 結(jié) 論

數(shù)據(jù)挖掘是信息處理的重要發(fā)展方向，而信息特征單元聚類(lèi)是數(shù)據(jù)挖掘中的重要概念，有效的信息特征單元聚類(lèi)方法可以為，高精度檢索海量數(shù)據(jù)中隱藏的有價(jià)值信息特征提供可靠依據(jù)。本文采用改進(jìn)EMD距離的信息特征單元聚類(lèi)方法，解決信息特征單元聚類(lèi)問(wèn)題。本文方法優(yōu)化傳統(tǒng)EMD距離計(jì)算過(guò)于復(fù)雜問(wèn)題，使信息特征單元聚類(lèi)性能達(dá)到最優(yōu)，并且解決了傳統(tǒng)信息特征單元聚類(lèi)方法存在的抗噪性差、單元過(guò)分割、正例現(xiàn)象增多等問(wèn)題，實(shí)現(xiàn)信息特征單元的高精度聚類(lèi)。

[1] 徐敏姣,徐青山,袁曉冬.基于改進(jìn)EMD及Elman算法的短期光伏功率預(yù)測(cè)研究[J].現(xiàn)代電力,2016,33(3):8-13

[2] 黃友朋,趙山,許凡,等.EEMD排列熵與PCA-G K的滾動(dòng)軸承聚類(lèi)故障診斷[J].河南科技大學(xué)學(xué)報(bào):自然科學(xué)版,2017,38(2):17-24

[3] 姜萬(wàn)錄,王浩楠,朱勇,等.變分模態(tài)分解消噪與核模糊C均值聚類(lèi)相結(jié)合的滾動(dòng)軸承故障識(shí)別方法[J].中國(guó)機(jī)械工 程,2017,28(10):1215-1220

[4] 張淑清,李威,張立國(guó),等.基于多元經(jīng)驗(yàn)?zāi)B(tài)分解互近似熵及GG聚類(lèi)的軸承故障診斷[J].中國(guó)機(jī)械工程,2016,27(24):3362-3367

[5] 陳安華,莫志軍,蔣玲莉,等.基于復(fù)雜網(wǎng)絡(luò)社團(tuán)聚類(lèi)的復(fù)合故障特征分離診斷方法[J].振動(dòng)與沖擊,2016,35(7):76-81

[6] 余煒,韓強(qiáng),馬晶晶,等.EMD和FCM的腦電信號(hào)處理方法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2016,46(15):223-228

[7] 魏林,白天亮,付華,等.基于EMD-LSSVM的瓦斯?jié)舛葎?dòng)態(tài)預(yù)測(cè)模型[J].安全與環(huán)境學(xué)報(bào),2016,16(2):119-123

[8] 程靜,劉家駿,高勇.基于時(shí)間序列聚類(lèi)方法分析北京出租車(chē)出行量的時(shí)空特征[J].地球信息科學(xué)學(xué)報(bào),2016,18(9):1227-1239

[9] 楊慧,李振,霍緯綱.改進(jìn)小波聚類(lèi)算法在QAR數(shù)據(jù)中的應(yīng)用[J].計(jì)算機(jī)工程,2017,43(9):29-33

[10] 張林,李秀友,劉寧波,等.基于分形特性改進(jìn)的EMD目標(biāo)檢測(cè)算法[J].電子與信息學(xué)報(bào),2016,38(5):1041-1046

The Method Clustering the Information Feature Units Based on Improved EMD Distance

LAN Hui-hong, HUANG Jin-de

530023,

To study on the method clustering information feature units based on EMD distance, this paper extracted information feature units by the vector space method to set EMD ground distances as the distances between different information feature units and information feature units were compared to suppliers and consumers. In order to avoid the over-segmentation for information feature units caused by EMD distance clustering, the increase of positive phenomena and the inability of suppliers to set a similar threshold for suppliers with similar characteristics to increase their weight and the use of thresholds made transportation mainly for low-cost suppliers improve EMD distance; An improved EMD distance algorithm was used to achieve effective clustering of information feature units. The method could effectively cluster different types of information feature units, such as text and stock, with an accuracy of more than 99 %, and the clustering process had fewer iterations and excellent clustering performance.

EMD distance; information feature units; clustering method

TP391

A

1000-2324(2019)05-0885-04

10.3969/j.issn.1000-2324.2019.05.033

2018-03-26

2018-05-09

廣西教育廳科研項(xiàng)目:基于文本聚類(lèi)的東盟跨語(yǔ)言查詢(xún)擴(kuò)展模型及算法研究(2019KY1678)

蘭慧紅(1985-),女,碩士,講師,主要從事數(shù)據(jù)挖掘和信息檢索等研究. E-mail:lanlandoll@163.com