面向簽到日志的用戶行為模式交互探索*

李叢敏, 李 杰, 張 康, 陶文源

1(天津大學 智能與計算學部,天津 300354)

2(The University of Texas at Dallas Computer Science Department, USA Texas 75080)

在很多領域中,用戶簽到日志是一種常見的數據類型,這類數據直接記錄了用戶對于某種設施的使用情況,常見的使用場景包括賓館入住記錄、網吧上網登記和在線系統的登錄日志等.從這類數據中挖掘出具有相似行為的用戶群體并分析該群體的行為模式,在信息服務、在線搜索服務、醫學診斷、網絡安全、商業營銷等方面具有非常重要的作用.

現有的方法常常基于統計對用戶時序行為進行分組,然而由于日志數據、行為模式、統計方法等方面的限制,已有的方法往往很難獲得準確且易于理解的結果,其挑戰主要體現在:

· 簽到日志的高維稀疏性:簽到日志往往時間跨度較長,用戶在不同時間點使用設施,形成了時間分布上的高維向量,使得行為特征在高維空間分布較為稀疏.因此,無論是傳統的聚類等機器學習算法、社區發現算法,還是推薦系統算法往往都不能直接得到高質量的具有相似行為模式的群體;

· 行為模式具有多樣性且與時間層次緊密相關:數據集中往往同時存在多個行為模式,且行為模式可能發生在任何特定的時間尺度上,例如白天、夜晚、假期、春季、下雨天等.多個行為模式交叉在一起,對其發現和理解帶來了較大的挑戰;

· 統計方法對參數和數據分布有要求:現有的分析方法往往需要事先設定某些先驗參數[1],或者要求數據符合某些特定的分布.這些參數設定和前提假設往往需要復雜的數據驗證,并且依賴分析人員對數據的理解和經驗.這也加大了群體行為模式發現的難度.

越來越多的研究人員采用可視分析方法分析群體模式,然而這些工作更多地只是展示統計分析的結果,缺少相似行為模式發現的過程.與其不同,本文設計了動態探索群體模式的可視分析方法,主要貢獻如下.

· 定義了一個動態迭代探索過程.該方法以一種“順藤摸瓜”的迭代方式將用戶逐步加入到群體中.本文引入了信息熵,動態地獲得具有較好行為區分度的時間子區間,并探索在此區間內具有相似行為特征的群體;

· 開發了一個支持以上迭代方法的可視分析工具.通過該工具,使用者可以交互地控制分析過程,直觀地理解和驗證所獲得的群體行為模式,并根據可視化反饋,實時主動地調整分析過程;

· 對群體在不同時間尺度上的統計和關聯進行分析,并減少由于數據偶然性帶來的噪聲,幫助使用者對群體行為模式進行理解.通過迭代前后群體行為模式的對比,驗證本文方法的有效性.

1 問題描述

1.1 數 據

簽到日志包含大量人員在較長時間上的行為記錄,其結構主要包括兩方面信息,即設施使用時間和用戶的基本信息.表1展示了某網吧3個用戶的上網記錄,其中,身份證號表示個人信息,上線和下線時間反映其在網吧上網的時間區間.大部分用戶只是固定或不固定地、有限度地使用設施,因此行為記錄在時間尺度上具有較為明顯的稀疏性.用戶簽到日志數據,時間的跨度很廣,并且絕大多數用戶使用某設施的起止時間不同,造成用戶使用設施時間沒有對齊,描述用戶行為的時間結構不統一,這給行為模式的探索造成了困難.

Table 1 User check-in logs in net bar表1 網吧用戶簽到日志

1.2 任 務

本文為數據分析人員提供了可視分析工具,幫助分析和理解簽到數據中存在的群體行為模式.如果某些用戶經常同時使用設施,則可認為這些用戶屬于一個群體,并具有相似的行為模式.本文的主要任務是找到頻繁在某些時間片上簽到的用戶群體.以網吧數據為例,有些用戶經常在周末上網,有些則經常在晚上或凌晨上網.了解這些群體行為,有助于獲取群體行為習慣,推斷其身份,有針對性地開展行業應用.同一用戶群體可能同時存在多種行為模式,這給模式的發現和理解造成了困難,因此,本文將這一探索過程分為3個不同層次的任務.

· T1:行為特征可視化.直觀地可視化數據中個體和群體的設施使用行為.該任務是后續分析的基礎,分析人員可以據此選擇具有特定行為特征的用戶,并交互探索與其具有相似行為的群體.所展示的行為特征應包括基本的行為時序特征,如周期性、趨勢、高頻使用階段、行為的統計指標以及不同用戶間的行為相似程度;

· T2:用戶群體發現.尋找頻繁共同使用設施的群體.由于簽到數據的稀疏性和用戶行為的偶然性,該過程往往受到數據噪聲的影響.方法應該提供必要的數據處理和過程控制,減少數據噪聲帶來的影響.探索過程應可視化并具有較好的交互能力,使分析人員實時全面地理解和調整分析過程.發現過程應該減少參數影響,參數能隨中間結果的變化而變化,發現過程也應是參數不斷優化的過程;

· T3:群體行為模式理解.在發現共同行為模式的基礎上,應進一步分析該模式在時間尺度上的分布特征.其目標是理解所發現模式的實際物理意義,輔助推斷群體的行為習慣和可能的身份,并據此開展實際行業應用.方法應該能從不同的時間尺度(如周、天、小時等)對群體行為特征進行理解,能將發現的群體與初始數據進行對比,驗證本文方法的有效性.

