基于關聯規(guī)則和時間閾值算法的5G基站部署研究

陳少權+杜翠鳳

【摘 要】為了保障高價值用戶感知，從高價值用戶的業(yè)務連續(xù)性出發(fā)，探尋高價值用戶使用業(yè)務的局部興趣區(qū)域，并結合用戶逗留時間來對基站進行評分，以評分高的區(qū)域作為通信運營商部署5G基站的優(yōu)先點。經過實驗表明，在極具稀疏性的數據集上，基于關聯規(guī)則算法的精度較以往傳統(tǒng)的方法有明顯提高，且具有較高的擴展性。

【關鍵詞】關聯規(guī)則 時間閾值 用戶感知 業(yè)務連續(xù)性 興趣區(qū)域

doi：10.3969/j.issn.1006-1010.2016.20.004 中圖分類號：TP391.4 文獻標志碼：A 文章編號：1006-1010（2016）20-0022-05

1 引言

隨著第四代移動通信技術的快速發(fā)展以及移動互聯網的大規(guī)模應用，給高價值用戶感知的維護帶來了嚴峻的挑戰(zhàn)，目前的網絡規(guī)劃是否能夠滿足用戶業(yè)務連續(xù)性使用的需求，成為5G時代亟待解決的問題。本文從高價值用戶的業(yè)務連續(xù)性出發(fā)，探尋高價值用戶使用業(yè)務的局部興趣區(qū)域，并結合用戶逗留時間來對基站進行評分，以此作為通信運營商部署5G基站的優(yōu)先點。

2 關聯規(guī)則算法的研究

2.1 問題定義

用戶使用業(yè)務的局部興趣區(qū)域是研究用戶出行行為的一個關鍵性的問題，局部興趣區(qū)域識別實質是通過軌跡數據分析得到的用戶的興趣區(qū)域集合，再根據設定的閾值范圍篩選具有價值的興趣區(qū)域?；谟脩舻木植颗d趣區(qū)域，并結合用戶逗留時間來對基站進行評分，以評分高的基站作為通信運營商部署5G基站的優(yōu)先點。

本文是采用Apriori算法挖掘出移動用戶具有一定價值的興趣區(qū)域，再通過時間閾值對用戶的興趣區(qū)域進行打分，以高得分的區(qū)域作為移動運營商部署5G基站的優(yōu)先點。

2.2 關聯規(guī)則——Apriori算法

（1）關聯規(guī)則算法

關聯規(guī)則的獲取主要是通過數據挖掘的方法，從大量的事件記錄數據庫中找出那些用戶給定的滿足一定條件的最小支持度（Minsup）和最小置信度（Minconf）的頻繁模式[1-2]。關聯規(guī)則的傳統(tǒng)算法步驟是：先找出所有的頻繁項目集，再由頻繁項目集產生滿足最小支持度和最小置信度的規(guī)則。因此，關聯規(guī)則的屬性可用以下參數描述[2-3]：

◆支持度：全體事務集T中有s%同時支持事務集X和Y，則稱s%為關聯規(guī)則X→Y的支持度。支持度S（X→Y）表示規(guī)則的頻繁程度，一般用Minsup表示最小支持度。

◆置信度：全體事務集T中支持事務集X的事務里有c%的事務同時也支持事務集Y，則稱c%為關聯規(guī)則X→Y的置信度。置信度C（X→Y）表示規(guī)則的強度，一般用Minconf表示最小置信度。

◆頻繁項集：滿足一定最小支持度和最小置信度的事務集?；陉P聯規(guī)則的算法以Apriori算法為代表，利用逐層搜索的迭代方法找出數據庫中項集的關系，以形成規(guī)則，其過程由連接（類矩陣運算）與剪枝（去掉那些沒必要的中間結果）組成。該算法中項集（Itemset）的概念即為項的集合，包含k個項的集合為K項集。項集出現的頻率是包含項集的事務數，稱為項集的頻率。如果某項集滿足最小支持度，則稱其為頻繁項集[4]。

