基于并行化K-means的綜合能源服務客戶識別

沈子垚，袁曉玲

(河海大學能源與電氣學院，江蘇 南京 211100)

0 引言

隨著綜合能源服務的不斷推廣和互聯網技術的高速發展，客戶的檔案信息與交易數據激增。傳統的供電公司與綜合能源服務企業積累了海量的營銷數據。通過對營銷數據的挖掘分析，能夠獲取客戶的行為信息和狀態數據，識別現有客戶的特征與交易模式，預測綜合能源服務需求，提高企業決策的前瞻性[1—3]。綜合能源服務企業如想在激烈的競爭中保持優勢，需要做好各類客戶的識別與服務拓展工作。如企業能采取有效措施精準識別潛在客戶，就能以較小的成本發展潛在客戶，針對客戶需求制定綜合能源服務策略[4—8]，提高投入產出比。文獻[9]構建了數據倉庫以整合數據資源并提取屬性特征，通過信息匹配實現對潛在客戶的識別。

傳統的聚類算法在處理海量數據時，存在計算復雜度高和計算能力不足等問題。文獻[10]優化了K-means聚類算法初始聚類中心的選取，并選用MapReduce并行編程方法，提高了傳統聚類方法的計算效率。文獻[11]將用戶的用電行為數據按行保存于Hadoop分布式文件系統(Hadoop distributed file system,HDFS),將用電行為數據集劃分為不同切片產生子數據集,利用MapReduce計算模塊對各切片數據進行讀取。Hadoop支持TB級別的數據和流式數據訪問，但實時性較差，不適合大量小文件存儲[12—13]。

在數據挖掘中，需處理大量數據，應構建簡單有效的模型。數據挖掘是指通過對海量雜亂無章的數據進行挖掘，找到其中蘊含的規律和有價值的信息。數據挖掘的主要步驟包括：確定數據挖掘的需求，采集相關數據并預處理，采用合適的數據挖掘算法構建識別模型，對識別結果進行分析評估。

為進一步減少數據聚類迭代過程中的冗余計算，提高聚類算法的效率和準確性，文中針對綜合能源服務潛在客戶識別問題，研究基于Spark[14—17]的K-means聚類算法，優化了初始點的選取和聚類時影響因素的權值選取。文中通過并行計算提高了數據的處理速度，依據實驗結果分析了算法的準確率和并行計算性能。

1 潛在客戶識別數據庫設計

潛在客戶識別數據庫的設計包括分析潛在客戶的各項標簽[18]，利用數據倉庫技術對數據資源進行整合。通過潛在客戶數據庫完成客戶的精準識別工作，可構建完成綜合能源服務潛在客戶識別模型。

1.1 客戶識別數據倉庫

客戶識別數據倉庫的建立基于現有的營銷業務系統及外部數據獲取渠道[19]，需要提取客戶信息形成客戶數據集。數據預處理操作包括缺失數據的補全，重復數據的刪除，數據泛化等工作。基于預處理之后的數據集，可以建立綜合能源服務潛在客戶數據倉庫。數據倉庫的構建基于收入貢獻、成本占用、成長性、信譽度、忠誠度等標簽，潛在客戶特征分析指標如表1所示。

表1 潛在客戶特征分析指標表Table 1 Characteristic analysis index for potential customers

對于大量數據，如無法補全缺失數據的記錄和屬性，應刪除該部分信息。對于缺失少量非關鍵數據的記錄，可根據部分未缺失數據的均值、眾數進行填充。綜合能源服務潛在客戶識別的數據來源眾多，可能存在大量冗余的數據。因此，可通過優化數據庫范式結構以刪除重復數據，對粒度較小的標簽進行泛化處理。數據的泛化是指用高層次的概念取代低層次的概念，能夠進一步明確數據屬性的取值差異，且減少數據的計算量。

1.2 客戶價值評價

綜合能源服務潛在客戶的價值可以用當前價值與潛在價值進行綜合評估，具體的客戶價值評估體系如圖1所示。

圖1 客戶價值評估指標體系Fig.1 Evaluation index system of customers

基于當前價值與潛在價值，可綜合評估綜合能源服務潛在客戶。綜合能源服務潛在客戶的當前價值可以用收入貢獻和成本占用兩個指標衡量。收入貢獻可以用購買服務頻率和各項服務收入兩個細分指標衡量。成本占用可以進一步細分為購買服務數量和各項服務成本。綜合能源潛在客戶的潛在價值可以用成長性、信譽度、忠誠度等指標衡量。客戶的成長性包括需求增長量和需求增長率；信譽包括服務的退訂率和服務的退訂量；忠誠度包括滿意度和近期消費頻率。

