基于粗糙神經網絡的用戶軌跡數據深度挖掘

秦澤浩，趙 理

(1.吉林大學計算機科學與技術學院，吉林 長春 130012；2.北京信息科技大學機電工程學院，北京 100192)

1 引言

伴隨著信息數據的積累，大量繁雜的軌跡數據中存在許多重要信息，普通的軌跡數據挖掘沒有對隱藏在軌跡數據背后的用戶進行深層次提取，導致挖掘信息過于抽象[1，2]，因此，為了保證軌跡數據能夠得到有效探索，需要對用戶軌跡數據進行深度挖掘。

在此背景下，相關學者與科研人員進行了大量研究，其中，有學者提出了基于粗糙集與BP神經網絡的分布式數據挖掘算法，該方法利用粗糙集與神經網絡構建一個分布式傳感器網絡，對節點的初始數據進行離散和約簡，最終形成BP神經網絡，通過集成將BP神經網絡設置到每個傳感器節點上，該方法沒有對用戶行為數據的影響因素進行特征提取，導致用戶軌跡數據挖掘的精準度低，存在用戶軌跡數據命中率低的問題，表明方法的實用性差。還有學者提出了基于模糊神經網絡的用戶軌跡數據挖掘方法，該方法為尋找不同用戶的軌跡數據規律，利用遺傳算法對網絡結構進行優化，壓縮聚類數據信息，將其應用到實際操作中，獲取有用知識，此方法在軌跡完整度的變化下，用戶軌跡數據誤差大，存在用戶軌跡數據挖掘魯棒性低的問題。除此之外，有學者提出了基于粗糙RBF神經網絡的用戶軌跡數據挖掘，該方法針對因通信和設備故障引起的用戶軌跡數據要素值丟失問題構建了一個徑向基神經網絡的插補模型。該模型以用戶軌跡數據為主，利用粗糙集理論對軌跡數據產生的影響進行簡化，將簡化后的數據輸入到徑向基神經網絡中，實現用戶軌跡數據的挖掘，該方法獲取的軌跡數據特征精準度較低，導致用戶挖掘軌跡數據與實際結果不符，存在預測命中率低的問題[3，4]。

為了解決上述方法中存在的問題，提出基于粗糙神經網絡的用戶軌跡數據深度挖掘。

2 用戶軌跡數據處理特征提取及算法實現

2.1 提取用戶軌跡數據特征

經過對用戶軌跡數據的調查，發現影響用戶軌跡的因素包括：訪問時間、訪問次數、星期幾、是否為節假日、天氣因素、用戶興趣地點、間隔七個訪問時間維度[5]。

1)用戶出行時訪問時間的影響力指標為

(1)

其中，h={1，2，3，…，24}，h代表記錄軌跡數據的當日小時；M代表h小時中的軌跡數據總數；Bhn代表在第h小時中的第n條軌跡數據。

進一步探索訪問時間對用戶行為產生的影響，即指標權重HWh，方程如下

(2)

其中：Tmax=max{T0，T1，…，T24}；Tmin=min{T0，T1，…，T24}。

2)用戶在星期幾出行訪問的影響指標為：

(3)

其中，j代表訪問時間為星期幾，m代表用戶在j的第n條用戶訪問標量。

深入研究訪問星期對用戶產生的影響，即指標權重，其方程如下

(4)

其中，Wmax=max{W0，W1}；Wmin=min{W0，W1}。

3)用戶出行訪問是否為節假日的影響力指標

(5)

其中，b代表是否為節假日，m代表用戶在b的記錄數量，Dbn代表b中第n條訪問標量。

進一步探索訪問是否為節假日對用戶產生的影響，即指標權重，其方程表示為

(6)

其中，Holmax=max{Hol0，Hol1}；Holmin=min{Hol0，Hol1}。

4)用戶出行時天氣因素造成的影響，由方程表示

(7)

其中，a代表天氣因素，Wetan代表記錄在a時第n條訪問標量。

進一步研究天氣因素對用戶造成的影響，即指標權重，其方程如下

(8)

式中，Wetmax=max{Wet0，Wet1，…}；Wetmin=min{Wet0，Wet1，…}。

4)用戶興趣地點對用戶出行目的的影響，其表示如下

(9)

其中，c代表用戶興趣地點，Pcn表示用戶訪問c的情況下第n條訪問標量。

