基于共享最近邻的客户交易数据聚类算法

李 遥，荀亚玲

(太原科技大学 计算机科学与技术学院，山西 太原 030024)

客户细分是电子商务和零售领域关注的重要内容之一，利用企业积累的海量客户交易数据，分析客户行为，进行合理的客户细分，有助于企业详尽地了解消费者，在激烈的市场竞争中脱颖而出。客户细分传统方式是利用客户年龄、性别等一般属性进行客户细分，但数据收集较难，细分效果并不理想。聚类分析是数据挖掘中的重要方法之一，使同一个簇中的对象尽可能相似，不同簇之间的对象尽可能相异。利用客户交易数据聚类分析，得到同一个簇中的客户拥有更相似的消费习惯，获得了更优异的客户细分效果。但客户之间的相似性度量和客户聚类分配等，是客户交易数据聚类分析面临的主要问题。

针对客户细分聚类分析，Kuo等人提出一种客户细分聚类算法，利用历史交易数据进行客户细分，但细分效果并不理想；
Tsai等人提出一种基于遗传算法的客户细分方法，依据交易行为划分客户簇并给出合适的营销建议；
Lu等人提出一种基于神经网络的客户细分算法，利用迭代计算减少簇间相关系数，实现客户细分；
Hsu等人提出一种客户交易数据聚类算法，将客户交易数据组织成树形结构，并利用层次聚类进行客户细分；
Yu等人提出一种基于随机子空间技术的客户交易数据聚类算法，获得了比较准确的结果；
Holy等人分析药店交易数据并提出一种基于遗传算法的商品聚类算法；
Chen等人提出一种从客户交易数据中细分客户的PurTreeClust聚类算法，将每个客户的交易记录组织成一棵交易树，并定义一种新型的度量方式PurTree距离，更好地反映了两棵交易树之间的距离，但在聚类分配过程中，仅将交易树分配到最近的聚类中心点所属类簇，并未考虑近邻点的影响，容易出现错误的聚类结果。

利用客户交易数据聚类分析，正确地进行聚类分配，可获得更加准确的聚类分簇，得到同一个簇中的客户拥有更相似的消费习惯，有利于企业制定更加精准的营销策略。但PurTreeClust在聚类分配过程中，仅将交易树分配到最近的聚类中心点所属类簇，容易出现错误的聚类结果。对此，该文提出一种基于共享最近邻的客户交易数据聚类算法。该算法在聚类分配时，考虑到了交易树之间的共享最近邻信息，不会将交易树直接分配给最近聚类中心所属类簇，有效地解决交易树错误分配问题，并改善了客户细分效果。最后采用六个真实的客户交易数据集进行实验，验证了该算法的有效性，并可以发现更加清晰紧凑的客户细分类簇。

客户细分是指企业根据客户之间的相似性程度，将客户划分成不同的群体，同群体内的客户消费需求相近，不同群体内的客户消费需求差异较大。与客户细分传统方式相比，利用客户交易数据聚类分析，能够更客观地反映不同客户群体的消费需求，有利于营销人员制定更精准的营销策略，提升企业效益。参照文献[14,16]的相关概念定义如下：

定义1(PurTree距离):设一个大小为

n

的交易树集合，

H

(Φ)表示交易树高度，

C

(

φ

)表示交易树中节点

v

的全部孩子节点，则交易树与交易树之间的PurTree距离定义为：

(1)

其中，

β

为节点

v

的权重，公式为：

β

=

(2)

其中，

ω

是

l

层的权重，公式为：

(3)

定义2(共享最近邻):对于数据集

D

中的任意点

i

和点

j

，设点

i

的

k

近邻是Γ(

i

)，点

j

的

k

近邻是Γ(

j

)，则点

i

和点

j

的共享最近邻是它们的公共部分，定义为：SNN(

i

,

j

)=Γ(

i

)∩Γ(

j

)

(4)

定义3(共享近邻相似度):假设点

