原型聚类之学习向量量化及Python实现

学习向量量化(Learning Vector Quantization)

学习向量量化(Learning Vector Quantization,简称LVQ)属于原型聚类，即试图找到一组原型向量来聚类，每个原型向量代表一个簇，将空间划分为若干个簇，从而对于任意的样本，可以将它划入到它距离最近的簇中，不同的是LVQ假设数据样本带有类别标记，因此可以利用这些类别标记来辅助聚类。
学习向量量化算法如下 ( 摘自于周志华《机器学习》)

---

输入：样本集D={(x1,y1),(x2,y2),...,(xm,ym)}；$D=\left\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\right\}；$
   原型向量个数q$q$，各原型向量预设的类别标记{t1,t2,...,tq}$\left\{t_1,t_2,...,t_q\right\}$
   学习率η∈(0,1)$\eta \in \left(0,1\right)$

过程：
1. 初始化一组原型向量{p1,p2,...,pq}$\left\{p_1,p_2,...,p_q\right\}$
2. repeat
3.  从样本集中随机选择样本(xj,yj)$(x_j,y_j)$ ;
4.  计算样本xj$x_j$与pj(1≤i≤p)$p_j(1\le i\le p)$的距离：dji=∥xj−pi∥2${\mathrm{d}}_{ji}={\Vert x_j-p_i\Vert }_2$;
5.  找出与xj$x_j$距离最近的原型向量pi∗$p_{i^{\ast }}$,i∗=argmini∈{1,2,...,q}dji$i^{\ast }=argmi{n}_{i\in \left\{1,2,...,q\right\}}{d}_{ji}$
6.  if yj=ti∗$y_j=t_{i^{\ast }}$ then
7.   p′=pi∗+η⋅(xj−pi∗)$p^{\prime }=p_{i^{\ast }}+\eta \cdot \left(x_j-p_{i^{\ast }}\right)$
8.  else
9.   p′=pi∗−η⋅(xj−pi∗)$p^{\prime }=p_{i^{\ast }}-\eta \cdot \left(x_j-p_{i^{\ast }}\right)$
10. end if
11.  将原型向量pi∗$p_{i^{\ast }}$更新为p′$p^{\prime }$
12. until 满足停止条件
输出：原型向量{p1,p2,...,pq}$\left\{p_1,p_2,...,p_q\right\}$

---

LVQ的关键实在第6-10行，即如何更新原型向量。直观上看，对样本xj$x_j$，若最近的原型向量pi∗$p_{i^{\ast }}$与xj$x_j$的类别标记相同，则令pi∗$p_{i^{\ast }}$向xj$x_j$的方向靠拢。如第7行所示，此时新原型向量为

p′=pi∗+η⋅(xj−pi∗)(1.1)$$\begin{array}{}\text{(1.1)}& p^{\prime }=p_{i^{\ast }}+\eta \cdot \left(x_j-p_{i^{\ast }}\right)\end{array}$$

p′$p^{\prime }$与xj$x_j$之间的距离为

∥p′−xj∥2=∥pi∗+η⋅(xj−pi∗)−xj∥=(1−η)⋅∥pi∗−xj∥2(1.2)$$\begin{array}{}\text{(1.2)}& {\Vert p^{\prime }-x_j\Vert }_2=\Vert p_{i^{\ast }}+\eta \cdot \left(x_j-p_{i^{\ast }}\right)-x_j\Vert =\left(1-\eta \right)\cdot {\Vert p_{i^{\ast }}-x_j\Vert }_2\end{array}$$

令学习率η∈(0,1)$\eta \in (0,1)$,则原型向量pi∗$p_{i^{\ast }}$在更新为p′$p^{\prime }$之后更接近xj$x_j$。
当pi∗$p_{i^{\ast }}$与xj$x_j$的类别标记不同，则更新后的原型向量与xj$x_j$之间的距离将增大为(1+η)⋅∥pi∗−xj∥2$\left(1+\eta \right)\cdot {\Vert p_{i^{\ast }}-x_j\Vert }_2$，从而远离xj$x_j$

python实现学习向量量化算法

完整代码见github。
1.数据生成，这里使用较小的样本集data$data$,共有13个样本，每个样本采集的特征为：密度，含糖率，是否好瓜。其中标签为：Y和N。

data = \
"""1,0.697,0.46,Y,
2,0.774,0.376,Y,
3,0.634,0.264,Y,
4,0.608,0.318,Y,
5,0.556,0.215,Y,
6,0.403,0.237,Y,
7,0.481,0.149,Y,
8,0.437,0.211,Y,
9,0.666,0.091,N,
10,0.639,0.161,N,
11,0.657,0.198,N,
12,0.593,0.042,N,
13,0.719,0.103,N"""

2.数据预处理

#定义一个西瓜类，四个属性，分别是编号，密度，含糖率，是否好瓜
class watermelon:
    def __init__(self, properties):
        self.number = properties[0]
        self.density = float(properties[1])
        self.sweet = float(properties[2])
        self.good = properties[3]

a = re.split(',', data.strip(" "))
dataset = []     #dataset:数据集
for i in range(int(len(a)/4)):
    temp = tuple(a[i * 4: i * 4 + 4])
    dataset.append(watermelon(temp))

3.距离计算，这里采用的是欧几里得距离。

def dist(a, b):
    return math.sqrt(math.pow(a[0]-b[0], 2)+math.pow(a[1]-b[1], 2))

4.算法模型

def LVQ(dataset, a, q,max_iter):
    #随机产生q个原型向量
    P = [(i.density, i.sweet,i.good) for i in np.random.choice(dataset, q)]
    while max_iter>0:
        #从样本集dataset中随机选取一个样本X
        X = np.random.choice(dataset, 1)[0]
        #找出P中与X距离最近的原型向量P[index]
        m = []
        for i in range(len(P)):
            m.append(dist((X.density, X.sweet),(P[i][0],P[i][1])))
        index = np.argmin(m)
        #获得原型向量的标签t,并判断t是否与随机样本的标签相等
        t = P[index][2]
        if t == X.good:
            P[index] = ((1 - a) * P[index][0] + a * X.density, (1 - a) * P[index][1] + a * X.sweet,t )
        else:
            P[index] = ((1 + a) * P[index][0] - a * X.density, (1 + a) * P[index][1] - a * X.sweet,t )
        max_iter -= 1
    return P

5.画图

def draw(C, P):
    colValue = ['r', 'y', 'g', 'b', 'c', 'k', 'm']
    for i in range(len(C)):
        coo_X = []    #x坐标列表
        coo_Y = []    #y坐标列表
        for j in range(len(C[i])):
            coo_X.append(C[i][j].density)
            coo_Y.append(C[i][j].sweet)
        pl.scatter(coo_X, coo_Y, marker='x', color=colValue[i%len(colValue)], label=i)
    #展示原型向量
    P_x = []
    P_y = []
    for i in range(len(P)):
        P_x.append(P[i][0])
        P_y.append(P[i][1])
        pl.scatter(P[i][0], P[i][1], marker='o', color=colValue[i%len(colValue)], label="vector")
    pl.legend(loc='upper right')
    pl.show()

6.实验结果

---

更多机器学习干货、最新论文解读、AI资讯热点等欢迎关注”AI学院(FAICULTY)”
欢迎加入faiculty机器学习交流qq群：451429116 点此进群
版权声明：可以任意转载，转载时请务必标明文章原始出处和作者信息.

---

参考文献

[1]. 周志华，机器学习，清华大学出版社，2016
[2]. 聚类算法——python实现学习向量量化（LVQ）算法