2 相關工作

簽到日志在很多領域都具有非常重要的分析應用價值.有些研究通過對簽到日志的分析,優化資源配置.Peng等人[2]通過社交媒體簽到日志,檢查出租車高需求區域,改善出租車資源分配.Li等人[3]通過行李托運日志,分析用戶行李登機行為和行李需求特征,優化機場資源配置.有些研究通過對用戶使用產品的行為和需求模式分析,改進產品設計.如 Leemans等人[4]通過分析用戶的軟件事件日志得到在現實生活中用戶操作軟件系統的過程,從而發現軟件存在的問題.Liu[5]和 Chen[6]等人通過分析社交媒體簽到日志,為用戶推薦其感興趣的主題.一些研究通過對用戶商店簽到日志的分析,得到用戶的消費模式,從而改善營銷策略.如Chen等人[7]通過分析顧客使用商場WiFi的簽到日志,分析時間對顧客選擇商場偏好的影響,從而基于時間為顧客推薦商場.Doi等人[8]通過商店簽到日志的分析,得到消費者的偏好,改進營銷方案.還有一些其他的研究在不同的領域中也具有重要的意義.例如,Yang等人[9]通過分析游客使用社交媒體的簽到日志,分析游客的旅游路線,幫助人們做出經濟有效的旅行決策.Liu等人[10]通過分析用戶使用出租車的日志,找到放置廣告牌的最佳位置.以上研究更偏重于對個人或整體簽到日志的統計分析,很少有通過分析用戶間相似度尋找分組行為模式的研究.

群體行為的發現往往根據個體之間的相似度,使用分組算法對數據分組.很多研究使用聚類的方法來尋找具有相似行為模式的分組.Frhan等人[11]提出了模式聚類和關聯聚類的方法來尋找用戶行為相似的群體.Lei等人[12]使用聚類方法尋找微博用戶的行為模式.這些方法往往對數據分布有要求且較依賴參數.各類社區發現算法也是經常采用的方法.Bron等人[13]用算法生成組,生成候選用戶集,刪除不符合派系定義的候選用戶,算法的終止條件是生成了一個完全連通的圖.Liu等人[14]提出了一種基于網絡連接強度的重疊社區發現算法,該算法從重要性最高的用戶逐步擴展,直到滿足終止條件.He等人[15]使用SimRank相似性度量和NMF模型發現復雜網絡中的社區.Zhou等人[16]使用基于主題感知特性的隱式關系和基于互動行為的顯示關系對動態社交用戶網絡模型進行擴展和完善,從而發現更為合理的社區.推薦系統是另一類典型的群體行為模式發現方法.Rohit等人[17]使用基于潛在語義索引的推薦系統算法來尋找相似類型的博客.Maake等人[18]利用選擇性驅動的推薦系統算法為用戶推薦需要的論文.Yi等人[19]分別使用基于圖形數據庫和基于深度學習的方法為用戶推薦同類型的電影.Hariadi[20]基于混合屬性和個性的推薦系統算法為用戶提供相關的書籍.這些分組算法往往使用用戶間的相似度分組,但相似度通常存在噪聲和稀疏數據,且相似度的度量方法也會影響分組結果,因此這些算法的準確率不高.不僅如此,預設的參數也無法根據中間結果實時調整.

越來越多的研究采用可視分析探索用戶行為模式.Liu等人[10]通過熱圖表示用戶在空間的行為模式.Saas等人[21]將熱圖、樹狀圖、折線圖結合,分析游戲玩家的行為模式.Krueger等人[22]使用圍巾圖和時空立方體圖揭示訪問者序列模式.Li等人[23]使用柱狀圖、平行坐標圖等視圖發現犯罪數據的多個屬性模式.Zhang等人[24]將熱圖和餅圖結合,展示在公共交通系統中用戶的流動模式.Li[25]通過詞云、時間流、地圖等視圖尋找文本時空模式.Zhao等人[26]利用邊緣重疊度概念,減少MSV的視覺混亂,同時保留網絡通信的時變特征,分析動態網絡的變化模式.Zhou等人[27]基于地圖發現移動學習者的行為模式.Chen[28]通過詞云、平行坐標圖來分析社交媒體中重大事件,將分析關聯模式,將模式形成故事.Wei等人[29]通過自組織映射將網絡點擊流投影到二維區域,研究用戶瀏覽網頁模式.Zhao等人[30]通過多維可視評估,使用模糊聚類尋找群體行為模式.Li等人[31,32]分別通過地圖、散點圖等多視圖協同尋找共現模式和氣象變化模式.這些研究更多是對分析結果的展示,用戶無法直觀了解探索過程.

綜上所述,簽到日志的研究偏重于統計分析,鮮有根據用戶相似度尋找群體行為模式的研究.而關于分組算法的研究大多因數據的稀疏性,分組結果的準確率不高.同時,關于行為模式的可視化研究大多是對分析結果的展示,使用者無法了解探索分析過程.為了解決以上問題,本文使用動態子空間策略迭代探索具有相似行為模式的群體,并通過可視化工具使用戶可以實時地控制探索過程,從而直觀地理解和驗證所獲得的群體行為模式.

3 分析流程

根據數據特征和任務,本文設計了一個發現群體的迭代探索方法和一個支持迭代過程的可視分析工具.如圖1,本文輸入簽到數據,經過迭代和可視分析處理,輸出找到的群體和群體行為模式.

