基于LZ編碼預(yù)測(cè)算法的數(shù)據(jù)挖掘應(yīng)用研究

劉詩(shī)淼 王博

摘 要： 隨著移動(dòng)通信系統(tǒng)的快速發(fā)展，用戶數(shù)量和業(yè)務(wù)種類的持續(xù)增長(zhǎng)給系統(tǒng)設(shè)計(jì)帶來了新的挑戰(zhàn)。針對(duì)這種情況，研究了數(shù)據(jù)挖掘在用戶路徑預(yù)測(cè)技術(shù)上的應(yīng)用，選擇LZ編碼預(yù)測(cè)方案用于數(shù)字集群系統(tǒng)的用戶路徑預(yù)測(cè)，并對(duì)方案進(jìn)行了模擬仿真，同時(shí)分析了數(shù)字集群通信系統(tǒng)設(shè)備條件、應(yīng)用場(chǎng)景和用戶移動(dòng)模型的特點(diǎn)，證明了其在用戶路徑預(yù)測(cè)應(yīng)用上的優(yōu)勢(shì)。針對(duì)數(shù)字集群通信系統(tǒng)的特點(diǎn)，提出一種基于路徑預(yù)測(cè)技術(shù)的動(dòng)態(tài)信道預(yù)留算法，以滿足系統(tǒng)QoS要求。并對(duì)提出的方案進(jìn)行了Matlab仿真研究，與其他方案進(jìn)行了性能比較，驗(yàn)證了其在業(yè)務(wù)狀態(tài)變化下可以通過實(shí)時(shí)調(diào)整系統(tǒng)參數(shù)，從而降低系統(tǒng)切換呼叫阻塞率和提高信道利用率。

關(guān)鍵詞： 數(shù)字集群； 數(shù)據(jù)挖掘； 路徑預(yù)測(cè)； LZ編碼

中圖分類號(hào)： TN919.6?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）05?0019?05

0 引 言

隨著移動(dòng)通信系統(tǒng)的快速發(fā)展，用戶數(shù)量和業(yè)務(wù)種類的持續(xù)增長(zhǎng)給系統(tǒng)設(shè)計(jì)帶來了新的挑戰(zhàn)。越區(qū)切換技術(shù)作為蜂窩小區(qū)移動(dòng)通信系統(tǒng)的核心技術(shù)，其資源分配算法將直接決定系統(tǒng)的通話質(zhì)量和業(yè)務(wù)承載能力。數(shù)字集群通信系統(tǒng)是一種專用移動(dòng)通信系統(tǒng)，其應(yīng)用場(chǎng)景、用戶組成都與公用移動(dòng)通信系統(tǒng)有著顯著的不同，針對(duì)其特點(diǎn)設(shè)計(jì)合理的切換算法是技術(shù)發(fā)展的必然。

數(shù)據(jù)挖掘技術(shù)是近十年隨著大型數(shù)據(jù)庫(kù)技術(shù)發(fā)展、互聯(lián)網(wǎng)數(shù)據(jù)爆炸而產(chǎn)生的新的數(shù)據(jù)處理與知識(shí)發(fā)現(xiàn)技術(shù)，它將傳統(tǒng)的數(shù)據(jù)處理方法與應(yīng)對(duì)大規(guī)模數(shù)據(jù)的復(fù)雜算法相結(jié)合，能夠從海量數(shù)據(jù)中發(fā)現(xiàn)新的數(shù)據(jù)模式。用戶移動(dòng)路徑預(yù)測(cè)技術(shù)是數(shù)據(jù)挖掘在移動(dòng)通信網(wǎng)絡(luò)優(yōu)化領(lǐng)域的典型應(yīng)用，通過對(duì)網(wǎng)絡(luò)運(yùn)行產(chǎn)生的用戶數(shù)據(jù)進(jìn)行挖掘，幫助系統(tǒng)提高運(yùn)行效率和服務(wù)質(zhì)量，對(duì)改善數(shù)字集群通信系統(tǒng)的性能具有重要意義[1]。

1 LZ編碼預(yù)測(cè)方案

1.1 方案設(shè)計(jì)

LZ78算法是較為原始的LeZi系列算法Active，編碼樹生成開始時(shí)，輸入數(shù)據(jù)就是已經(jīng)處理完成的用戶移動(dòng)序列，每個(gè)用戶都需要單獨(dú)生成一次預(yù)測(cè)樹并存儲(chǔ)起來，如圖1所示。

