馬滿福，張凱旋，李 勇，王常青，張 強

（1.西北師范大學 計算機科學與工程學院，蘭州 730070；2.甘肅省物聯(lián)網(wǎng)工程研究中心，蘭州 730070；3.中國互聯(lián)網(wǎng)絡信息中心互聯(lián)網(wǎng)基礎技術開放實驗室，北京 100190）

0 概述

由于生物遺傳和變異，自然界中存在大量性狀相同的物種，其在進化上或個體發(fā)育上因具有共同來源呈現(xiàn)出的相似性稱為同源性。這種同源性被廣泛應用于醫(yī)療健康、生物制藥和遺傳研究等諸多領域［1-2］，也為虛擬空間中在線用戶行為相似性研究提供了新思路。在虛擬空間中，不同用戶群體的行為特征通常存在不同程度的差異性［3-4］和相似性［5-6］。文獻［7］基于用戶主題感知和行為相似性分析動態(tài)用戶的相關性，指出同種社區(qū)類型的用戶具有強相關性，不同社區(qū)類型的用戶具有弱相關性。文獻［8］對16 個國家微博用戶行為的差異性和相似性進行研究，發(fā)現(xiàn)在人口少且凝聚力強的國家，用戶更關注微博的社會功能，而在人口較多的國家，用戶僅將微博作為新聞傳播平臺。

在證實虛擬空間中用戶行為特征具有差異性和相似性的基礎上，研究人員結合在線用戶的自身特征屬性給出部分應用場景［9-11］。文獻［12］提出一種基于同義詞組的用戶行為匯聚方法，利用匯聚結果對用戶進行性別預測，證明不同性別群體的興趣具有差異性，該方法能根據(jù)用戶性別進行有效的個性化系統(tǒng)推薦。文獻［13］通過調(diào)查歐洲60 000 多名工人的收入、教育程度、職業(yè)類型、自治水平、時間壓力和社會互動6 個維度的信息，提出雙變量有序概率計量經(jīng)濟模型以衡量互聯(lián)網(wǎng)對工人工作滿意度的影響，該研究對提高企業(yè)管理水平具有重要意義。

用戶點擊路徑反映出用戶在一段時間內(nèi)點擊的頁面和駐留時間［14］，分析用戶的點擊行為是研究用戶行為相似性的有效方法［15］。目前關于用戶行為相似性缺乏統(tǒng)一量化標準，對虛擬空間中在線同源用戶（根據(jù)同源理論，即點擊序列相似度超過30%的在線用戶）是否存在也未有驗證。此外，關于不同特征屬性對在線同源用戶行為相似性影響程度的研究也較少。因此，本文提出一種虛擬空間中在線同源用戶識別算法。從在線用戶行為數(shù)據(jù)集中提取點擊流數(shù)據(jù)，采用序列對齊方法處理點擊流數(shù)據(jù)以度量在線用戶的行為相似性。同時從數(shù)據(jù)集的人口統(tǒng)計信息中獲取在線用戶不同維度的特征屬性，研究各種特征屬性對在線同源用戶行為相似性的影響程度。

1 數(shù)據(jù)描述

用戶的在線行為主要通過點擊流數(shù)據(jù)來體現(xiàn)。本文采用中國互聯(lián)網(wǎng)信息中心（China Internet Network Information Center，CNNIC）提供的在線行為日志作為數(shù)據(jù)集（以下稱為CNNIC 數(shù)據(jù)集）進行研究，其中數(shù)據(jù)要素包含每個用戶的點擊路徑以及每個路徑對應的點擊時刻，點擊時刻采用標準時間格式記錄。CNNIC 數(shù)據(jù)集中某用戶的部分點擊流數(shù)據(jù)如表1 所示。

表1 原始點擊流數(shù)據(jù)Table 1 Raw click stream data

本文主要研究在線同源用戶的識別及特征屬性對其行為的影響程度，因此用戶特征屬性提取是關鍵。利用上述數(shù)據(jù)集中的人口統(tǒng)計信息提取用戶的年齡、社會階層、教育程度、性別、戶籍和收入水平6 個維度的特征屬性，部分用戶的人口統(tǒng)計信息如表2 所示。對每個特征屬性進一步分類，結果如表3 所示。

表2 部分用戶的人口統(tǒng)計信息Table 2 Demographic information of partial users

表3 特征屬性分類Table 3 Classification of feature attributes

