基于覆蓋算法概率模型的海量數據挖掘研究＊

李其芳

（陸軍軍官學院 合肥 230031）

1 引言

覆蓋算法是一種構造性的神經網絡學習算法，它根據數據自身的結構，構造性地建立了神經網絡模型。構造性神經網絡可分層逐步構造，網絡的基本功能被劃分成若干獨立的功能模塊。各模塊獨自負責解決問題的一部分，因此在學習階段所處理的數據也不完全相同。其有如下特點：

1）構造性的網絡結構中各功能模塊相對簡單，各模塊主要是集中于問題的一部分，所要解決的問題也相對簡單，不會受到各種不同信號的影響，因此容易訓練，相對簡單的網絡結構提高了網絡的泛化能力；

2）各功能模塊相對獨立，可并行地進行訓練，訓練效率高；

3）網絡的行為便于解釋、分析，網絡的設計容易改進；

4）硬件更易實現，因為構造若干簡單的模塊再將它們連接起來比建立全連接的大規模網絡更容易。

構造性神經網絡將無限大的劃分區域變換為有限的劃分區域，通過非線性變換，將學習問題變為劃分問題，將多區域相交復雜性簡單化，可以實現多類別樣本的同時劃分；將神經元的功能局部化，將非局部性的劃分區域變換為局部性劃分區域，故其計算量少，速度快，能實現海量的模式分類。

2 覆蓋算法的概率模型

2.1 概率有限混合模型

在概率論中有如下的命題成立：任何連續分布均可由等方差高斯密度的有限混合任意逼近。也就是說，在近似的意義下，只要研究有限高斯混合密度就足夠了。通過這種思想，可以利用有限高斯混合密度為覆蓋算法建立概率模型。

2.2 有限混合模型的定義

設X1，…，Xp是樣本量為p的獨立同分布隨機樣本，其中Xi是n維隨機向量，其概率密度函數為f（x）。設f（xi）可表示成：

其中fj（xi）表示觀察值xi來自第j分量時的條件概率密度函數。

若取fj（x）為1維高斯分布，則上式可表示成：

3 覆蓋算法的概率模型的實現

設給定分類問題，即共有p個n維樣本，分成m類。

簡單的覆蓋算法，對每個覆蓋取特征函數來表示，這種表示未能反映樣本在覆蓋中的分布情況。高斯分布函數可以克服這個缺點，若對每覆蓋引入高斯核函數（以覆蓋的中心為高斯核函數的均值，取半徑為方差，記為對應于第i類的決策函數為

上式又可以理解為高斯函數的覆蓋算法得到的決策函數。從上面一系列變換后，使我們可以從概率的角度來考察它，因為式（3）可以看成是一個有限混合概率模型，于是可以利用最大似然的算法，求得式（3）的最優參數。這樣就從概率角度為函數的確定參數問題，給出一個合理的解決方法。于是可將概率統計中現成的方法引入分類學習，也就是把覆蓋算法與統計模型結合起來，為覆蓋算法找到全局優化的途徑。

4 基于覆蓋算法的概率模型的海量數據挖掘算法

給定m類分類的訓練樣本集K＝｛K1，K2，…，Km｝，算法實現具體步驟如下：

1）利用覆蓋算法，求出各類的覆蓋組｛C1，C2，…，Cm｝：

（1）將所有的點投影到Sn上（中心在原點，半徑為R，R＞max（｜xl｜），l＝1，2，…，p），仍記為 K1，K2，…，Km；

（2）若K1（開始時i＝1）非空，作一覆蓋，i＝1，2，…，m，j＝1，2，…，gi，它只覆蓋K1的點，被覆蓋Ki的子集為Kij（j＝1，2，…，gi）；

（3）若 Ki被覆蓋完，i＝i＋1，若i＞m，則轉至（8），否則，任取Ki中尚未被覆蓋的一點ai；

（5）求C（ai）所覆蓋點的重心，將其映射到球面上，設投影點為a′i，按（4）中公式求θ′i，求得球形領域C（a′i）；

（6）若C（a′i）所覆蓋的點數大于C（ai）所覆蓋的點數，則令a′i→ai，θ′i→θi，返回（5），否則，得到C（ai）的一個覆蓋，轉到（7）；

（7）求ai的平移點a″i，并求對應的球形領域C（a″i），若C（a″i）覆蓋的點數大于C（ai）所覆蓋的點數，轉到（5），否則，得到C（ai）的一個覆蓋，轉步（3）；

（8）樣本學習結束，得到覆蓋組。

2）以覆蓋的中心為高斯核函數的均值，取半徑為方差，對每覆蓋引入高斯核函數；

4）利用文獻［7］中給出求解最大似然的迭代EM算法進行最大似然擬合。

利用EM方法求解最大似然問題，難點在于如何合理地選取混合模型的分量個數問題（這就像k－均值法中如何取k的問題）。對覆蓋算法，這個問題可利用覆蓋算法求得的覆蓋，作為EM算法的迭代起始值，得到很好地解決。因為利用覆蓋算法求得的覆蓋組，基本已是次優的覆蓋，在此基礎上再利用EM算法進行迭代就能很快求到最優解。這也是對覆蓋算法的概率模型引入“最大似然原則”成功的所在。

另外需要說明的是，為了防止迭代過程發散，對出現下面情況進行調整：

3）給定ε2，對＜ε2的覆蓋Cj，將覆蓋Cj保留，下一輪迭代時對該覆蓋不進行迭代，防止EM迭代的發散，因為方差很小的覆蓋，所覆蓋的點多是“離群點”。

給出一個迭代停止的條件（如達到一定迭代精度或達到一定的迭代次數），最后迭代停止時所得到有限概率模型即所求。