通過Active LZ算法預(yù)測(cè)流程圖，可以觀察到：與單階數(shù)馬爾科夫模型和序列模式挖掘方法相比，在預(yù)測(cè)過程中，可將用戶當(dāng)前的移動(dòng)序列與編碼預(yù)測(cè)樹中節(jié)點(diǎn)按條件概率最大的原則進(jìn)行匹配得到預(yù)測(cè)結(jié)果，且無論預(yù)測(cè)結(jié)果是否正確，都可以實(shí)時(shí)調(diào)整編碼樹，在使用過程中提高預(yù)測(cè)精度，如圖2所示。

下面將給出一個(gè)基于Active LZ編碼預(yù)測(cè)方法進(jìn)行路徑預(yù)測(cè)的示例：假設(shè)服務(wù)區(qū)域只有四個(gè)服務(wù)小區(qū)，編號(hào)分別為abcd，一個(gè)移動(dòng)用戶移動(dòng)路徑則可以被編碼為abcd組成的符號(hào)序列。為了顯示與LZ78編碼預(yù)測(cè)方法的區(qū)別，假設(shè)用戶路徑仍為“aaababbbbbaabccddcbaaaa”，通過Active LZ算法的編碼預(yù)測(cè)樹，可以觀察到某些路徑模式分支的統(tǒng)計(jì)頻次比LZ78算法增加了，這是因?yàn)長(zhǎng)Z78中某些存在于讀入序列后綴中的序列模式?jīng)]有被統(tǒng)計(jì)，而在Active LZ中都被統(tǒng)計(jì)了[2]。將預(yù)測(cè)樹用于路徑預(yù)測(cè)時(shí)，假設(shè)用戶當(dāng)前的路徑為ba，觀察到預(yù)測(cè)樹中ba沒有子節(jié)點(diǎn)，則只能按當(dāng)前路徑為a來預(yù)測(cè)，觀察到a下方節(jié)點(diǎn)中a的子節(jié)點(diǎn)統(tǒng)計(jì)頻次最大，路徑預(yù)測(cè)結(jié)果即為a，如圖3所示[3]。

1.2 仿 真

仿真過程使用Matlab軟件進(jìn)行，用戶移動(dòng)模型采用隨機(jī)移動(dòng)模型?？紤]到不同的用戶會(huì)有不同長(zhǎng)度的移動(dòng)模式，數(shù)據(jù)集將用一個(gè)混合多階馬爾科夫模型生成。根據(jù)移動(dòng)模型中目標(biāo)的移動(dòng)隨機(jī)程度，數(shù)據(jù)集將被分為強(qiáng)移動(dòng)性數(shù)據(jù)集和弱移動(dòng)性數(shù)據(jù)集。強(qiáng)移動(dòng)性數(shù)據(jù)集中用戶的全部移動(dòng)序列都由模型產(chǎn)生，弱移動(dòng)性數(shù)據(jù)集則有部分用戶移動(dòng)序列是等概率隨機(jī)產(chǎn)生的，以模擬某些移動(dòng)用戶的無規(guī)律性。訓(xùn)練集和測(cè)試集由同一個(gè)混合多階馬爾科夫模型生成，分別從中隨機(jī)截取而成，模型參考數(shù)[4]見表1。

表1 模型參數(shù)表

[參數(shù)＼&取值 /%＼&長(zhǎng)度為2的移動(dòng)模式比例＼&60＼&長(zhǎng)度為3的移動(dòng)模式比例＼&20＼&長(zhǎng)度為4的移動(dòng)模式比例＼&15＼&長(zhǎng)度為5的移動(dòng)模式比例＼&5＼&強(qiáng)移動(dòng)數(shù)據(jù)集中由模型產(chǎn)生的移動(dòng)序列比例＼&100＼&弱移動(dòng)數(shù)據(jù)集中由模型產(chǎn)生的移動(dòng)序列比例＼&80＼&]

1.2.1 預(yù)測(cè)精度

