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

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

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

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

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

1 模型與方法

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

1.1 UFS-MI 特征選擇模型

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

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

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

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

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

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

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

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

一個特征gt對特征 fi的相關(guān)度定義為：

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

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

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

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

1.2 用戶行為相似性度量

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

加權(quán)相關(guān)度的計算公式為：

1.3 Blondel 算法

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

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

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

2 實驗及分析

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

2.1 數(shù)據(jù)的預處理

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

2.2 特征提取與篩選

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

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

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

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

2.4 聚類準確性度量

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

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

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

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

2.5 聚類結(jié)果分析

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

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

3 結(jié) 束 語

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

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