基于共享最近鄰的客戶交易數(shù)據(jù)聚類算法

李 遙，荀亞玲

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

0 引 言

客戶細(xì)分是電子商務(wù)和零售領(lǐng)域關(guān)注的重要內(nèi)容之一，利用企業(yè)積累的海量客戶交易數(shù)據(jù)，分析客戶行為，進(jìn)行合理的客戶細(xì)分，有助于企業(yè)詳盡地了解消費(fèi)者，在激烈的市場(chǎng)競(jìng)爭(zhēng)中脫穎而出。客戶細(xì)分傳統(tǒng)方式是利用客戶年齡、性別等一般屬性進(jìn)行客戶細(xì)分，但數(shù)據(jù)收集較難，細(xì)分效果并不理想。聚類分析是數(shù)據(jù)挖掘中的重要方法之一，使同一個(gè)簇中的對(duì)象盡可能相似，不同簇之間的對(duì)象盡可能相異。利用客戶交易數(shù)據(jù)聚類分析，得到同一個(gè)簇中的客戶擁有更相似的消費(fèi)習(xí)慣，獲得了更優(yōu)異的客戶細(xì)分效果。但客戶之間的相似性度量和客戶聚類分配等，是客戶交易數(shù)據(jù)聚類分析面臨的主要問(wèn)題。

針對(duì)客戶細(xì)分聚類分析，Kuo等人提出一種客戶細(xì)分聚類算法，利用歷史交易數(shù)據(jù)進(jìn)行客戶細(xì)分，但細(xì)分效果并不理想；Tsai等人提出一種基于遺傳算法的客戶細(xì)分方法，依據(jù)交易行為劃分客戶簇并給出合適的營(yíng)銷建議；Lu等人提出一種基于神經(jīng)網(wǎng)絡(luò)的客戶細(xì)分算法，利用迭代計(jì)算減少簇間相關(guān)系數(shù)，實(shí)現(xiàn)客戶細(xì)分；Hsu等人提出一種客戶交易數(shù)據(jù)聚類算法，將客戶交易數(shù)據(jù)組織成樹形結(jié)構(gòu)，并利用層次聚類進(jìn)行客戶細(xì)分；Yu等人提出一種基于隨機(jī)子空間技術(shù)的客戶交易數(shù)據(jù)聚類算法，獲得了比較準(zhǔn)確的結(jié)果；Holy等人分析藥店交易數(shù)據(jù)并提出一種基于遺傳算法的商品聚類算法；Chen等人提出一種從客戶交易數(shù)據(jù)中細(xì)分客戶的PurTreeClust聚類算法，將每個(gè)客戶的交易記錄組織成一棵交易樹，并定義一種新型的度量方式PurTree距離，更好地反映了兩棵交易樹之間的距離，但在聚類分配過(guò)程中，僅將交易樹分配到最近的聚類中心點(diǎn)所屬類簇，并未考慮近鄰點(diǎn)的影響，容易出現(xiàn)錯(cuò)誤的聚類結(jié)果。

利用客戶交易數(shù)據(jù)聚類分析，正確地進(jìn)行聚類分配，可獲得更加準(zhǔn)確的聚類分簇，得到同一個(gè)簇中的客戶擁有更相似的消費(fèi)習(xí)慣，有利于企業(yè)制定更加精準(zhǔn)的營(yíng)銷策略。但PurTreeClust在聚類分配過(guò)程中，僅將交易樹分配到最近的聚類中心點(diǎn)所屬類簇，容易出現(xiàn)錯(cuò)誤的聚類結(jié)果。對(duì)此，該文提出一種基于共享最近鄰的客戶交易數(shù)據(jù)聚類算法。該算法在聚類分配時(shí)，考慮到了交易樹之間的共享最近鄰信息，不會(huì)將交易樹直接分配給最近聚類中心所屬類簇，有效地解決交易樹錯(cuò)誤分配問(wèn)題，并改善了客戶細(xì)分效果。最后采用六個(gè)真實(shí)的客戶交易數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證了該算法的有效性，并可以發(fā)現(xiàn)更加清晰緊湊的客戶細(xì)分類簇。

1 客戶細(xì)分和聚類分析

