算法介绍
LVQ(Learning vector Quantization) 假设数据样本带有类别标记, 学习过程利用样本的这些监督信息来辅助聚类.
给定样本集 $D=\{(x_{1}, y_{1}), (x_{2}, y_{2}), \ldots, (x_{n}, y_{n})\}$,
$x_{i} \in R^{p}$, $y_{i} \in \mathcal{Y}$ 是样本的类别标记.
LVQ的目标是学得一组 $n$ 维原型向量 $\{p_{1}, p_{2}, \ldots, p_{q}\}$,
每个原型向量代表一个聚类簇, 簇标记为 $t_{i}\in \mathcal{Y}$.
算法
输入:
样本集:
$D=\{(x_{1}, y_{1}), (x_{2}, y_{2}), \ldots, (x_{n}, y_{n})\}$;原型向量个数
$q$, 各原型向量预设的类标记$\{t_{1}, t_{2}, \ldots, t_{q}\}$;学习率
$\eta \in (0,1)$.过程:
- 初始化一组原型向量:
$\{p_{1}, p_{2},\ldots,p_{q}\}$- repeat
- 从样本集中随机选取样本
$(x_{j}, y_{j})$;- 计算样本
$x_{j}$与$p_{i} (1 \leqslant i \leqslant q)$的距离:$d_{ji}=\|x_{j}-p_{i}\|_{2}$;- 找出与
$x_{j}$距离最近的原型向量$p_{i^{*}}$,$i^{*}=arg min_{i \in \{1, 2, \ldots, q\}}d_{ji}$;- if
$y_{j}=t_{i^{*}}$$p' = p_{i^{*}} + \eta \cdot (x_{j}-p_{i^{*}})$- else
$p' = p_{i^{*}} - \eta \cdot (x_{j}-p_{i^{*}})$- end if
- 将原型向量
$p_{i^{*}}$更新为$p'$- until 满足停止条件
输出:
原型向量
$\{p_{1}, p_{2}, \ldots, p_{q}\}$,
算法解释
- 算法第1行: 对原型向量进行初始化. 例如: 对第
$i,i=(1,2,\ldots,q)$个簇,从类别标记为$t_{i}$的样本中随机选取一个作为原型向量. - 算法第2-12行: 对原型向量进行迭代优化. 在每一轮迭代中, 算法随机选取一个有标记训练样本,
找出与其距离最近的原型向量, 并根据两者的类别标记是否一致来对原型向量进行相应的更新.
- 第6-10行: 如何更新原型向量. 对样本
$x_{j}$,- 若距离
$x_{j}$最近的原型向量$p_{i^{*}}$与$x_{j}$的标记相同, 则令$p_{i^{*}}$向$x_{j}$的方向靠拢, 此时新的原型向量为 $$p’ = p_{i^{}} + \eta \cdot (x_{j}-p_{i^{}})$$$p^{'}$与$x_{j}$之间的距离为 $$|p’-x_{j}|{2}=(1-\eta) \cdot |p{i^{*}}-x_{j}|_{2}$$ 原型向量$p_{i^{*}}$更新为$p'$之后将更接近$x_{j}$. - 若距离
$x_{j}$最近的原型向量$p_{i^{*}}$与$x_{j}$的标记不同, 则令$p_{i^{*}}$向$x_{j}$的方向远离, 此时新的原型向量为 $$p’ = p_{i^{}} - \eta \cdot (x_{j}-p_{i^{}})$$$p^{'}$与$x_{j}$之间的距离为 $$|p’-x_{j}|{2}=(1+\eta) \cdot |p{i^{*}}-x_{j}|_{2}$$ 原型向量$p_{i^{*}}$更新为$p'$之后将更远离$x_{j}$.
- 若距离
- 第6-10行: 如何更新原型向量. 对样本
- 算法第12行: 若算法的停止条件已满足(例如已达到最大迭代轮数, 或原型向量更新很小甚至不再更新), 则将当前原型向量作为最终结果返回.
- 在学得一组原型向量
$\{p_{1}, p_{2}, \ldots, p_{q}\}$后即可实现对样本空间$\mathcal{X}$的簇划分.- 对任意样本
$x$, 他将被划入与其距离最近的原型向量所代表的簇中, 每个原型向量$p_{i}$定义了与之相关的一个区域$R_{i}$, 该区域中每个样本与$p_{i}$的距离不大于他与其他原型向量$p_{i'} (i \neq i')$, 即 $$R_{i}={x \in \mathcal{X}||x-p_{i}|{2} \leqslant |x-p{i’}|_{2}, i \neq i’}$$ 由此形成了对样本空间$\mathcal{X}$的簇划分$\{R_{1}, R_{2}, \ldots, R_{q}\}$, 该划分通常称为"Voronoi剖分"(Voronoi tessellation).
- 对任意样本