2 研究方法

本文提出基于序列對齊的在線同源用戶識別（Sequence Alignment-based Online Homologous User Recognition，SA-OHUR）算法，其主要包括以下步驟：1）處理點擊行為數(shù)據(jù)；2）基于序列對齊思想計算在線用戶的行為相似度，并對其以相似度矩陣形式進行量化；3）根據(jù)行為相似度矩陣對用戶進行聚類驗證并識別在線同源用戶。此外，采用基于特征屬性的方法計算聚類結果的熵值和純度，并由此分析在線用戶特征屬性對其行為的影響程度。

2.1 在線同源用戶識別算法

在線用戶行為由一系列點擊路徑及其對應的點擊時刻構成，若將每個點擊路徑看作用戶點擊序列中一個字符串，則在點擊流數(shù)據(jù)中點擊路徑和對應路徑花費的時間可反映用戶的點擊行為，其用包含時間的字符串序列表示。例如，表1 中點擊流數(shù)據(jù)對應的該用戶點擊序列SF=｛（［'explorer.exe'］，08-01 20：29：57），（［'AliIM.exe'］，08-01 20：29：59），（［'SohuNews.exe'］，08-01 20：30：05，），（［'360SE.exe'］，08-01 20：30：23），（［'AliIM.exe'］，08-01 20：30：27），（［'360SE.exe'］，08-01 20：30：31），（［'AliIM.exe'］，08-01 20：30：59）｝。用戶行為相似度計算問題可轉換為編輯距離的問題。

2.1.1 序列對齊方法

序列對齊也稱編輯距離，主要通過對齊的方法來度量兩個序列的相似性［16］，其核心思想是利用一個序列轉換為另一個序列所花費的最小代價衡量兩個序列的相似性。序列Q和序列C之間的編輯距離和相似度分別定義為：

其中，dSAM（Q，C）為序列Q和序列C之間的編輯距離，SSAM（Q，C）為序列Q和序列C之間的相似度，D、I和R分別為轉換過程中刪除、插入和重排的次數(shù)，|Q|和|C|分別為序列Q和序列C的長度，ωd、ωi和μ分別為序列Q轉換為序列C過程中刪除、插入和重排操作的代價，且均為用戶給定的正常數(shù)。

2.1.2 數(shù)據(jù)預處理

本文基于序列對齊思想處理持續(xù)點擊流數(shù)據(jù)，具體步驟如下：

1）計算在線用戶在每個點擊路徑的持續(xù)時間，當前點擊路徑的持續(xù)時間即為當前點擊時刻與前一個點擊時刻之差，若某一個點擊路徑的持續(xù)時間超過30 min，則默認為用戶已經(jīng)下線，并將該點擊路徑及其持續(xù)時間從用戶點擊序列中去除，即會話時間間隔閾值定義為30 min［17］，處理后的持續(xù)點擊流數(shù)據(jù)如表4 所示。

表4 持續(xù)點擊流數(shù)據(jù)Table 4 Continuous click stream data

2）記錄用戶一個月內(nèi)的點擊路徑并計算其對應的持續(xù)時間，處理后的累計點擊流數(shù)據(jù)如表5 所示，用戶累計點擊序列SU=｛（［'explorer.exe'］，2），（［'AliIM.exe'］，24），（［'Sohu News.exe'］，18），（［'360SE.exe'］，32）｝。

表5 累計點擊流數(shù)據(jù)Table 5 Cumulative click stream data

2.1.3 在線用戶行為相似度算法

本文提出的SA-OHUR 算法是利用基于序列對齊的在線用戶行為相似度算法獲得用戶間相似度。由于該算法所用累計點擊序列的時間為累計時間，因此不考慮點擊路徑的先后順序，即轉換過程中重排操作代價為0。同時，若兩個用戶點擊路徑相同但對應路徑的累計時間不同，則可能造成點擊行為的差異，因此，增加兩個在線用戶點擊的相同路徑所對應累計時間差值的絕對值作為補償操作。設在線用戶Ui的點擊序列，…，（ain，Tin）｝，在線用戶Uj的點擊序列，（aj2，Tj2），…，（ajm，Tjm）｝。其中，（ai1，ai2，…，ain）與（aj1，aj2，…，ajm）分別為在線用戶Ui和Uj的點擊路徑集Ai和Aj。（Ti1，Ti2，…，Tin）與（Tj1，Tj2，…，Tjm）分別為在線用戶Ui和Uj的累計時間集Ti和Tj。在線用戶Ui和Uj基于序列對齊的編輯距離定義為：

