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

李其芳

（陸軍軍官學(xué)院 合肥 230031）

1 引言

覆蓋算法是一種構(gòu)造性的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法，它根據(jù)數(shù)據(jù)自身的結(jié)構(gòu)，構(gòu)造性地建立了神經(jīng)網(wǎng)絡(luò)模型。構(gòu)造性神經(jīng)網(wǎng)絡(luò)可分層逐步構(gòu)造，網(wǎng)絡(luò)的基本功能被劃分成若干獨(dú)立的功能模塊。各模塊獨(dú)自負(fù)責(zé)解決問(wèn)題的一部分，因此在學(xué)習(xí)階段所處理的數(shù)據(jù)也不完全相同。其有如下特點(diǎn)：

1）構(gòu)造性的網(wǎng)絡(luò)結(jié)構(gòu)中各功能模塊相對(duì)簡(jiǎn)單，各模塊主要是集中于問(wèn)題的一部分，所要解決的問(wèn)題也相對(duì)簡(jiǎn)單，不會(huì)受到各種不同信號(hào)的影響，因此容易訓(xùn)練，相對(duì)簡(jiǎn)單的網(wǎng)絡(luò)結(jié)構(gòu)提高了網(wǎng)絡(luò)的泛化能力；

2）各功能模塊相對(duì)獨(dú)立，可并行地進(jìn)行訓(xùn)練，訓(xùn)練效率高；

3）網(wǎng)絡(luò)的行為便于解釋、分析，網(wǎng)絡(luò)的設(shè)計(jì)容易改進(jìn)；

4）硬件更易實(shí)現(xiàn)，因?yàn)闃?gòu)造若干簡(jiǎn)單的模塊再將它們連接起來(lái)比建立全連接的大規(guī)模網(wǎng)絡(luò)更容易。

構(gòu)造性神經(jīng)網(wǎng)絡(luò)將無(wú)限大的劃分區(qū)域變換為有限的劃分區(qū)域，通過(guò)非線(xiàn)性變換，將學(xué)習(xí)問(wèn)題變?yōu)閯澐謫?wèn)題，將多區(qū)域相交復(fù)雜性簡(jiǎn)單化，可以實(shí)現(xiàn)多類(lèi)別樣本的同時(shí)劃分；將神經(jīng)元的功能局部化，將非局部性的劃分區(qū)域變換為局部性劃分區(qū)域，故其計(jì)算量少，速度快，能實(shí)現(xiàn)海量的模式分類(lèi)。

2 覆蓋算法的概率模型

2.1 概率有限混合模型

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

2.2 有限混合模型的定義

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

其中fj（xi）表示觀(guān)察值xi來(lái)自第j分量時(shí)的條件概率密度函數(shù)。

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

3 覆蓋算法的概率模型的實(shí)現(xiàn)

設(shè)給定分類(lèi)問(wèn)題，即共有p個(gè)n維樣本，分成m類(lèi)。

簡(jiǎn)單的覆蓋算法，對(duì)每個(gè)覆蓋取特征函數(shù)來(lái)表示，這種表示未能反映樣本在覆蓋中的分布情況。高斯分布函數(shù)可以克服這個(gè)缺點(diǎn)，若對(duì)每覆蓋引入高斯核函數(shù)（以覆蓋的中心為高斯核函數(shù)的均值，取半徑為方差，記為對(duì)應(yīng)于第i類(lèi)的決策函數(shù)為

上式又可以理解為高斯函數(shù)的覆蓋算法得到的決策函數(shù)。從上面一系列變換后，使我們可以從概率的角度來(lái)考察它，因?yàn)槭剑?）可以看成是一個(gè)有限混合概率模型，于是可以利用最大似然的算法，求得式（3）的最優(yōu)參數(shù)。這樣就從概率角度為函數(shù)的確定參數(shù)問(wèn)題，給出一個(gè)合理的解決方法。于是可將概率統(tǒng)計(jì)中現(xiàn)成的方法引入分類(lèi)學(xué)習(xí)，也就是把覆蓋算法與統(tǒng)計(jì)模型結(jié)合起來(lái)，為覆蓋算法找到全局優(yōu)化的途徑。

4 基于覆蓋算法的概率模型的海量數(shù)據(jù)挖掘算法

