avatar
阳生。
风毛丛劲节，只上尽头竿。

学习向量量化

这篇blog用于记录我使用python对学习向量量化这种聚类算法的复现

算法简介

学习向量量化也成为LVQ(Learning Vector Quantization)，同样属于原型聚类算法，类似于k-means通过希望划分的簇的数量求得相同数量的“簇中心”并以此为原型将数据集划分为对应的簇，LVQ通过求得与希望划分的簇数量相同的“原型向量”，并以此来将数据集划分为对应的簇。

如果说k-means也同样是借助原型向量的话，那么关键就在于两种算法更新原型向量的方法不同。k-means是不断的用原型向量划分簇，又用簇更新原型向量；LVQ则是利用样本的预先标注作为“监督信息”，不断利用样本更新原型向量。

算法详解

整个算法的大致流程如下：

输入: $D = {(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}, q, {t_1,t_2,…,t_q},\eta \in (0,1)$其中，D是带有标记的数据集，q是原型向量个数，$t_i,i \in {1,2,…,q}$ 对应原型向量的标记，$\eta$是学习率

算法过程：

  1. 初始化原型向量${p_1,p_2,…,p_q}$
  2. repeat:
  3. 从$D$中随机挑选一个样本$(x_j,y_j)$
  4. 找到与$x_j$最近的原型向量$p_i^{*}$
  5. if($t_i^{*}$ == $y_j$): $p’ = p_i^{*} + \eta(p_i^{*} - x_j)$
  6. else: $p’ = p_i^{*} - \eta(p_i^{*} - x_j)$
  7. 判断是否到达退出条件

整个算法过程的关键就在于5、6，实际上相当于找到距离原型向量最近的样本，如果是同标记的则将该原型向量向该样本“拉近”，如果是不同标记的则“推远”（因为对应的是同标记的在一个簇中可能性较大，不同标记在不同簇中可能性较大）

关于7的退出条件，通常可以设置一个最大迭代轮数，或者是原型向量的更新程度已经小于了一个阈值。

代码

使用python对西瓜书上的示例复现代码如下（30个样本，9-21号样本标记为2，其它样本标记为1，随机选择5个样本作为原始向量，标记分别为1、2、2、1、1，学习率为0.1）

Data.py数据集部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
D = [
    [0, 0],
    [0.697, 0.460], [0.774, 0.376], [0.634, 0.264], [0.608, 0.318], [0.556, 0.215],
    [0.403, 0.237], [0.481, 0.149], [0.437, 0.211], [0.666, 0.091], [0.243, 0.267],
    [0.245, 0.057], [0.343, 0.099], [0.639, 0.161], [0.657, 0.198], [0.360, 0.370],
    [0.593, 0.042], [0.719, 0.103], [0.359, 0.188], [0.339, 0.241], [0.282, 0.257],
    [0.748, 0.232], [0.714, 0.346], [0.483, 0.312], [0.478, 0.437], [0.525, 0.369],
    [0.751, 0.489], [0.532, 0.472], [0.473, 0.376], [0.725, 0.445], [0.446, 0.459]
]  # 数据集，1~30，0索引不使用
# 数据集的标记，LVQ使用
T = [
    0,
    1, 1, 1, 1, 1,
    1, 1, 1, 2, 2,
    2, 2, 2, 2, 2,
    2, 2, 2, 2, 2,
    2, 1, 1, 1, 1,
    1, 1, 1, 1, 1
]
# 原始向量标记的输入
q_vect = [1, 2, 2, 1, 1]

main.py主函数部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import K_means
import LVQ
import Data


def main(): 
    print("LVQ 的结果", end="\n")
    res = LVQ.lvq(Data.D, Data.T, Data.q_vect)
    for i in range(5):
        print(len(res[i]) - 1, end="\n")
        if len(res[i]) == 1:
            print("[]", end="\n")
            continue
        for j in range(len(res[i])):
            if j == 0:
                continue
            print(res[i][j], end=" ")
        if len(res[i]) != 1:
            print(" ")


    if __name__ == "__main__":
        main()

LVQ.py学习向量量化算法部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def lvq(D:[[float]], T:[int], q_vect:[]):
l_rate = 0.1
import random as rd
q_vec_index = rd.sample(range(1, 31), 5)  # 随机选取5个样本作为原型向量
q_vec = []  # 原型向量
for i in range(0,5):
    q_vec.append(D[q_vec_index[i]])

for _ in range(0,10000):  # 迭代10000轮
    j_dex = rd.randint(1,30)  # 随机挑选一个样本，randint函数的参数是一个闭区间！
    q = 0 # 距离j_dex最近的原型向量的索引
    d = (D[j_dex][0] - q_vec[0][0])**2 + (D[j_dex][1] - q_vec[0][1])**2
    for i in range(1,5):
        d_i = (D[j_dex][0] - q_vec[i][0])**2 + (D[j_dex][1] - q_vec[i][1])**2
        if d_i < d:
            q = i
            d = d_i
    if q_vect[q] == T[j_dex]:  # 将原型向量与样本拉近
        q_vec[q][0] = q_vec[q][0] + l_rate*(D[j_dex][0] - q_vec[q][0])
        q_vec[q][1] = q_vec[q][1] + l_rate*(D[j_dex][1] - q_vec[q][1])
    else:  # 将原型向量与样本推远
        q_vec[q][0] = q_vec[q][0] - l_rate * (D[j_dex][0] - q_vec[q][0])
        q_vec[q][1] = q_vec[q][1] - l_rate * (D[j_dex][1] - q_vec[q][1])
result = [[], [], [], [], []]
for i in range(0,5):
    result[i].append(q_vec[i])
for i in range(1,31):
    j = 0
    d = (D[i][0] - q_vec[j][0])**2 + (D[i][1] - q_vec[j][0])**2
    for _ in range(1,5):
        d_ = (D[i][0] - q_vec[_][0])**2 + (D[i][1] - q_vec[_][1])**2
        if d_ < d:
            d = d_
            j = _
    result[j].append(D[i])
return result

捉个一个虫，py中万物皆对象，在初始化q_vec的时候直接将数据集D中的元素append进去，实际上共享了内存，这会导致更新原型向量的时候，数据集中的元素被更新，解决方案是使用深拷贝

修改方法：
将q_vec初始化的地方：

1
2
3
q_vec = []  # 原型向量
for i in range(0,5):
    q_vec.append(D[q_vec_index[i]])

更改为：

1
q_vec = [x.copy() for x in (D[i] for i in q_vec_index)]  # 关键修复点：使用列表拷贝

最终运行结果：

3
[0.36, 0.37] [0.478, 0.437] [0.446, 0.459]
8
[0.634, 0.264] [0.556, 0.215] [0.666, 0.091] [0.639, 0.161] [0.657, 0.198] [0.593, 0.042] [0.719, 0.103] [0.748, 0.232]
9
[0.403, 0.237] [0.481, 0.149] [0.437, 0.211] [0.243, 0.267] [0.245, 0.057] [0.343, 0.099] [0.359, 0.188] [0.339, 0.241] [0.282, 0.257]
5
[0.697, 0.46] [0.774, 0.376] [0.714, 0.346] [0.751, 0.489] [0.725, 0.445]
5
[0.608, 0.318] [0.483, 0.312] [0.525, 0.369] [0.532, 0.472] [0.473, 0.376]

对应为5个簇中样本的数量和相应的样本

注：理论上应该将数据集D划分为训练集和测试集，通过训练集训练模型（得到所有合理的原型向量），然后利用测试集测试，利用原型向量将测试集划分为对应数量的簇；这样才能完整地体现“机器学习”，但是这里只是一个简单的例子，将数据集D全用作训练集，得到原型向量，再把整个训练集划分为了对应的簇。
有了原型向量之后，划分为簇是很简单的，样本距离哪个原型向量最近，就纳入对应的簇即可。

Site by 阳生 | Powered by Hexo | theme PreciousJoy