分析流程分為如下4部分.

(1) 數據預處理

簽到日志是用戶使用設施的記錄,不同用戶使用設施的時間各不相同并且數據量很大,這給群體的尋找帶來了困難.為了解決該困難,本文對數據進行預處理,將原始記錄處理為時間對齊,結構統一地用于描述用戶行為的特征向量,具體方法如下.

本文把每個用戶的簽到時間對應一個長度統一的離散化的簽到時間片集合.首先,本文把簽到時間劃分成m個連續的時間片序列T=(t1,t2,t3,...,tm).為了便于計算,時間片采用固定長度,其時間跨度可以根據分析目標進行靈活設定,時間跨度越小,會得到越精確的時間片序列,但是時間片序列也會變長、更加稀疏,同時也增大計算復雜度.較長的跨度可能產生錯誤的行為記錄,因此,使用者要根據數據特點靈活設定時間跨度.本文為每個用戶生成一個簽到時間片集合,用戶i在時間片序列T上對應一個簽到時間片集合ci=(ci1,ci2,ci3,...,cim).如果用戶i在時間片tj內使用某設施,則向量對應位置的cij=1;否則,cij=0.例如,本文將用戶上網數據的時間跨度設為30分鐘,因為根據統計大部分的有效數據,用戶連續上網時間都超過了30分鐘.如果用戶a在8:40～10:10和12:00～13:00上網,那么生成的簽到時間片集合如圖2中的ca所示.

本文根據簽到時間片集合計算兩兩用戶之間的行為相似性,從而判斷兩個用戶是否屬于一個群體.行為相似性是后續迭代探索的計算依據.如果兩個用戶使用設施重合度較高,即簽到時間片集合中“1”的重合度較高,則認為這兩個用戶具有很相似的行為.令ca和cb分別為用戶a和b的簽到時間片集合,a和b之間的行為相似度定義見公式(1):

以圖2為例,ca和cb分別為a和b的簽到時間片集合,則ca∩cb=5,ca∪cb=9,sab=0.556.

為了提高后續的分析效率,在數據初始化時,可以依據用戶在全部時間區間內的行為特征進行初始分組.初始分組可使用現有的聚類算法.聚類算法需設置較小的簇個數,以保證具有相似行為特征的用戶不被分開,本文將初始化分組得到的組稱為初始組,如圖3中(a6)有3個初始組.后續分析可以針對初始化得到的其中一個組開展.這一過程是可選的,當數據量不大或用戶行為不存在明顯差異無法得到清晰的簇時,可不進行初始化分組.

(2) 行為特征可視化

行為特征可視化的目的是直觀地向使用者展示初始組的行為特征,為行為模式探索提供初始的依據.本文提供了多種可視化設計輔助使用者選擇初始用戶,可視化設計包含行為相似性、統計指標、行為分布這3部分.

首先,使用者通過用戶行為相似性的可視化設計,即投影分布,觀察用戶間的相對關系,結合投影點的大小(點的大小映射某個統計屬性)選擇一個初始用戶;第二,當使用者選擇某個初始用戶后,系統可以在底部統計屬性視圖中展示其多個量化指標,如 Betweenness,Closeness等;第三,用戶關系視圖中展示初始組和初始用戶的行為分布.使用者可根據行為特征動態地更換初始用戶.在以上多種方式中,行為分布對于初始點選擇非常重要.一個好的初始個體,應在時間尺度上具有較為集中的行為分布,通過觀察行為特征視圖可以了解其在不同時間尺度上的分布情況,有助于選出具有潛在行為模式的群體.依據這些行為特點,使用者可快速了解用戶之間的相似程度,用戶個體在初始組中的地位和使用設施的時間分布特征,初始組和初始用戶在不同時間尺度的行為分布情況等信息.使用者將根據這些信息,在下一階段選擇合適的用戶作為群體的初始用戶.

(3) 用戶群體發現

尋找具有相似行為模式的群體本質上是用戶聚類的過程.由于時間片集合分布稀疏以及用戶行為的偶然性,導致很多時間片對于群體的發現是沒有作用的,因此,本文選擇一種子空間探索的方法,挑選出時間片子集來取代整個時間片集合進行探索.子空間就是時間片子集,它相對于原數據來說,維度降低了很多,稀疏性也有了很大的改善.該方法解決了上文中提出的簽到日志數據的高維稀疏性問題.在子空間中,群體使用設施的行為較為一致.不僅如此,本文設計了一個迭代探索過程,每一次迭代都會依據當前群體中用戶行為數據的分布,動態改變用于探索的子空間.同時,迭代過程還把在子空間上與群體行為相似度較大的其他用戶加入群體,從而保證新生成的群體使用設施的時間也能夠集中在子空間上.每個時間片可看做一個離散隨機變量,本文使用信息熵度量群體在不同時間片上使用設施的一致性,熵越大,表示群體在該時間片上的簽到行為越一致,可以認為在該時間片上更有可能存在特定的簽到行為模式.熵的計算如下:

其中,P(uj)表示用戶uj在時間片ti上使用某設施的概率,n表示當前群體用戶的個數.eti的值越大,表示群體在ti時間片共同簽到行為越一致.本方法會為熵設置閾值et,只有熵大于et的時間片才會進入下一次迭代,以確保群體行為在時間片上具有較高的一致性.迭代過程見算法1,迭代探索的具體流程如圖1的“用戶群體發現”所示.

