基于改進遺傳算法的客戶購買行為聚類

[摘 要] 針對電子商務客戶購買行為，構建客戶——商品矩陣，度量客戶購買行為相似度。基本遺傳算法存在一定的缺陷，本文提出一種改進的混合并行遺傳算法，結合k-means算法的高效性和局部搜索能力，以及并行遺傳算法的全局優化能力，并運用該算法對客戶購買行為聚類。實驗結果表明該方法在客戶行為聚類應用中具有較高的效率和精確度。

[關鍵詞] 并行遺傳算法 購買行為 k-means聚類

電子商務飛速發展，網站品種類繁多，客戶千姿百態，如何在海量的信息中找到客戶行為信息成為一個至關重要的問題。Irene S.Y. Kwan等人建立了客戶在線行為模型，有助于為B2C網站制定營銷計劃。客戶行為分析主要集中于客戶的基本面分析與客戶購買行為分析兩方面，本文主要研究客戶購買行為分析。

聚類可以根據客戶的某些屬性把大量的客戶分成不同的類，能有效地分析客戶購買行為。客戶行為聚類用于發現客戶偏好、客戶行為規律等信息，利用這些信息，有針對性地促銷和廣告。L.B.Romdhane等人用模糊C均值法對客戶聚類，并用反向傳播神經網絡方法構建了客戶模型，分析客戶行為。本文構建了客戶商品矩陣，用于度量客戶購買行為相似性。提出一種改進的混合遺傳算法用于客戶購買行為聚類，并通過實驗來證明了該方法的有效性。

一、購買行為相似性度量

客戶購買行為相似性度量是客戶行為聚類的基礎。Ching-Hsue Cheng用RFM模型作為客戶購買行為度量。RFM模型對客戶行為特征描述是間接的，張志宏等人提出不同客戶購買相同商品占總購買商品的比重作為購買行為相似度。本文構建客戶——商品關聯矩陣，對客戶購買行為進行相似性度量。

假設某電子商務網站共銷售n種商品，用Y表示商品的集合，

；在某段時間內有m個客戶在該網站購買了商品，用X表示這些客戶的集合， 。本文構建的客戶——商品關聯矩陣，主要利用客戶ID，購買商品編號，購買數量等信息。

1．構建客戶——商品關聯矩陣

以客戶ID為行，以商品ID為列，建立客戶——商品矩陣 ：

（1）

表示某段時間內客戶i購買商品j的數量。每一行向量表示客戶i對所有商品的購買情況；每一列向量表示所有用戶對商品j的購買情況。度量矩陣行向量的相似性，可以得到相似客戶群體。

2.相似性度量

相似度的有很多度量方法，一般向量的相似性函數的應用比距離測度更廣泛。本文采用夾角余弦公式，夾角余弦規范化了向量的長度，不會放大數據重要部分的作用。

（2）

表示不同客戶對所有商品的購買向量。

二、改進的混合并行遺傳算法

遺傳算法具有良好的全局搜索性質等特點，使得它在處理聚類方面的問題具有一定優勢。但應用實際表明，遺傳算法容易產生早熟，局部尋優能力較差，收斂速度慢等問題。針對這些問題，A.A. Javadi提出結合神經網絡和遺傳算法的混合算法，利用反向傳播神經網絡方法來改善遺傳算法的收斂效率。H. Mühlenbeina，和M. Schomisch研究了并行遺傳算法，并將其應用于函數優化。

本文提出一種改進的混合并行遺傳算法（hybrid parallel genetic algorithm，HPGA），并應用于客戶行為聚類。該算法結合k-means算法的高效性和局部搜索能力，以及并行遺傳算法的全局優化能力，針對客戶購買行為聚類對適應度函數，遺傳算子作了相應調整，通過種群內的遺傳、變異和種群間的進化、聯姻，使客戶行為聚類應用中具有較高的效率和精確度。

k-均值算法由于其簡單高校而被廣泛應用，但k-均值算法對初始聚類中心的敏感很大，極易陷入局部最優值。遺傳算法具有良好的全局搜索性質，但局部搜索能力較差，且容易早熟。并行遺傳算法各子種群并行進化，能有效提高算法運行速度和效率，有效避免了算法的早熟收斂。基于k-means算法和遺傳算法的優缺點，本文提出的混合并行遺傳算法。

1.編碼

在k均值聚類中，聚類個數不同將直接影響聚類的結果。因此本文采用遺傳算法來確定聚類中心數，其確定聚類中心數的方式是動態的，采用可變長染色體編碼方案，染色體長度即聚類個數，每個基因位(客戶ID)代表一個類的類中心。編碼形式為：

2.適應度函數

適應度函數表示了單個個體對于當前環境的適應程度，好的個體適應度相對較高，差的個體適應度則相對較低。適應度函數的定義如下：

（3）

k為聚類數目， 為類內相似度， 為類間相似度，計算公式分別為：

（4）

（5）

是類 中的樣本， 是分別是類 的中心。這個適應度函數會隨著類數目k的變化盡可能地提高類內的相似程度和類間的差異程度。

3.遺傳算子

本文遺傳算子采用用輪盤賭注選擇和最優保存策略。各個體的選擇概率為：

（6）

式中P為種群規模， 為個體i的適應度。