圖4比較了LZ編碼方案，基于Apriori序列模式挖掘方案和二階馬爾科夫預(yù)測(cè)方案對(duì)同一生成數(shù)據(jù)集的預(yù)測(cè)結(jié)果，顯示出Active LZ編碼方案在預(yù)測(cè)精度上性能稍好于其他兩個(gè)方案，驗(yàn)證了在實(shí)際數(shù)據(jù)集中，用戶移動(dòng)模式長(zhǎng)短不一時(shí)，LZ編碼方案對(duì)移動(dòng)模式長(zhǎng)度的自適應(yīng)特性，從而在預(yù)測(cè)精度上好于單階數(shù)馬爾科夫模型和Apriori算法。

同時(shí)可以觀察到：大多數(shù)情形下，LZ編碼和二階馬爾科夫方案預(yù)測(cè)用戶到達(dá)某一小區(qū)的數(shù)量都會(huì)大于實(shí)際到達(dá)的數(shù)量，這是因?yàn)槎邔?shí)質(zhì)上是概率模型，預(yù)測(cè)中總會(huì)選擇條件概率最大的分支作為預(yù)測(cè)結(jié)果，但是實(shí)際并不會(huì)總是到達(dá)該小區(qū)，因此在統(tǒng)計(jì)數(shù)量較小時(shí)，會(huì)出現(xiàn)這種預(yù)測(cè)結(jié)果大于實(shí)際結(jié)果的現(xiàn)象。

從LZ編碼和Apriori預(yù)測(cè)方案在兩種不同移動(dòng)性的數(shù)據(jù)集中的性能可以看出兩種方案的預(yù)測(cè)正確率都有所下降，但LZ編碼預(yù)測(cè)算法性能下降的稍小一些，即使在低移動(dòng)性數(shù)據(jù)集中表現(xiàn)也好于Apriori算法[5]，如圖5所示。

1.2.2 算法對(duì)訓(xùn)練集數(shù)量的依賴

二階馬爾科夫模型和Apriori預(yù)測(cè)算法在訓(xùn)練集較小時(shí)就可以提供較高的預(yù)測(cè)精度，而LZ編碼預(yù)測(cè)算法對(duì)訓(xùn)練集數(shù)量較為敏感，少量訓(xùn)練集下預(yù)測(cè)精度低，但達(dá)到一定閾值之后，預(yù)測(cè)精度穩(wěn)定后，性能優(yōu)于其他兩種預(yù)測(cè)算法，三種預(yù)測(cè)方案預(yù)測(cè)精度和訓(xùn)練集數(shù)量的關(guān)系如圖6所示。

2 路徑預(yù)測(cè)技術(shù)的動(dòng)態(tài)信道預(yù)留方案

動(dòng)態(tài)信道預(yù)留方案針對(duì)不同的場(chǎng)景調(diào)整信道預(yù)留策略，在保證切換呼叫阻塞率指標(biāo)的同時(shí)，盡可能地提高信道利用率，改善新呼叫阻塞率。

2.1 方案介紹

動(dòng)態(tài)信道預(yù)留的關(guān)鍵在于合理地針對(duì)未來業(yè)務(wù)狀態(tài)調(diào)節(jié)信道資源預(yù)留數(shù)量。為了解決這個(gè)問題，在信道預(yù)留系統(tǒng)之外設(shè)置一個(gè)路徑預(yù)測(cè)系統(tǒng)，用于預(yù)測(cè)下一時(shí)段用戶是否會(huì)到達(dá)基站覆蓋范圍，統(tǒng)計(jì)所有用戶路徑的預(yù)測(cè)結(jié)果，結(jié)合用戶呼叫業(yè)務(wù)狀態(tài)，就可以得到下一時(shí)段切換呼叫的到達(dá)數(shù)量[6]。

基于路徑預(yù)測(cè)的動(dòng)態(tài)信道預(yù)留系統(tǒng)分為三個(gè)部分：信道預(yù)留系統(tǒng)、路徑預(yù)測(cè)系統(tǒng)和業(yè)務(wù)狀態(tài)模型。路徑預(yù)測(cè)系統(tǒng)用于對(duì)交換中心下的所有注冊(cè)用戶進(jìn)行路徑預(yù)測(cè)，通過統(tǒng)計(jì)路徑預(yù)測(cè)的結(jié)果得出各個(gè)基站下一時(shí)段的到達(dá)用戶數(shù)量和離開用戶數(shù)量。預(yù)測(cè)結(jié)果將提供給業(yè)務(wù)狀態(tài)模型，借助到達(dá)和離開用戶數(shù)量預(yù)測(cè)結(jié)果計(jì)算每個(gè)基站下一時(shí)段切換呼叫到達(dá)率和總呼叫到達(dá)率，最后根據(jù)這些業(yè)務(wù)狀態(tài)參數(shù)調(diào)整信道預(yù)留系統(tǒng)的信道資源預(yù)留數(shù)量。信道預(yù)留系統(tǒng)是由若干個(gè)資源預(yù)留數(shù)量不同的固定信道預(yù)留系統(tǒng)組成，業(yè)務(wù)狀態(tài)參數(shù)和信道資源預(yù)留數(shù)量的關(guān)系將由切換呼叫阻塞率指標(biāo)和信道利用率指標(biāo)確定[7]，如圖7所示。

