LVQ聚类算法

LVQ算法

LVQ是learning vector quantization的简称，是一种被称之为学习向量量化的算法。

其算法思想是通过找到一组原型向量来代表聚类的中心。而与其他的聚类算法不同，LVQ假设每个样本是有标签的，LVQ通过这些假设的标签来辅助聚类。

LVQ算法实现

给定样本集$\left \{ (x_1),(x_2),...,(x_N) \right \}$, 我们假设样本是有标签的，如下所示：$\left \{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \right \}$ 标签是随机指定的，但是需要在范围$\left \{ t_1,t_2,...,t_q \right \}$内, $q$是我们执行聚类的簇的个数。

我们的目标是学习到一组原型向量$\left \{ p_1,p_2,...,p_q \right \}$，每个向量表示聚类簇的中心。

算法的实现步骤如下：

输入：
样本集$\left \{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \right \}$
聚类的个数$q$
学习率$\eta \subset (0,1)$

算法过程：
1) 初始化一组原型向量$\left \{ p_1,p_2,...,p_q \right \}$，一般是在我们的每个标记中随机选择一个向量作为初始向量
2) 从样本集中随机选取样本$\left \{ (x_i,y_i) \right \}$, 计算$x_i$与每个原型向量$p_j \qquad (0 \leq j \leq 1)$的距离$d_{ij}$
3) 选择与$x_i$距离最近的原型向量$p_{j*}$其中$j* = arg min (d_{ij})$
4) 如果样本的标签$y_{i*} == t_{j*}$, 那么$p'_{j*} = p_{j*} + \eta (x_i - p_{j*} )$
5) 如果样本的标签$y_{i*} \neq t_{j*}$, 那么$p'_{j*} = p_{j*} - \eta (x_i - p_{j*} )$
6) 更新$p_{j*}$ 为 $p'_{j*}$
7) 重复上面的2，3，4，5，6步骤直到满足停止条件（一般是原型向量不再变动或者变动很小，或者达到了最大的迭代次数）
8) 输出原型向量$\left \{ p_1,p_2,...,p_q \right \}$

重点

我们可以看到LVQ算法的重点是更新原型向量，为什么是这样的公式更新呢？
我们看下面的方程：

$$p'_{j*} = p_{j*} + \eta (x_i - p_{j*} )$$

计算$p'_{j*}$ 与$x_{i}$的距离

$$||p'_{j*} - x_i||^2 = ||p_{j*} + \eta (x_i - p_{j*} )-x_i||^2 = (1- \eta)^2||p_{j*} - x_i ||^2$$

而由于$\eta \subset (0,1)$，所以如果$p'_{j*}$ 与$x_{i}$是同类的话（记住这里的类别是我们最初随机指定的），那就说明我们最初的指定是靠谱滴，他们两个确实距离近，所以我们要将原型向量$p'_{j*}$向$x_{i}$移动，反之，如果他们两个不是一类，那么说明我们最初的假设不对，而他的距离确实最近的，所以那么我们就要将原型向量$p'_{j*}$向$x_{i}$远离。

但是有一点，随机选择的原型向量可能会影响聚类效果，不过这个是聚类都存在的问题，除了层次聚类，但是层次聚类也有他的限制之处。

实验验证