基于密集子圖挖掘的刷單團伙識別方法*

鄭賾一，王 澎

(杭州師范大學 阿里巴巴商學院，浙江 杭州 311121)

0 引言

中國的電子商務及其相關的附屬產(chǎn)業(yè)發(fā)展迅速，而“刷單”與“炒信”作為其中一種“產(chǎn)業(yè)”也得到了快速的壯大。刷單是通過虛假交易提高商品的銷量，以吸引買家促成更多的交易。 但是這是一種欺詐消費者的手段[1]。 刷單違背了市場公平，傷害了消費者的權益，并且已經(jīng)形成了完整的黑色產(chǎn)業(yè)鏈。 據(jù)報道，僅 2016 年上半年，淘寶上從事刷單等虛假交易的賣家就有150 萬家，涉及交易數(shù)目約5億筆，虛假交易的買家賬號達到900 萬個，交易額超 120 億 元[2]。

最簡單的刷單方法就是用一個賬號不停地購買自己的商品。但是這種方法非常容易被電商平臺的算法檢測出來。 于是刷單平臺成為了一個常見的選擇。 商戶通過刷單平臺發(fā)布任務，然后常駐平臺的“刷手”則會接收任務通過自己刷單賬號來進行刷單[3]。 所以通常情況下刷單具有很強的行為相關性。

目前國內(nèi)外對于這種情況有多種基于圖挖掘的異常識別方法。 ZHAO Y 等[4]提出了 BotGraph 方法，針對用戶間的郵件發(fā)送情況，根據(jù)郵件數(shù)目進行剪枝，以發(fā)現(xiàn)異常的用戶基團。BEUTEL A 等[5]提出了 CopyCatch 算法，JIANG M 等[6]提出了 CatchSync算法，均是捕獲大規(guī)模有向圖中同步行為，挖掘網(wǎng)絡中的異常。 CAO Q 等[7]提出了 SynchroTrap 算法，利用在一定時間內(nèi)發(fā)生的相似行為的數(shù)量， 計算節(jié)點之間的相似性，根據(jù)相似性建立網(wǎng)絡圖，根據(jù)閾值進行圖切割，再根據(jù)圖的連通性進行聚類以尋找異常子圖。 MA J 等[8]提出了 GraphRAD 算法，通過賬戶之間共享的設備、IP、地址等信息，將節(jié)點連邊。 通過人工尋找的欺詐賬戶作為種子節(jié)點，找到每一個種子節(jié)點所在的局部社區(qū)， 然后將這些局部社區(qū)進行過濾和合并成一個大社區(qū)，再將這個大社區(qū)進行劃分， 得到剩余的不重疊社區(qū)。PRAKAS B A 等[9]提出了 EigenSpokes 算法，該方法使用奇異矩陣分解(Singular Value Decomposition，SVD)，根據(jù)特征值較大的特征向量來識別欺詐賬戶。

但是由于電商平臺算法的升級和對刷單打擊手段的提高，刷單的方法也進行了升級。 刷單平臺會對刷手進行訓練，使他們的行為更像一個正常的用戶。刷手會在電商平臺上購買一些銷量高的商品， 使自己的行為網(wǎng)絡與大量的普通用戶相連，以降低自己在反欺詐算法中的排名。 這是一種常見且有效的偽裝方法，被稱為Lockstep 行為。

針對這種行為，JIANG M 等[10]提出了 LOCKINFER 算法，計算譜子空間(spectral-subspace)，并將譜子空間轉(zhuǎn)成極坐標，繪制每個節(jié)點關于半徑和角度的分布，再通過Mean Filter 算法識別這種分布中的尖峰來找到具有特殊模式的節(jié)點作為種子，輸入到信念傳播算法中，最終識別出異常團塊。 劉梟[11]提出了一種通過在賬戶-資源二部分圖尋找子圖可疑度量最大的子圖的密集子圖挖掘方法。 HOOI B 等[12]提出FRAUDAR 算法，根據(jù)整個二部分圖節(jié)點權重，不停地移除節(jié)點，直到整個圖的權重密度最大。SHIN K 等[13-14]提出了 M-Zoom 算法，可以在高維空間使用貪心的方法不斷地移除一個個屬性，最后找到密集的欺詐團伙。 FENG W J 等[15]提出了EagleMine 算法，根據(jù)用戶特征的直方圖，通過水位樹(water-level tree)方法來分割用戶的特征，尋找微小的團塊，以達到分離異常團塊的目的。