i

和点

j

是数据集

D

中的任意不同点，它们的共享近邻相似度定义为：

(5)

其中，

d

是点

i

和点

j

的距离。定义4(局部密度):假设数据集

D

中的任意点

i

，

L

(

i

)={

x

,

x

,…,

x

}是与点

i

相似度最高的

k

个交易树集合。那么，点

i

的局部密度定义为：

(6)

定义5(分离距离):假设点

i

和点

j

是数据集D中的任意不同点，点

j

的局部密度大于点

i

的局部密度，点

i

的分离距离定义如下：

(7)

局部密度最高的点的分离距离，是其他所有点中最高的分离距离。

定义6(从属点)：假设点

i

已被分配到簇A，而点

j

还未被分配，如果点

i

和点

j

满足公式8，则交易树

j

是簇A的从属点。|SNN(

i

,

j

)|≥

k/

2

(8)

定义7(可能从属点)：假设点

i

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

j

还未被分配，如果点

i

和点

j

满足公式9，则点

j

是簇A的可能从属点。0<|SNN(

i

,

j

)|<

k/

2

(9)

PurTreeClust算法根据定义(1)计算交易树之间的PurTree距离后，先利用CoverTree寻找聚类中心所在层的所有节点集合

Q

；
然后计算集合

Q

中节点的局部密度、分离距离和分离密度；
其次筛选集合

Q

中分离密度最大的前

K

个交易树，作为聚类中心；
最后将剩余节点分配到距离最近的聚类中心所在的聚类簇，完成聚类。

尽管PurTreeClust可以比较高效地完成客户交易数据的聚类，但PurTreeClust在聚类分配时，只是将客户交易树分配给距离最近的聚类中心所属类簇，容易出现错误分配的情况。如图1所示，点1和点3分别是不同类簇的聚类中心，按照PurTreeClust的分配思想，因为点2距离点3更近，因此会将点2分配给点3所属类簇，但很明显，点2应该分配给点1所属类簇，出现了错误分配的现象。

图1 PurTreeClust错误分配的情况

出现PurTreeClust错误分配的主要原因是在聚类分配时，将客户交易树直接分配给距离最近的聚类中心所属类簇，没有考虑到交易树的近邻影响。在聚类分配时，可考虑到客户交易树之间的共享最近邻信息，不会将客户交易树直接分配给最近聚类中心所属类簇。

(10)

聚类分配时，首先分配类簇的从属点。由定义6可知，类簇的从属点公式为|SNN(

i

,

j

)|≥

k/

2，即点

i

和点

j

各自的

k

近邻中，有一半以上为两者的共享最近邻，则认为点

i

和点

j

属于同一个类簇，点

j

一定属于点

i

所属类簇。由定义7可知，类簇的可能从属点公式为0<|SNN(

i

,

j

)|<

k/

2，即某未分配点

j

与任意类簇中已分配点

i

的共享最近邻个数满足公式(9)时，则认为点

i

和点

j

有可能属于同一个类簇，即未分配点

j

是已分配点

i

所属类簇的可能从属点。分配可能从属点时，若该未分配点的多个近邻被分配到同一个类簇，那么该未分配点也应该被分配到此类簇。

依据上一章节中的聚类分配策略，给出了PurTreeClust局部密度和分离距离的计算方法，避免了PurTreeClust错误分配的问题。其基本思想：首先利用定义4和定义5计算局部密度和分离距离；
然后从聚类中心出发，依据近邻信息先分配类簇的从属交易树，再分配类簇的可能从属交易树。Snn-PurTreeClust聚类算法的伪代码，详见算法1～算法3。

在算法1中，首先计算交易树之间的PurTree距离，然后计算客户交易树的局部密度、分离距离和分离密度，通过分离密度筛选聚类中心。分配客户交易树时，依据交易树的近邻分配情况，利用算法2和算法3分配客户交易树。