算法1.迭代過程算法.

U為初始組集合,U′為新生成的群體集合,a為初始用戶,T為總的時間片集合,T′為根據熵選擇的時間片子空間集合,

sij為用戶i和用戶j之間的行為相似度,ei為在時間片i上的熵,st為行為相似度的閾值,et為熵的閾值.

在迭代開始之前,使用者選擇閾值st和et,此時初始狀態僅一個用戶,無群體模式,為了不失一般性,此時不計算熵,而是在全部時間片上尋找與其具有相似行為的用戶加入U′,進行群體的初始化,在后續迭代過程中計算熵,并通過熵選擇時間片.迭代開始后,本方法首先使用當前U′中的用戶計算所有時間片T的熵,選取大于et的時間片,得到子空間T′?T,然后計算U′和U中兩兩用戶在T′上的相似度,選擇U中相似度大于st的用戶加入到U′中.如果沒有新用戶加入到U′,則停止迭代,得到群體U′;否則,按以上步驟執行下一次迭代.迭代過程也可由使用者控制結束.

(4) 行為模式理解

完成探索之后,本文幫助使用者理解群體的行為模式.群體行為模式中經常存在多個行為模式交叉的問題,為了解決該問題,本文將群體使用設施的時間按照不同的時間尺度進行劃分,如“小時”、“周”、“日”等,之后,對不同的時間尺度采用同一個分析框架,分別對不同時間區間上的用戶進行統計,并分析這些區間上用戶的關聯程度,幫助使用者分析群體在不同時間尺度上的行為模式.

在理解群體行為模式時,為了便于描述不同用戶在不同時間區間上的簽到分布,本文統計用戶在不同時間區間上的簽到比例(用戶在某時間區間上使用設施的時長占該用戶使用設施總時長的百分比),不同用戶會有不同的行為偏好.為了描述所找到的群體的共同的行為偏好,本文使用弦圖描述群體在哪些時間區間同時簽到以及在這些區間上簽到的相同的用戶個數.例如,群體中只包含兩個用戶,假設用戶在周一～周三的簽到比例為50%,49%,1%,此時在弦圖中,周一～周三這3個時間區間上,兩兩都有連線且連線的粗度和顏色都是一樣的.明顯地,該用戶絕大部分時間在周一和周二上網,在周三上網具有很強偶然性,因此周三對理解行為模式的理解不僅沒有幫助,反而會干擾使用者的理解.為了減少噪音和突出重要的組群內的模式,本文設置了“25%”,“50%”,“75%”這3個閾值,以選出群體內前x%高的分布的時間區間進行繪圖.本文使用兩兩時間區間上的相同用戶個數來表示用戶在時間區間上的關聯程度,通過相同用戶的絕對個數和相對個數來表示不同時間區間上用戶的絕對和相對關系.絕對個數為兩兩時間區間上相同用戶的個數,相對個數為相同用戶的個數與兩時間區間上用戶并集元素個數的比值.最后,本文通過弦圖將統計結果和關聯程度可視化,如圖3(b)所示.

4 可視設計

為了讓使用者實時全面地了解并靈活地控制行為模式探索過程,我們開發了一種可視分析工具.本文將從分析流程出發,分別介紹6個與探索流程相關的視圖.

(1) 統計屬性視圖

統計屬性視圖用來幫助使用者了解初始組中的個體在統計屬性上的特征,如圖 3(d)所示.這些統計特征包括用戶個體在初始組內的作用和地位以及使用某設施時間的分布特征.使用者可以通過該視圖了解每個用戶在統計屬性上的特征,并將其作為選擇迭代探索的初始用戶的依據之一(T1).

本文使用了9個統計屬性來描述個體的特征,如圖3(d)所示.這些屬性包括:

1) Core指點度中心性(degree centrality),它描述了個體位于組中“核心”位置的程度;

2) Betweenness是中介中心性(betweenness centrality),是指個體在組中起到的“橋梁”或“中介”作用的程度,描述了該個體與其他個體交往的能力;

3) Closeness表示接近中心性(closeness centrality),反映了組中個體與其他個體之間的接近程度;

4) Normality描述個體使用設施的時間符合正態分布的程度;

5) Uniformity反映了個體使用設施的時間分布的穩定程度;

6) Outliers用來衡量時間分布中離群值的個數;

7) Unique是個體使用設施的次數在時間分布上唯一值的個數,表示數據的唯一性;

8) Age 為初始組用戶年齡分布,共有“<20”,“20～30”,“30～40”,“>40”這 4 個年齡段,在圖 3(d)中,表示這 4個年齡段的顏色依次變深;

9) Sex為初始組用戶的性別分布,在圖3(d)中,表示Male的顏色比表示Female顏色淺.

本文通過一個熱力圖表格來表示各個用戶屬性值特征,表格的每一列代表一個用戶,從上到下依次是各個屬性的值對應的矩形,矩形的顏色越深,表示對應屬性值越大.最左側標有屬性名的按鈕控制用戶的順序,點擊其中一個按鈕,可視化工具會按照對應屬性值的大小對用戶排序.在迭代過程中,本文使用對應迭代次數顏色的矩形框來表示加入群體P′的用戶.

(2) 用戶關系視圖

