基于多維行為分析的用戶聚類方法研究

張林兵，郭 強，吳行斌，梁耀洲，劉建國

(1.上海理工大學復雜系統科學研究中心 上海 楊浦區 200093；2.上海財經大學合計與財務研究院 上海 楊浦區 200433)

隨著大數據技術的不斷發展，人們收集到的用戶行為數據維度越來越多，如何能夠有效的對多維用戶行為數據進行分析，是目前行為分析的難點之一[1-2]。聚類分析是數據挖掘領域中較為基礎的數據處理手段，通過聚類算法對數據分類能夠將一個數據集劃分為若干個類內對象相似而類間對象相異的類簇[3]，從而在數據集中發現潛在的數據模式和內在聯系[4]，為此國內外的眾多專家學者們研究了各類聚類算法。其中傳統聚類算法主要可以分為層次化聚類算法、劃分式聚類算法和基于密度的聚類算法[5]。層次聚類算法又稱為樹聚類算法，它的優點是距離和規則的相似度容易定義、不需要預先制定聚類數、可以發現類的層次關系，缺陷[6]在于沒有全局待優化的目標函數；合并或分裂點的選擇困難，好的局部合并選擇不能保證高質量的全局聚類結果；算法的計算復雜度高，適合小型數據集的分類；對噪聲、孤立點敏感，不適合非凸型分布數據集。K-means 算法是經典的劃分式聚類算法，它的優點[7]是思想簡單、易于實現，可用于大規模數據集的并行聚類挖掘，通常在對大型數據集聚類時，K-means 算法比層次聚類算法快得多，它的缺點是需要事先確定聚類個數 k的大小，因為很多應用事先是無法確定的，如網絡社團的劃分；k個初始聚類中心是隨機選擇的，由于隨機選擇 k個初始聚類中心，導致算法對異常數據敏感。DBSCAN聚類算法是經典的基于密度的聚類算法，它的優點[8]是不需要事先確定簇的個數以及選擇初始聚類中心，能夠識別噪聲數據點，且對數據點的輸入順序不敏感，缺點是需要事先確定Eps 和MinPts這2 個參數，而這2 個參數的確定無規律可循且DBSCAN 算法對這2 個參數比較敏感，參數的輕微變化可能導致差別較大的聚類結果，DBSCAN算法不能有效地處理數據分布比較均勻的數據集，也無法有效處理維數較大的數據集。上述的傳統聚類方法在進行多維行為數據聚類分析時，存在很多問題，因而傳統聚類算法不能直接應用到多維行為聚類分析。為了解決這個問題，本文嘗試用網絡科學[9-11]的方法對多維行為數據聚類分析。

與小世界性、無標度性[12-13]等基本統計特性相并列，網絡簇結構(network community structure，NCS)是復雜網絡最普遍和最重要的拓撲結構屬性之一，具有同簇節點相互連接密集、異簇節點相互連接稀疏的特點，復雜網絡聚類方法旨在揭示出復雜網絡中真實存在的網絡簇結構。復雜網絡聚類算法主要分為啟發式方法(heuristic method，HM)和基于優化的方法(optimization based method，OBM)[14]。文獻[15]提出的GN 算法是經典的啟發式方法，該方法的優點是思想簡單而得到廣泛應用，缺點是計算速度慢，不適合大規模的網絡，同時又難以確定合適的終止條件。文獻[16]提出的分級凝聚快速算法(FN 算法)是經典的基于優化的方法，與GN 算法相比，時間復雜度大大降低，但準確性不如GN 算法。文獻[17]提出的Blondel 算法是一種基于模塊度最優化的啟發式算法，與普通的基于模塊度和模塊度增益算法相比該算法的執行效率高且聚類效果非常明顯，是目前國際上公認的執行速度最快且精度較高的非重疊社區發現算法[18]，因而本文選擇用Blondel算法進行聚類分析。

本文的主要貢獻是：1)將機器學習中的無監督特征選擇方法與網絡科學中的社團劃分算法相結合，提出一種多維用戶行為聚類分析方法。在某公交線路的實證數據集上的實驗結果表明，該方法聚類準確率明顯高于傳統K-means 算法；2)本文提出的方法不僅為多維駕駛行為數據分析提供新的思路，還可以在不同的場景中廣泛應用，例如金融市場的數據分析、互聯網企業用戶行為的數據挖掘等。

1 模型與方法