在算法2中，首先将所有聚类中心压入队列，从聚类中心出发，判断该聚类中心的

k

近邻是否满足公式|SNN(

i

,

j

)|≥

k/

2，若满足则将该近邻交易树分配到该类簇，并将该近邻交易树压入队列。算法2通过聚类中心向外扩散，找到各聚类簇所有的从属交易树，并将其分配到对应的聚类簇，得到初步的聚类结果。在算法3中，观察每一个未分配交易树的近邻分配情况，如果发现多个近邻被分配到同一个聚类簇中，那么该未分配交易树也有可能被分配到这个聚类簇。首先建立一个矩阵，矩阵的行代表未分配交易树，列代表聚类簇。通过一次循环，找到矩阵中的最大值，该最大值的行代表当前最需要被分配的交易树，列代表该未分配交易树的所属类簇，将其分配到该聚类簇中。如果一次循环后未找到最需要被分配的交易树，则增大近邻数

k

，扩大搜索范围。

算法1：Snn-PurTreeClust聚类算法

输入：客户交易树集合

Q

，近邻数

k

，簇数

m

输出：聚类结果Φ={

C

,

C

,…,

C

}

算法开始

计算交易树之间的PurTree距离

计算交易树之间的共享近邻相似度；

for each

q

∈

Q

do计算

q

的局部密度den(

q

);计算

q

的分离距离sdis(

q

);计算

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

);

算法结束

算法2：AssignSubTree(客户交易树集合

Q

，聚类中心集合

U

，近邻数

k

，簇数

m

)输出：初步聚类结果Φ={

C

,

C

,…,

C

}

算法开始

初始化空队列

P

，将所有聚类中心压入队列

P

；
while

P

非空 do弹出队列头元素

p

；
for all

p

的邻居交易树

n

doif

n

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

p

,

n

)|≥

k

/2 then将

n

分配到

p

所在的簇；
将

n

压入队列；

end if

end for

end while

算法结束

