構建基于密度峰值聚類算法的反作弊系統

葉 楠，寇麗杰

（福州理工學院，福建 福州 350506）

0 引言

隨著互聯網技術的發展普及，日益增加的廣告投放需求與流量需求，不停推動著廣告平臺自身對流量擴增的需求，在存量時代的零和博弈現狀下，數以百萬計的應用激烈爭奪有限的流量市場，自然而然會引來大量的黑產，去謀取其中的一些利益[1]。廣告黑產的定義，即通過制造大量虛假的曝光和點擊下載的傳播，來達到更多的曝光、更多的點擊、更多的下載、更多的轉化。黑產演進已經從技術實現簡單的協議刷量、群控刷量發展到了技術復雜度越高的真人眾包刷量[2]。

本文分析了主要的流量反作弊的痛點和技術難點，構建基于對抗性訓練的廣告流量反作弊學習框架，結合對密度峰值聚類算法的多重改良，提出了一種解決行為序列分類問題的Transformer self attention模型，旨在將多模態結合提升模型效果，通過流量反作弊中的對抗性訓練設計實現黑產演變攻擊的對抗方案[3]。

1 流量反作弊的對抗性學習框架

洞察出正常流量與惡意流量的區別，關鍵點就在于惡意流量是很難完全偽造出正常流量的，它會在某些行為或者說數據的特征上呈現出與正常流量的一些區別[4]。利用這個思路，本文創新性地提出了一個流量反作弊的對抗性學習框架，如圖1所示[5]。整個學習框架分為四層，第一層為數據安全層，即數據的管理層，相當于把所有的數據收集起來，然后做一系列的清洗之后作為第二層畫像層的輸入，在畫像層構建出關于設備和環境等不同Item的一些畫像。最后通過把這些構建出來的畫像提供到對抗學習模型上面，給需要的一些模型進行學習，最終發布到應用層面上，提供強有力的反作弊服務能力[6]。

圖1 流量反作弊對抗性學習框架

2 改進密度峰值聚類算法模型

2.1 密度峰值聚類算法

密度峰值聚類算法是一種很簡要易用的聚類算法，能夠識別各種不同形狀的類簇，該算法有兩步很重要的步驟，一個是密度的計算，另一個是最小距離的計算，密度的計算就主要是指計算每一個點，與其所有其他點的最小距離之和[7]。當得到每一個點的最小距離和密度后，可以由局部密碼和距離( ， )構造出對確定聚類中心具有決定性作用的決策圖，這個決策圖橫坐標是每一個點的密度，然后縱坐標是點的一個最小的距離[8]。局部密度 和距離 的計算公式如下。

從公式中可以看到，密度越大、距離越遠的點，越有可能被定義成一個聚類的中心，因為該算法的假設是類簇的中心由一些局部密度比較低的點圍繞，并且這些點距離其他有高局部密度的點的距離都比較大。從另一個層面來說，聚類中心與聚類中心之間會有一定的距離，同時也可以發現那些密度很小，但是距離很遠的點，很有可能就是所要找到的一些離群點。

2.2 算法改良優化思路

經過深入分析并結合具體應用，采用該密度峰值聚類算法會有以下問題：時間復雜度高、強高斯假設和無法準確檢測離群點[9]。

（1）時間復雜度高。算法中三個計算步驟時間復雜度為 ，當數據規模較大時，算法基本不能輸出結果。

（2）強高斯假設。密度的計算是基于球體半徑作為閾值來計算的，所以依然以高斯假設為前提。無法理想地聚集任意形狀的簇，密度的計算以高斯假設為前提，所以簇依然與高斯分布相關。

（3）無法準確檢測出離群點。根據密度與距離判斷離群點缺乏魯棒性，離群點之間也會相互影響，無法根據離群點的最小距離判斷其離群的程度。

如何解決時間復雜度問題？通過合并多個重復計算、進行數據點距離計算、密度函數等優化，可以將多個計算步驟時間復雜度由 下降至 ，如表1所示，達到百萬級數據集輕松計算，時間縮小100倍。

表1 解決時間復雜度的算法優化

如何理想地聚集任意形狀的簇？通過去掉高斯假設，如果密度的計算是基于k個最近鄰居點，則其分布可以是任意形狀。如何使離群點檢測更具魯棒性？在關于離群點檢測這個方法上增加一個新的指標LOF（Local Outlier Factor），如式（3）所示，主要用于衡量每個點的密度與它最近鄰居點的密度之比的平均。

在LOF計算指標公式中，j為k個最近鄰居點；和 分別為i點和j點的密度。

通過如上改善，本文所提出的改良DPeak后的算法IM-DPeak（Improve DPeak）解決了幾個重要的問題：第一個是把時間復雜度，從 下降至 ；第二個是引入了k最近鄰居的計算，成功去掉了一個高斯假設；第三個是通過計算k最近鄰居點的密度之比的平均作為衡量新指標，可以使得離群點的檢測更具魯棒性。從實際的場景和數據也可以發現，如果根據最小的距離無法檢測出一些很準確的離群點，而通過新的指標，卻能發現一些相應的離群點，并且我們把這些離群點剔除之后，使本文的分類算法在設計上得到了一定的提高。