客戶細(xì)分是指企業(yè)根據(jù)客戶之間的相似性程度，將客戶劃分成不同的群體，同群體內(nèi)的客戶消費(fèi)需求相近，不同群體內(nèi)的客戶消費(fèi)需求差異較大。與客戶細(xì)分傳統(tǒng)方式相比，利用客戶交易數(shù)據(jù)聚類分析，能夠更客觀地反映不同客戶群體的消費(fèi)需求，有利于營(yíng)銷人員制定更精準(zhǔn)的營(yíng)銷策略，提升企業(yè)效益。參照文獻(xiàn)[14,16]的相關(guān)概念定義如下：

定義1(PurTree距離):設(shè)一個(gè)大小為

n

的交易樹集合，

H

(Φ)表示交易樹高度，

C

(

φ

)表示交易樹中節(jié)點(diǎn)

v

的全部孩子節(jié)點(diǎn)，則交易樹與交易樹之間的PurTree距離定義為：

(1)

其中，

β

為節(jié)點(diǎn)

v

的權(quán)重，公式為：

β

=

(2)

其中，

ω

是

l

層的權(quán)重，公式為：

(3)

定義2(共享最近鄰):對(duì)于數(shù)據(jù)集

D

中的任意點(diǎn)

i

和點(diǎn)

j

，設(shè)點(diǎn)

i

的

k

近鄰是Γ(

i

)，點(diǎn)

j

的

k

近鄰是Γ(

j

)，則點(diǎn)

i

和點(diǎn)

j

的共享最近鄰是它們的公共部分，定義為：SNN(

i

,

j

)=Γ(

i

)∩Γ(

j

)

(4)

定義3(共享近鄰相似度):假設(shè)點(diǎn)

i

和點(diǎn)

j

是數(shù)據(jù)集

D

中的任意不同點(diǎn)，它們的共享近鄰相似度定義為：

(5)

其中，

d

是點(diǎn)

i

和點(diǎn)

j

的距離。定義4(局部密度):假設(shè)數(shù)據(jù)集

D

中的任意點(diǎn)

i

，

L

(

i

)={

x

,

x

,…,

x

}是與點(diǎn)

i

相似度最高的

k

個(gè)交易樹集合。那么，點(diǎn)

i

的局部密度定義為：

(6)

定義5(分離距離):假設(shè)點(diǎn)

i

和點(diǎn)

j

是數(shù)據(jù)集D中的任意不同點(diǎn)，點(diǎn)

j

的局部密度大于點(diǎn)

i

的局部密度，點(diǎn)

i

的分離距離定義如下：

(7)

局部密度最高的點(diǎn)的分離距離，是其他所有點(diǎn)中最高的分離距離。

定義6(從屬點(diǎn))：假設(shè)點(diǎn)

i

已被分配到簇A，而點(diǎn)

j

還未被分配，如果點(diǎn)

i

和點(diǎn)

j

滿足公式8，則交易樹

j

是簇A的從屬點(diǎn)。|SNN(

i

,

j

)|≥

k/

2

(8)

定義7(可能從屬點(diǎn))：假設(shè)點(diǎn)

i

已被分配到簇A，而交易樹

j

還未被分配，如果點(diǎn)

i

和點(diǎn)

j

滿足公式9，則點(diǎn)

j

是簇A的可能從屬點(diǎn)。0<|SNN(

i

,

j

)|<

k/

2

(9)

PurTreeClust算法根據(jù)定義(1)計(jì)算交易樹之間的PurTree距離后，先利用CoverTree尋找聚類中心所在層的所有節(jié)點(diǎn)集合

Q

；然后計(jì)算集合

Q

中節(jié)點(diǎn)的局部密度、分離距離和分離密度；其次篩選集合

Q

中分離密度最大的前

K

個(gè)交易樹，作為聚類中心；最后將剩余節(jié)點(diǎn)分配到距離最近的聚類中心所在的聚類簇，完成聚類。

2 共享最近鄰與聚類分配策略

盡管PurTreeClust可以比較高效地完成客戶交易數(shù)據(jù)的聚類，但PurTreeClust在聚類分配時(shí)，只是將客戶交易樹分配給距離最近的聚類中心所屬類簇，容易出現(xiàn)錯(cuò)誤分配的情況。如圖1所示，點(diǎn)1和點(diǎn)3分別是不同類簇的聚類中心，按照PurTreeClust的分配思想，因?yàn)辄c(diǎn)2距離點(diǎn)3更近，因此會(huì)將點(diǎn)2分配給點(diǎn)3所屬類簇，但很明顯，點(diǎn)2應(yīng)該分配給點(diǎn)1所屬類簇，出現(xiàn)了錯(cuò)誤分配的現(xiàn)象。