1.3 指標映射數據庫

由于評估潛在客戶指標的量綱不同，需要將不同指標值進行無量綱化處理。文中通過構造綜合能源服務潛在客戶的指標映射數據庫，定量計算客戶之間的差異度。

若綜合能源服務客戶的當前價值為主導因素，則映射區間可以超出標準區間限制；而對于非主導因素的潛在價值，映射區間可以限制在一定范圍內。

數據庫映射關系f表示為：

f:(x1,x2,…,xn)→(y1,y2,…,yn)

(1)

式中：(x1,x2,…,xn)為評價客戶價值的各個指標；(y1,y2,…,yn)為評價指標通過數據庫映射，投影到映射區間的值。部分映射區間的取值如表2所示。

表2 部分映射數據庫取值Table 2 Database value of partial mapping

在綜合能源服務發展的過程中，如綜合能源服務企業對潛在客戶的評估標準改變，那么指標映射數據庫的映射取值可能會發生變化。

2 K-means并行聚類識別潛在客戶

聚類分析通過反復分區，將數據進行歸類，使得同類的對象之間能夠彼此聯系。聚類算法能夠在沒有客戶類別標識的前提下對客戶進行分類，最大化不同類別客戶的差異。聚類對象根據最大化同一簇中的相似性，最小化不同簇之間相似性原則進行劃分[20]。

綜合能源服務企業可以修改客戶價值的映射數據庫，通過聚類效果探索出適合自身的映射關系。在與綜合能源客戶交易的過程中，用戶的價值評價體系和企業的偏好可能會發生改變，綜合能源服務企業可以根據偏好改變聚類過程中映射區間的取值。

文中采用Spark平臺對大數據進行并行化處理。Spark是為大數據處理專門設計的快速通用的計算引擎，該框架多任務之間的數據基于內存進行通信，消除了冗余的Hadoop分布式文件系統讀寫，并針對Java虛擬機 (Java virtual machine,JVM)進行了優化。因此，Spark更加適用于實時處理等數據挖掘工作，在大規模的數據計算上優于傳統的MapReduce編程模式[21]。基于Spark的潛在客戶識別的并行聚類模型如圖2所示。

圖2 并行聚類模型Fig.2 Parallel clustering model

對于傳統的K-means算法，首先利用流式聚類思想優化選取初始聚類中心點，再通過映射數據庫衡量不同標簽對聚類算法的影響，計算聚類中心。K-means并行聚類算法運行于Spark平臺，并行聚類運算完成后更新聚類中心。

2.1 初始化聚類中心的優化

文中提出一種基于流式動態聚類思想的單遍權重K均值聚類方法(single-pass-weightedK-means,SWPK-means)。首先，在原數據集上通過隨機抽樣構造出s個大小為n的數據子集X。算法最初將每個數據子集X中的樣本權重設置為1。然后，計算第一組權值為1的樣本K-means的聚類中心y,得到最小的聚類誤差平方和D(y)：

(2)

式中：wi為樣本第i個指標的權值；yi為該樣本第i個指標的數據庫映射值；yi,k為第k個聚類中心第i個指標的數據庫映射值。

迭代剩余的X的數據子集，每一次迭代運用K-means聚類算法在一組更大的數據集上進行聚類劃分，數據集由上一次迭代的聚類中心yt-1和本次的樣本子集Xt-1組成。第t次迭代有t+n-1個實體進行聚類，重復迭代s次K-means算法,直至選擇出共k個聚類中心。該方法基于上一次初始化的聚類中心加速收斂，代替了傳統算法的閾值收斂方法，大大降低了聚類算法的迭代次數，在進行海量數據的聚類分析時更具有優勢。

2.2 客戶樣本隸屬的中心點

定義基于Spark平臺的聚類過程中的距離為歐幾里德距離，對于兩點y′=[y′1y′2…y′n]和y″=[y″1y″2…y″n]之間的歐幾里德距離計算公式為：

(3)

(4)

