云计算比赛总结

2017年4月23日，今天为期近半年的云计算比赛终于落下了帷幕。尘埃落定，分完奖金，分完奖品，好像一切没有发生过一样，生活也慢慢步入了正轨。但是我总觉得，一切事情总得留下写什么值得记忆和回味的东西。在一切渐渐过去之后，比赛本身变得其实不那么重要，反而是那些看起来与比赛无关的细节更值得铭记。从前我一直觉得，有些事情体验了就好，但是我渐渐发现，体验过的东西几乎都特别的容易忘记，没有思考与总结的体验只能算的上是走马观花，我特别羡慕像杨振宁那样的学者，虽然身体渐渐衰老，但是他总能非常清楚的记得在某年某月某日，与某人发生过哪些对话。虽然我的记性不太好，但是我也希望我的经历能够不仅仅成为过去，而是成为自己一直受用的财富。

起因

其实参加这个比赛的原因非常搞笑，在上学期的一次大创项目的例会上，指导老师跟我们聊了聊项目的问题，发现没啥好聊的，然后话锋一转说，“哎？我听说最近有个云计算比赛，你们要不要参加看看，前几年某某老师带的队伍好像都拿了不错的名次，blabla。。。”，我们当然不敢表达什么反对意见了，然后就在我们的项目没啥进展的情况下，撂下手头的事开始搞这个云计算方面的事情。。。 然而尴尬的是，我们并没有人会scala，hadoop，spark这类搞分布式云计算常用的疙瘩，一切都得从头学起，但是我们其实也并没有太多的时间。因此拖着拖着，就过了春节。春节过来后，发现不能再拖了，就迎着头皮加班加点的搞了一个多礼拜，才稍微理清楚眉目。虽说是四人的小team，但是实际做起来就我跟某大佬两个人在做。比赛总共两道题，那就一人一道题，我负责基于kmeans聚类的大数据分类算法，大佬负责通用后缀树的构建算法。

研究

关于这个kmeans算法，其实spark的mllib里有一个kmeans的库。不过显然，这个在我们的数据集上跑的效率并不好，于是我们就参照大赛提供的一个名叫cluto的单机kmeans工具作为参照。里面有一些相关文档，因此我主要是参照这个进行处理。

问题描述

问题其实很简单，就是给定两个数据集，你给我用spark跑出这两个数据集的聚类结果。这两个数据集，一个是数目较多特征较少的稠密矩阵，另一个是数目较少特征较多的文本矩阵。初赛跑第一类数据，决赛跑第二类数据。然后评测的时候总和比较准确率(NMI)跟时间。

我的思路

照着cluto的意思，我就简单的利用spark mllib中的相关函数进行拼接处理。事实上mllib提供的kmeans库本身没有太大的毛病（感觉毛病其实有两点，后面会说），之所以在大多数情况下效果不是太好，我看主要是因为，人家在设计这个玩意的时候，压根就没打算让你直接套。你得根据你实际的数据集，进行相应的预处理，而这些预处理的手段他其实也在其他的模块里有提供，而且大部分都实现的没啥问题。问题的重点就在于我们如何去根据数据集去选择正确的预处理方式。 通常情况下，预处理的方式无非下面这几步：

1. 特征提取（降维）
2. 行列加权
3. 归一化

所谓特征提取，通常也就是用PCA，SVD这类算法，从高维数据中提取更有代表性的维度来讨论，从而加快运算速度。 所谓行列加权，通常是采用一些经验算法，比如IDF加权，将数据进“强化”，使其能更加突出主要维度的作用。 所谓归一化，很简单，就是消除各条数据尺度不同带来的影响。虽然很简单，但是也很重要，对结果的影响也不小。

不过上面的这些步骤也不能一概而论，比如有些数据集上，降维有可能导致数据丢失，行列加权会导致数据异常，归一化会导致主要维度丢失等等。因此mllib在设计的时候就没有将这些方法融入kmeans里面，而是分开来供大家选择，有针对性的使用。

没错，虽然答辩的时候吹的天花乱坠（其实也没啥干货。。。），但是实际操作的时候用的就是上面的三个步骤，自己几乎没有实现任何功能模块，完全调用mllib中的库。。。

除此预处理之外，就是些细节参数的选择了，主要包括下面几点：

1. 距离函数的选择
2. 初始化中心点的选择
3. 平均准确率与时间的抉择

mllib自带的kmeans模块有一个缺点就是他只支持了平方欧氏距离，虽然现在看起来，似乎所有的距离公式都可以某种程度上互相转换。但是简单的看，在很多情况下，不同的距离测度在不同数据集上的表现也不完全相同，因此更换一个合适的距离测度似乎是一个轻松讨巧的提高准确率的办法。我在实际操作中采用的是余弦距离，稍微修改下源码就可以办到。 初始化中心点的方法大多数情况采用其自带的kmeans++算法，准确率一般会提高一点。不过也不排除random更好的情况。 至于平均准确率与时间的抉择就十分有讲究了，我们比赛成绩说的过去的很大一部分原因就是这个抉择做的还算不错。我们知道在spark1.6以下的版本里，有一个参数叫runs，不过由于一些代码可维护性、执行效率等的原因，在高版本的spark里这个参数被取消了。这个参数曾经存在的意义在于，我们知道kmeans本身的初始点选择具有一定的随机性，那么每次聚类结果的准确率就不一定相同，有时好，有时不好。我们在比赛的时候显然希望尽可能的避免表现不好的情况，那么我们就可以通过运行多次数据，取代价函数最低的那组模型作为最终的模型，这个运行次数就是runs参数的意义。显然，这个参数并不能提高kmeans本身的准确率，而是通过时间，去换取准确率高的概率，减少准确率低的概率。这就是一个简单的“时间换准确率的想法”。与之对应的，也有用“准确率换时间的想法”，比如有许多队伍，在聚类时并不采用整个数据集，而是去进行采样，获取一些有代表性的数据，来做聚类，这样有的确会提高算法执行速度，但是也有降低准确率的可能。

一些问题

当然，我的算法是存在问题的。最突出的问题在于，在实际的运行中，我发现spark提供的kmeans算法并不能很好的并行计算，绝大多数的stage都集中在一个worker上。。，这是一个很尴尬的问题，他意味着这实际上就不是一个分布式程序。不过这个问题也不完全出于我，因为我采用的就是spark mllib中的kmeans实现。这个实现似乎在操作中有一些问题，导致几乎所有的数据都在一个worker上跑，我尝试采用了RangePartition来代替HashPartition，但是结果也并没有任何好转。情急之下我也就没有过多的考虑这个问题，就直接提交了代码。事实上如果这个问题解决了，那么运行时间应该能缩短成1/7左右，成绩排进前两名应该是没啥问题的。不过这或许就是差距所在吧。

结果

虽然总体上讲，在进入决赛的11支队伍里，我们在两道题上做的都不是很突出，但是由于我们两道题都比较稳定，没有出现短板，因此最后拿了第三名，低于南大PASA实验室的研究僧以及东北大学的队伍。相比之下，南师大的队伍虽然第二题全场最高，但是第一题却是倒数第二，混了个三等奖；东南大学的队伍，虽然第二题跟南大一样跑除了隐藏数据集，但是第一题同样扑街，也混了三等奖。。。 说起第一题的结果，其实也颇有争议，评委方认为这个聚类问题得综合考虑时间以及准确率来判分，但是实际操作中，为了防止高速低准确度混分情况的出现，在评价速度分的时候乘上了与准确率有关的系数，导致准确率的影响过大。我这种“时间换准确率”的做法就比较占便宜了，而那种“准确率换时间”的做法就吃了亏。。。