经典聚类算法及在互联网络的应用

经典聚类算法及在互联网的应用

此处并不会列举每一种聚类(Clustering)算法，因为学术界Clustering算法如果真要细分，还真有很多变种。此处只会介绍几种在我近几年互联网工作生涯中实际碰到的具体问题， 以及如何使用Clustering算法解决这些问题。

一般来说，我们可以将Clustering认为是将出现的数据进行Data Segmentation，也就是经常说的哲理： 物以类聚。 从机器学习的观点来看， Clustering算是Unsupervised Learning，或者叫做Learning by Observation，根据观察到的情况进行Clustering。 因为形成簇的数据都被聚到一起，所以Clustering 方法也可以用来发现噪音或是异常点。

Clustering 算法大致可以分为以下几类（参见Data Mining Concepts and Techniques）：

1. Partitioning Methods：这是一类经典的，最简单的聚类方式，就是直接按照类内的点距离最近，类间距离足够远的原则进行数据Clustering。该类方法比较经典的方法有K-Means 和K-Medoids。下文中会以广告分段问题来具体介绍K-Means的实现（K-Medoids类似）
2. Hierachical Methods:层次Clustering算法，又大致分为bottom-up和top-down两种思路，bottom-up为自底向上，逐渐合并离得比较近的类以形成更大的类，top-down为一种divisive的思路，逐渐对离得比较远的类进行分裂。下文中会以如何合并搜索引擎中的同意，近义词词形成簇的的方式具体介绍bottom-up hierachical methods。
3. Density-based Methods：以上两种方法基本上都是在高维空间中将数据聚成球形的多个类的方法，却不能处理非球形的聚类，Density-based Methods就是解决非球形数据的聚类方法。
4. Model-based Methods：对数据进行建模，之后使用观察到的数据预估模型参数，比较经典的使用EM方法，先假设数据服从某种分布（例如k个高斯分布），并且这k个高斯分布由一系列隐随机变量决定。之后在E步预估这些隐随机变量，而在M步固定这些隐随机变量后，使用最大似然估计迭代得到最优参数。

文章以下内容将介绍3种聚类方法解决3个问题：

1. 使用K-Means方法对广告受众网民进行Data Segmentation。
2. 使用Bottom Up Hierachical Clustering方法对搜索引擎query进行聚类以进行流量推荐。
3. 使用EM方式寻找数据中的隐藏主体。

 使用K-Means方法对广告受众网民进行Data Segmentation

K-Means是一种球形的聚类，在二维空间中，类别会被聚成以圆心为中心的圆，三维空间中则会被聚成以球心为中心的球状簇（当然，这与选择的相似度度量有关，例如使用cosine计算归一化后的两个向量长度，就会变成计算二向量的夹角）

在K-Means算法运行前，有两个因素比较重要： 数据预处理和距离度量方法。具体距离度量参见博文相似度度量 ，数据预处理则包括数据归一化， 去除噪音等操作。

因为K-Means算法本身较为简单，此处直接给出Andrew Ng机器学习公开课教案中的伪代码：

其中uj为第j个簇的中心点，ci为第i条数据的簇类别。基本步骤就是遍历数据，每一轮迭代，先计算当前数据与哪个类中心最近，该条数据属于距离最近的簇，之后根据新计算出来的每条数据的类别，更新类中心。下图给出在指定数据上给出2个类的4轮迭代情况：

使用distortion function度量分类的好坏情况， distortion 越小越好，当然，一般distortion大小需要和类别 k 的数量间进行权衡。

应用： 虽然k-means堪称最简单的算法，但之前在实习时，在前东家还是用了一把，应用场景是使用MSN用户的注册信息（年龄，喜好，性别），以及MSN用户在 msn.com上经常访问的导航类别，搜索关键词等数据，使用决策树选出区分度较大的特征构成特征向量，使用L1-Norm进行归一化后，对特征向量进行Clustering。之后按Clustering向广告主售卖这些用户的pv。 该模式的优势是具有一定的兴趣定向作用。

右侧即为MSN展示广告。当然，该方法已经是2007年所使用的方法，现在相信MS已经使用更精准的方法了 。

该过程中尝试较多的是如何选择合适的类别数量k值，以及如何初始化初始类中心。当时迫于项目进度，k值最后根据经验并进行了粗略的搜索选择，初始类中心则使用在相同k值得情况下进行多次随机初始化Clustering

使用Bottom Up Hierachical Clustering方法对搜索引擎query进行聚类以进行流量推荐

例如在搜索引擎中， 很多网民的query意图的比较类似的，对这些query进行聚类，一方面可以使用类内部的词进行关键词推荐； 另一方面， 如果聚类过程实现自动化， 则也有助于新话题的发现；同时还有助于减少存储空间等。

例如：

训龙记国语  训龙记2 寻龙记  训龙记博克岛的骑手  驯龙记电影

骂人大全    骂人不带脏字的顺口溜    骂人带脏字越毒越好  骂人脏字的狠话

要设计层次聚类，就需要考虑一下几个因素及环节：

1. 使用何种聚类算法： top-down 还是bottom-up 还是其他
2. clusting的合并策略
3. 使用哪些特征
4. 如何度量距离
5. 使用何种评估标准对效果进行评估

确定以上5个因素后，聚类算法也就确定了。

聚类算法：考虑到实现的复杂度， 一开始我们就确定使用bottom-up的方式作为聚类策略；后续也就没有尝试top-down的方式。

clusting的合并策略：

一般有两类合并策略： 选取最相近的两个clustering进行合并；求连通分量。 因为寻找相近cluster的方式， 时间复杂度会达到O(n^2)， 所以最后决定使用连通分量。

特征： 我们使用字面特征及query在session中的共现特征； 例如， 对字面进行切词后的term(做适当过滤降维：idf太小则过滤)

距离函数， 尝试过cosine和jaccard后， 最终使用jaccard作为距离度量。

 也可关注微博： weibo.com

或是直接访问： http://semocean.com

广告： 长期社招推荐引擎，数据挖掘，机器学习，信息检索方向策略工程师，有意者可通过微博联系； 或直接将简历发至lihaibo@baidu.com