《大数据架构和算法实现之路:电商系统的技术实战》——2.4 案例实践

本节书摘来自华章计算机《大数据架构和算法实现之路:电商系统的技术实战》一书中的第2章,第2.4节,作者 黄 申,更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.4 案例实践

2.4.1 使用R进行K均值聚类

在实践部分,我们仍然采用之前介绍的R和Mahout。首先是基于R的快速测试。由于之前在分类的R实战中,已经进行了很多相关的预处理,因此这里可以直接从listing_all_knn开始。K均值聚类的函数kmeans()非常简单,只需指定被聚类的数据框(data frame)和聚类数量k即可。此处较难决定的是聚类的数量k,一种简单的经验值是总样本数一半的平方根。这里的样本数为28?000多,一半是14?000,因此取平方根的近似值100:

> listing_clusters <- kmeans(listing_all_knn, 100)

将聚类的结果转化为数据框,然后随机抽取一个聚类的内容。这里选取ID为37的聚类:

> listing_clusters_test <- as.data.frame(listing_clusters$cluster)

> sample_ids <- vector(mode="numeric", length=28706)
> for(i in 1:28706) {sample_ids[i] <- i}
> listing_clusters_test$sample_ids <- sample_ids

> listing_clusters_test_subset <- subset(listing_clusters_test, listing_clusters_
test[, 1] == 37)
> listing_test_subset <- listing[listing_clusters_test_subset[, 2], ]

查看这个聚类所包含的样本数量:

> dim(listing_test_subset)
[1] 482   4

查看482个样本的前20个:

> head(listing_test_subset, 20)
    ID    Title CategoryID CategoryName
1   22785 samsung 三星 galaxy tab3 t211 1g 8g wifi+3g 可 通话 平板 电脑 gps 300万像素 白色    15    电脑
2   19436 samsung 三星 galaxy fame s6818 智能手机 td-scdma gsm 蓝色 移动 定制 机    14    手机
40  19971 samsung 三星 galaxy siv 盖世 4 s4 i9500 双 四 核 手机 大陆 行货 全国 联保    14    手机
68  22574 samsung 三星 n5100 galaxy note 8.0 exynos 4412 2g 16g 四 核心 8寸 平板 电脑    15    电脑
111 19552 samsung 三星 galaxy mega i9158p 3g 智能 手机 td-scdma gsm 四 核 1.2ghz 处理器    14    手机
116 22422 samsung 三星 np270e5u-k02cn 15.6英寸 笔记本电脑 双 核 1007u 4g 500g dvd 刻录 曜 月 黑    15    电脑
155 19920 三星 samsung 三星 galaxy s5 g9008v 4g 智能手机 td-lte td-scdma gsm    14    手机
352 21883 samsung 三星 np450r4v-k02cn 14寸 笔记本电脑 i3-3110m 4g 500g 曜 月 黑    15    电脑
417 20439 samsung 三星 g3819 智能手机 cdma2000 gsm 双模 双 待 单 通 电信 版    14    手机
466 20687 三星 galaxy note 3 n9008v 4g 手机    14    手机
502 20858 samsung 三星 galaxy note ii n719 电信 版 5.5寸 双模 双 待 四 核 智能手机    14    手机
536 21639 samsung 三星 galaxy tab3 t311 8英寸 1.5ghz 双 核 android 白 棕色 可选    15    电脑
539 19916 samsung 三星 galaxy s4 i9500 16g 版 3g 智能手机 wcdma gsm 5.0寸 屏 双 四 核 cpu 智能手机    14    手机
569 21628 samsung 三星 galaxy tab3 t311 8.0英寸 平板 电脑 双 核 16g 通话 功能 500万 摄像头 白色    15    电脑
618 20397 samsung 三星 galaxy note3 n9008v 16g 版 4g 智能手机 5.7英寸 屏 安 卓 4.3 四 核    14    手机
643 21670 samsung 三星 galaxy note10.1 wlan 版 p600 10英寸 平板 电脑 32g    15    电脑
679 21643 samsung 三星 np270e5u-k03cn 15.6寸 笔记本电脑 双 核 1007u 4g 500g d 刻 神秘 银    15    电脑
759 19393 samsung 三星 galaxy s4 i959 双模 双 待 智能手机 cdma2000 gsm 皓 月白 电信 定制 机 esr 
          高亮 清 透 手机 贴 膜 透明 屏幕 保护 贴 适用于 三星 galaxy s4 i9500 i9502 i9508 i959    14    手机