其中，刪除和插入的代價分別為刪除和插入路徑所對應的累計時間，|Tip-Tjq|為補償操作的代價。

兩個用戶基于序列對齊的行為相似度計算公式為：

其中，當用戶點擊序列（點擊路徑及其對應的累計時間）完全相同時，用戶的相似度為1，當點擊序列完全不同時，相似度為0。在線用戶Ui和Uj的行為相似度計算如算法1 所示。

算法1基于序列對齊的用戶行為相似度算法

上述算法在用戶行為相似度計算過程中，主要利用用戶累計點擊流數(shù)據(jù)，且無需考慮點擊順序。在處理點擊流數(shù)據(jù)時，將點擊序列按照點擊路徑進行掃描，可得到用戶之間的行為相似度。由于在數(shù)據(jù)處理階段已去除冗余點擊路徑，因此與傳統(tǒng)的序列對齊算法相比，算法1 復雜度大幅降低。

2.1.4 基于行為相似度矩陣的層次聚類

SA-OHUR 算法最后一步是根據(jù)相似度矩陣對在線用戶進行聚類，以驗證在線同源用戶的存在。為更直觀地區(qū)分出用戶在線行為并識別同源用戶群，該算法采用基于行為相似度矩陣的層次聚類。由于傳統(tǒng)層次聚類HC 算法每進行一次簇間合并均需更新相似度矩陣，造成算法步驟重復，因此為避免該問題，SA-OHUR 算法將相似度矩陣中在線用戶之間相似度值和用戶編號采用數(shù)組的形式按照相似度值進行降序排列，根據(jù)相似度值在數(shù)組中的位置從大到小合并用戶，即引入優(yōu)先級隊列。

SA-OHUR 算法將在線用戶按照點擊行為劃分為不同類別，具體流程如下：1）初始化每個用戶作為單獨的簇；2）根據(jù)相似度矩陣將相似度值及其對應的用戶存入已定義的數(shù)組并按照降序排列；3）合并數(shù)組中第1 個相似度值，將最大相似度值對應的兩個用戶作為一個簇；4）從第二輪合并開始，若相似度值對應的兩個用戶均未合并到某個簇中，則將這兩個用戶合并為一個簇；若其中一個用戶已合并到另外一個簇中，則將另一個用戶也合并到該簇中；若兩個用戶分別合并到不同簇中，則將這兩個用戶所在的兩個簇合并；5）按順序取數(shù)組N的相似度值，且在每輪合并時簇的個數(shù)減少1；6）重復步驟4 和步驟5 直到生成K個簇。

給定在線用戶集U=｛u1，u2，…，un｝，將其根據(jù)點擊行為相似性劃分K個類C1，C2，…，CK，要求每個類別不能為空且類與類之間用戶不相同，主要步驟如算法2 所示。

算法2基于行為相似度矩陣的層次聚類算法

在算法2中，先對n個用戶的n×（n－1）/2個相似度進行快速降序排列，排序的時間復雜度為O（n2×lbn）［18］，再對n個用戶根據(jù)相似度進行聚類，該過程中聚類循環(huán)的時間復雜度為O（n）。因此，相較傳統(tǒng)層次聚類的時間復雜度O（n3），算法2 的時間復雜度降低為O（n2×lbn），算法運行效率更高。

SA-OHUR 算法的關鍵是計算簇間相似度和簇內(nèi)相似度，進而識別出在線同源用戶群。由于每個簇即為在線用戶集合，因此本文采用簇內(nèi)在線用戶與另一個簇內(nèi)在線用戶的平均相似度來表示。例如，給定聚類簇Ci和Cj，則兩個簇間的相似度定義為：

其中，Savg(Ci，Cj)為聚類簇Ci和Cj的相似度，x為屬于聚類簇Ci的用戶，z為屬于聚類簇Cj的用戶，為在線用戶x和z的行為相似度，|Ci|和|Cj|分別為聚類簇Ci和Cj的在線用戶個數(shù)。

2.2 基于特征屬性的熵值和純度算法