3 黑產演變攻擊的對抗方案

方案參考了Few Shot Learning的思想，主要采用Prototypical Network with Attention網絡，這張網絡的核心思想在于讓網絡去學習一個轉義的空間，然后讓輸入映射到一個圓形的空間里面，使得不同種類的流量會在圓形空間里面分布在不同的角落，而網絡的目標是讓它們形成各自的簇，然后在預測時，只要把流預測的樣本輸入網絡，讓它映射回圓形空間里面去看，判斷它會更接近于哪一個種類的流量。

通過如上Transformer網絡已經可以很好地抽取到一些行為的特征，圖2為進行多模態結合的流程模型，結合之前一些App的畫像Embedding、設備的畫像以及IP地址的畫像，把這些不同模態的特征融合在一起，作為多模態模型的一個輸入，能夠為分類器的模型帶來很大的提升效果。

圖2 多模態結合提升模型效果

4 實驗分析

4.1 背景和實驗環境描述

為了評估本文優化構建的IM-DPeak算法的聚類效果和離群點檢測準確性，對接擁有線上百萬級用戶的第三方新媒體IP視頻云平臺中的程序化廣告系統進行實驗，該平臺注冊用戶在200萬以上，在線并發率超過10%，終端涵蓋了機頂盒端、手機端、PC端等門戶，提供了以視頻、圖片為主的廣告推送服務。實驗結果以規則校驗下異常流量的過濾能力、聚類中心判定的識別準確度作為參考，同時要求IM-DPeak算法能夠聚集任意形狀的類簇，具備標準數據集的同等聚類效果。發起單次完整的廣告流程中包括了請求、下發、曝光和點擊四個基本要素。

4.2 實時和離線反作弊系統策略

實時反作弊系統策略主要依賴直接反饋特征，在快速、高效的基礎上，根據獨立廣告流量進行實時分析。其策略主要包括參數合規性檢查、廣告流量地址防盜鏈校驗、點擊事件真實性決策等。離線廣告反作弊系統主要依賴于統計分析和關聯分析，根據用戶基數和日志量級需要損耗一定的計算性能。規則策略分為以下幾類。

（1）基于點擊的策略。①進行頁面上下游分析、頁面行為深度分析、頁面加載耗時分析，了解用戶在點擊事件上的跳轉行為是否符合規律和合法路徑；②進行用戶畫像、標簽組關聯大量分組廣告的用戶請求分析，判決點擊事件真實性；③繪制點擊次數跟隨時間變化的控制圖，描述上下限變化穩定度，發現點擊事件轉化情況。

（2）基于曝光的策略。①一定時間內累計達到廣告曝光次數時，比對設備、IP地址、用戶ID、時間間隔等參數；②單維度曝光量突降時應檢查慢速比、卡頓比的影響；③當A/B Test數據驅動決策時對曝光率變化情況的融合進行分析。

如上策略結合請求和下發情況，可以更進一步產生基于組合的策略，通過對廣告全流程的節點監控，如多維度的歷史數據挖掘和系統質量趨勢，進行持續跟蹤、發現異常、及時報警。

4.3 合成和真實數據集上的聚類對比

實驗環境包含x86服務器1臺，配置為Windows 10 64位操作系統，Intel XEON金牌6130 2.1 GHz，64 GB內存，軟件為PyCharm Python 3.8 64bit版本。

表2為基于廣告大數據系統軟硬探針和終端SDK采集統計的實例，提供實驗所用的4個真實數據集，其中各數據集按照不同獎勵形式定義了規則分類，按照整體熱度分布提取了一定量級的實例數進行集合分析。

表2 實驗中采用的真實數據集

為了分析新媒體IP視頻云平臺抽樣用戶的行為規律和檢測是否存在刷量離群樣本，IM-DPeak算法在4個真實數據集上的聚類結果如圖3所示。從圖3(a)決策圖中可以看出，通過IM-DPeak算法進行不同數據集的聚類后，通過混合不同采樣數據集同樣可以正確找出聚類中心，根據反作弊系統規則，在這些數據集上的類中僅存在按設定分類的明顯密度峰值，同時用三角形標出距離較大、密度較小的離群點。在圖3(b)中，IM-DPeak算法在4個真實數據集上可以準確劃分聚類結果，且存在部分離群點（使用黑色點標注）及部分需要借助反作弊系統輔助二次審計的疑似離群點（使用放大同色點標注），實驗真實數據集的聚類情況說明本文所設計的IM-DPeak算法在不同形狀數據集上的處理效果較優，可與不同群體類別的廣告用戶行為數據進行混合分析。

圖3 IM-DPeak算法在4個真實數據集上的聚類效果

5 結束語

密度峰值聚類算法具備很好的分類及離群檢測機制，本文將密度峰值聚類算法進行改良后，創新性地應用于面向黑產技術演進發展的流量反作弊系統，提出了一種基于DPeak算法的對抗性學習框架，通過復雜度降級提高算力、構建模型解決少量樣本的行為序列分類問題等步驟，形成了完善流程的反作弊系統。同時建立多維度的畫像輸入機制，讓不同模態特征進行融合，持續提升新分類器模型效果。■