794 22598 samsung 三星 galaxy tab3 p5200 10寸 平板 电脑 双 核 1.6ghz 16gb 通话 功能 300w 像素 白色    15    电脑
809 20407 samsung 三星 galaxy note 3 n9006 3g 手机 炫 酷 黑 wcdma gsm 5.7英寸 屏    14    手机
>

你会发现这是一个关于三星手机的聚类,其中样本ID为466(listing-segmented-shuff?led.txt文件中的第467行),其商品ID为20687,标题为“三星galaxy note 3 n9008v 4g手机”,比较其他相似商品明显偏短。那么,是否存在可能利用该聚类,为这个商品丰富一下其标题呢?下一步,查看这个聚类中经常出现的热门词有哪些。将listing_test_subset的Title字段转为文档和文档-单词矩阵:

> listing_corpus_test_subset <- VCorpus(VectorSource(listing_test_subset$Title))
> listing_dtm_test_subset <- DocumentTermMatrix(listing_corpus_test_subset, 
control=list(wordLengths=c(0,Inf)))

利用tm扩展包的f?indFreqTerms()函数,发现词频达到10次的单词如下:

> findFreqTerms(listing_dtm_test_subset, 10)
  [1]    "1.2g"    "1.2ghz"    "1.6ghz"    "10.1"    "10.1寸"    "1007u"    "14寸"    "15.6寸"    "16g"
    "16gb"    "2"    "2g"    "3"    "32g"    "3g"
 [16]    "3g-"    "4.0"    "4.0英寸"    "4.1"    "4.3英寸"    "4g"    "500g"    "8.0"    "8gb"
    "8英寸"    "android"    "cdma"    "cdma2000"    "cpu"    "d"
 [31]    "dvd"    "galaxy"    "gps"    "gsm"    "i8268"    "i9500"    "ii"    "mega"    "n5100"
    "n5110"    "n7100"    "n9008v"    "note"    "note3"    "s-pen"
 [46]    "s3"    "s4"    "s5"    "s7568i"    "samsung"    "ssd"    "tab3"    "td-lte"    "td-scdma"
    "trend"    "wcdma"    "wifi"    "三星"    "全国"    "内存"
 [61]    "刻"    "刻录"    "功能"    "卓"    "双"    "双模"    "可"    "四"    "处理器"
    "大"    "安"    "官方"    "定制"    "屏"    "屏幕"
 [76]    "平板"    "待"    "手机"    "显卡"    "智能"    "智能手机"    "曜"    "月"    "机"
    "标配"    "核"    "正品"    "炫"    "版"    "现货"
 [91]    "电信"    "电脑"    "白"    "白色"    "盖世"    "移动"    "笔记本电脑"    "系统"    "联保"
    "联通"    "蓝牙"    "行货"    "通话"    "酷"    "黑"
[106]    "黑色"

结果非常有意思,你会受到不少启发。例如,“智能手机”“16gb”“3g”,这些词都没有出现在样本466的标题中。如果仔细研究“三星galaxy note 3 n9008v 4g手机”这款手机,你很可能会发现这几个词都是相关的,是非常棒的描述。可惜,原有的样本标题却未能包含。如此一来,搜索“智能手机”“16gb”“3g”等词的时候这个样本商品就无法被找到。

再看个例子,这次我们观察ID为28的聚类:

> listing_clusters_test_subset <- subset(listing_clusters_test, listing_clusters_test[, 1] == 28)
> listing_test_subset <- listing[listing_clusters_test_subset[, 2], ]
> dim(listing_test_subset)
[1] 196   4

在其中我们也能发现一些标题很短的商品,例如:

> listing_test_subset[40:50,]
    ID Title CategoryID CategoryName
4742   10562   我们 时代 休闲 零食 澳洲 夏 果 夏威夷 果 奶油味 168gx3 袋    8    坚果
4933   10305   清 之 坊 夏威夷 果 200 3袋 牛 奶油味 澳洲 夏 果 坚果 休闲 零食 干果 特产 果实
               坚果 小食    8    坚果