采用SA-OHUR 算法對在線用戶進行聚類時，為更好地將在線用戶特征屬性與其行為相似性進行結合，可用熵值和純度來衡量用戶特征屬性對其行為相似性的影響程度。熵值和純度可用來衡量某個指標的混亂度［19］，本文分別計算基于表3 中6 個不同特征屬性下點擊行為相似度聚類結果的熵值和純度，由此判定特征屬性對用戶行為相似性的影響程度。

給定n個在線用戶，根據(jù)在線用戶行為相似度將其分為K個簇，其中每個簇分別包含n1，n2，…，nK個用戶。假設某個特征屬性有M個類別，如教育程度分為初等教育水平、中等教育水平、高等教育水平3 個類別，則在該特征屬性下聚類簇i的熵值計算公式為：

在該特征屬性下聚類的整體熵值計算公式為：

在該特征屬性下聚類簇i的純度計算公式為：

在該特征屬性下聚類的整體純度計算公式為：

其中，nij表示聚類簇i中用戶屬于類別j的個數(shù)，ni為聚類簇i中所有用戶個數(shù)，n為參加聚類的所有用戶個數(shù)?；谔卣鲗傩缘撵刂岛图兌扔嬎闳缢惴? 所示。

算法3基于特征屬性的熵值和純度算法

算法3 是通過聚類結果的熵值和純度衡量特征屬性對行為相似性的影響程度。若基于某一個特征屬性計算得到的聚類結果熵值越小，混亂程度越低，該特征屬性下類別分散程度越小，則基于該屬性聚類結果的綜合評價越好，即特征屬性對同源用戶行為相似性的影響程度越大。而純度相反，若基于某一個特征屬性計算得到的聚類結果純度越大，混亂程度越低，該特征屬性下的類別分散程度就越小，則基于該屬性聚類結果的綜合評價越好，即特征屬性對用戶行為相似性的影響程度越大。

3 實驗與結果分析

本文抽取848 名用戶一個月內(nèi)約1.2 億條點擊流數(shù)據(jù)進行分析，實驗采用Windows 8 操作系統(tǒng)和8 GB 運行內(nèi)存并通過Python3.6 實現(xiàn)。

3.1 結果分析

按照SA-OHUR 算法流程，本文將點擊流數(shù)據(jù)進行處理后得到在線用戶累計點擊行為序列。例如，在線用戶Ua的累計點擊行為序列SUa=｛（［'explorer.exe'］，2），（［'AliIM.exe'］，24），（［'SohuNews.exe'］，18），（［'360SE.exe'］，32）｝，在線用戶Ub的累計點擊行為序列SUb=｛（［'explorer.exe'］，2），（［'AliIM.exe'］，34），（［'xmp.exe'］，5）｝，并由式（4）計算得到用戶Ua與Ub的相似度如下：

采用算法1 得到848 名用戶間相似度并將結果以相似度矩陣A輸出，表達式如下：

相似度矩陣A是一個848×848 對稱矩陣，其中第i行第j列的數(shù)值表示第i個在線用戶和第j個在線用戶的點擊行為相似度，對角線元素表示每個在線用戶與自身行為的相似度，相似度值均為1，在該矩陣中相似度取值分布范圍為0～1。

由相似度矩陣A得到在線用戶不同相似度區(qū)間數(shù)量統(tǒng)計如圖1 所示。其中，x軸為相似度值，y軸為投影在該區(qū)間相似度值的個數(shù)。圖1 中相似度值主要分布在（0.00，0.60）區(qū)間內(nèi)，表明虛擬空間中存在行為相似度超過30%的在線同源用戶，SA-OHUR 算法能有效驗證在線同源用戶的存在。

圖1 不同區(qū)間相似度值統(tǒng)計情況Fig.1 Statistics of similarity values in different intervals

為進一步識別在線同源用戶群，采用SA-OHUR算法基于相似度矩陣A和算法2 對用戶進行聚類。不同聚類簇個數(shù)下的簇間相似度值和簇內(nèi)相似度值的對比如圖2 所示?？梢钥闯?，隨著聚類簇個數(shù)的增加，簇內(nèi)相似度值逐步上升并最終穩(wěn)定在（0.4，0.5）區(qū)間，而簇間相似度值雖然呈現(xiàn)上升趨勢但始終低于簇內(nèi)相似度值，且最大值不超過0.3。這表明屬于同一個簇的在線用戶即為在線同源用戶且其點擊行為相似度超過40%，而屬于不同簇的在線用戶即為在線非同源用戶，采用SA-OHUR 算法能有效識別在線同源用戶群。識別出在線同源用戶后，可根據(jù)表3中用戶特征屬性類別，采用SA-OHUR 算法將用戶分為2 個簇、3 個簇和4 個簇，并利用算法3 研究特征屬性對在線同源用戶行為相似性的影響程度。不同特征屬性下各個簇及聚類結果整體的熵值和純度如圖3 所示。