（2）Apriori算法實現步驟

Apriori算法實現步驟具體如下：

◆設定最小支持度（Minsup）和最小置信度（Minconf）。

◆Apriori算法是一種需要多次迭代的算法，經過掃描一次數據庫，統(tǒng)計數據庫中單個項目的計數，將滿足最小支持度要求的單個項目提取成1-頻繁項集L1，并將頻繁項目L1作為下一次掃描的基礎項目[3]。然后重復掃描數據庫，第（k-1）次掃描生成（k-1）-頻繁項集L后，第k次掃描時先通過連接操作將Lk-1中的項集生成k-項候選集Ck，再通過剪枝操作刪除Ck中不滿足最小支持度計數的項集，從而得到頻繁項集Lk。重復掃描數據庫，從該集合里產生下一級候選項集，直到不產生新的候選項集為止[4]。

2.3 時間閾值實現步驟

時間閾值法作為移動對象頻繁模式挖掘的常用算法，其定義為：在一定時間范圍內，用戶發(fā)生事件之間先后順序的事件間隔大于δ，只有滿足該條件，才能挖掘移動對象頻繁模式。本文通過檢測移動用戶停留在用戶頻繁活動區(qū)域的時間間隔，如果用戶都留在該區(qū)域的時間大于設定的時間閾值且評分較高，則判定該區(qū)域是5G基站部署的優(yōu)先點。

其實現步驟具體如下：

（1）通過Apriori算法找到興趣區(qū)域數據——小區(qū)；

（2）對每個移動用戶所涉及到的興趣小區(qū)按照時間順序排序：Cell1（Lngt1， Lat1， t11， t12）， Cell2（Lngt2， Lat2， t21， t22）， …， Cellm（Lngtm， Latm， tm1， tm2）；

（3）遍歷Cell1-Cellm ，判斷每個Cell的停留時間是否大于設定的閾值δ，若大于則評分為1，否則為0；

（4）遍歷每個Cell的停駐點，計算每個用戶在每一個Cell的得分，再通過歸一化得出每個基站的最終得分。

3 基于關聯規(guī)則和時間閾值算法挖掘5G優(yōu)先部署站點

3.1 移動用戶軌跡數據的提取

在提取用戶的軌跡數據之前，首先需要說明切換的定義。切換是指當移動臺在通話過程中從一個基站覆蓋區(qū)移動到另一個基站覆蓋區(qū)或者由于外界干擾造成通話質量下降時，必須改變原有的話音信道而轉接到一條新的空閑話音信道上，以繼續(xù)保持通話的過程。切換通常發(fā)生在移動臺從一個基站覆蓋小區(qū)進入到另一個基站覆蓋小區(qū)的情況下，為了保持通信的連續(xù)性，MSC（Mobile Switching Center，移動交換中心）將移動臺與當前基站之間的鏈路轉移到移動臺與新的基站之間的鏈路，這種切換操作不僅要識別一個新的基站，而且要求將語音和控制信號分配到新的基站相關信道上[5]。

在移動用戶進行移動的過程中會發(fā)生各種手機業(yè)務或者進行小區(qū)的切換，這些信息都會記錄在用戶的軌跡數據里，具體如表1所示：

3.2 采用Apriori算法挖掘移動用戶的興趣區(qū)域

本文對某地市運營商的10萬VIP移動用戶在一個月工作日時間段（8點至17點）的軌跡進行分析。在實驗中，min_sup設置為0.1，min_conf設置為0.2，把數據放進MATLAB中進行處理，得到的結果如表2所示。

由表2可知，有13 330名VIP移動用戶在一個月工作日時間段（8點至17點）同時去過基站19567和基站19598；有3 523名VIP移動用戶經過基站19567后又到達基站19598。

通過Apriori算法找到運營商關注的VIP移動用戶的興趣區(qū)域局部相似性，下一步需要通過計算VIP移動用戶在該區(qū)域的停留時長，才能作為5G基站部署的優(yōu)先點。

3.3 基于時間閾值識別5G基站部署的優(yōu)先點