給定m類(lèi)分類(lèi)的訓(xùn)練樣本集K＝｛K1，K2，…，Km｝，算法實(shí)現(xiàn)具體步驟如下：

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

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

（2）若K1（開(kāi)始時(shí)i＝1）非空，作一覆蓋，i＝1，2，…，m，j＝1，2，…，gi，它只覆蓋K1的點(diǎn)，被覆蓋Ki的子集為Kij（j＝1，2，…，gi）；

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

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

（6）若C（a′i）所覆蓋的點(diǎn)數(shù)大于C（ai）所覆蓋的點(diǎn)數(shù)，則令a′i→ai，θ′i→θi，返回（5），否則，得到C（ai）的一個(gè)覆蓋，轉(zhuǎn)到（7）；

（7）求ai的平移點(diǎn)a″i，并求對(duì)應(yīng)的球形領(lǐng)域C（a″i），若C（a″i）覆蓋的點(diǎn)數(shù)大于C（ai）所覆蓋的點(diǎn)數(shù)，轉(zhuǎn)到（5），否則，得到C（ai）的一個(gè)覆蓋，轉(zhuǎn)步（3）；

（8）樣本學(xué)習(xí)結(jié)束，得到覆蓋組。

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

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

利用EM方法求解最大似然問(wèn)題，難點(diǎn)在于如何合理地選取混合模型的分量個(gè)數(shù)問(wèn)題（這就像k－均值法中如何取k的問(wèn)題）。對(duì)覆蓋算法，這個(gè)問(wèn)題可利用覆蓋算法求得的覆蓋，作為EM算法的迭代起始值，得到很好地解決。因?yàn)槔酶采w算法求得的覆蓋組，基本已是次優(yōu)的覆蓋，在此基礎(chǔ)上再利用EM算法進(jìn)行迭代就能很快求到最優(yōu)解。這也是對(duì)覆蓋算法的概率模型引入“最大似然原則”成功的所在。

另外需要說(shuō)明的是，為了防止迭代過(guò)程發(fā)散，對(duì)出現(xiàn)下面情況進(jìn)行調(diào)整：

3）給定ε2，對(duì)＜ε2的覆蓋Cj，將覆蓋Cj保留，下一輪迭代時(shí)對(duì)該覆蓋不進(jìn)行迭代，防止EM迭代的發(fā)散，因?yàn)榉讲詈苄〉母采w，所覆蓋的點(diǎn)多是“離群點(diǎn)”。

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

5 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)將基于覆蓋算法的概率模型的海量數(shù)據(jù)挖掘算法應(yīng)用到短波無(wú)線(xiàn)電監(jiān)測(cè)中以驗(yàn)證數(shù)據(jù)挖掘的效果。

無(wú)線(xiàn)電監(jiān)測(cè)的目的是維護(hù)電臺(tái)活動(dòng)秩序，及時(shí)發(fā)現(xiàn)非法電臺(tái)。一般說(shuō)轄區(qū)內(nèi)合法電臺(tái)的用頻、工作時(shí)間等都是經(jīng)過(guò)政府認(rèn)可的，我們可以此為依據(jù)發(fā)現(xiàn)非法電臺(tái)。然而，短波信號(hào)通過(guò)天波傳播，傳播距離遠(yuǎn)，在檢測(cè)無(wú)線(xiàn)電信號(hào)時(shí)，能截獲大量信號(hào)數(shù)據(jù)，容易受到其他國(guó)家和地區(qū)通信電臺(tái)的影響，噪聲比較多，信號(hào)很密集，要處理的數(shù)據(jù)量相當(dāng)大。

本實(shí)驗(yàn)分成三個(gè)部分：一是調(diào)諧接收機(jī)，采集信號(hào)作為分析數(shù)據(jù)；二是將采集信號(hào)的前一部分作為訓(xùn)練樣本，利用覆蓋算法的概率模型進(jìn)行聚類(lèi)；三是用后一部分信號(hào)數(shù)據(jù)作為測(cè)試樣本檢驗(yàn)基于覆蓋算法的概率模型的海量數(shù)據(jù)挖掘算法的挖掘效果。

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

圖1 所采集信號(hào)頻占圖

圖2 經(jīng)過(guò)算法處理后的信號(hào)頻占圖