圖2 簇間相似度值和簇內(nèi)相似度值的對比Fig.2 Comparison of similarity values between clusters and similarity values within clusters

圖3 不同特征屬性下聚類結果的熵值和純度Fig.3 Entropy values and purity of clustering results under different feature attributes

由圖3 可以看出，基于性別、戶籍和教育程度的聚類結果整體熵值分別為0.541、0.754 和0.622，其結果低于基于收入水平、社會階層和年齡的聚類結果（熵值分別為1.689、1.259 和1.144），表明基于性別、戶籍和教育程度的聚類結果分散程度低且綜合評價較好，即該3 類特征屬性對在線同源用戶行為相似性影響較大?；谛詣e、戶籍和教育程度的聚類結果整體純度分別為0.890、0.872 和0.878，其結果高于基于收入水平、社會階層和年齡的聚類結果（純度分別為0.517、0.740 和0.732），表明基于性別、戶籍和教育程度的聚類結果純度較高且混亂度較低，這3類特征屬性對在線同源用戶行為相似性影響更大。綜上可知，性別、戶籍和教育程度3 種特征屬性對在線同源用戶行為相似性的影響程度大于收入水平、社會階層和年齡的影響程度，其中影響最高的特征屬性為性別，影響最低的特征屬性為收入水平。

3.2 對比實驗

為驗證SA-OHUR 算法的時間復雜度，本文采用時間序列相似性度量（DTW）［18］和萊文斯坦相似性度量（Leven）［20］兩種經(jīng)典的相似性度量算法，分別計算點擊流數(shù)據(jù)中前200 名、400 名、600 名和800 名在線用戶的相似度，3 種算法運行時間如表6 所示。

表6 3 種算法的運行時間對比Table 6 Running time comparison of three algorithms s

由表6 可知，SA-OHUR 算法在一定程度上減少程序運行時間，提升了程序運行效率，在處理大批量數(shù)據(jù)時該算法有明顯優(yōu)勢。這是因為SA-OHUR 算法采用累計點擊數(shù)據(jù)流進行計算，無需考慮累計點擊數(shù)據(jù)流中序列的順序性，同時去除冗余序列，降低了算法復雜度。

相較傳統(tǒng)層次聚類HC 算法，SA-OHUR 算法降低了時間復雜度，提高了運行效率，但其聚類效果還未知。因此，本文將采用傳統(tǒng)層次聚類HC 算法和SA-OHUR 算法所得聚類結果的熵值和純度進行對比，結果分別如表7 和表8 所示。

表7 2 種算法不同特征屬性的熵值對比Table 7 Comparison of entropy values of different feature attributes of two algorithms

表8 2 種算法不同特征屬性的純度對比Table 8 Comparison of purity of different feature attributes of two algorithms

由表7 和表8 可知，SA-OHUR 算法得到的聚類結果整體熵值較低且純度較大，其中在社會階層屬性中較反常。從整體來看，年齡對行為相似性影響程度低于性別、教育程度、戶籍3 種屬性，對結果影響不大。因此，在分析特征屬性對在線同源用戶行為相似性影響程度時，基于相似度矩陣的層次聚類整體效果更好。

4 結束語

利用海量的互聯(lián)網(wǎng)信息找出在線用戶行為的主要影響因素，并據(jù)此對不同用戶群體進行分類具有重要意義。本文基于序列對齊技術提出一種在線同源用戶識別算法，提取在線用戶點擊流數(shù)據(jù)和特征屬性，采用序列對齊方法計算用戶行為相似度，識別具有相似行為的在線同源用戶，并分析不同特征屬性對用戶行為相似性的影響程度。實驗結果表明，該算法能有效區(qū)分在線同源用戶，用戶行為相似性受性別、戶籍和教育程度3 種特征屬性影響較大。本文主要研究獨立的特征屬性，未考慮不同特征屬性組合對用戶行為的影響，后續(xù)將從用戶行為權值較大的部分特征屬性入手，進一步研究包含該部分屬性不同組合的用戶行為。