时雨小径 May the Spirit be with you

初窥Clustering(聚类)

为什么是窥呢, 因为基本都是在上班的时候偷偷摸摸地看的. —-题记

古谚道: 物以类聚,人以群分. 说明相似的人事物之间有着微妙的吸引力, 使得他们能够在某些维度上保持相对其他更近的距离. 这里对不同维度的解释是, 比如说具有相同背景技术的民工可能会聚集在同一个工地上, 这是一个空间上的接近; 又比如酷爱熬夜的大学生们基本能够在半夜2点保持在线, 这个可以看做是一个时间上的接近.

聚类的算法的应用是很广的, 讲几种通俗的吧, 比如说投放广告, 客户A在一个购物网站上买了一系列商品, 同样客户B也买了一些, 通过聚类算法发现客户A和客户B的消费行为非常接近, 那么这个时候购物网站就可以选一些客户B买过而客户A没买过的东西, 在广告中推荐给客户A, 这样就一定程度上提高了广告投放的精确性. 另外一个应用其实是可以作为一个过滤器, 比如商户在海量的review中将其归类, 只研究对其中感兴趣的几个类型.

主要的聚类算法有以下几种:


  • K-means
  • Fuzzy C-means
  • Hierarchical clustering
  • Mixture of Gaussians

其中着重研究了一下Fuzzy C-means, 顾名思义, 这种聚类算法是模糊的, 同一个体可以同时属于不同的种群, 而对于不同的种群有各自的关联程度, 我们用$u_{ij}$来表示个体$i$和种群$j$的关联程度, 则有$\sum\limits_{j=1}^C u_{ij}= 1$. 每个种群可以用处于该种群中心的一个个体来表示. 对于个体$x_i$, 与种群$c_j$之间的差异程度, 可以用$|x_i - c_j|$来表示, 那么可以构造出一个目标函数$F(m) = \sum\limits_{i=1}^N \sum\limits_{j=1}^C u^m_{ij}|x_i-c_j|^2 $, 优化方向是通过改变$u_{ij}$和$c_j$的值, 使目标函数的值尽量小, 其中变量$m$的取值将决定算法的模糊程度, $m$越大越模糊, 取值范围为$(1,\infty) $

然后具体怎么推的我也不是很懂, 但是可以通过以下的迭代过程优化这个目标函数.

  1. 初始化矩阵$U$, 即设定种群个数, 并为每个个体和种群中心设置随机的关联程度.
  2. 在迭代的每一步, 计算新的中心向量$C$, 其中
    \begin{equation} \
    c_j = \frac{\sum\limits_{i=1}^Nu^m_{ij} \cdot x_i}{\sum\limits_{i=1}^Nu^m_{ij}}\
    \end{equation}
  3. 根据新的种群中心更新关联系数矩阵$U$.
    \begin{equation}
    u_{ij} = \frac{1}{\sum\limits_{k=1}^C \left(\frac{|x_i - c_j|}{|x_i - c_k|}\right)^{\frac{2}{m-1}}}\
    \end{equation}
  4. 迭代直到
    \begin{equation}
    max_{ij}\left\lbrace |u^{k+1}_{ij} - u^k_{ij}|\right\rbrace < \mathcal{E} \
    \end{equation}

我实现了一个二维平面上点集的测试程序, 测试数据的生成方法是先随机在平面上构造4个点作为种群中心, 接着以各个中心随机产生一系列个体, 这样基本上可以确保可识别的种群的存在性.
对于测试结果的表示方式, 则是对于每个点根据其对于每个种群的关联程度进行染色:
\begin{equation}
$color_i = \frac{\sum\limits_{j=1}^C corlor_j \cdot u_{ij}}{|C|}$
\end{equation}
在跑过几组数据后, 成功的一些如下图所示(图是用PyGame画的, 非常方便):
白色的是生产数据用的种群中心, 彩色是经过迭代计算出的种群中心.
1
可以看见, 种群中心经过迭代已经非常接近真正的中心, 而每个个体也正确地被染色.

失败的比如说:
2
种群的中心与正确的结果相差较远, 每个个体的颜色都很接近而且比较暗.

算法的结果很大程度上取决于初始化. 普遍采用的初始化方法是设置关联程度, 或者其实可以随机设置种群中心, 两种方法看起来差不多, 但是在测试中, 似乎后者成功的概率要高一些.

差的初始化将会使迭代过早地收敛于局部最优(就像遗传算法里一样?), 我的考虑是也许应该加入一个方法对当前的结果进行评估, 如果在收敛时结果较差的话则应该重新调整个体的关联程度或者种群中心, 以减少失败结果的出现概率. 关于评估函数, 没能想得太多, 但是直接一点的, 比如每个种群中心间的距离可以当作一个参考, 因为经过观察似乎每次失败的结果里错误的种群中心都非常接近.

另外, 遗传算法应该也可以取代以上算法中的迭代过程, 似乎没有什么优势, 但是值得一试, 两年过去了, 我想我应该可以比本科毕业时做的更好一些.

CREDITS:
http://home.deib.polimi.it/matteucc/Clustering/tutorial_html/
http://en.wikipedia.org/wiki/Fuzzy_clustering