5013   10350   良 品 铺子 新品 良 品 山 核桃仁 150g 美国进口 原料 碧 根 果 坚果 休闲 零食    8    坚果
5049    9689   三只 松鼠 碧 根 果 210gx2 包 奶油味 长寿 果 休闲 零食 坚果 美国 山核桃 be1    8    坚果
5397   10322   嘀嗒 猫 坚果 干果 特产 美国 山核桃 长寿 果 奶 香 碧 根 果 208g    8    坚果
5467    9742   饕 哥 澳洲 夏威夷 果 200g 3袋 奶油味 坚果 小吃 零食 特产    8    坚果
5572   11114   松鼠 请客 夏威夷 果 奶油 夏威夷 果 送 开 果 器 坚果 年货 零食 200g 2袋    8    坚果
5771   10384   百草 味 坚果 零食 碧 根 果 218g 袋装 奶油味 长寿 果 美国 山核桃    8    坚果
5878    9870   新 农 哥 坚果 炒货 夏威夷 果 168克 休闲 零食    8    坚果
6183   11373   良 品 铺子 夏威夷 果 盐 焗 味 280g 澳洲 坚果 夏 果 坚果 休闲 零食    8    坚果
6215   11192   零度 果 坊 买 1箱 送 1箱 老年 混合 坚 果仁 原 味 礼盒 罐装 650克 碧 根 果 
               核桃 松子 休闲 零食 品 袋装    8    坚果

其中,样本ID为5878的样本,其商品ID为9870,标题为“新 农 哥 坚果 炒货 夏威夷 果 168克 休闲 零食”。来看看同一个聚类中,其他相似商品一般是怎样描述的:

> listing_corpus_test_subset <- VCorpus(VectorSource(listing_test_subset$Title))
> listing_dtm_test_subset <- DocumentTermMatrix(listing_corpus_test_subset, control=list(wordLengths=c(0,Inf)))
> findFreqTerms(listing_dtm_test_subset, 10)
 [1]    "180g"    "200g"    "218g"    "2袋"    "休闲"    "农"    "剥"    "办公室"    "包"    "原"    "口器"
    "口水"    "味"    "品"    "哥"    "器"    "坚果"    "壳"    "夏威夷"    "奶"    "奶油"    "奶油味"
[23]    "小吃"    "山核桃"    "干果"    "年货"    "开"    "新"    "新货"    "松鼠"    "果"    "果仁"    "核桃"
    "根"    "澳洲"    "炒货"    "特产"    "百草"    "碧"    "罐装"    "美国"    "袋"    "袋装"    "趣"
[45]    "送"    "长寿"    "零"    "零食"    "食"    "食品"    "香"    "香味"
>

如果这个夏威夷坚果是美国进口的,而且是奶油口味的,那么错过了“美国”“奶油味”这样的关键词,也是非常可惜的。看了这两例子,试想一下,如果将这些数据提供给商家,让他们进行合理的关键词搜索引擎优化,那么将对顾客搜索的体验、卖家的销售转化率,以及平台的最终收益将会产生何等可观的价值?

不过,和KNN相仿,K均值聚类算法最大的问题就是运行时间,计算复杂度通常是O (nkl),n是样本总数,k是聚类数量,l是迭代次数。即使样本的数量只有2万多,期望的聚类数量也只有100,在单台iMac上运行R的代码,时间也达到了数十分钟。为此,我们将试图从Mahout那里找到更好的解决方案。

2.4.2 使用Mahout进行K均值聚类

1.通过命令行进行聚类
和分类任务相似,有的时候我们希望进行大规模的并行处理。这里同样是在Mahout平台上开展相关的实验。Mahout中的聚类算法同样实现了K-Means算法,以及针对其所做的优化和扩展。对于K-Means,Mahout提供了基本的基于内存的实现和基于Hadoop Map/Reduce的实现。首先我们还是从单机的内存版开始。由于之前基于词频tf的向量已经准备就绪,我们可以直接使用mahout命令的kmeans选项:

[huangsean@iMac2015:/Users/huangsean/Coding]mahout kmeans -i /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-vec/tf-
vectors -c /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-
shuffled-kcentroids -o /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-kclusters -dm org.apache.mahout.common.distance.Euclidean
DistanceMeasure -k 100 -x 10 -cl -ow -xm sequential
MAHOUT_LOCAL is set, so we don't add HADOOP_CONF_DIR to classpath.
MAHOUT_LOCAL is set, running locally
...
17/01/18 20:35:13 INFO driver.MahoutDriver: Program took 14644 ms (Minutes: 0.24
406666666666665)

