基于多維行為分析的用戶(hù)聚類(lèi)方法研究

張林兵，郭 強(qiáng)，吳行斌，梁耀洲，劉建國(guó)

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

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

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

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

1 模型與方法

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

1.1 UFS-MI 特征選擇模型

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

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

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

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

特征選擇過(guò)程從一個(gè)空集 S開(kāi)始，采用步進(jìn)的方式，每次從特征全集中選擇一個(gè)特征，令：

由式(5)可知，選擇的第一個(gè)重要特征g1為fl1，因?yàn)樵谥贿x擇一個(gè)特征的情況下，g1可以最大程度地降低其他未選特征的不確定性。

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

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

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

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

一個(gè)特征 fi對(duì)特征gt的冗余度定義為：

所以在選擇第 m個(gè)重要特征時(shí)，綜合考慮候選特征的相關(guān)度以及已選特征的冗余度，得到“無(wú)監(jiān)督最小冗余-最大相關(guān)”特征重要性評(píng)價(jià)標(biāo)準(zhǔn)(UmRMR)：

由式(10)得，第 m個(gè) 特征選擇為 gm=flm，因?yàn)樵撎卣髯畲蟪潭鹊亟档土似渌卣鞯牟淮_定性，同時(shí)帶來(lái)最少的冗余信息，所以采用該方法逐個(gè)選取特征。

1.2 用戶(hù)行為相似性度量

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

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

1.3 Blondel 算法

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

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

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

2 實(shí)驗(yàn)及分析

本實(shí)驗(yàn)的數(shù)據(jù)來(lái)源于某公交線路2017 年9 月1 日～2017 年9 月30 日，133 名司機(jī)、55 輛車(chē)、共16 個(gè)字段的駕駛信息。

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

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

2.2 特征提取與篩選

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

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

2.3 司機(jī)駕駛行為相似性度量

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

2.4 聚類(lèi)準(zhǔn)確性度量

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

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

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

根據(jù)平均分類(lèi)準(zhǔn)確性指標(biāo)，計(jì)算得出Blondel算法分類(lèi)準(zhǔn)確率為92%，而傳統(tǒng)算法K-means 算法在k=3 時(shí)，分類(lèi)準(zhǔn)確率為75%。

2.5 聚類(lèi)結(jié)果分析

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

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

3 結(jié) 束 語(yǔ)

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

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