圖1 PurTreeClust錯(cuò)誤分配的情況

出現(xiàn)PurTreeClust錯(cuò)誤分配的主要原因是在聚類分配時(shí)，將客戶交易樹直接分配給距離最近的聚類中心所屬類簇，沒有考慮到交易樹的近鄰影響。在聚類分配時(shí)，可考慮到客戶交易樹之間的共享最近鄰信息，不會(huì)將客戶交易樹直接分配給最近聚類中心所屬類簇。

(10)

聚類分配時(shí)，首先分配類簇的從屬點(diǎn)。由定義6可知，類簇的從屬點(diǎn)公式為|SNN(

i

,

j

)|≥

k/

2，即點(diǎn)

i

和點(diǎn)

j

各自的

k

近鄰中，有一半以上為兩者的共享最近鄰，則認(rèn)為點(diǎn)

i

和點(diǎn)

j

屬于同一個(gè)類簇，點(diǎn)

j

一定屬于點(diǎn)

i

所屬類簇。由定義7可知，類簇的可能從屬點(diǎn)公式為0<|SNN(

i

,

j

)|<

k/

2，即某未分配點(diǎn)

j

與任意類簇中已分配點(diǎn)

i

的共享最近鄰個(gè)數(shù)滿足公式(9)時(shí)，則認(rèn)為點(diǎn)

i

和點(diǎn)

j

有可能屬于同一個(gè)類簇，即未分配點(diǎn)

j

是已分配點(diǎn)

i

所屬類簇的可能從屬點(diǎn)。分配可能從屬點(diǎn)時(shí)，若該未分配點(diǎn)的多個(gè)近鄰被分配到同一個(gè)類簇，那么該未分配點(diǎn)也應(yīng)該被分配到此類簇。

3 共享最近鄰與客戶交易數(shù)據(jù)聚類算法

依據(jù)上一章節(jié)中的聚類分配策略，給出了PurTreeClust局部密度和分離距離的計(jì)算方法，避免了PurTreeClust錯(cuò)誤分配的問(wèn)題。其基本思想：首先利用定義4和定義5計(jì)算局部密度和分離距離；然后從聚類中心出發(fā)，依據(jù)近鄰信息先分配類簇的從屬交易樹，再分配類簇的可能從屬交易樹。Snn-PurTreeClust聚類算法的偽代碼，詳見算法1～算法3。

在算法1中，首先計(jì)算交易樹之間的PurTree距離，然后計(jì)算客戶交易樹的局部密度、分離距離和分離密度，通過(guò)分離密度篩選聚類中心。分配客戶交易樹時(shí)，依據(jù)交易樹的近鄰分配情況，利用算法2和算法3分配客戶交易樹。

在算法2中，首先將所有聚類中心壓入隊(duì)列，從聚類中心出發(fā)，判斷該聚類中心的

k

近鄰是否滿足公式|SNN(

i

,

j

)|≥

k/

2，若滿足則將該近鄰交易樹分配到該類簇，并將該近鄰交易樹壓入隊(duì)列。算法2通過(guò)聚類中心向外擴(kuò)散，找到各聚類簇所有的從屬交易樹，并將其分配到對(duì)應(yīng)的聚類簇，得到初步的聚類結(jié)果。在算法3中，觀察每一個(gè)未分配交易樹的近鄰分配情況，如果發(fā)現(xiàn)多個(gè)近鄰被分配到同一個(gè)聚類簇中，那么該未分配交易樹也有可能被分配到這個(gè)聚類簇。首先建立一個(gè)矩陣，矩陣的行代表未分配交易樹，列代表聚類簇。通過(guò)一次循環(huán)，找到矩陣中的最大值，該最大值的行代表當(dāng)前最需要被分配的交易樹，列代表該未分配交易樹的所屬類簇，將其分配到該聚類簇中。如果一次循環(huán)后未找到最需要被分配的交易樹，則增大近鄰數(shù)

k

，擴(kuò)大搜索范圍。

算法1：Snn-PurTreeClust聚類算法

輸入：客戶交易樹集合

Q

，近鄰數(shù)

k

，簇?cái)?shù)

m

輸出：聚類結(jié)果Φ={

C

,

C

,…,

C

}

算法開始