其中,-c指定的目录,是用于存储系统随机挑选的质心的。而-o指定的目录则用于存储聚类的结果,org.apache.mahout.common.distance.EuclideanDistanceMeasure将向量相似度的计算设置为欧式距离。最后,-k指定了聚类的个数,-x指定了最大的迭代次数,以免过久的循环计算。运行结束后,可以看到如图2-3所示的聚类结果文件。其中cluster-0~9目录代表了10次迭代,每个目录均包含了某次迭代中的结果,而part-00028表示某轮迭代中第29个聚类的内容,每个迭代的目录中包含了一共100个这样的文件。

《大数据架构和算法实现之路:电商系统的技术实战》——2.4 案例实践

由于这种聚类结果对我们来说并不可读,所以还需要clusterdump选项来导出可读的结果:

[huangsean@iMac2015:/Users/huangsean/Coding]mahout clusterdump -dt sequencefile
-d /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-
shuffled-vec/dictionary.file-* -i /Users/huangsean/Coding/data/BigDataArchitecture
AndAlgorithm/listing-segmented-shuffled-kclusters/clusters-*-final -o /Users/huangsean/
Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-kclusters-
dump.txt -b 1 -n 20
MAHOUT_LOCAL is set, so we don't add HADOOP_CONF_DIR to classpath.
MAHOUT_LOCAL is set, running locally
...
17/01/18 20:36:07 INFO driver.MahoutDriver: Program took 624 ms (Minutes: 0.0104)

其中-dt和-d参数指定了字典的类型和存储位置,让你可以看到聚类样本的文本信息。而-i指定了最后一轮迭代的目录,-o指定了存放导出结果的文件。将-b设置为1是为了跳过聚类成员的冗长内容,-n设置为20是为了导出聚类中的更多热词。打开导出后的文件listing-segmented-shuff?led-kclusters-dump.txt,在其底部可以看到这样的内容:

:V
    Top Terms: 
        戴尔                                      =>   1.012448132780083
        dell                                    =>  0.9336099585062241
        显                                       =>  0.5103734439834025
        4g                                      =>  0.5020746887966805
        独                                       =>  0.4979253112033195
        500g                                    =>  0.4190871369294606
        2g                                      =>  0.4190871369294606
        笔记本电脑                                   =>  0.3236514522821577
        电脑                                      => 0.27800829875518673
        dvd                                     => 0.24066390041493776
        win8                                    => 0.23236514522821577
        1g                                      => 0.21991701244813278
        核                                       =>  0.1991701244813278
        触                                       => 0.18672199170124482
        dvdrw                                   => 0.17842323651452283
        14英寸                                    => 0.17427385892116182
        固态                                      => 0.17427385892116182
        主机                                      => 0.17012448132780084
        刻录                                      => 0.16597510373443983
        越                                       => 0.16597510373443983

从热词可以看出,这是一个和电脑商品有关的聚类。完整的listing-segmented-shuff?led-kclusters-dump.txt文件位于:

https://github.com/shuang790228/BigDataArchitectureAndAlgorithm/blob/master/Clustering/Mahout/listing-segmented-shuff?led-kclusters-dump.txt

从理论知识的介绍中,你不难发现K-Means的参数选择是个问题。首先K-Means需要在执行聚类之前就有明确的群组个数设置,但在处理大部分问题时,这一点事先很难知道,一般需要通过多次试验才能找出一个最优的k值;此外,由于算法在最开始采用的是随机选择初始质心的方法,所以算法对噪音和异常点的容忍能力较差。一旦噪声点在最开始被选作群组的初始质心,就会对后面整个聚类过程带来很大的负面影响。因此,Mahout还实现了Canopy算法,用于优化K-Means聚类的效果。Canopy聚类算法的基本原则是:首先应用低成本的近似的相似度计算方法将数据高效地分为多个“Canopy”(Canopy之间可以有重叠的部分),然后采用严格的距离计算方式准确地计算在同一Canopy中的点,将它们分配到最合适的群组中。Canopy聚类算法经常用作K-Means聚类算法的预处理,用来找到合适的k值和群组质心。为了实现这一步,可以执行如下的操作:

[huangsean@iMac2015:/Users/huangsean/Coding]mahout canopy -i /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-vec/tf-vectors -o /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-kcentroids-canopy -dm org.apache.mahout.common.distance.EuclideanDistanceMeasure -t1 5.5 -t2 5 -ow
MAHOUT_LOCAL is set, so we don't add HADOOP_CONF_DIR to classpath.
MAHOUT_LOCAL is set, running locally
...
17/01/18 20:37:39 INFO driver.MahoutDriver: Program took 45502 ms (Minutes: 0.7583666666666666)

