基于情景感知與約束的移動用戶序列行為研究

張曉濱，李園園，郭 斌

ZHANG Xiaobin,LI Yuanyuan,GUO Bin

西安工程大學 計算機科學學院，西安710048

College of Computer Science,Xi’an Polytechnic University,Xi’an 710048,China

1 引言

傳統的序列模式挖掘算法通常將用戶歷史行為數據作為整體進行頻繁模式挖掘，發現用戶購買行為習慣，產生推薦，并未考慮一段時間內，行為之間的內在關聯性。而用戶的行為并不是獨立存在的，行為與行為之間存在著關聯性[1]，尤其在移動環境下，具有情景敏感特性的用戶序列行為的關聯性更為顯著[2]，通過研究前一行為與后續行為的聯系，發現用戶行為序列模式，根據發現的行為序列模式可以更準確地預測后續行為，提高推薦質量。文獻[3]對比移動用戶與傳統用戶的需求、行為差異性，提出移動用戶需求面臨的新挑戰，即實時性、上下文感知等特點[4-5]。該文獻定義情境即“上下文”，是用于描述實體狀態的任何信息，其中，實體可以是人、地點或者和應用程序之間相互交互的客體[6-7]。文獻[8]將用戶位置、環境等情景信息與用戶運動軌跡進行聚合，形成用戶潛在社交網絡，情景感知的自動聚合加快了潛在網絡的發現速度和準確性，然而文獻[8]中對情景數據進行簡單聚合，并沒有深入研究各情景要素對用戶行為的影響。序列模式挖掘是用戶行為研究的主要方法，文獻[9]總結了序列模式挖掘近十年來的發展狀況并提出了其未來的研究重點，即用戶行為模式發現的片面性以及多情景屬性對移動用戶序列行為挖掘的巨大潛力[10]。本文在用戶行為模式挖掘基礎上加入情景敏感性因素，提出一種將描述實體狀態的多情景屬性與用戶行為模式挖掘相結合的用戶行為模式挖掘方法。

2 基于情景敏感的用戶行為序列

研究從移動用戶序列行為的情景敏感性入手，將收集到的用戶序列行為記錄以時間、位置因素對其進行約束處理，進而提出一種將約束后的用戶序列行為轉化成決策表的方法，此方法解決了進一步用粗糙集屬性約簡方法對決策表進行序列行為模式挖掘的首要問題。

2.1 序列項約束處理

用戶歷史數據中的序列行為必須在一定時間段內才有效、有意義，即序列行為是有時間、位置限制的。前序行為與后序行為如果相隔時間太長，則可能沒有任何關系，可以認為前一序列活動已經結束；相反，如果連續的兩個行為之間相隔時間太短，考慮用戶不可能在同一時間同時完成多個行為可以判定這兩個行為之間也是無關的。文獻[11]以序列項之間的時間間隔和整個序列的時間間隔對用戶簽到段進行約束，這種方法充分考慮了序列項之間的時間特性，但忽視了項與項之間的位置變化，序列項之間的時間段的分割產生是隨著項位置的改變而產生的，只有位置發生了改變才能將時間這個連續實體分割產生“時間段”，如果時間變了，位置沒變，則用戶的行為未發生轉移。因此，將位置與時間結合起來對研究序列項更有實際意義。

將獲得的原始簽到段數據表示為I={I1,I2,…,I n}，每一個行為項由時間、位置等情景屬性構成，即Ii∈I，Ii={(Pi,R)|Ti∈R,Pi∈R}，Pi表示位置，R表示描述項Ii的各情景屬性組成的集合。行為序列I中，相鄰兩個項的時間差是ΔTnext(Ii)=(Ti-Ti-1)，整個序列的時間間隔是Twhole(In)=(Tn-T1)，由此定義Cmax-next和Cmin-next為相鄰序列間最大和最小時間間隔，定義Cmax-whole和Cmin-whole為整個序列的最大和最小時間間隔。則由Cmax-next、Cmin-next、Cmax-whole、Cmin-whole、Pi五個參數對原始數據進行約束處理，基于時間、位置約束的序列項處理算法步驟如下：

步驟1將項集合中的每個項依次追加到事務項中，生成預處理事務項，并對生成的每一個預處理事務項進行步驟2 的約束處理。

步驟2對事務項進行約束處理，約束規則如下：

（1）如果該預處理事務項的相鄰序列項時間差和整個序列的時間差在給定最大、最小時間差范圍內，且位置不相等，就將該項加入事務項Sj，然后返回判斷下一個項。

（2）如果該預處理事務項相鄰項時間差小于Cmin-next，或者整個序列時間差小于Cmin-whole，或者位置相等，Ii是錯誤項，返回判斷下一個項。

（3）如果該預處理事務相鄰項時間差大于Cmax-next，或者整個序列時間差大于Cmax-whole，則結束當前序列Sj；開始下一個事務序列項Sj+1的判斷。

步驟3經過約束處理后的事務項放入事務集合中，直至項集合遍歷結束，得到事務集合。

算法實現如下：

輸入：項的集合I={I1,I2,…,I n}，預處理事務項Sj'={I1}，Cmax-next，Cmin-next，Cmax-whole，Cmin-whole，Pi

輸出：D

2.2 生成決策表

Pawlak[12]提出粗糙集屬性約簡與規則提取不僅能發現影響行為模式的各屬性重要度，并且通過粗糙集規則提取挖掘基于多情景屬性組合影響的用戶行為模式[13-14]。

定義1（決策信息系統）IS={U,R,V,f}，U是有限對象集，x∈U,R=C∪D,C是條件屬性，D是決策屬性，C∩D=?，V=Ra，Ra是屬性a的值域，?a∈R，f是U×R→V的一個信息函數，它為每個對象的每個屬性賦予一個信息值，f(x,a)∈Ra。