用戶關系視圖是本文的主視圖,用來幫助使用者了解初始組用戶的行為相似性(T1)以及迭代探索的步驟(T2),如圖3(e)所示.在每次迭代中,群體的變化、某個用戶是在第幾次迭代被加入群體的以及在迭代過程中群體的某個用戶與其他用戶的關系等信息都可從該視圖中得到.

本文根據預處理階段得到的用戶簽到時間片集合對初始組數據降維,將結果投影到二維的用戶關系視圖中.降維算法[33]有很多種,比如線性方法PCA,LDA、非線性方法MDS,T-SNE等.其中,T-SNE[34]又稱為t分布隨機領域嵌入算法,它是用于探索高維數據的非線性維數降低算法.它將多維數據映射到適合人類觀察的兩個或多個維度,主要是保證高維空間中相似的數據點在低維空間中的距離盡量較近.MDS[35]同樣用于高維非線性降維,但它更適合用于沒有特征矩陣只有相似矩陣的情況.由于簽到時間片集合是特征矩陣同時又是高維數據,同時,本文希望降維之后在高維中相似的點在低維空間也能保持相對關系,綜合以上考慮,本文選擇 T-SNE算法.用戶關系視圖中,每個點代表初始組中的一個用戶,點之間的相對位置表示用戶行為相似性.其中,碰撞算法[36]用來減少點的重疊.視圖中點的大小由控制面板 Attribute的值來確定,若復選框中值為 Core,那么用戶的 Core值越大,對應到視圖中的點越大.

在迭代開始之前,使用者在控制面板視圖 3(a)中選擇相似度的閾值st和熵的閾值et,然后根據用戶行為相似性,圖3(b)中用戶行為分布以及圖3(d)中統計屬性上的特征,進行初始用戶的選擇.迭代過程中,如果某個用戶已被加入到群體U′,那么該用戶對應點的顏色變淺,該用戶周圍也會生出花瓣,如圖3(e)所示.圖中花瓣個數表示該用戶與群體中其他用戶相似度大于閾值st的用戶個數,花瓣的顏色用來表示迭代的次數,顏色越深,迭代次數越大.不同于其他分組算法,本文的方法將使用者考慮其中,通過交互控制迭代進度,進入下一次迭代或返回上一次迭代,或終止迭代.使用者還可以在群體中加入或剔除某個用戶.

(3) 子空間選擇視圖

子空間選擇視圖是對子空間中時間片在不同時間尺度上的統計,用于了解迭代過程中子空間的變化(T2),如圖3(c)所示.該視圖的前4行是對子空間T′在“月”、“周”、“日”、“小時”的統計,顏色深淺代表時間片的個數.該視圖的最后一行是對時間片分布的展示,該行被分為m個小矩形R=(r1,r2,r3,...,rm),對應在數據預處理時m個連續的時間片T=(t1,t2,t3,...,tm),如果某個時間片的熵大于閾值,即ei>et,那么ri被染上色;否則,ri為無色.

(4) 組信息視圖

(5) 行為特征視圖

行為特征視圖用于對初始組和個體行為分布的描述、群體行為模式的理解和探索結果的驗證(T3),如圖3(b),該視圖對不同時間尺度上行為分布和關聯進行統計分析.在迭代探索開始之前,本文需選擇初始用戶,該視圖對初始組和初始用戶在不同時間尺度上的行為分布進行統計分析,結合圖3(d)和圖3(e)中對統計屬性和行為相似性的可視化,幫助使用者選擇初始用戶.在迭代過程中,該視圖會隨著群體的變化而變化.使用者可結合用戶關系視圖,調整迭代過程中群體中的用戶.使用者分析群體行為的分布和關聯,得到群體的行為模式.使用者在該視圖中對初始組、群體、剩下組(初始組用戶減去群體用戶得到的組)的行為模式進行對比,從而驗證本文方法的正確性.同時,使用者還可以通過該視圖和子空間選擇視圖中時間的對應關系,驗證動態子空間策略的正確性.

在行為特征視圖中,使用者在圖3(b1)Evaluation復選框中的“日”、“周”、“小時”這3個時間尺度上選擇以后,視圖會展示對應時間尺度的關系圖.圖 3(b2)的第2個復選框Percent是對重要用戶的百分比進行篩選,視圖對篩選結果進行統計.圖 3(b3)中,Threshold用來控制連線的多少,弦圖中的連線會隨著滑動條值的增大去掉顏色比較淺的線(也就是相對用戶個數比較少的連線).行為特征視圖主要由弦圖構成,圖3(b)共有3個弦圖,從上到下依次初始組關系圖、群體關系圖、剩下組關系圖.群體關系圖和剩下組關系圖都會隨著迭代過程不斷變化.弦圖的弧長代表在對應時間上用戶的個數.連接弧的弦具有顏色和粗細兩個特征,它們分別代表兩個弧中相同用戶個數的相對值和絕對值.顏色越深,表示兩個弧相同用戶的相對值越大;線越粗,表示絕對值越大.

(6) 控制面板