針對這種情況本文提出了一種新的方法，利用用戶共同購買的商品的銷量及新的權重公式計算不同用戶之間的關聯(lián)度，根據(jù)關聯(lián)度的大小進行閾值剪枝以對抗刷單用戶的Lockstep 行為。 同時定義了一種新的密集子圖可疑度量，通過密集子圖的可疑度量， 設計了一種基于密集子圖挖掘的算法，在真實的數(shù)據(jù)集上取得了較好的效果。

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

本文所用數(shù)據(jù)集來自天貓2012 年所有發(fā)生過購買行為的用戶的1%隨機抽樣，數(shù)據(jù)包含了這些用戶此年內(nèi)所有交易行為。 具體數(shù)據(jù)字段包含：買家ID、商品 ID、購買時間(精確到小時)。 數(shù)據(jù)中包括995 638 個 用 戶 ，2 433 466 個 商 品 ，14 121 705 次 購買記錄。

首先對數(shù)據(jù)進行初步的分析。 根據(jù)圖1(a)可以看出商品的銷售情況符合冪率分布的特點。 這是因為正常用戶大多數(shù)的購買是被銷量吸引的，大量的用戶會去購買銷量高的商品，形成長尾效應。 圖1(b)中用戶購買量的分布則有些不同，在50 左右出現(xiàn)了一個明顯的下降。 這是因為人們的購買量是有限制的，不可能每個人都擁有無限的購買力。 根據(jù)對數(shù)據(jù)的基本分析，可以得出一個結(jié)論：即使存在刷單用戶，數(shù)據(jù)的基本分布還是符合正常的數(shù)據(jù)分布。

圖 1 用戶購買量和商品銷量的分布圖

2 刷單網(wǎng)絡挖掘

2.1 網(wǎng)絡圖構(gòu)建

定義一部分無向帶權圖 G=(B，E)， 其中 B={b1，b2， …，bn} 表示數(shù)據(jù)中的所有用戶，E={e1，e2，…，em}表示圖中節(jié)點之間的連邊，如果兩個節(jié)點代表的用戶之間曾經(jīng)購買過相同的商品，那么他們之間存在連邊。 但是此處并沒有計算兩個用戶多次購買同一個商品的情況。 圖的構(gòu)成如表1 所示。

表1 圖的構(gòu)成

2.2 對抗偽裝

銷量高的商品如果想用刷單提高效果，那么需要刷單的數(shù)量也會更多，這樣在每一單的成本不變時，顯然是不劃算的。而還有一些銷量極少的商品，他們一整年只賣出幾件商品，顯然他們也不會進行刷單。 刷單可能性最大的就是銷量在中間的商品。所以對商品賦予了新的權重。

根據(jù)式(1)得到新的商品權重集合。其中 si是第i 個商品的銷量對數(shù)，Smax是商品銷量最大值加 1 的對數(shù)。 得到新的商品權重之后重新為圖的邊進行關聯(lián)度設置：

其 中 ，corij是用 戶 i 與用 戶 j 的關 聯(lián) 度 ，ζ1，…，k是 用 戶i 與用戶 j 共同購買的商品的權重。 這里使用“和”而不是“平均數(shù)”，是因為刷單的偽裝購買記錄權重非常小，計算平均數(shù)會對兩個用戶的關聯(lián)度大小造成極大的影響。 利用這種加權方法相比于文獻[7，12-14]中的加權方法不但可以盡量減小欺詐用戶在網(wǎng)購過程中利用熱門產(chǎn)品進行偽裝，同時也考慮了對銷量極小的商品的處理。

2.3 關聯(lián)度剪枝

由于刷單是一種很強的共謀行為，刷單團伙之間會有很強的相關性， 他們都會購買相同的產(chǎn)品。而正常用戶和偽裝的邊大多沒有這種共謀性，他們之間的關聯(lián)性一般都很小。 可以通過關聯(lián)性剪枝的方法剔除正常用戶和偽裝的邊。

首先對整個網(wǎng)絡圖使用閾值進行剪枝。 將圖中所有關聯(lián)度小于閾值的邊全部進行刪除處理。 這樣可以降低偽裝和正常用戶之間購買記錄的影響。 利用這種剪枝方法，可以有效地將刷單用戶的偽裝行為進行去除。

2.4 密集子圖挖掘

定義子圖的密集函數(shù)為：

其中，τ 為圖中三角形的數(shù)量，g*為子圖中的點的數(shù)量，ρ 為子圖的密度。 圖中三角形是指若三個節(jié)點兩兩之間都存在邊，則這三個點構(gòu)成一個三角形。

利用三角形數(shù)量來定義圖的連通性是在社會網(wǎng)絡分析(Social Network Analysis，SNA)中使用的一種用于衡量節(jié)點社團的方法[16-17]。 在一個網(wǎng)絡中某個節(jié)點的三角形越多，證明這個節(jié)點的重要性越大。同時三角形越多，整個網(wǎng)絡的密集程度就越大，本文就是利用這一點來衡量整個網(wǎng)絡的密集性。 同時若有正常的用戶混入，其連邊一般較少，可以通過密集度量將其去除，減小誤殺率。