5 實驗與結果分析

實驗將基于覆蓋算法的概率模型的海量數據挖掘算法應用到短波無線電監測中以驗證數據挖掘的效果。

無線電監測的目的是維護電臺活動秩序，及時發現非法電臺。一般說轄區內合法電臺的用頻、工作時間等都是經過政府認可的，我們可以此為依據發現非法電臺。然而，短波信號通過天波傳播，傳播距離遠，在檢測無線電信號時，能截獲大量信號數據，容易受到其他國家和地區通信電臺的影響，噪聲比較多，信號很密集，要處理的數據量相當大。

本實驗分成三個部分：一是調諧接收機，采集信號作為分析數據；二是將采集信號的前一部分作為訓練樣本，利用覆蓋算法的概率模型進行聚類；三是用后一部分信號數據作為測試樣本檢驗基于覆蓋算法的概率模型的海量數據挖掘算法的挖掘效果。

本實驗通過計算機遙控某種型號的短波接收機，使其在15MHz～16MHz頻段內，按照5kHz步進，從低到高循環搜索，3分鐘為一個周期，搜索到任一頻點（第i頻點頻率為（15001.5＋5*i）kHz，i＝0，2，…，332），駐留一短暫的時隙（如70ms），此時從接收機的中頻輸出端采集信號并存入數據庫或直接分析。接收機的中頻輸出頻率是200kHz，帶寬設置為3kHz，采用帶通采樣，采樣頻率為10.24kHz。采集的數據是時域數據，不便分析，被采樣的時域數據經快速傅立葉變換（FFT）轉化為頻域數據存入數據庫，等采集樣本達到一定的數據量時再進行處理。利用部分被采集的數據作為訓練樣本，構建神經網絡，再用另一部分數據（如一天的數據）作測試樣本。

圖1 所采集信號頻占圖

圖2 經過算法處理后的信號頻占圖

圖1是15MHz～16MHz頻段內連續3天被截獲信號的頻占圖（約1.44×106個數據點），橫軸代表時間，縱軸代表頻率，圖1中點的虛實代表該點對應的時間和頻率上有無信號。圖1中存在一個跳頻信號，它是在實際頻率占用度基礎上，利用頻率間隙嵌入跳頻信號。這樣模擬的數據比單純模擬的數據更加符合實際情況。它的頻率集包含31個頻率點，但是由于信號環境復雜，包含其他電臺信號、噪聲干擾等信息，跳頻信號頻率集不容易被提取。

為了有效地獲取知識，對圖1所示數據進行預處理，經算法處理，剔除干擾、過濾噪聲后，頻率占用度如圖2所示，絕大部分噪聲被有效地濾除。

利用覆蓋算法的概率模型得到的改進覆蓋算法，并與原覆蓋算法、核覆蓋算法進行挖掘，得到表1所示的結果。

表1 不同方法實驗結果表

從表1得出，利用改進覆蓋算法對無線電監測數據進行挖掘，挖掘所用時間和正確率比原覆蓋算法和核覆蓋算法都提高了，這是由于改進的算法從全局出發，對所有測試樣本都能到達最優。

6 結語

本章從大規模數據挖掘的角度出發，分析了傳統神經網絡的不足，在M－P神經元幾何意義的基礎上，介紹了覆蓋算法的原理及其經典算法，即領域覆蓋算法和交叉覆蓋算法；然后簡單介紹了核覆蓋算法，并在核覆蓋算法的基礎上，利用高斯函數的概率意義（高斯分布），為核覆蓋算法建立一個有限混合概率模型，提出了覆蓋算法的概率模型，對覆蓋算法進行改進，給出了一種新的算法，即基于覆蓋算法的概率模型的海量數據挖掘算法；利用這種改進的算法構造的神經網絡，在保持計算復雜度不變的前提下，引入全局優化計算，擴大了覆蓋算法的使用范圍，提高了算法的精度，適合大規模數據挖掘。最后的實驗驗證了算法的實效性。

［1］張鈴，張鈸.多層反饋神經網絡的FP學習和綜合算法［J］.軟件學報，1997，8（4）：252－258.

［2］張莉.SVM與核方法研究［D］.西安：西安電子科技大學，2002.

［3］趙姝，張燕平，張媛，等.基于交叉覆蓋算法的入侵檢測［J］.計算機工程與應用，2005（1）：141－143.

［4］張燕平，張鈴，段震.構造性核覆蓋算法在圖像識別中的應用［J］.中國圖象圖形學報，2004，9（11）：1304－1308.

［5］張旻，陳加興.基于粒度計算和覆蓋算法的信號樣式識別［J］.計算機工程與應用，2003（24）：56－59.

［6］王倫文，張鈴，張旻.一種適合于無線電監測的數據挖掘技術［J］.計算機工程與應用，2004（4）：37－40.

［7］張立斌，高仲春.基于遺傳算法的數據挖掘維度選擇［J］.計算機與數字工程，2012（5）.

［8］周義建，王軼，王輝.基于Apriori數據挖掘優化方法研究［J］.計算機與數字工程，2008（2）.

［9］Dempster A P，Laird N M，Rubin D B.Maximum likelihood from incomplete data using the EM algorithm（with discussion）［J］.R.Stat.Soc.Ser.B，1977：1－38.

［10］Heckman D，Geiger D，Chickering D.Learning Bayesian networks：the combination of knowledge and statistical data［J］.Machine Learning，1995，20（3）：197－243.

［11］Heckman D，Mandani A，Wellman M.Real－World applications of Bayesian networks［J］.Communications of the ACM，1995，8（3）：38－45.

［12］Heckerman D.Bayesian networks for data mining［J］.Data Mining and Knowledge Discovery，1997：79－119.