控制面板視圖包含使用者可控的所有變量,用于變量選取.使用者對該視圖的操作貫穿了本文的大部分工作,包含分組算法選取、初始組集合表示、初始組選取、用戶關系視圖中點大小的表示、閾值選取和新群體的表示.使用者可在圖3(a1)中選擇分組算法(kmeans,spectral clustering,decision tree等)生成初始分組,并在Group Number中選擇生成初始組的個數.若數據量較少,初始數據也可不進行分組.圖 3(a3)中,Attribute復選框包含“Core”“Betweenness”“Closeness”“Normality”“Uniformity”“Outliers”“Unique”這 7 個統計屬性,使用者可按需選擇一個屬性,用戶關系視圖中點的大小將映射該屬性值的大小.圖3(a4)和3(a5)中的“Similarity”和“Entropy”兩個滑動條控制迭代過程中的兩個閾值,分別為時間行為相似度的閾值st和熵的閾值et.只有大于st的用戶和大于et的時間片才會進入下一次迭代.使用者若希望得到關系緊密的群體,可把閾值調大;反之,可調小.在該視圖最下方的柱狀圖是組的列表,每個小矩形代表一個組,矩形的長代表組中用戶的數量.圖3(a6)記錄了全體用戶的整體分組情況,其狀態會隨著探索結束后產生的新群體發生變化.圖 3(a6)展示了初始狀態(全體個體被分為 3個組),迭代結束之后,產生新的狀態(包含178個用戶的組分為兩個分別包含168個用戶和10個用戶的新組).

5 案例分析

本節利用真實的網吧上網數據,分別從群體發現和群體行為理解兩個方法驗證方法的有效性.

5.1 群體發現

本文首先對上網數據進行初始化.在數據離散化時,本案例將時間跨度設為 30分鐘,因為根據統計,大部分用戶的連續上網時間都超過了30分鐘.由于上網記錄的數據量較大,本案例根據數據量將數據分成3個組,生成初始組的用戶個數分別為85,37,178.本案例通過3個組中用戶個數的比較,得出用戶個數為178的組數據量最大,分組結果可能最為粗糙,因此,本案例選擇初始用戶個數為178的初始組進行迭代探索.

首先,本文根據用戶的行為相似性、統計指標以及行為分布為初始組選擇初始個體(T1).因為在初始組中重要的用戶是該組的核心,與很多用戶都有關聯,同時,迭代方法是通過用戶之間的相似度將用戶加入到群體的,所以本案例使用Core值來映射用戶關系視圖中點的大小.如圖4(b)所示,被圓形框標記出來的點較大,表示該點對應的用戶在初始組中比較重要,并且該點位于用戶關系視圖的中心,周圍環繞著很多的用戶,表示與其行為相似的用戶有很多.如圖 5所示,被矩形框出的用戶對應圖 4中被圓形框標記的點,該點在初始組中“Core”“Betweenness”“Closeness”的值較大,表示在初始組中的“重要性”“橋梁”作用、與其他點的接近程度方面的值較大.并且該點使用設施在時間上的分布較為集中,離群值較少.因此,本案例選擇該點作為初始個體.

然后,本文進行迭代探索(T2).如圖 4所示,已加入群體的點用圓形框標記,群體中點相似度大于閾值的點用方形框標記,它們會在下一次迭代中加入群體.如圖4(b)所示,與初始點相似度大于閾值的點有4個,在圖4(c)中,這4個點被加入群體,此時,初始點對應的點周圍有4個花瓣,表示該點與剛進入群體的點相似度均較大;剛進入群體的4個點都只有一個花瓣,表示這些點只與初始點相似度較大,4個點之間相似度不大.通過圖4(b)～圖4(d)這3次迭代后,已無點被加入群體.由于子空間被不斷改變,群體中的點可能在新的子空間中,與其他點的相似度均小于閾值,即無花瓣的顏色較淺的點,如圖4(d)中被箭頭標記的點,本文將這些點從群體中去除.如圖4(d)所示,最終本文得到了一個用戶數為10的群體.

得到具有相似行為模式的群體之后,本案例通過行為特征視圖對群體行為模式進行理解(T3).用戶上網的偶然性給群體行為模式的理解帶來了困難,因此,本案例對在不同時間尺度上的用戶進行篩選,通過比較群體在“25%”“50%”和“75%”這 3個閾值上弦圖的效果之后,我們發現閾值為“25%”時,弦圖中弧的分布更為清晰集中,并且細小的連線和顏色較淺連線也減少了很多.這表示在閾值為“25%”時,用戶上網模式更為明顯,并且不同時間上的關聯也較為緊密,因此,本案例使用閾值為“25%”時的行為特征視圖對群體行為模式進行理解.

圖6是對初始組、群體和剩下組在“小時”“天”“周”上行為分布的展示.圖6(a)中,在“小時”上,群體中大部分用戶在16～21時上網,且連線呈完全圖,因此群體明顯集中在16～21時上網.如圖6(b)所示,在“日”上,與其他兩組相比,群體在時間分布的比重上有了很大變化,大部分用戶分布在1～4日、12日、17日,且群體在這些時間的比重明顯高于其他時間.初始組和剩下組的時間分布差別不大,時間之間的關聯比較混亂,沒有明顯的規律.在“周”上,群體在周三、周四、周末上網的比重較大.周末有很多用戶一起上網,周三、周四也有較多用戶一起上網.群體中,上網的人的籍貫主要分布在河北、浙江,性別均為男性,并且年齡全部在20歲～30歲之間,如圖3(f).綜上所述:群體成員主要在月初(1～4日)和月中(12日、17日),周三、周四、周末,16～21時上網.