深度探索用戶興趣地點對用戶行為形成的影響，即指標權重，其方程如下

(10)

其中，Pmax=max{P0，P1…}；Holmax=max{P0，P1…}。

6)用戶訪問興趣點次數用方程表示如下

Fpid=Vpid/D

(11)

其中，pid代表用戶興趣點的id，D代表時間跨度，單位為天，Vpid代表D天內訪問pid的天數。

7)訪問時間間隔Durpid，其方程如下所示

(12)

其中，K代表用戶訪問興趣點的總數目，Durpid1k代表第k次訪問pid的時間間隔時長。

2.2 挖掘規則

根據上述因素提取用戶軌跡數據的最優特征，利用粗糙神經網絡獲取用戶軌跡數據挖掘規則。通常情況下，數據冗余越小，神經網絡學習得越快[6，7]。利用粗糙集簡化數據，將簡化后的數據作為神經網絡設計依據和訓練數據。這樣就會獲取清晰的數據，兩種方法得到互補，可以通過神經網絡進行降噪處理。

基于粗糙集理論的數據深度挖掘屬于屬性約簡，其步驟為：利用差別矩陣求取屬性核心，再對屬性歸約集進行計算。通過粗糙集理論對數據深度挖掘的流程如圖1所示。

圖1 粗糙集的數據深度挖掘流程圖

粗糙集約簡的終止條件或神經網絡訓練數據數量的選擇是該算法的難點[8]。現如今還沒有能夠準確獲取訓練數據數量的方法，但有一個簡略估算方法，假設訓練數據的數目為連接節點個數的二倍，其中一個神經網絡中存在p個節點輸入、n1個節點隱層、q個節點輸出，其訓練數據為2×(p×n1+n1×q)個。

神經網絡的精度與訓練數據的數量息息相關[9]。通常使用均方根誤差對學習性能進行有效反映，其方程定義如下

(13)

其中，X代表自變量。代價函數表示如下

(14)

其中，x代表系數，取值范圍>1；y代表代價函數。

代價函數就是訓練數據或粗糙集歸約的選擇依據，采用粗糙神經網絡獲取用戶軌跡數據挖掘規則的流程如圖2所示。

圖2 算法流程圖

具體實現步驟如下：

1)提取挖掘數據，選擇挖掘條件，確立挖掘方向。

2)通過粗糙集理論消除冗余數據屬性。

3)根據粗糙集理論實行離散、屬性約簡。

4)在用戶最少約簡表中選擇訓練數據集，否則通過代價函數的最高代價和約簡屬性對訓練樣本數據進行計算，若計算結果<<數據約簡后的總數目，則輸送到步驟3)繼續約簡，或根據代價函數的推薦選擇訓練數據集。

5)通過訓練數據樣本對神經網絡進行設計和訓練。

6)獲取數據挖掘規則。

3 用戶軌跡數據挖掘模型

3.1 根據挖掘規則構建挖掘模型

通過訓練集、測試集和數據特征在挖掘規則的基礎上建立用戶軌跡數據挖掘模型，構建基于網格的ANFIS軌跡數據模型如圖3所示。

圖3 用戶軌跡數據挖掘模型

該軌跡數據模型共分為五層，方框中的節點是可以進行參數調整的，圓形中的節點不可以改變。ANFIS中能夠更改的參數主要居于第一層和第五層，第一層代表隸屬函數參數，第五層代表規則后件參數。在ANFIS模型中，第一層模糊化輸出用方程定義為

(15)

設{X1，X2，…，Xn}為輸入空間的維數，其中有多個數據點，函數Xi(i=1，2，…，n)表示m×1的列向量。因為聚類中心的候選點由每個數據點代替，所以Xi的聚類中心潛能方程表達式為

(16)

其中，ra代表半徑正數，若數據點Xi附近存有多個數據點，則Xi存在巨大潛能。選取一個最大潛能數據點，設Xci代表被選中的數據點，Pci為它的潛能，因此，改正后的Xi潛能用方程表示如下

(17)

