張曉濱，李園園，郭 斌

ZHANG Xiaobin,LI Yuanyuan,GUO Bin

西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安710048

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

1 引言

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

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

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

2.1 序列項(xiàng)約束處理

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

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

步驟1將項(xiàng)集合中的每個(gè)項(xiàng)依次追加到事務(wù)項(xiàng)中，生成預(yù)處理事務(wù)項(xiàng)，并對生成的每一個(gè)預(yù)處理事務(wù)項(xiàng)進(jìn)行步驟2 的約束處理。

步驟2對事務(wù)項(xiàng)進(jìn)行約束處理，約束規(guī)則如下：

（1）如果該預(yù)處理事務(wù)項(xiàng)的相鄰序列項(xiàng)時(shí)間差和整個(gè)序列的時(shí)間差在給定最大、最小時(shí)間差范圍內(nèi)，且位置不相等，就將該項(xiàng)加入事務(wù)項(xiàng)Sj，然后返回判斷下一個(gè)項(xiàng)。

（2）如果該預(yù)處理事務(wù)項(xiàng)相鄰項(xiàng)時(shí)間差小于Cmin-next，或者整個(gè)序列時(shí)間差小于Cmin-whole，或者位置相等，Ii是錯(cuò)誤項(xiàng)，返回判斷下一個(gè)項(xiàng)。

（3）如果該預(yù)處理事務(wù)相鄰項(xiàng)時(shí)間差大于Cmax-next，或者整個(gè)序列時(shí)間差大于Cmax-whole，則結(jié)束當(dāng)前序列Sj；開始下一個(gè)事務(wù)序列項(xiàng)Sj+1的判斷。

步驟3經(jīng)過約束處理后的事務(wù)項(xiàng)放入事務(wù)集合中，直至項(xiàng)集合遍歷結(jié)束，得到事務(wù)集合。

算法實(shí)現(xiàn)如下：

輸入：項(xiàng)的集合I={I1,I2,…,I n}，預(yù)處理事務(wù)項(xiàng)Sj'={I1}，Cmax-next，Cmin-next，Cmax-whole，Cmin-whole，Pi

輸出：D

2.2 生成決策表

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

定義1（決策信息系統(tǒng)）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的一個(gè)信息函數(shù)，它為每個(gè)對象的每個(gè)屬性賦予一個(gè)信息值，f(x,a)∈Ra。

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

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

3 實(shí)驗(yàn)分析

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

表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是情景屬性集合，將事務(wù)D轉(zhuǎn)換成決策對，結(jié)果為：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順序做了調(diào)整，與表1 對應(yīng)）屬性集合R由用戶生理環(huán)境C1（心跳、體溫、運(yùn)動(dòng)方式）和物理環(huán)境C2（時(shí)間、位置、濕度、交通狀況）組成，各情景屬性在數(shù)據(jù)預(yù)處理階段需要進(jìn)行概化和分層，條件屬性R5的位置信息和決策屬性D的位置信息由于不同標(biāo)準(zhǔn)的概念分層而產(chǎn)生不同結(jié)果。將決策對轉(zhuǎn)換成決策信息表如表1 所示。

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

4 結(jié)束語

移動(dòng)環(huán)境下，用戶的興趣和選擇是實(shí)時(shí)的、動(dòng)態(tài)的、情景敏感的[15]，針對當(dāng)前移動(dòng)用戶序列行為挖掘的情景敏感性問題，本文提出一種對用戶序列行為進(jìn)行情景約束以及一種將約束后的用戶序列行為轉(zhuǎn)化成可用粗糙集屬性約簡方法進(jìn)行序列行為模式挖掘的決策表方法。在此基礎(chǔ)上，可以對基于情景敏感的用戶序列行為進(jìn)行挖掘，對基于情境敏感的用戶興趣建模和序列個(gè)性化推薦展開進(jìn)一步研究。

[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] 孟祥武，王凡，史艷翠，等.移動(dòng)用戶需求獲取技術(shù)及其應(yīng)用[J].軟件學(xué)報(bào)，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] 王立才，孟祥武，張玉潔.上下文感知推薦系統(tǒng)[J].軟件學(xué)報(bào)，2012，23（1）：1-20.

[7] 李蕊，李仁發(fā).上下文感知計(jì)算及系統(tǒng)框架綜述[J].計(jì)算機(jī)研究與發(fā)展，2007，44（2）：269-276.

[8] 曹懷虎，朱建明，潘耘，等.情景感知的P2P 移動(dòng)社交網(wǎng)絡(luò)構(gòu)造及發(fā)現(xiàn)算法[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（6）：1223-1233.

[9] 王虎，丁世飛.序列模式挖掘研究與發(fā)展[J].計(jì)算機(jī)科學(xué)，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] 夏英，孫沖武.基于時(shí)空序列模式匹配的興趣點(diǎn)推薦方法[J].重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，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ìn)差別矩陣的屬性約簡增量式更新算法[J].計(jì)算機(jī)學(xué)報(bào)，2007，30（5）：815-816.

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

[15] 史翠艷，孟祥武，張玉潔，等.一種上下文移動(dòng)用戶偏好自適應(yīng)學(xué)習(xí)方法[J].軟件學(xué)報(bào)，2012，23（10）：2533-2549.