基于譜聚類算法的城市快遞客戶聚類研究

王長瓊,邱 杰,曹乜蜻,王艷麗

(武漢理工大學(xué) 物流工程學(xué)院,湖北 武漢 430063)

近年來，隨著城市化水平的不斷提高以及經(jīng)濟(jì)的快速發(fā)展，我國城市人口急劇上升，網(wǎng)購人數(shù)不斷增加。在現(xiàn)實(shí)的經(jīng)濟(jì)生活中，城市人口分布在城市的各個(gè)大街小巷，在地理位置上相對集中又整體分散，因此城市快遞客戶需求呈現(xiàn)出高度碎片化的特征[1-2]。針對以上特征，學(xué)者們提出對客戶進(jìn)行聚類分析，實(shí)現(xiàn)快遞物流企業(yè)配送資源的合理調(diào)度。覃文文等基于快遞客戶屬性進(jìn)行聚類分析，提出從快遞企業(yè)呼叫中心客戶信息庫中提取細(xì)分變量，通過k-means算法對客戶進(jìn)行聚類分析[3]。蹤鋒等運(yùn)用k-means算法從給定的數(shù)據(jù)中獲取數(shù)據(jù)對象之間有價(jià)值的關(guān)聯(lián)要素，將顧客信息進(jìn)行分組，描述顧客的購買模式，并進(jìn)行分類管理[4]。韓世蓮提出一種可以反映多種客戶需求屬性的模糊系統(tǒng)聚類方法進(jìn)行客戶分類，運(yùn)用智能加權(quán)對動(dòng)態(tài)屬性進(jìn)行集成，生成相應(yīng)的配送策略[5]。WANG 等認(rèn)為客戶聚類是降低物流網(wǎng)絡(luò)優(yōu)化復(fù)雜度的重要步驟，通過對相似客戶進(jìn)行分組，物流企業(yè)可降低運(yùn)營成本，提高客戶滿意度[6]。此外，為了對客戶進(jìn)行分類管理，學(xué)者們提出對配送區(qū)域進(jìn)行有效劃分。谷煒等設(shè)計(jì)了一種改進(jìn)的兩階段k-means聚類算法，實(shí)現(xiàn)對物流配送區(qū)域的均衡劃分[7]。GONZLEZRAMREZ等結(jié)合貪婪隨機(jī)自適應(yīng)搜索算法與禁忌搜索算法的基本原理提出一種啟發(fā)式算法，對集送貨的物流分區(qū)問題進(jìn)行研究[8]。

1 城市快遞客戶聚類指標(biāo)

隨著城市經(jīng)濟(jì)的發(fā)展，網(wǎng)購規(guī)模不斷擴(kuò)大，城市快遞配送難度加大，實(shí)現(xiàn)城市快遞客戶的有效聚類成為城市快遞市場發(fā)展的關(guān)鍵。客戶聚類是物流配送研究領(lǐng)域的基本問題，一般考慮客戶的地理位置、需求量及配送車輛負(fù)載量，這樣客戶聚類問題便可以簡化為物流配送路徑優(yōu)化、車輛調(diào)度優(yōu)化等問題。在進(jìn)行城市快遞配送中，客戶的消費(fèi)能力決定了配送人員和車輛的數(shù)量，客戶的地理位置直接影響配送的車輛路徑規(guī)劃。因此，在進(jìn)行城市快遞客戶聚類時(shí)，考慮客戶的消費(fèi)能力和地理位置，對城市快遞的人員和車輛數(shù)量確定和配送路徑的規(guī)劃具有十分重要的理論與現(xiàn)實(shí)意義。根據(jù)科學(xué)性、可行性原則，并考慮數(shù)據(jù)的可得性，建立客戶聚類指標(biāo)體系，如表1所示。

表1 客戶聚類指標(biāo)體系