其中，rb代表一個正數，一般取rb>ra，表示潛能較少的領域，通過改正后第一個潛能為零，距離Xci越近其潛能降低越快，這樣成為下一個聚類中心的可能性就越小。將Xc2作為最大潛能數據點，再次進行潛能修正后，整個過程中沒有在符合范圍內的候選點。因此，當輸入變量變少時，采用網格方法區分效果比聚類方法顯著；當輸入變量增多時，利用聚類方法減少規則數量，系統仿真效果具有明顯提升。

通過對輸入空間進行劃分后，需要為每個模糊劃分選擇合適的函數。其常用函數有：三角形、梯形、高斯函數等。ANFIS模型中主要運用高斯函數和鐘型函數，其中，高斯函數表示如下

(18)

鐘型函數如下表示

(19)

其中，C代表模糊集合的中心向量。

第二層的每個輸出節點都是輸入信號的乘積，乘積結果就是這一條的規則強度，其方程為

(20)

第三層對第i個激勵強度節點規則與規則激勵強度總和進行比值計算，得出

(21)

第四層規則輸出表示為

(22)

其中，{pi，qi，ri}代表規則后件參數。

第五層對每層輸出求和后得出的總輸出

(23)

通過上述步驟實現模型輸出，輸出結果就是用戶軌跡數據。

4 實驗與分析

為了驗證基于粗糙神經網絡的用戶軌跡數據深度挖掘的整體有效性，需要對用戶軌跡數據深度挖掘進行測試，本次測試的實驗平臺為，系統：Microsofte Windows XP；處理器：Inter(R)Celeron(R)M 1.40GHz；內存：760MB。

采用基于粗糙神經網絡的用戶軌跡數據深度挖掘方法(方法1)、基于模糊神經網絡的用戶軌跡數據挖掘(方法2)、基于粗糙RBF神經網絡的用戶軌跡數據挖掘(方法3)對用戶軌跡數據模型進行軌跡終點預測精度測試，實驗結果如圖4所示。

圖4 模型終點預測精度對比圖

通過上述分析可知，方法1進行模型終點預測精度測試時，隨著時間的增加距離誤差一直處于100米以下，表明該模型的距離誤差小，終點預測精度高，因為該方法在軌跡數據挖掘之前獲取了用戶出行訪問時間影響指標，將其作為用戶軌跡數據初始特征，根據提取的特征完成軌跡數據深度挖掘，提高了挖掘數據的精準度。

圖5為用戶軌跡數據模型魯棒性對比結果。

圖5 用戶軌跡數據模型魯棒性對比

隨著軌跡完整度的增加，方法1的距離誤差逐漸變小，其數據波動呈下降趨勢，說明方法1的魯棒性強。采用方法2和方法3分別對模型進行測試時，隨著軌跡完整度的逐步增加，數據波動劇烈。相比于方法1，說明方法2和方法3的距離誤差大，魯棒性低。綜上所述，軌跡完整度不會影響方法1的數據挖掘精度，當軌跡完整度較低時，方法1可以根據提取的多種特征實現用戶軌跡數據的挖掘。

設用戶軌跡數據深度挖掘時間為5秒，通過方法1、方法2和方法3對用戶軌跡數據模型命中率進行測試，命中率越高，表明用戶軌跡數據深度挖掘模型越好，其測試如圖6所示。

圖6 用戶軌跡數據模型命中率變化圖

根據上述數據可知，方法1在進行用戶軌跡數據模型命中率測試時，它的初始命中率為0.7%，隨著時間的增加，其命中率一直處于上升狀態，說明方法1的命中率高，用戶軌跡數據深度挖掘準確性高。利用方法2和方法3對模型命中率進行測試時，命中率極低，且數據波動不穩定。因為方法1在不同角度中對影響用戶估計的因素進行分析，多方面地提取用戶軌跡特征，在多特征的基礎上對用戶軌跡數據進行挖掘，進而提高了方法1挖掘軌跡數據的命中率。

5 結束語

經研究發現，傳統用戶軌跡數據挖掘方法存在終點預測精度低、系統模型魯棒性低和系統模型命中率差的問題。針對以上問題提出基于粗糙神經網絡的用戶軌跡數據深度挖掘方法，將用戶軌跡數據特征提取，利用粗糙集獲取數據挖掘規則，構建挖掘模型，從而實現用戶軌跡數據挖掘，提高了粗糙神經網絡的有效性和數據挖掘的準確性，解決了目前方法中存在的問題，為用戶軌跡數據深度挖掘提供了保障。