快速距離算法的優勢明顯，可以提前計算樣本向量的2范數，極大地降低計算量。易知dquick(y′,y″)≤d(y′,y″)，對于同一個樣本，當聚類中心pi的快速距離大于聚類中心pj的歐幾里德距離時，聚類中心pi的歐幾里德距離必大于聚類中心pj的歐幾里德距離。此時，該樣本所在簇的聚類中心應為pj。倘若聚類中心pi的快速距離小于聚類中心pj的歐幾里德距離，快速距離算法失效，需要重新計算樣本與聚類中心pi的歐幾里德距離。

2.3 聚類效果評估

聚類效果評估采用集合內誤差平方和(within set sum of squared error,WSSSE)WSSSE，WSSSE為所有數據點到距離該點最近的聚類中心的平方和：

(5)

式中：m為樣本總個數；n為指標投影向量的維數；yi,j為i個樣本的第j個指標投影到映射區間的值；yclose,j為第i個樣本最近的聚類中心的第j個指標投影到映射區間的值。

易知隨著聚類個數K的增大，WSSSE減少。當聚類個數K=m時，WSSSE=0。一般來說，最優的K取值是K-WSSSE曲線的拐點位置。在拐點處，K值的增加能最大程度地優化聚類效果。

3 案例分析

文中選取2017—2019年常州市供電局綜合能源服務相關的部分負荷數據以組成客戶識別數據倉庫。此外，客戶數據集加入實地客戶集中調研及獲取外部數據渠道提取的客戶信息。將數據集的收入貢獻、成本占用、成長性、信譽度、忠誠度等標簽進行泛化處理，轉化為客戶的當前價值和潛在價值作為輸入。對潛在客戶案例及不同的數據挖掘算法進行對比分析，得出最優的挖掘算法。最終輸出綜合能源潛在客戶及客戶類型，針對性地對各類客戶推廣綜合能源服務。

3.1 模型構建

客戶的當前價值能幫助綜合能源服務企業評估客戶的購買力，且基于客戶的潛在價值可衡量客戶在后續交易中帶來的利潤。文中結合綜合能源客戶的歷史數據，采用基于數據挖掘中的K-means聚類方法進行定量分析，利用矩陣分類法建立綜合能源潛在客戶的二維細分模型，如圖3所示。

圖3 基于當前價值與潛在價值的客戶分類Fig.3 Customer classification based on current value and potential value

Ⅰ類用戶的當前價值較高，且該類客戶較為穩定，綜合能源服務企業與該類用戶合作可以獲取較大的利潤。Ⅱ類用戶的當前價值同樣較高，但綜合能源服務企業無法滿足客戶的綜合能源服務需求，導致后續交易過程中用戶的潛在價值較低，需要投入一定資源激活，避免該類用戶轉向競爭對手。Ⅲ類用戶的當前價值較低，但具有較大的發展潛力，同樣屬于綜合能源服務企業的發展對象。Ⅳ類客戶的當前價值和潛在價值都較低，該類客戶購買力有限，對于綜合能源服務需求較少，屬于綜合能源服務中的“劣質客戶”，不屬于綜合能源服務的交易對象。

3.2 結果分析

3.2.1 聚類效果分析

文中通過綜合評價指標F評估算法的性能：

(6)

式中：TP為正確識別潛在用戶的數量；P為被分為潛在用戶的類別中實際為潛在用戶的比例；R為潛在用戶被正確識別的比例，用于衡量覆蓋面；FP為將非潛在用戶識別為潛在用戶的數量；FN為將潛在用戶識別為非潛在用戶的數量。

在不同的映射權值下，聚類結果不同。客戶當前價值與潛在價值的映射權值為(0.67,1.33)時，聚類結果如圖4所示。

圖4 K-means聚類結果Fig.4 K-means clustering results

Ⅰ類客戶449個，正確識別416個；Ⅱ類客戶448個，正確識別448個；Ⅲ類客戶262個，正確識別229個；Ⅳ類客戶67個，正確識別67個。綜合評價指標F為92.6%。

映射權值表示綜合能源服務企業對該類價值的重視程度。以客戶潛在價值為主導時，客戶的潛在價值映射區間大于當前價值的映射區間，Ⅰ類用戶與Ⅲ類用戶的潛在價值都較高，主要差異為客戶當前價值。當前價值的映射區間較小時區分度不明顯，此時聚類模型無法很好地區分Ⅰ類用戶與Ⅲ類用戶。

客戶當前價值與潛在價值的映射權值為(1,1)時，基于權值的K-means算法聚類結果如圖5所示。

圖5 基于權值的K-means聚類結果Fig.5 Weighted K-means clustering results