2.2 仿 真

2.2.1 仿真條件

組呼是專用移動(dòng)通信網(wǎng)絡(luò)特有的呼叫業(yè)務(wù)形式，呼叫過程中所有組內(nèi)用戶共享下行信道資源，實(shí)際應(yīng)用中組呼占呼叫業(yè)務(wù)比例高達(dá)80%。除去單呼和組呼，小區(qū)內(nèi)還處在移動(dòng)臺(tái)呼叫調(diào)度臺(tái)，調(diào)度臺(tái)呼叫移動(dòng)臺(tái)等多種業(yè)務(wù)形式，為了簡(jiǎn)化模型，將移動(dòng)臺(tái)與調(diào)度臺(tái)之間的呼叫作為特殊形式的組呼，且在所有呼叫中移動(dòng)臺(tái)都是發(fā)起方。此時(shí)無論對(duì)于單呼、組呼，移動(dòng)臺(tái)發(fā)起呼叫都需要分配上行信道，對(duì)于基站信道資源分配來說要求是相同的。根據(jù)選取的場(chǎng)景，列出仿真過程中業(yè)務(wù)模型參數(shù)如表2所示。

為一個(gè)組呼組內(nèi)的成員分配相同的移動(dòng)模型，且組呼成員的移動(dòng)模型的規(guī)律性將高于個(gè)呼用戶移動(dòng)模型的規(guī)律性。仿真過程中，整個(gè)移動(dòng)區(qū)域如圖8所示，共有13個(gè)服務(wù)小區(qū)，用字母A～M標(biāo)記，用戶隨機(jī)從邊界進(jìn)入移動(dòng)區(qū)域，按混合多階馬爾科夫模型移動(dòng)，仿真所預(yù)測(cè)的服務(wù)小區(qū)位于區(qū)域正中心。

在下列假設(shè)下考察基于路徑預(yù)測(cè)的動(dòng)態(tài)信道預(yù)留策略的性能：服務(wù)小區(qū)內(nèi)用戶的到達(dá)和離開數(shù)量基本平衡，仿真過程中固定用戶數(shù)量不變，根據(jù)用戶移動(dòng)模型仿真結(jié)果調(diào)整切換呼叫比例，從而模擬服務(wù)小區(qū)內(nèi)用戶移動(dòng)導(dǎo)致切換呼叫數(shù)量變化引起切換呼叫比例變化，獲得基于路徑預(yù)測(cè)的動(dòng)態(tài)信道預(yù)留策略性能曲線。

仿真過程中將以切換阻塞率小于0.03為判斷切換算法是否合格的指標(biāo)。圖9中給出了仿真業(yè)務(wù)參數(shù)下切換率和切換呼叫阻塞率的對(duì)應(yīng)關(guān)系，觀察可以發(fā)現(xiàn)，信道預(yù)留1條只能滿足切換率小于0.14時(shí)的要求，信道預(yù)留2條只能滿足切換率小于0.35時(shí)的要求，信道預(yù)留3條只能滿足切換率小于0.46時(shí)的要求。于是為了滿足切換阻塞率小于0.03，可以得到動(dòng)態(tài)信道預(yù)留調(diào)節(jié)的參數(shù)如表3所示，動(dòng)態(tài)信道預(yù)留算法的理論性能如圖10所示。

2.2.2 仿真結(jié)果分析