(1)消費(fèi)能力?？蛻舻南M(fèi)能力可以反映出客戶的網(wǎng)購消費(fèi)能力[9]。客戶網(wǎng)購能力越強(qiáng)，網(wǎng)購產(chǎn)生的包裹越多，配送所需的人員和車輛就越多。將消費(fèi)能力相似的客戶進(jìn)行有效的聚類，更容易把握客戶所需的配送資源，制定最佳的人員和車輛調(diào)度策略?？蛻舻南M(fèi)能力主要體現(xiàn)在快遞網(wǎng)點(diǎn)數(shù)量、人均消費(fèi)支出、電子商務(wù)交易額、快遞包裹量和移動(dòng)互聯(lián)網(wǎng)用戶等方面。

(2)地理位置?？蛻艟垲惪紤]客戶地理位置是指將地理位置相近的客戶進(jìn)行聚類。客戶的地理位置反映了客戶在城市的分布情況，直接影響配送車輛的路徑規(guī)劃。在客戶聚類中，應(yīng)盡量把地理位置較近，快遞配送需求相似度高的客戶聚為一類。

2 城市快遞客戶聚類方法

譜聚類是從圖論中演化出來的算法，廣泛應(yīng)用于聚類分析中。譜聚類的基本思想是對樣本數(shù)據(jù)的Laplace矩陣進(jìn)行特征分解，利用Laplace矩陣特征向量數(shù)據(jù)特性，基于數(shù)據(jù)挖掘技術(shù)對其進(jìn)行聚類分析，形成具體的聚類方案。

2.1 基于譜聚類算法的聚類數(shù)目確定

2.1.1 構(gòu)建Laplace矩陣

Laplace矩陣也稱基爾霍夫矩陣，主要應(yīng)用在圖論中。作為圖的矩陣表示，Laplace矩陣由度矩陣和相似度矩陣之差構(gòu)成。

(1)數(shù)據(jù)標(biāo)準(zhǔn)化。6個(gè)指標(biāo)數(shù)據(jù)的量綱不同，數(shù)量級(jí)差也懸殊，因此采用min-max標(biāo)準(zhǔn)化方法對每類指標(biāo)的原始數(shù)據(jù)進(jìn)行預(yù)處理。

(1)

式中：Z*為標(biāo)準(zhǔn)化處理后的指標(biāo)值；Zmin為指標(biāo)數(shù)據(jù)的最小值；Zmax為指標(biāo)數(shù)據(jù)的最大值。

(2)相似度矩陣。相似度矩陣，也叫權(quán)重矩陣，能夠真實(shí)反映數(shù)據(jù)之間的相似關(guān)系。譜聚類算法中重要的一步是構(gòu)建相似度矩陣，要求相似數(shù)據(jù)點(diǎn)之間的差異盡可能小，相異數(shù)據(jù)點(diǎn)之間的差異盡可能大。預(yù)處理后的數(shù)據(jù)構(gòu)成的矩陣S為樣本空間，將矩陣S中每一個(gè)行向量視為圖的一個(gè)頂點(diǎn)，通過歐式距離定義客戶相似度矩陣W，生成基于相似度的無向圖G。

(2)

式中：wij為矩陣W中的元素，即圖G邊的權(quán)重；Si為矩陣S的第i行向量；Sj為矩陣S的第j行向量；W為n×n的矩陣，n為客戶總數(shù)。

(3)度矩陣。度矩陣D中的元素為相似度矩陣W第i邊的權(quán)重之和，其計(jì)算公式為：

(3)

(4)Laplace矩陣。圖G的非歸一化Laplace矩陣由度矩陣和相似度矩陣之差構(gòu)成，即L=D-W。

(4)

歸一化Laplace矩陣為：

(5)

式中：L和Ln分別為非歸一化Laplace矩陣和歸一化Laplace矩陣；Ln=D-1/2LD-1/2。

2.1.2 計(jì)算聚類數(shù)目

(1)計(jì)算Laplace矩陣的特征值和特征向量，并將特征值λ按從小到大排列，即λ1≤λ2≤…≤λn-1≤λn。

Lx=λx

(6)