計(jì)算交易樹之間的PurTree距離

計(jì)算交易樹之間的共享近鄰相似度；

for each

q

∈

Q

do計(jì)算

q

的局部密度den(

q

);計(jì)算

q

的分離距離sdis(

q

);計(jì)算

q

的分離密度sden(

q

)=den(

q

)*sdis(

q

);

end for

篩選聚類中心集合

U

={

q

∈

Q

:?

q

?

U

,sden(

q

)>sden(

q

)}，使得|

U

|=

m

;AssignSubTree(

Q

,

U

,

k

,

m

);AssignPossSubTree(

Q

,

U

,

k

,

m

);

算法結(jié)束

算法2：AssignSubTree(客戶交易樹集合

Q

，聚類中心集合

U

，近鄰數(shù)

k

，簇?cái)?shù)

m

)輸出：初步聚類結(jié)果Φ={

C

,

C

,…,

C

}

算法開始

初始化空隊(duì)列

P

，將所有聚類中心壓入隊(duì)列

P

；while

P

非空 do彈出隊(duì)列頭元素

p

；for all

p

的鄰居交易樹

n

doif

n

未被分配到任何簇且滿足公式|SNN(

p

,

n

)|≥

k

/2 then將

n

分配到

p

所在的簇；將

n

壓入隊(duì)列；

end if

end for

end while

算法結(jié)束

算法3：AssignPossSubTree(客戶交易樹集合

Q

，聚類中心集合

U

，近鄰數(shù)

k

，簇?cái)?shù)

m

)輸出：最終聚類結(jié)果Φ={

C

,

C

,…,

C

}

算法開始

while 有交易樹未被分配 do

建立分配矩陣，矩陣行代表未分配交易樹，矩陣列代表聚類簇；for all 未分配交易樹

p

dofor all

p

的鄰居交易樹

q

do使矩陣行為

q

，矩陣列為

p

的值+1；

end for

end for

篩選矩陣

M

中的最大值max；

if max > 0 then

記錄max所在的矩陣行row和矩陣列col；

將第row個(gè)交易樹分配到col聚類簇；

else

k

=

k

+1;

end if

end while

算法結(jié)束

假設(shè)有

n

棵客戶交易樹，近鄰數(shù)為

k

，聚類簇?cái)?shù)為

m

。由上述算法描述可知，交易樹之間的PurTree距離時(shí)間復(fù)雜度為

O

(

n

)，共享近鄰相似度、局部密度和分離距離的時(shí)間復(fù)雜度分別為

O

(

kn

)、

O

(

kn

)和

O

(

n

)，篩選聚類中心集合時(shí)間復(fù)雜度為

O

(

n

log

n

)，算法2與算法3的時(shí)間復(fù)雜度分別為

O

(

mn

)和

O

((

k

+

m

)

n

)，因此Snn-PurTreeClust算法總的時(shí)間復(fù)雜度為

O

((

k

+

m

)

n

)。

4 實(shí)驗(yàn)結(jié)果分析

為驗(yàn)證Snn-PurTreeClust(SPTC)算法的聚類效果，實(shí)驗(yàn)采用6個(gè)真實(shí)數(shù)據(jù)集對(duì)文中算法進(jìn)行測(cè)試和評(píng)價(jià)，并與PTC、DBSCAN、2種譜聚類算法和3種凝聚層次聚類算法進(jìn)行了對(duì)比分析。

在表1所示的6個(gè)真實(shí)交易數(shù)據(jù)集中，D1、D2、D3是3個(gè)超市交易數(shù)據(jù)集，分別包含795個(gè)客戶的9 995筆交易記錄、795個(gè)客戶的9 995筆交易記錄、1 179個(gè)客戶的51 200筆交易記錄。D4、D5、D6是從kaggle比賽一年的歷史交易數(shù)據(jù)中構(gòu)建的3個(gè)子集，該數(shù)據(jù)集一共包括30多萬(wàn)個(gè)客戶的3.49億筆交易記錄。

表1 6個(gè)真實(shí)交易數(shù)據(jù)

采取與PurTreeClust同樣的方法確定最佳的聚類簇?cái)?shù)，首先選定了14組簇?cái)?shù)

k