本文提出基于復雜網絡多維用戶行為聚類方法。首先對原始數據進行預處理，包括數據清洗和數據采樣，之后從處理好的數據中提取多維用戶行為特征，構建用戶行為特征向量。然后用UFSMI 模型對多維用戶行為特征向量降維并給特征確定權重，基于加權的用戶行為特征向量計算不同用戶之間的相似性構建網絡。最后用Blondel 算法對網絡進行聚類分析。實驗的流程圖如圖1 所示。

1.1 UFS-MI 特征選擇模型

UFS-MI 是一種基于互信息的無監督特征選擇模型，屬于過濾型特征排序方法。UFS-MI 模型在進行特征選擇時，首先計算出每個特征的相關度，再使用前向順序搜索對特征進行重要性評價，最后輸出一個有序特征序列。UFS-MI 模型的評價標準UmRMR 綜合考慮了特征的相關度和冗余度的信息度量[19-20]。

假設集合 D= {f1,f2,···,fn}表示完整的特征集合， fi( i=1,2,···,n)表 示特征集合中的第i個特征，P(ft)是 特征為 ft的概率。特征 ft取值的初始不確定性可由如下信息熵度量：

在已知另一個特征 ft′的取值之后， ft取值的不確定性由條件熵來度量：

兩個特征 ft與 ft′之間的互信息定義為：

特征選擇過程從一個空集 S開始，采用步進的方式，每次從特征全集中選擇一個特征，令：

由式(5)可知，選擇的第一個重要特征g1為fl1，因為在只選擇一個特征的情況下，g1可以最大程度地降低其他未選特征的不確定性。

假設 U為未被選擇的特征集合， Sm?1為已經被選擇的 m? 1個 特征集合。在選擇第 m個特征gm時，gm應該與 U中的所有特征最大程度相關，同時與 Sm?1中 的 m?1個特征最小程度的冗余。

一個特征 fi的相關度就是其與整個特征集合的平均互信息：

一個特征gt對特征 fi的相關度定義為：

顯然，條件相關度小于等于相關度(當兩個特征相互獨立時相等)，將兩特征之間的差別定義為冗余。

一個特征 fi對特征gt的冗余度定義為：

所以在選擇第 m個重要特征時，綜合考慮候選特征的相關度以及已選特征的冗余度，得到“無監督最小冗余-最大相關”特征重要性評價標準(UmRMR)：

由式(10)得，第 m個 特征選擇為 gm=flm，因為該特征最大程度地降低了其他特征的不確定性，同時帶來最少的冗余信息，所以采用該方法逐個選取特征。

1.2 用戶行為相似性度量

相似性度量，即綜合評定兩個事物之間相近程度的一種度量。兩個事物越接近，它們的相似性度量也就越大，而兩個事物越疏遠，它們的相似性度量也就越小。假設每個特征具有不同的重要程度，可用權向量 w 表示，用來計算x ，y兩個用戶行為之間的相關性。采用加權相關度對兩個用戶之間的行為特征進行計算。

加權相關度的計算公式為：

1.3 Blondel 算法

Blondel 算法常被用于社團劃分問題[21]。在社交網絡中，用戶相當于每一個點，用戶之間通過互相的關聯關系構成了整個網絡的結構，有的用戶之間的連接較為緊密，有的用戶之間的連接關系較為稀疏，在這樣的網絡中，連接較為緊密的部分可以被看成一個社團，其內部的節點之間有較為緊密的連接，而在兩個社團間則相對連接較為稀疏，這便稱為社團結構。為了評價社團劃分的優劣，用模塊度來衡量社團劃分的好壞。模塊度的計算公式如下：

式中， Aij是實際網絡的鄰接矩陣； ki和 kj分別為原網絡中節點i和 節點 j 的度； ci與 cj分別表示節點i與節點 j在網絡中所屬的社團，如果這兩個節點屬于同一社團，δ取值為1，否則δ 取值為0。

Blondel 算法的思想是：首先將網絡中的每個節點看成是一個獨立的社團，慢慢將鄰近的節點合并，如果合并之后整個網絡的模塊度提高，那么就合并，否則撤銷；如此循環，直到網絡的模塊度無法提高為止；接著再把每個社團當成一個節點，對每個社團進行如此的合并算法，直到整個網絡的模塊度無法提高為止。

2 實驗及分析

本實驗的數據來源于某公交線路2017 年9 月1 日～2017 年9 月30 日，133 名司機、55 輛車、共16 個字段的駕駛信息。

2.1 數據的預處理

為了讓司機的駕駛行為特征具有可比性，設定一個具體場景，即從起點至終點的一趟行車記錄作為每個司機的駕駛行為特征計算基準。對每趟行車路程設定閾值進行篩選，最終得到包含103 名司機、51 輛車、879 趟完整行車記錄的實驗數據。

