基于改進EMD距離的信息特征單元的聚類方法

蘭慧紅,黃緊德

基于改進EMD距離的信息特征單元的聚類方法

蘭慧紅,黃緊德

廣西教育學院數學與信息科學學院, 廣西 南寧 530023

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

EMD距離; 信息特征單元; 聚類方法

近年來網絡發展飛速，人類生活已經越來越走進信息化[1]。在這種大數據環境下，如何從繁瑣無規律的信息中有效尋找自身需要且具有價值信息是目前急需解決的問題[2]。在大數據環境下檢索信息特征單元，并將信息特征單元進行分類與融合，在數據挖掘、知識管理與數據搜索等領域中都具有重要意義[3,4]。

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

1 信息特征單元聚類方法分析

1.1 提取信息特征單元

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

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

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

式中，n表示訓練特征集中出現t的數量，(t)表示待聚類特征t的信息增益，(t)公式如下：

特征的條件熵公式如下：

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

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

1.2 EMD距離

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

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

以上公式中，,?為該特征空間中一點，點的權值用w表示。

設=[d]為地面距離矩陣，表示點與點間地面距離。設點p與點q間流用S表示，存在流矩陣=[S]以保證全局代價函數為最小，且應滿足的約束條件如下：

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

利用以上公式解決EMD距離的運輸問題，獲取矩陣，可得EMD距離的運輸工作規格化值：

EMD距離中EMD值不會隨特征分布的微小變化而引起波動，因此具有連續性；EMD距離的特征分布緊湊型與靈活性可避免屬性相似性度量的量化問題；有利于特征匹配的平衡。雖然EMD距離具有以上優點，但是EMD距離也有著對精度要求高導致計算過于復雜的缺點，因此在進行信息特征單元聚類時需要對EMD距離進行改進。

1.3 基于改進EMD距離的信息特征單元聚類

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

將現有的信息單元特征值集定義w。對信息單元特征集以“分割特征數量與總特征集比值”作為相應區域權值。通過特征與質心距離計算信息特征單元集，具體計算過程為：

式中，O表示特征S質心。

采用未改進EMD距離聚類信息特征單元時，會引起特征單元過分割、正例現象增多以及供貨商無法供貨的問題，因此需改進EMD距離，使信息特征單元聚類結果最優。

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

若公式（11）計算結果sim(x,x)<，那么對應特征示例可合并為新示例，合并過程如下：

以上公式中，為|S|內與x相似示例數量。

2 實驗分析

為檢驗改進EMD距離方法對信息特征單元的聚類效果，在Matlab仿真實驗平臺中編寫本文方法進行聚類實驗，實驗目標分別為（1）來自中國科學院計算技術研究所文本數據；（2）Iris數據庫中選取的信息特征單元；（3）MIL標準數據庫中數據集MUSK；（4）中國財經股票2018年1月1日至12月31日的30支股票數據。并將本文方法聚類結果與GDD方法和PCAP方法聚類結果進行比較。

2.1 文本特征單元聚類結果

將來自中國科學院計算技術研究所文本信息特征單元10000例進行分析，利用本文方法、GDD方法和PCAP方法三種方法進行聚類，結果見表1。

表1 三種方法聚類文本特征單元結果

三種方法聚類文本特征單元結果準確率見圖1。

圖1 三種方法聚類文本特征單元準確率

從表1與圖1結果可以看出，本文方法聚類中國科學院計算技術研究1000例文本信息特征單元結果準確率最高，準確率均在99%以上，說明了本文方法的聚類有效性。

2.2 Iris數據庫聚類結果

在Iris數據庫中選取鳶尾花特征作為聚類信息特征單元，該信息特征共有200例，分為4類，每類包含50例，各例信息特征單元中含有4個屬性。三種方法聚類結果見表2。

表2 三種方法聚類鳶尾花信息特征單元結果

表2可以看出，本文方法聚類結果較準確，正確率在95%以上，而GDD方法正確率僅為80%左右，PCAP方法正確率最高僅為76%，驗證了本文方法的聚類有效性及準確性。

2.3 MIL標準數據庫聚類結果

在MIL標準數據庫中選取MUSK數據集作為實驗對象，MUSK數據集是來自麝香分子的樣本，該數據集中包括Musk1與Musk2兩個子信息特征單元，Musk1中包括57例正向信息特征單元與64例負向特征單元，Musk2中包括162例正向信息特征單元與174例負向特征單元。三種方法聚類實驗結果見表3。

表3 三種方法聚類MUSK信息特征單元結果

表3結果可以看出，本文方法聚類457例信息特征單元僅有一例聚類錯誤，正確率為99.8%，而GDD方法和PCAP方法正確率分別為97.8%與97.4%，再次驗證了本文方法的聚類準確性。

2.4 迭代次數統計

為驗證本文方法聚類效率，在實驗中統計了以上三種方法迭代次數，結果見圖2。

圖2 三種方法聚類迭代次數

從圖2可以看出，本文方法在聚類五個信息特征單元集時迭代次數均在10次以下，而GDD方法在聚類依據風險程度進行股票聚類時迭代次數達到了160次，PCAP方法在聚類依據上升趨勢進行股票聚類時迭代次數高達185次，迭代次數的增多不僅會為算法的計算增加復雜多，并且影響聚類的準確度，因此可以看出本文方法聚類效率最高。

根據以上實驗分析三種方法對不同類型信息特征單元的聚類結果、聚類準確率以及方法聚類迭代次數可以看出，本文方法聚類準確率明顯高于其它兩種方法，并且迭代次數最少，不僅節省了運算時間，也增加了信息特征單元聚類準確性。

3 結 論

數據挖掘是信息處理的重要發展方向，而信息特征單元聚類是數據挖掘中的重要概念，有效的信息特征單元聚類方法可以為，高精度檢索海量數據中隱藏的有價值信息特征提供可靠依據。本文采用改進EMD距離的信息特征單元聚類方法，解決信息特征單元聚類問題。本文方法優化傳統EMD距離計算過于復雜問題，使信息特征單元聚類性能達到最優，并且解決了傳統信息特征單元聚類方法存在的抗噪性差、單元過分割、正例現象增多等問題，實現信息特征單元的高精度聚類。

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

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

[3] 姜萬錄,王浩楠,朱勇,等.變分模態分解消噪與核模糊C均值聚類相結合的滾動軸承故障識別方法[J].中國機械工 程,2017,28(10):1215-1220

[4] 張淑清,李威,張立國,等.基于多元經驗模態分解互近似熵及GG聚類的軸承故障診斷[J].中國機械工程,2016,27(24):3362-3367

[5] 陳安華,莫志軍,蔣玲莉,等.基于復雜網絡社團聚類的復合故障特征分離診斷方法[J].振動與沖擊,2016,35(7):76-81

[6] 余煒,韓強,馬晶晶,等.EMD和FCM的腦電信號處理方法[J].數學的實踐與認識,2016,46(15):223-228

[7] 魏林,白天亮,付華,等.基于EMD-LSSVM的瓦斯濃度動態預測模型[J].安全與環境學報,2016,16(2):119-123

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

[9] 楊慧,李振,霍緯綱.改進小波聚類算法在QAR數據中的應用[J].計算機工程,2017,43(9):29-33

[10] 張林,李秀友,劉寧波,等.基于分形特性改進的EMD目標檢測算法[J].電子與信息學報,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

廣西教育廳科研項目:基于文本聚類的東盟跨語言查詢擴展模型及算法研究(2019KY1678)

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