Ⅰ類客戶431個，正確識別423個；Ⅱ類客戶448個，正確識別448個；Ⅲ類客戶280個，正確識別272個；Ⅳ類客戶67個，正確識別67個。綜合評價指標F為98.6%。

設映射權值為(1,1)，SPWK-means算法聚類結果如圖6所示。

圖6 SPW K-means聚類結果Fig.6 SPW K-means clustering results

Ⅰ類客戶431個，正確識別426個；Ⅱ類客戶448個，正確識別448個；Ⅲ類客戶280個，正確識別275個；Ⅳ類客戶67個，正確識別67個。綜合評價指標F為98.7%。

客戶的當前價值與潛在價值的映射區間相同時，客戶的當前價值與潛在價值重要程度相近，聚類結果更符合矩陣分類法建立的二維細分模型。優化特征向量的權值將改善基于權值的K-means算法與SPWK-means算法的聚類性能。在權值相同且測試數據較少的情況下，初始中心點的選取對最終的聚類結果影響不大，這表明基于權值的K-means算法具有良好的穩定性。

為驗證進一步不同算法的聚類效果，對原有的數據集進行擴容，不同擴容倍率下聚類算法的誤差平方和如圖7所示。

圖7 不同擴容倍數下的誤差平方和Fig.7 MSE with different expansion times

由圖7可知，隨著數據集擴容倍數的增長，SPWK-means的聚類誤差增加趨勢小于K-means算法和基于權值的K-means算法。在數據集擴大的情況下，初始聚類中心點選取的優劣程度將決定最終的聚類性能。

3.2.2 性能分析

為了檢驗算法的執行效率，對20 000個測試數據進行算法的時間復雜度分析，并行聚類部分執行時間，如圖8所示。

圖8 不同并行度下的算法執行時間Fig.8 Algorithm execution time with different parallelism

隨著算法并行度的增加，聚類模型執行的時間優化幅度減少。這是因為增加算法的并行度能充分利用空閑線程，提高運行效率。同時，并行度為4時的算法運行時間小于并行度為8的時間，這是由于隨著并行度的提高，運行節點之間的數據傳輸會消耗資源。

采用加速比Speedup和擴展比E測試并行K-means算法的并行化性能，加速比Speedup和擴展比E的公式為：

(7)

(8)

式中：Ts為單節點進行運算消耗的時間；Tp為p個節點進行運算所消耗的時間。

通過聚類算法的串行執行時間與并行執行時間的比率來判斷并行效果，不同聚類算法的加速比如圖9所示。

圖9 不同并行度下聚類算法的加速比Fig.9 Speedup of clustering algorithm with different parallelism

在不同并行度下，文中提出的SPWK-means算法加速比優于其他聚類算法。添加節點后，處理速度變快，但加速比未能符合線性增長。

文中通過對數據集的規模進行擴展，比較SPWK-means算法在不同節點數量下的擴展比，如表3所示。

表3 SPW K-means聚類算法的擴展比Table 3 The expansion ratio of SPW K-means clustering algorithm

Spark框架更加適合大量數據的處理，當數據量足夠大時，集群并行化能夠有效提高聚類算法的速度，數據集越大，并行效果越明顯。這是因為數據量增加，節點更容易發揮它的計算能力，節點利用率提高。而隨著節點的增加，擴展比未能線性增加。這是因為在集群上運行時，平臺啟動，任務調動與數據通信等因素會影響聚類算法的運行。

4 結語

文中針對綜合能源服務潛在客戶的精準識別問題，整合了近期的客戶信息，建立客戶識別數據庫；基于流式動態聚類的思想優化初始聚類中心的選取，分析了客戶的不同標簽并用標簽的映射權值來衡量對價值的影響；基于分布式內存計算框架Spark進行并行化聚類，達到了綜合能源服務潛在客戶精準識別的目的。

文中將改進后的K-means聚類算法在集群上并行運行，比較聚類的準確率。通過比較不同并行度下的算法執行時間、加速比、并行度，驗證并行化計算的高效性。結果表明基于Spark平臺的改進K-means算法不僅能夠有效利用閑置CPU內核的運算能力縮短訓練建模時間，且能根據各類標簽對客戶價值的優化調節映射權值提高分類的精度。針對海量數據集，調節聚類算法的并行度可以減少算法執行時間，這說明該算法具有良好的擴展性。但基于Spark框架的K-means聚類算法本身具有局限性，未來如何在不同場景下對聚類算法進行并行化設計有待進一步實踐。