其中t1和t2是Canopy算法的距离参数,要求t1大于t2。可适当调整两者的值,以产生合适的k值。同样可以使用mahout命令的clusterdump查看Canopy初始聚类的结果,可以看到这里将产生76个初始聚类:

[huangsean@iMac2015:/Users/huangsean/Coding]mahout clusterdump -dt sequencefile -d /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-vec/dictionary.file-* -i /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-kcentroids-canopy/clusters-*-final -o /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-kcentroids-canopy-dump.txt -b 1 -n 20
MAHOUT_LOCAL is set, so we don't add HADOOP_CONF_DIR to classpath.
MAHOUT_LOCAL is set, running locally
...
17/01/18 20:38:36 INFO driver.MahoutDriver: Program took 825 ms (Minutes: 0.01375)

再次使用kmeans选项进行聚类:

[huangsean@iMac2015:/Users/huangsean/Coding]mahout kmeans -i /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-vec/tf-vectors -c /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-kcentroids-canopy/clusters-0-final -o /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-kclusters-canopy -dm org.apache.mahout.common.distance.EuclideanDistanceMeasure -x 10 -ow -xm sequential
MAHOUT_LOCAL is set, so we don't add HADOOP_CONF_DIR to classpath.
MAHOUT_LOCAL is set, running locally
...
17/01/18 20:39:45 INFO driver.MahoutDriver: Program took 13907 ms (Minutes: 0.23178333333333334)

这里需要特别注意的是,不要再设置-k选项,否则刚刚通过Canopy生成的质心将被随机质心所覆盖。最后,使用clusterdump选项导出聚类的内容:

[huangsean@iMac2015:/Users/huangsean/Coding]mahout clusterdump -dt sequencefile -d /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-vec/dictionary.file-* -i /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-kclusters-canopy/clusters-*-final -o /Users/huangsean/Coding/data/BigDataArchitectureAndAlgorithm/listing-segmented-shuffled-kcluster-canopy-dump.txt -b 1 -n 20
MAHOUT_LOCAL is set, so we don't add HADOOP_CONF_DIR to classpath.
MAHOUT_LOCAL is set, running locally
...
17/01/18 20:40:11 INFO driver.MahoutDriver: Program took 549 ms (Minutes: 0.00915)

完整的聚类内容文件位于:

https://github.com/shuang790228/BigDataArchitectureAndAlgorithm/blob/master/Clustering/Mahout/listing-segmented-shuff?led-kcluster-canopy-dump.txt

如果要在多机环境中使用Mahout的聚类算法,具体步骤和1.3.6节介绍的类似,首先搭建Hadoop环境,将数据上传至HDFS中,然后运行类似的聚类算法命令。具体实现过程这里就不再赘述了。

2.实时聚类?

“小明哥,为什么要给“实时聚类”加个问号呢?”

“大宝,如果你仔细研读一下,就会发现聚类算法所解决的问题都是批量数据的处理,计算量很大,因此常常需要在Hadoop平台上进行并行化,而不会涉及实时性的服务。”

“那么,如何解决商家能提出的关键词SEO问题呢?他们很可能需要即时地获取结果,例如输入一个商品的标题,系统很快就能提示可能缺失了哪些重要的关键词。”大宝问道。

“这是个很好的问题。不过,你再思考一下自己刚刚所说的,就会发现这个问题变成了聚类的一个子问题,和KNN分类更像。普通的聚类是要将所有的数据样本,划分到一个大家都长得很相似的组中,而你刚刚描述的需求是为单个数据样本,找到和它最相似的其他样本,商家并不关心除了所输入商品之外的其他商品之间的关系,这为实时服务提供了可能。不过,在n个样本中找出相似度最高的k个样本,常规解法的时间复杂度仍然达到了
O (nlogk),这还没有包括向量之间相似度计算的开销。”

对于在线服务,性能确实是个大问题啊!”

“不要着急,也不是说这个需求就没有办法解决了。我们完全可以利用现有的一些系统进行优化的实现。在之后介绍推荐系统的时候,其中有一个关键步骤和这个任务非常相近,我们会在那个时候进行详细的阐述。”

上一篇:Oracle跨服务器访问使用dblink


下一篇:[LeetCode] Rotate List 旋转链表