鄭賾一，王 澎

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 圖的構(gòu)成

2.2 對抗偽裝

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

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

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

2.3 關(guān)聯(lián)度剪枝

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

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

2.4 密集子圖挖掘

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

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

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

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

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

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

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

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

3.1 實驗過程

實驗過程如圖2 所示。

圖 2 實驗流程圖

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

3.2 實驗結(jié)果

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

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

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

3.3 結(jié)果討論

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

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

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

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

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

4 結(jié)論

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