遺傳交叉算子計算采用單點交叉。從現有群體中按輪盤賭法選擇兩條染色體，分別隨機選擇兩條染色體交叉點位置，按概率 將兩條染色體的后半段互換并重新連接。變異算子采用基本位變異，即隨機選取染色體上一個基因位，按事先確定的變異概率 進行變異。在算法中，交叉概率 和變異概率 的取值會直接影響算法的收斂效果和遍歷性，交叉概率和變異概率越大，算法收斂性就較差；這兩個概率過小則搜索速度變慢并產生局部最優。基本遺傳算法是通過反復試驗來確定 和 。本文采用自適應遺傳算法確定交叉概率 和變異概率 。即當種群各個體適應度趨于一致或局部最優時， 和 增加；而當各個體適應度比較分散時， 和 減少。 計算公式如下：

（7）

（8）

和 分別表示交叉概率的下限和上限， 和 分別表示變異概率的下限和上限， 為每代的平均適應度值， 為種群中的最大適應度值， 為要進行變異的個體的適應度值， 為要交叉的兩個個體中的較大適應度值。

4.種群初始化

(1)設置種群規模 ，設置控制參數I值為1；

(2)如果 ，則轉(3)，否則結束初始化；

(3)隨機生成k個[1，m]之間的自然數，形成一條染色體；

(4)判斷染色體是否已經在種群中存在，如果存在則轉(3)，否則轉(5)；

（5）I=I+1；

（6）轉(2)。

5.算法終止條件

進化代數超過最大遺傳代數Q或運行過程中得到相同的最優結果次數連續超過某一閥值 ，則算法終止。

6.整個算法流程

(1)初始化種群。確定種群規模 ，隨機選擇客戶作為聚類中心，組成一個個體， 對個體進行編碼，客戶ID作為染色體基因；

(2)對每一個個體進行k均值處理。將每個數據對象分配到最近的聚類中心，等分配完畢后計算新的聚類中心 ；

(3)計算每個個體的適應度f，如果子代個體適應度大于其父代，則用子代個體替換父代個體；

(4)并行進化。每個種群各自進行選擇、交叉和變異。每代進化完成后，將兩種群中的精英個體交叉變異，并進行遺傳和進化，交叉變異個體中的優良個體替代適應度最差的個體；

(5)如果各種群達到停止標準轉(6)，否則轉(2)；

(6)在兩個種群中，選擇適應度最大的個體作為初始聚類中心，對客戶進行k-means聚類，得到最終聚類結果。

三、實驗

本文選擇某電子商務網站2010年11月1日至2011年12月31日的交易記錄，該電子商務網站主要銷售日常生活用品，該事件段內共計833種商品，65536條銷售記錄。數據處理采用matlab 7，算法采用Visual C++6.0進行開發，以多線程的方式模擬并行計算。

對初始數據進行預處理，共有1829個客戶，選擇總購買次數超過5次的商品共526件，提取客戶ID，商品ID及銷售數量構建1829x526客戶——商品矩陣。

本文以類內平均相似度和類間平均相似度兩個指標最為評價算法的標準。參數設置：并行種群數為2，種群規模 =100，遺傳代數Q=500， ， ， ， ，精英個體3。

比較k均值，遺傳算法，本實驗的算法聚類結果如下表：

聚類算法結果比較

從上述實驗結果分析可知，改進的混合并行遺傳算法在類內平均相似度和類間平均相似度上都優于一般的算法。從時間開銷看，IHPGA由于運用的并行遺傳，節省了開銷，提高了效率。

四、結束語

客戶行為分析的目的是保持客戶、發現潛在客戶，有針對性促銷。本文針對電子商務客戶購買行為，構建客戶——商品矩陣，度量客戶購買行為相似度，并提出一種改進的混合并行遺傳算法，結合k-means算法的高效性和局部搜索能力，以及并行遺傳算法的全局優化能力提高算法效率，并運用該算法對客戶購買行為聚類。實驗結果表明該方法在客戶行為聚類應用中具有較高的效率和精確度。

參考文獻：

[1] Irene S.Y. Kwan， Joseph Fong， H.K. Wong. An e-customer behavior model with online analytical mining for internet marketing planning Decision Support Systems， 2005， 41: 189–204

[2] L.B. Romdhane ， N. Fadhel， B. Ayeb. An efficient approach for building customer profiles from business data Expert Systems with Applications ，2010， 37:1573–1585

[3] Ching-Hsue Cheng， You-Shyang Chen. Classifying the segmentation of customer value via RFM model and RS theory. Expert Systems with Applications 2009， 36: 4176-4184

[4] 張志宏，寇紀淞，陳富贊，李敏強. 基于遺傳算法的顧客購買行為特征提取. 模式識別與人工智能，2010，23(2)：256-266

[5] 張宇，劉雨東，計 釗. 向量相似度測度方法. 聲學技術，2009，28(4)：532-536

[6] A.A. Javadi， R. Farmani， T.P. Tan. A hybrid intelligent genetic algorithm. Advanced Engineering Informatics， 2005， 19: 255–262

[7] H. Mühlenbeina， M. Schomischa， J. Bornb. The parallel genetic algorithm as function optimizer Parallel Computing， September 1991， 17: 619-632

[8] 徐家寧，張立文，徐素莉，李進. 改進遺傳算法的K-均值聚類算法研究. 微計算機應用，2010，31(4)：11-15

[9] 黃裕洋，金遠平. 一種基于余弦因子改進的混合聚類算法. 東南大學學報(自然科學版)， 2010，40(3)：496-499