算法3：AssignPossSubTree(客户交易树集合

Q

，聚类中心集合

U

，近邻数

k

，簇数

m

)输出：最终聚类结果Φ={

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个交易树分配到col聚类簇；

else

k

=

k

+1;

end if

end while

算法结束

假设有

n

棵客户交易树，近邻数为

k

，聚类簇数为

m

。由上述算法描述可知，交易树之间的PurTree距离时间复杂度为

O

(

n

)，共享近邻相似度、局部密度和分离距离的时间复杂度分别为

O

(

kn

)、

O

(

kn

)和

O

(

n

)，筛选聚类中心集合时间复杂度为

O

(

n

log

n

)，算法2与算法3的时间复杂度分别为

O

(

mn

)和

O

((

k

+

m

)

n

)，因此Snn-PurTreeClust算法总的时间复杂度为

O

((

k

+

m

)

n

)。

为验证Snn-PurTreeClust(SPTC)算法的聚类效果，实验采用6个真实数据集对文中算法进行测试和评价，并与PTC、DBSCAN、2种谱聚类算法和3种凝聚层次聚类算法进行了对比分析。

在表1所示的6个真实交易数据集中，D1、D2、D3是3个超市交易数据集，分别包含795个客户的9 995笔交易记录、795个客户的9 995笔交易记录、1 179个客户的51 200笔交易记录。D4、D5、D6是从kaggle比赛一年的历史交易数据中构建的3个子集，该数据集一共包括30多万个客户的3.49亿笔交易记录。

表1 6个真实交易数据

采取与PurTreeClust同样的方法确定最佳的聚类簇数，首先选定了14组簇数

k

，在D2上运行Snn-PurTreeClust算法，并计算了间距统计量值，结果如图2。可以看出，当γ={10,+∞}时，Gap值接近甚至小于0，说明这两个参数无法找到簇类结构。当γ={0，0.2，0.5，1}时，Gap在

k

=4时陡然增加，因此为了更好地揭示D2数据集的聚类结构，选用γ=0.5，

k

=4且近邻数

m

=28来进行下列部分实验。

图2 Snn-PurTreeClust在D2上六种聚类结果的Gap值

为了更加直观地观测Snn-PurTreeClust算法的聚类效果，利用PurTreeClust算法中聚类结果的表示方式，将聚类结果绘制成图，如图3所示。将同一类簇中的交易树安置在一起，让其紧挨着，并且使行与列以相同的顺序表示交易树，图中深色表示较小的距离，浅色表示较大的距离。从图中可以清晰地观测到，当

k

=4且

γ

={0.2，0.5，1}时，Snn-PurTreeClust算法均可以发现更加紧凑清晰的类簇，PurTreeClust算法均不能发现较紧凑清晰的类簇。经过上述对比，可以验证Snn-PurTreeClust算法在不同参数下均可以发现较紧凑清晰的类簇，具有更好的伸缩性，聚类效果比PurTreeClust算法更优秀。

图3 PTC与SPTC在D2上的聚类结果

为了进一步检验Snn-PurTreeClust算法的聚类效果，将Snn-PurTreeClust算法与六种聚类算法进行对比，所有算法均使用PurTree距离，其中参数

γ

=0

.

5，簇数

k

=4。六种聚类算法的结果如图4所示。从图中可以看出，DBSCAN算法可以发现较清晰紧凑的类簇，其余五种算法均没有发现清晰紧凑的类簇，由此可说明，Snn-PurTreeClust算法具有较好的聚类效果，可以准确发现比较清晰紧凑的类簇。

图4 六种聚类算法在D2上的聚类结果(γ=0.5,k=4)

采用6个数据集来比较Snn-PurTreeClust算法与之前七种聚类算法的聚类效果。在本实验中，八种聚类算法均使用PurTree距离，其中参数γ设置为{0,0.2,0.5,1,10,+∞}。选定同样14组

k

值来运行除DBSCAN外的其他七种算法。对于每一种算法的聚类结果，分别计算簇内离散度log(

W

(

k

))，结果如表2所示。由表2可知，Snn-PurTreeClust算法在6个数据集上的聚类结果均具有较低的簇内离散度log(

W

(

k

))，说明Snn-PurTreeClust可发现更紧凑的聚类簇，与其他七种聚类算法相比，Snn-PurTreeClust算法的聚类效果更优异。

表2 八种算法在6个数据集上的平均簇内离散度比较(粗体为最佳结果)

利用客户交易数据聚类分析，可体现同簇客户拥有的相似消费习惯，从而获得了良好的客户细分效果。利用交易树之间的共享最近邻信息，该文提出一种客户交易数据聚类算法，可有效地发现更加紧凑清晰的类簇，避免了交易树错误分配，并通过6个客户交易数据集上的实验验证了该算法的有效性。未来如何降低Snn-PurTreeClust算法的时间代价有待进一步研究。

猜你喜欢 细分聚类密度 六大趋势引领扫地机器人细分市场蓬勃发展消费电子(2022年6期)2022-08-25基于数据降维与聚类的车联网数据分析应用汽车实用技术(2022年4期)2022-03-07基于模糊聚类和支持向量回归的成绩预测华东师范大学学报（自然科学版）(2019年5期)2019-11-11购买一个度假产品海峡旅游(2017年9期)2017-09-19基于密度的自适应搜索增量聚类法电子技术与软件工程(2016年23期)2017-03-06“密度”练习中学生数理化·八年级物理人教版(2015年12期)2016-01-25密度的应用趣谈中学生数理化·八年级物理人教版(2015年12期)2016-01-25密度的不变性与可变性中学生数理化·八年级物理人教版(2015年12期)2016-01-25市场细分中的市场泛化策略法制与社会(2009年5期)2009-09-28三种经典网格细分算法的研究与分析中小企业管理与科技·下旬刊(2009年12期)2009-06-21

推荐访问:近邻 算法 客户