式中：x為Laplace矩陣的特征向量；λ為Laplace矩陣的特征值。

(2)計(jì)算相對特征值差Δλk：

(7)

其中，λk為Laplace矩陣的第k個(gè)特征值,k≥2。

2.2 基于k-means算法的聚類方案確定

k-means算法是將樣本中各元素的距離作為衡量相似性的標(biāo)準(zhǔn)，對樣本中的元素進(jìn)行聚類分析，最終得出同一聚類中的對象相似度較高，而不同聚類中的對象相似度較小的聚類結(jié)果[10]。算法描述如下：①輸入聚類個(gè)數(shù)為k、數(shù)據(jù)對象為n的數(shù)據(jù)庫；②從n個(gè)數(shù)據(jù)對象任意選擇k個(gè)對象作為初始聚類中心；③計(jì)算每個(gè)對象與聚類中心的距離，并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分；④重新計(jì)算每個(gè)聚類的均值，并將其作為新的聚類中心；⑤循環(huán)步驟③和步驟④，當(dāng)每個(gè)聚類不再發(fā)生變化，則計(jì)算終止；⑥輸出滿足方差最小標(biāo)準(zhǔn)的k個(gè)聚類。

基于譜聚類算法確定客戶聚類數(shù)目k后，選取前k個(gè)最小特征值對應(yīng)的特征(列)向量，把k個(gè)特征(列)向量排列組成一個(gè)n×k的矩陣，構(gòu)造新的數(shù)據(jù)特征空間X=[υ1,υ2,…,υk]，將X的每一行看作一個(gè)樣本，運(yùn)用k-means算法進(jìn)行聚類，聚類結(jié)果映射到原數(shù)據(jù)空間，則每一行所屬的類別分別為原來n行數(shù)據(jù)所屬的類別，最終可確定具體的聚類方案。聚類后的客戶，同類中具有較大的相似性，不同類之間具有較小的相似性。充分識(shí)別各類客戶的快遞物流需求，針對各類客戶的特點(diǎn)，快遞物流企業(yè)可做出合理的人員配置和車輛調(diào)度。

3 算例分析

為了驗(yàn)證算法在客戶聚類中的有效性，以武漢市某區(qū)的36個(gè)街道的6個(gè)指標(biāo)數(shù)據(jù)為例來驗(yàn)證算法的可行性，具體數(shù)據(jù)如表2所示。

表2 武漢市某區(qū)36個(gè)街道的數(shù)據(jù)

續(xù)表2

3.1 聚類數(shù)目

根據(jù)式(7)計(jì)算前6個(gè)最小特征值的相對特征值差，根據(jù)Laplace矩陣的相對特征值差的最大值自動(dòng)確定客戶聚類數(shù)目。Laplace矩陣的客戶聚類數(shù)目如圖1所示。從圖1可以看出，當(dāng)k=4時(shí)，Laplace矩陣相對特征值差最大，故武漢市某區(qū)36個(gè)街道可分為4類。

圖1 Laplace矩陣的客戶聚類數(shù)目

3.2 聚類結(jié)果

根據(jù)Laplace矩陣相對特征值差確定聚類數(shù)目為4，選取前4個(gè)最小特征值對應(yīng)的特征(列)向量，把4個(gè)特征(列)向量排列組成一個(gè)36×4的矩陣，構(gòu)造新的數(shù)據(jù)特征空間X=[υ1,υ2,υ3,υ4]，將X的每一行看作一個(gè)樣本，運(yùn)用k-means算法進(jìn)行聚類，聚類結(jié)果如表3所示，聚類示意圖如圖2所示。

由表3可知，第一類有11條街道，第二類有5條街道，第三類有10條街道，第四類有10條街道。充分識(shí)別這4類客戶的物流需求，針對各類客戶的特點(diǎn)，快遞物流企業(yè)可合理地配置人員和調(diào)度車輛。

表3 k-means算法確定的具體聚類結(jié)果

圖2 算例中的聚類示意圖

4 結(jié)論