圖1是15MHz～16MHz頻段內(nèi)連續(xù)3天被截獲信號(hào)的頻占圖（約1.44×106個(gè)數(shù)據(jù)點(diǎn)），橫軸代表時(shí)間，縱軸代表頻率，圖1中點(diǎn)的虛實(shí)代表該點(diǎn)對(duì)應(yīng)的時(shí)間和頻率上有無(wú)信號(hào)。圖1中存在一個(gè)跳頻信號(hào)，它是在實(shí)際頻率占用度基礎(chǔ)上，利用頻率間隙嵌入跳頻信號(hào)。這樣模擬的數(shù)據(jù)比單純模擬的數(shù)據(jù)更加符合實(shí)際情況。它的頻率集包含31個(gè)頻率點(diǎn)，但是由于信號(hào)環(huán)境復(fù)雜，包含其他電臺(tái)信號(hào)、噪聲干擾等信息，跳頻信號(hào)頻率集不容易被提取。

為了有效地獲取知識(shí)，對(duì)圖1所示數(shù)據(jù)進(jìn)行預(yù)處理，經(jīng)算法處理，剔除干擾、過(guò)濾噪聲后，頻率占用度如圖2所示，絕大部分噪聲被有效地濾除。

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

表1 不同方法實(shí)驗(yàn)結(jié)果表

從表1得出，利用改進(jìn)覆蓋算法對(duì)無(wú)線(xiàn)電監(jiān)測(cè)數(shù)據(jù)進(jìn)行挖掘，挖掘所用時(shí)間和正確率比原覆蓋算法和核覆蓋算法都提高了，這是由于改進(jìn)的算法從全局出發(fā)，對(duì)所有測(cè)試樣本都能到達(dá)最優(yōu)。

6 結(jié)語(yǔ)

本章從大規(guī)模數(shù)據(jù)挖掘的角度出發(fā)，分析了傳統(tǒng)神經(jīng)網(wǎng)絡(luò)的不足，在M－P神經(jīng)元幾何意義的基礎(chǔ)上，介紹了覆蓋算法的原理及其經(jīng)典算法，即領(lǐng)域覆蓋算法和交叉覆蓋算法；然后簡(jiǎn)單介紹了核覆蓋算法，并在核覆蓋算法的基礎(chǔ)上，利用高斯函數(shù)的概率意義（高斯分布），為核覆蓋算法建立一個(gè)有限混合概率模型，提出了覆蓋算法的概率模型，對(duì)覆蓋算法進(jìn)行改進(jìn)，給出了一種新的算法，即基于覆蓋算法的概率模型的海量數(shù)據(jù)挖掘算法；利用這種改進(jìn)的算法構(gòu)造的神經(jīng)網(wǎng)絡(luò)，在保持計(jì)算復(fù)雜度不變的前提下，引入全局優(yōu)化計(jì)算，擴(kuò)大了覆蓋算法的使用范圍，提高了算法的精度，適合大規(guī)模數(shù)據(jù)挖掘。最后的實(shí)驗(yàn)驗(yàn)證了算法的實(shí)效性。

［1］張鈴，張鈸.多層反饋神經(jīng)網(wǎng)絡(luò)的FP學(xué)習(xí)和綜合算法［J］.軟件學(xué)報(bào)，1997，8（4）：252－258.

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

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

［4］張燕平，張鈴，段震.構(gòu)造性核覆蓋算法在圖像識(shí)別中的應(yīng)用［J］.中國(guó)圖象圖形學(xué)報(bào)，2004，9（11）：1304－1308.

［5］張旻，陳加興.基于粒度計(jì)算和覆蓋算法的信號(hào)樣式識(shí)別［J］.計(jì)算機(jī)工程與應(yīng)用，2003（24）：56－59.

［6］王倫文，張鈴，張旻.一種適合于無(wú)線(xiàn)電監(jiān)測(cè)的數(shù)據(jù)挖掘技術(shù)［J］.計(jì)算機(jī)工程與應(yīng)用，2004（4）：37－40.

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

［8］周義建，王軼，王輝.基于A(yíng)priori數(shù)據(jù)挖掘優(yōu)化方法研究［J］.計(jì)算機(jī)與數(shù)字工程，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.