2.2 特征提取與篩選

結合原始數據和業務場景提取了車速平均值、車速中位數、車速標準差、加速度絕對值平均值、加速度標準差、電子剎車使用概率、油門踏板百分比平均值、油門踏板百分比標準差、腳剎使用概率、加速度絕對值大于2 m/s2的概率、行車過程中拉手剎的概率、空擋狀態下的滑行概率共12 個特征。

為了從初步提取的眾多特征中篩選出需要的有效特征，用UFS-MI 模型對特征進行重要性排序，然后選取具有代表性的特征。

2.3 司機駕駛行為相似性度量

選取排序靠前的9 個特征，按照平均互信息值的大小確定權重，得到權向量，然后計算每兩趟行車記錄之間的皮爾森相關系數。設定閾值為0.94，當兩趟行車記錄的行為相似性大于該閾值時，建立連邊。最終構造成的網絡包含879 個節點，183 046條連邊。

2.4 聚類準確性度量

將構造成的網絡用Blondel 算法進行聚類，聚類結果將駕駛記錄分為3 類。第一類包含55 個司機共365 趟行車記錄，第二類包含64 個司機共325 趟行車記錄，第三類包含21 個司機共189 趟行車記錄。

對于一個司機而言，如果司機駕駛行為是穩定的，那么他所有駕駛趟都會分到同一類中，但在司機駕駛行為發生變化的情況下，就會被分到不同的類中。因此本文定義了一個分類準確性指標：

式中， ni為 司機i行 駛的總趟數；為第Cl類中司機i 的行駛趟數；為司機i在 Cl類中行駛最多的趟數； m為司機總數。對所有司機求平均，得到平均分類準確性。

根據平均分類準確性指標，計算得出Blondel算法分類準確率為92%，而傳統算法K-means 算法在k=3 時，分類準確率為75%。

2.5 聚類結果分析

因為每一個類別中的司機駕駛行為是以趟的形式來度量的，所以根據Blondel 算法聚類的結果實際上是不同趟的行車記錄。由于公交司機駕駛的車輛會更換，同一司機在不同車輛上的駕駛行為可能不同，因此，需要先從趟的信息中，提取出司機的類別和駕駛車輛的類別，然后再進行用戶行為分析。將9 個駕駛行為特征轉化為3 個綜合駕駛行為維度：駕駛不平穩性、剎車偏好性、車速偏好性。為了將特征對應到綜合駕駛行為維度上，首先對特征進行0～1 標準化處理，去除特征數據的單位限制。然后對無量綱的特征數值進行綜合駕駛行為維度分析，得到如圖2 所示的駕駛行為偏好雷達圖。最后，將3 個綜合駕駛行為維度的評分求平均，得到如圖3 所示的司機的綜合評分直方圖。

由圖2 可以看出，在駕駛A 類車時，3 類司機在剎車偏好性維度上具有顯著的區別。駕駛B 類車時，第二類司機的駕駛行為在3 個維度上都要優于其他兩類司機。而對于C 類車，3 類司機在剎車偏好性維度上也有明顯區別。由圖3 可以看出，司機在3 個維度下的綜合評分接近正態分布，綜合評分較低的司機較少，這表明駕駛行為優秀的司機占極少數而綜合評分較高的司機相對較多，表明大部分司機駕駛行為需要改善。

3 結 束 語

對多維用戶行為進行聚類分析，可以幫助管理人員得到更為精確和有效的用戶評價信息，為管理層決策參考提供依據。本文從多維用戶行為數據中提取用戶行為特征，采用UFS-MI 模型對提取的用戶行為特征進行排序并篩選，然后按照平均互信息的值給特征確定權重，得到用戶行為的加權特征向量。通過計算用戶行為之間的皮爾森相關系數，設定閾值并構建網絡，再結合復雜網絡理論，采用Blondel 社團劃分算法對用戶行為網絡進行聚類分析。在某公交線路的實證數據集上的實驗結果表明，該方法的準確率為92%，比傳統聚類算法Kmeans 的準確率有明顯提升。

本文提供的方法還有眾多的應用場景，例如根據股票價格波動的相似性構建股票關聯網絡，對股票進行聚類分析。根據個股進行相關股的推薦，為投資者提供參考。通過對互聯網企業用戶簇集進行數據挖掘，有助于企業及時掌握和研究用戶的總體變化，為不同類型的用戶提供更有針對性的個性化服務，從而增加企業市場份額和利潤。此外，本文根據UFS-MI 模型進行特征篩選，沒有結合具體的業務，未來的工作可以結合具體業務對特征進行篩選，從而提高聚類的效果。