本节书摘来自华章计算机《大数据架构和算法实现之路：电商系统的技术实战》一书中的第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个这样的文件。
由于这种聚类结果对我们来说并不可读，所以还需要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，在其底部可以看到这样的内容：
:VTop Terms: 戴尔 => 1.012448132780083dell => 0.9336099585062241显 => 0.51037344398340254g => 0.5020746887966805独 => 0.4979253112033195500g => 0.41908713692946062g => 0.4190871369294606笔记本电脑 => 0.3236514522821577电脑 => 0.27800829875518673dvd => 0.24066390041493776win8 => 0.232365145228215771g => 0.21991701244813278核 => 0.1991701244813278触 => 0.18672199170124482dvdrw => 0.1784232365145228314英寸 => 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)，这还没有包括向量之间相似度计算的开销。”
对于在线服务，性能确实是个大问题啊！”
“不要着急，也不是说这个需求就没有办法解决了。我们完全可以利用现有的一些系统进行优化的实现。在之后介绍推荐系统的时候，其中有一个关键步骤和这个任务非常相近，我们会在那个时候进行详细的阐述。”