群體的行為模式可得出如下結論:用戶主要在周三、周四、周末和傍晚、晚上上網,并且沒有熬夜.同時,我們根據基本屬性分布可知,群體均為男性且年齡在20歲～30歲之間,因此該群體可能為課余時間較多大學生或上班時間較為松散的上班族.對比初始組、群體和剩下組中用戶在時間上的分布,我們可以明顯看到群體中的用戶上網時間更集中,并且關聯也更緊密清晰,這也驗證了本文方法的正確性.

5.2 行為特征理解

本案例通過行為特征視圖中不同時間尺度上人數的統計和關聯,以及子空間選擇視圖中時間片在不同時間尺度的分布,對群體行為特征進行進一步的理解(T3).本案例對網吧初始分組的另一個組進行迭代探索,該組有85個用戶,探索得到的群體中有12個用戶.該組群體發現流程與第5.1節大致相同,因此本案例不再詳細描述.圖 7(a)是群體分別在時間尺度為“月”“小時”“日”“周”上的行為特征圖.圖 7(b)是群體的子空間在“月”“周”“日”“小時”上的統計分布.

圖7(a1)為群體在“月”上的行為特征視圖.在圖7(a1)中,11月上網的用戶明顯多于12月.對應圖7(b1)中,時間片的分布也是如此,兩圖時間分布相對應.圖 7(a2)中,群體中大部分用戶在周末上網,且上網人數相差不大,說明群體中大部分用戶在周末一起上網.對應圖7(b2)中時間片的分布,即周末分布較多,群體在周末一起上網的概率較大.圖 7(a3)為群體在“日”上的行為特征視圖,群體中大部分用戶3日、4日、9日、10日、14日、18日～20日上網,在4日、10日、19日分布更多,連線更粗且構成完全圖,說明群體中有更多用戶在4日、10日、19日一起上網,與圖7(b3)中的時間分布大致相對應.但時間片在9日分布最多,而圖7(a3)中,9日的用戶分布卻不是最多的.如圖7(a4),在“時”上,群體上網的人數大多分布在17時～21時,并且兩兩之間都有連線,構成一個完全圖,表明群體該時間上網的用戶有一部分是相同的,即群體中有一部分用戶經常在17時～21時一起上網.18～20時之間的連線明顯比其他連線粗,表明在18時～20時,群體中有更多用戶一起上網.在圖7(b4)中,17時～21時的時間片分布較多,說明群體在該時間段一起上網的概率較大,與圖 7(a4)中部分用戶一起上網的時間相對應.18時～20時的時間片分布更多,也與圖7(a4)對應.

根據上述分析,群體在不同時間尺度上網規律如下:在“小時”上,群體經常在17時～21時上網,并且上網時間更集中在18時～20時;在“日”上,群體在月初(3日、4日、9日)和月中(14日、18日～20日)上網,且上網時間更加集中在4日、10日、19日;在“周”上,群體集中周末上網.根據群體上網模式,我們發現:群體通常在周末和晚上上網,并且可能在17日～21時連續上網,說明群體可能在工作日有工作要做,因此我們推測該群體的身份為上班族.

圖 7(a)和圖 7(b)統計中,兩圖在時間上基本能夠相互對應;同時,由于圖 7(b)只是對子空間的統計,而圖 7(a)是對全部時間片集合的統計,并且群體只是在子空間的時間片上一起上網的概率較大,一起上網不是必然事件,因此,兩視圖不能完全對應.總體來說,兩圖時間上基本相互對應,間接驗證了本文動態子空間策略的正確性.

6 專家意見

為了對本文方法的可用性進行評估,我們進行了一個實驗.我們邀請了15位參與者(5位女性、10位男性,年齡在24歲～49歲),為了避免模糊指代,本文根據研究領域對參與者編號.參與者包含2位來自數據可視化領域的教授(編號V1,V2),5位來自數據可視化方向的研究生(編號V3～V7),1位來自人工智能領域的副教授(編號A1),3位來自人機交互領域的專家(編號H1～H3),3位來自大數據領域的研究員(編號D1～D3),1位來自虛擬現實研究領域的副教授(編號R1).他們之前均未使用過本文方法.我們首先向參與者介紹本文提出的問題和解決方法,然后參與者使用可視化工具尋找上網數據的群體行為模式.最后,我們對參與者進行訪談.

大多數參與者認為本文可視界面美觀,操作流程簡單流暢,視圖含義易于理解,有較強的可用性.他們指出:多視圖協同展示迭代過程,可幫助他們多方位實時了解數據信息.9個參與者(V1,V2,V4,V6,H2,H3,D1,D3,R1)指出:用戶關系視圖可幫助他們利用位置判斷用戶行為相似性,并在本文方法的理解上起到了關鍵作用.7個專家(V1,V3,V7,H1,D2,D3,R1)認為:本文的行為特征視圖,簡單易懂,不僅可幫助他們了解在迭代過程中群體模式的變化,而且 3個弦圖的對比,可明顯地看出群體與其他兩組的區別,從而驗證本文方法的正確性.同時,他們還指出:行為特征視圖使用弦圖,直觀展示了不同時間上的分布和關聯,能容易地找到具體細致的行為模式.V1認為:用戶關系視圖中花瓣的設計新穎美觀,點會隨著迭代過程改變顏色,添加花瓣易引起注意,使復雜的迭代過程變得易于理解.V2指出:若數據量很大,聚類算法分組后每組用戶數仍很多,由于可視界面可容納的用戶數有限,會出現點重疊等問題.經測試,本方法可容納數千用戶,滿足大部分應用場景的需要.如果數據集包含了更多的樣本,可通過提升初始聚類的個數,以減少單個初始簇中用戶個數.