從靜態(tài)信道預(yù)留方案和基于路徑預(yù)測(cè)的動(dòng)態(tài)信道預(yù)留方案瞬時(shí)切換呼叫阻塞率和信道利用率的曲線圖中可以看出，隨著切換呼叫比例的變化，動(dòng)態(tài)預(yù)留方案的切換呼叫阻塞率始終保持在0.03以下，而兩種固定預(yù)留方案的切換呼叫阻塞率均有超出0.03的時(shí)刻，其中固定預(yù)留2條信道的方案幾乎完全無法滿足切換呼叫阻塞率低于0.03的要求，如圖11所示。

從給出了三種方案下切換呼叫阻塞率和信道利用率的時(shí)間平均曲線圖中可以看出，動(dòng)態(tài)預(yù)留方案的信道利用率介于兩者固定信道預(yù)留方案之間，達(dá)到了75%，高于固定信道預(yù)留3條的72%，在保證切換呼叫阻塞率指標(biāo)的情況下，提高了信道利用率，如圖12所示。

從三種方案下新呼叫阻塞率的性能曲線圖中可以看出動(dòng)態(tài)預(yù)留方案的平均新呼叫阻塞率介于兩者固定信道預(yù)留方案之間，達(dá)到0.38，低于固定預(yù)留3條的0.42，如圖13所示。

3 結(jié) 論

本文在數(shù)據(jù)挖掘理論的基礎(chǔ)上選擇了基于LZ編碼的預(yù)測(cè)算法對(duì)用戶路徑序列進(jìn)行處理，生成編碼預(yù)測(cè)樹，能有效地應(yīng)對(duì)不同長(zhǎng)度的用戶移動(dòng)模式挖掘需求，提高預(yù)測(cè)精度。經(jīng)過Matlab的仿真，證明了LZ編碼預(yù)測(cè)方案在混合長(zhǎng)度用戶模式數(shù)據(jù)集中能夠有效提高預(yù)測(cè)準(zhǔn)確率，并且對(duì)訓(xùn)練集數(shù)量要求較低；提出一種基于路徑預(yù)測(cè)技術(shù)的動(dòng)態(tài)信道資源預(yù)留方案，有效地預(yù)測(cè)業(yè)務(wù)狀態(tài)變化，并合理調(diào)整信道資源預(yù)留，始終將切換呼叫阻塞率保持在要求指標(biāo)之下，同時(shí)部分改善新呼叫阻塞率性能，提高了信道利用率。

本文雖然在路徑預(yù)測(cè)技術(shù)方面做了部分理論研究，并得出了一些結(jié)論，但在工作中仍有很多需要進(jìn)一步深入的問題，包括：LZ編碼預(yù)測(cè)算法在實(shí)際數(shù)據(jù)集中的預(yù)測(cè)性能需要進(jìn)一步驗(yàn)證；研究過程中，難以獲得真實(shí)的用戶路徑數(shù)據(jù)集；在仿真過程中以混合多階馬爾科夫模型為用戶模型生成路徑數(shù)據(jù)集以供使用，但生成數(shù)據(jù)集和實(shí)際數(shù)據(jù)集仍有很大區(qū)別，其影響需進(jìn)一步研究。

參考文獻(xiàn)

[1] LANGDON G G. A note on the Ziv?Lempel model for compres?sing individual sequences [J]. IEEE transactions on information theory， 1983， 29（2）： 284?287.

[2] GOPALRATNAM K， COOK D J. Online sequential prediction via incremental parsing： the active Lezi algorithm [J]. IEEE intelligent systems， 2007， 22（1）： 52?58.

[3] 王浩，武凌，司鳳山，等.基于移動(dòng)代理的分布式入侵檢測(cè)系統(tǒng)研究[J].重慶科技學(xué)院學(xué)報(bào)（自然科學(xué)版），2013，78（6）：143?145.

[4] 王晟，趙壁芳.基于模糊數(shù)據(jù)挖掘和遺傳算法的網(wǎng)絡(luò)入侵檢測(cè)技術(shù)[J].計(jì)算機(jī)測(cè)量與控制，2012，20（3）：660?663.

[5] 趙艷君，魏明軍.改進(jìn)數(shù)據(jù)挖掘算法在入侵檢測(cè)系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（18）：69?72.

[6] 段惠超，王麗俠，潘旭，等.入侵檢測(cè)系統(tǒng)中的帶權(quán)模式匹配算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2014，24（2）：160?163.

[7] 閆光燦.60 GHz網(wǎng)絡(luò)MAC層的干擾抑制和空間重用[D].北京：北京郵電大學(xué)，2012.