，在D2上運(yùn)行Snn-PurTreeClust算法，并計(jì)算了間距統(tǒng)計(jì)量值，結(jié)果如圖2。可以看出，當(dāng)γ={10,+∞}時(shí)，Gap值接近甚至小于0，說(shuō)明這兩個(gè)參數(shù)無(wú)法找到簇類結(jié)構(gòu)。當(dāng)γ={0，0.2，0.5，1}時(shí)，Gap在

k

=4時(shí)陡然增加，因此為了更好地揭示D2數(shù)據(jù)集的聚類結(jié)構(gòu)，選用γ=0.5，

k

=4且近鄰數(shù)

m

=28來(lái)進(jìn)行下列部分實(shí)驗(yàn)。

圖2 Snn-PurTreeClust在D2上六種聚類結(jié)果的Gap值

為了更加直觀地觀測(cè)Snn-PurTreeClust算法的聚類效果，利用PurTreeClust算法中聚類結(jié)果的表示方式，將聚類結(jié)果繪制成圖，如圖3所示。將同一類簇中的交易樹安置在一起，讓其緊挨著，并且使行與列以相同的順序表示交易樹，圖中深色表示較小的距離，淺色表示較大的距離。從圖中可以清晰地觀測(cè)到，當(dāng)

k

=4且

γ

={0.2，0.5，1}時(shí)，Snn-PurTreeClust算法均可以發(fā)現(xiàn)更加緊湊清晰的類簇，PurTreeClust算法均不能發(fā)現(xiàn)較緊湊清晰的類簇。經(jīng)過(guò)上述對(duì)比，可以驗(yàn)證Snn-PurTreeClust算法在不同參數(shù)下均可以發(fā)現(xiàn)較緊湊清晰的類簇，具有更好的伸縮性，聚類效果比PurTreeClust算法更優(yōu)秀。

圖3 PTC與SPTC在D2上的聚類結(jié)果

為了進(jìn)一步檢驗(yàn)Snn-PurTreeClust算法的聚類效果，將Snn-PurTreeClust算法與六種聚類算法進(jìn)行對(duì)比，所有算法均使用PurTree距離，其中參數(shù)

γ

=0

.

5，簇?cái)?shù)

k

=4。六種聚類算法的結(jié)果如圖4所示。從圖中可以看出，DBSCAN算法可以發(fā)現(xiàn)較清晰緊湊的類簇，其余五種算法均沒有發(fā)現(xiàn)清晰緊湊的類簇，由此可說(shuō)明，Snn-PurTreeClust算法具有較好的聚類效果，可以準(zhǔn)確發(fā)現(xiàn)比較清晰緊湊的類簇。

圖4 六種聚類算法在D2上的聚類結(jié)果(γ=0.5,k=4)

采用6個(gè)數(shù)據(jù)集來(lái)比較Snn-PurTreeClust算法與之前七種聚類算法的聚類效果。在本實(shí)驗(yàn)中，八種聚類算法均使用PurTree距離，其中參數(shù)γ設(shè)置為{0,0.2,0.5,1,10,+∞}。選定同樣14組

k

值來(lái)運(yùn)行除DBSCAN外的其他七種算法。對(duì)于每一種算法的聚類結(jié)果，分別計(jì)算簇內(nèi)離散度log(

W

(

k

))，結(jié)果如表2所示。由表2可知，Snn-PurTreeClust算法在6個(gè)數(shù)據(jù)集上的聚類結(jié)果均具有較低的簇內(nèi)離散度log(

W

(

k

))，說(shuō)明Snn-PurTreeClust可發(fā)現(xiàn)更緊湊的聚類簇，與其他七種聚類算法相比，Snn-PurTreeClust算法的聚類效果更優(yōu)異。

表2 八種算法在6個(gè)數(shù)據(jù)集上的平均簇內(nèi)離散度比較(粗體為最佳結(jié)果)

5 結(jié)束語(yǔ)

利用客戶交易數(shù)據(jù)聚類分析，可體現(xiàn)同簇客戶擁有的相似消費(fèi)習(xí)慣，從而獲得了良好的客戶細(xì)分效果。利用交易樹之間的共享最近鄰信息，該文提出一種客戶交易數(shù)據(jù)聚類算法，可有效地發(fā)現(xiàn)更加緊湊清晰的類簇，避免了交易樹錯(cuò)誤分配，并通過(guò)6個(gè)客戶交易數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了該算法的有效性。未來(lái)如何降低Snn-PurTreeClust算法的時(shí)間代價(jià)有待進(jìn)一步研究。