大多數參與者認為:信息熵用來度量活動的穩定性,在很多領域有應用,如檢測網絡異常、圖像處理等,本文將熵用于檢測群體在某時間上使用設施的一致性是可取的.他們還指出:動態子空間策略相當于在中間過程中改變參數,是對分組算法的創新.D1認為:動態子空間策略雖新穎,可以改變過程中的參數,但對于該策略的驗證不夠直接,應設計進一步的驗證.D2指出:本文所提方法需要構建初始聚類,以縮小探索空間和提高后期迭代分析的效率,并提供了多個候選聚類算法,但不同的聚類算法可能產生不同的聚類結果.本文提供了多個候選聚類算法,并采用歐式距離作為用戶相似度指標.雖然不同的聚類算法和距離指標可能產生不同的結果,但由于初始聚類只是對用戶進行粗略的分組,且聚類算法設置的簇個數較小,具有相似行為特征的用戶被分到不同簇的可能性較小,因此,使用不同的聚類算法對后續具有相同行為模式群體的探索影響不大.此外,這一過程是可選的,當數據量不大或用戶行為不存在明顯的差異無法得到清晰的簇時,可不進行初始化分組.

H1認為:本文交互操作方便有效,他們可靈活探索群體,可依需選擇閾值,從而控制群體用戶的個數和相似程度,通過交互控制迭代探索過程;同時,可根據自己的判斷和需要從群體中增刪用戶.這些交互設計新穎特別,將人的智慧融入其中.4個參與者(V3,V4,H1,H2)認為:他們雖可通過鼠標交互控制迭代過程,但鼠標點擊敏感,一次無意識的點擊就會改變迭代進程,如果本文使用其他的交互方式可能會更好.因為本文的迭代方法是可逆的,因此該問題可通過另一交互操作返回上一迭代進程來解決.6個參與者(V5～V7,H2,H3,R1)認為:他們雖可通過交互控制探索進程,但交互操作太多,不易記憶,且未在探索過程中用到全部交互操作.H3認為:本文案例中,時間跨度是兩個月,但使用者可能只對某時間段比較感興趣,因此,若本文可動態選擇時間段,這將會有更好的體驗.

綜上所述,大多數參與者對本文方法表示了欣賞,一些參與者對本文方法提出了中肯的建議.我們會根據這些建議,在未來的工作中找到合理的方案來調整本文的設計.

7 討 論

本節對方法中潛在的問題進行分析,并提供可能的解決方法.

· 數據噪聲.若某用戶長期占用設施,則其日志于行為模式發現是無用的,迭代探索時,很多用戶會因該用戶加入群體,使其他用戶與該用戶關聯很強,其他用戶之間的關聯很弱.但本文會對用戶間關系可視化,如圖 3(e),若某個點有很多花瓣,而群體內其他點僅一個花瓣,表明其他用戶只與該用戶有關,可通過交互去掉該用戶;

· 可視重疊.本文通過降維,將數據映射到用戶關系視圖中,但映射會造成一些相似點的重疊.為了減少重疊,本文使用碰撞算法調整點的相對位置,但位置變化會對用戶間關系的判斷造成一定的影響,且用戶數越多影響越大.本文考慮用氣泡代替某些區域,在需要時再將該區域放大,當區域變大時,用戶間的重疊就會相對減少;

· 可視化空間有限.由于可視化空間有限,可視化工具不能無限制地容納數據,數據量越大,視圖中點重疊問題越嚴重,算法調整后,點的位置變化越大.本文可增加聚類算法設置的簇個數,從而減少初始組的數據量;

· 閾值選擇的主觀性.迭代開始之前,使用者要選擇熵和相似度的閾值,由使用者主觀決定,因此有兩個極限情況:當閾值都選擇為0時,初始組的用戶都會進入群體,造成迭代探索失效;當閾值都為1時,群體中只包含最初選擇的一個用戶.由于迭代方法是可逆的,因此在遇到這兩種情況時,使用者可交互地回到最初狀態,調整閾值;

· 可擴展性.本文方法僅根據數據的時間屬性探索行為模式,并未結合空間等其他信息.若方法結合其他信息,可能會得到更加準確的群體;同時,也使行為模式更易于理解.因為本文數據均來自于一個網吧,因此本文僅使用了時間屬性.作者將來會分析簽到日志的時空模式,將時間先后順序和空間拓撲關系納入分析范疇.

8 總結與展望

本文設計了一個行為模式探索流程和一個可視分析工具,該流程使用動態迭代方法逐步將用戶加入群體,同時引入熵的概念,挑選時間子空間,逐步提升迭代效果.可視分析工具將迭代過程可視化,幫助使用者實時了解數據的變化.使用者根據這些變化將自身的判斷融合進迭代過程,通過交互對迭代過程進行調整,并對探索結果進行理解和驗證.最后,本文通過兩個案例分析以及專家意見驗證本文方法的可用性.在未來的工作中,我們將嘗試將不同的行為記錄結合在一起,通過不同方面的屬性對用戶進行分析,得到更為準確的群體.對于閾值的選取,我們將為使用者推薦更為合理的閾值作為參考.現在的工具通過弦圖向使用者描述用戶在時間上的分布,未來我們也將改進可視化工具,使行為模式更加易于理解.我們還將對動態子空間策略進行進一步的驗證.