通過遍歷G 的聯(lián)通子圖集合中的子圖，不停地刪除子圖中三角形數(shù)量最少的節(jié)點，在刪除節(jié)點的過程中若子圖的聯(lián)通子圖增加，則分別重新遍歷兩個新的聯(lián)通子圖。 計算當前子圖的密度，當刪除某個節(jié)點后，密度開始變小時，則停止遍歷，此時的子圖即為所需子圖。 見算法1。

算法1 三角形密集子圖挖掘算法

輸入： Gs為圖G 的所有聯(lián)通子圖的集合

3 實驗與結(jié)果分析

由于本文使用的數(shù)據(jù)是真實的脫敏天貓數(shù)據(jù)，原始數(shù)據(jù)中沒有標簽。 本文使用現(xiàn)工業(yè)屆和學術界都非常流行的FRAUDAR 算法作為對比算法，將其結(jié)果作為實驗的標簽。

3.1 實驗過程

實驗過程如圖2 所示。

圖 2 實驗流程圖

首先根據(jù)用戶的購買記錄建立一部分圖。 根據(jù)商品的銷量計算商品的權重，以及用戶之間的關聯(lián)性。 本實驗使用 12.1 為關聯(lián)性剪枝的閾值。 將圖中關聯(lián)性小于閾值的邊全部刪除，得到剪枝網(wǎng)絡。 在剪枝網(wǎng)絡上使用三角形密集子圖挖掘算法，最后得到刷單用戶的密集子圖。

3.2 實驗結(jié)果

AUC 反映的是模型對測試樣本的整體預測能力，是樣本數(shù)量不平衡的分類方法中最為常見的指標。 本文使用FRAUDAR 算法的結(jié)果作為實驗的標簽，以本文方法作為結(jié)果，AUC 值為0.98。

根據(jù)相似度計算方法：

其中，A 為 FRAUDAR 的結(jié)果，B 為本實驗的結(jié)果。兩種方法結(jié)果的相似度達到83.2%。 說明兩種方法的結(jié)果相當。

3.3 結(jié)果討論

圖3 用戶與商品的購買矩陣

根據(jù)結(jié)果繪制用戶和商品的購買鄰接矩陣，如圖3 所示。 圖中左側(cè)是隨機抽取的正常用戶，右側(cè)是刷單團體。 隨機抽樣的方法是首先隨機抽取一個正常用戶，從其鄰居中隨機抽取一個未抽取的正常用戶。 繼續(xù)迭代至達到取樣的數(shù)量。 如果某個用戶沒有可抽取的鄰居則重新隨機抽取。 x 軸代表用戶ID，y 軸代表商品ID，商品ID 包括用戶購買過的所有商品。 當 x 號用戶購買 y 號商品時，點(x，y)為 1，否則為0。 可以看出即使在抽取方法有一定相關性時，左側(cè)的大部分用戶的購買關系之間并沒有什么關聯(lián)性，而右側(cè)可以明顯地看到多條橫線，這證明右側(cè)用戶的購買記錄有大量的相同商品，他們的行為方式有很強的共謀性。 這正是團伙欺詐的重要標志。

本文截取了 10 月 21 日～11 月 18 日之間 4 周的用戶購買記錄時間分布，見圖 4，圖中 y 軸是當天的兩種購買記錄分別占其全年購買記錄數(shù)量的百分比。 可以看出在正常用戶有巨大購買量的雙11當天，異常用戶的購買量反而不多。 但是在雙 11 前兩周，卻有大量的購買行為，這是很不正常的行為特征。這種行為是為了提高銷量以吸引消費者在雙 11 期間的購買。

圖4 刷單用戶與正常用戶購買時間的差異

這些特征可以說明，本文的算法可以有效地將刷單團體分離識別出來。

4 結(jié)論

本文基于真實的天貓數(shù)據(jù)分析，利用圖特征挖掘方法，結(jié)合電商平臺刷單的特點，設計了一種基于密集子圖挖掘的刷單團體的識別方法。 結(jié)果表明， 本文的方法與 FRAUDAR 算法結(jié)果相當， 有較為良好的效果。 同時由于在計算密集子圖時，本文采用分離子圖，單個計算的方法，使得其可以使用多核心進行計算。但是由于計算三角形個數(shù)方法復雜，因此消耗的時間較多。 本文的未來工作將著眼于分布式系統(tǒng)的開發(fā)和時間復雜度的降低。