（2）將Si中滿足fk≥δ的相鄰兩項依次序轉換成決策對Xi={Pi,Ri,Pi+1}，Pi表示行為Ii發生時所處位置信息，R是描述Ii的情景屬性集合，Pi+1表示緊隨Ii的后序行為項Ii+1發生時所處位置信息。

（3）決策對Xi={Pi,Ri,Pi+1}，Xi∈U，將Ii的屬性集合Ri轉化成決策信息系統IS中的條件屬性集合C，Pi+1是項Ii+1的位置屬性，將Pi+1轉化成Xi的決策屬性D，V=∪Ri∪Pi+1，?a∈(Ri∪Pi+1)，f(xi,a)∈Va。

3 實驗分析

實驗中選取某市區100 位志愿者最近3 個月的簽到記錄作為實例數據，對大量簽到數據進行統計實驗分析得出，簽到段所包含的簽到序列記錄的時間差在10～120 min內的概率為0.9以上，據此設置參數值Cmax-next=80 min，Cmin-next=15 min，Cmax-whole=130 min，Cmin-whole=100 min，δ=0.85，Pi是對位置語義本體信息概念分層后的場所地點“電影院”，根據時間、位置約束后的事務D={S1,S2,…,S4009}，經過fk約束后的事務項如下：

表1 信息決策表

Sn1(A,Ra1)→(B,Rb1)→(C,Rc1)→(F,Rf1)Sn2(A,Ra2)→(F,Rf2)

Sn3(A,Ra3)→(B,Rb3)→(F,Rf3)

Sn4(B,Rb4)→(F,Rf4)

其中A、B、C、F是位置信息，R是情景屬性集合，將事務D轉換成決策對，結果為：X1={A,Ra1,B}，X2={A,Ra2,F}，X3={A,Ra3,B}，X4={B,Rb1,C}，X5={B,Rb3,F}，X6={B,Rb4,F}，X7={C,Rc1,F}，（X1-X7順序做了調整，與表1 對應）屬性集合R由用戶生理環境C1（心跳、體溫、運動方式）和物理環境C2（時間、位置、濕度、交通狀況）組成，各情景屬性在數據預處理階段需要進行概化和分層，條件屬性R5的位置信息和決策屬性D的位置信息由于不同標準的概念分層而產生不同結果。將決策對轉換成決策信息表如表1 所示。

實驗證明，經過時間、位置約束的序列項集合中已去除了無意義的簽到數據，精確了樣本數據，約束后的用戶數據經過模式轉換生成決策表的方法則解決了粗糙集挖掘基于情景敏感的行為模式所面臨的首要、關鍵問題，此基于情景約束和情景感知的行為模式挖掘方法具有更好的有效性和準確性。

4 結束語

移動環境下，用戶的興趣和選擇是實時的、動態的、情景敏感的[15]，針對當前移動用戶序列行為挖掘的情景敏感性問題，本文提出一種對用戶序列行為進行情景約束以及一種將約束后的用戶序列行為轉化成可用粗糙集屬性約簡方法進行序列行為模式挖掘的決策表方法。在此基礎上，可以對基于情景敏感的用戶序列行為進行挖掘，對基于情境敏感的用戶興趣建模和序列個性化推薦展開進一步研究。

[1] Lin Mingyen，Lee Suhyin.Efficient mining of sequential patterns with time constraints by delimited pattern growth[J].Knowledge and Information Systems，2005，7（4）：499-514.

[2] Staunstrup J，Tong F，Yu L，et al.Services in context[J].Computer System Application，2009，18（6）：161-167.

[3] 孟祥武，王凡，史艷翠，等.移動用戶需求獲取技術及其應用[J].軟件學報，2014，25（3）：439-456.

[4] Mahmoud Q H，Al-Masri E，Wang Zhixin.Design and implementation of a smart system for personalization and accurate selection of mobile services[J].Requirements Engineering，2007，12（4）：221-230.

[5] Ricci F.Mobile recommender systems[J].Journal of Information Technology and Tourism，2011，12（3）：205-231.

[6] 王立才，孟祥武，張玉潔.上下文感知推薦系統[J].軟件學報，2012，23（1）：1-20.

[7] 李蕊，李仁發.上下文感知計算及系統框架綜述[J].計算機研究與發展，2007，44（2）：269-276.

[8] 曹懷虎，朱建明，潘耘，等.情景感知的P2P 移動社交網絡構造及發現算法[J].計算機學報，2012，35（6）：1223-1233.

[9] 王虎，丁世飛.序列模式挖掘研究與發展[J].計算機科學，2009，36（12）：14-17.

[10] Adomavicius G，Sankaranarayanan R，Sen S，et al.Incorporating contextual information in recommender systems using a multidimensional approach[J].ACM Transactions on Information Systems，2005，23（1）：103-145.

[11] 夏英，孫沖武.基于時空序列模式匹配的興趣點推薦方法[J].重慶郵電大學學報：自然科學版，2011，23（3）：368-373.

[12] Pawlak Z.Rough set[J].International Journal of Computer and Information Science，1982，11（5）：341-356.

[13] 楊明.一種基于改進差別矩陣的屬性約簡增量式更新算法[J].計算機學報，2007，30（5）：815-816.

[14] 常犁云，王國胤，吳渝.一種基于Rough Set 理論的屬性約簡及規則提取方法[J].軟件學報，1999，10（11）：1206-1211.

[15] 史翠艷，孟祥武，張玉潔，等.一種上下文移動用戶偏好自適應學習方法[J].軟件學報，2012，23（10）：2533-2549.