通過Apriori算法確定VIP移動用戶興趣區(qū)域的相似性后，提取每個VIP移動用戶停留在興趣區(qū)域的時間，運營商可以設置時間閾值δ識別。如果VIP移動用戶在該區(qū)域停留的時間大于時間閾值δ且發(fā)生的得分較高，則認為基站可作為5G基站的優(yōu)先部署點。VIP移動用戶在興趣區(qū)域的最終得分如表3所示：

由表3可知，基站19567最終得分較少，因此可以認為部署5G基站所獲得的預期收益相對較少；而該用戶在基站20137得分很高，則可以認為部署5G基站所獲得的預期收益相對較多（注：本文認為若有價值用戶在基站得分大于0.8時，則判斷該基站是5G的優(yōu)先部署點）。

3.4 實驗結果及分析

本文對某地市運營商的10萬VIP移動用戶進行關聯規(guī)則和時間閾值算法的處理后，將得到的結果與基于傳統(tǒng)方法得出的5G基站優(yōu)先部署點進行對比分析，具體如圖1和圖2所示：

通過對比圖1和圖2可知，采用Apriori算法和時間閾值相結合的算法來挖掘5G基站的優(yōu)先部署點具有較高的精度。運營商根據有價值用戶的業(yè)務行為確定5G部署的優(yōu)先點，不僅實現基站的精準規(guī)劃建設，使用有限的資源最大程度地滿足用戶的需求和提升用戶的感知，而且還能保證有價值用戶對運營商自身利潤的貢獻，提升市場競爭力。

4 結束語

本文以高價值用戶感知為出發(fā)點，提出了滿足高價值用戶業(yè)務連續(xù)性使用需求的5G基站部署算法——基于關聯規(guī)則和時間閾值的算法。通過實驗證明，該算法不僅比較貼合運營商的實際需要，還能夠體現網絡精細化規(guī)劃的思路，以最少的資源實現利潤的最大化，在一定程度上提升運營商網絡運行和客戶維護的能力。

參考文獻：

[1] 郭濤，張代遠. 基于關聯規(guī)則數據挖掘Apriori算法的研究與應用[J]. 計算機技術與發(fā)展， 2011，21（6）： 101-103.

[2] 滕智源. 基于關聯規(guī)則挖掘的Q-CFIsL算法在網絡入侵檢測系統(tǒng)中的應用[J]. 企業(yè)科技與發(fā)展， 2010（10）： 59-61.

[3] 趙洪英，蔡樂才，李先杰. 關聯規(guī)則挖掘的Apriori算法綜述[J]. 四川理工學院學報： 自然科學版， 2011，24（1）： 66-70.

[4] 趙文濤，楊靜. 基于數據挖掘的煤礦安全信息管理模型的研究[J]. 工礦自動化， 2009，35（7）： 36-39.

[5] 楊飛，惠英. 基于手機切換變化模式的道路匹配方法[J]. 系統(tǒng)工程， 2007，25（11）： 6-13.

[6] Lu E H-C， Tseng V S， Yu P S. Mining cluster-based mobile sequential patterns in location-based service environments[J]. IEEE Transactions on Knowledge and Data Engineering， 2011，23（6）： 914-927.

[7] Monreale A， Pinelli F， Trasarti R， et al. WhereNext： a location predictor on trajectory pattern mining[A]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining （KDD09）[C]. New York： ACM， 2009： 637-646.

[8] Agrawal R， Imiclinski T， Swami A. Mining Assocation Rules between Sets of Items in Large Database[A]. Proceedings of the 1993 ACM SIGMOD Conference on Management of Data Table of Contents[C]. New York： ACM， 1993： 207-216.

[9] 王德興. 基于概念格模型關聯規(guī)則挖掘的關鍵問題研究[D]. 合肥： 合肥工業(yè)大學， 2006.

[10] 羅可，賀才望. 基于Apriori算法改進的關聯規(guī)則提取算法[J]. 計算機與數字工程， 2006，34（4）： 48-51.