kernel k-means（wine数据集聚类）

kernel k-means（wine数据集聚类）

实验过程

kernel核函数

'''
created by Chenyufei on 2022/4/8
注意：包含的核函数，是对两个多维度向量进行计算，返回的内积是一个常数
input：sample， A ：两个1*n的向量
output：常数
'''


import numpy as np
# 线性核
def liner_kernel(sample,A,C=0):#C为常数
    K = np.dot(sample.T,A) +C
    #print("KKK")
    #print(K)
    return K
    
#高斯核
'''
theta:正态分布的theta
'''
def squared_exponential_kernel(sample,A,theta=1):
    delta = sample-A
    # print(delta)
    K = np.dot(delta.T,delta)
    K = np.exp(K/(-1*theta**2)) 
    return K
# 多项式核函数
'''
alpha:slope
c:constant,c=0,同质多项核函数,c=1,不同质多项核函数
d:次数:多项式次数>=1
'''
def polynomial_kernel(sample,A,alpha=1,c=0,d=3):
    t = np.dot(sample.T,A)
    t = t*alpha+c
    K = t**d
    return K

#拉普拉斯核函数
def laplacian_kernel(sample,A,theta = 1):
    delta = sample-A
    t = np.dot(delta.T,delta)
    t = pow(t,0.5)
    K = np.exp(t/(-1*theta))
    return K
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
37
38
39
40
41
42
43
44
45

这里要注意数据的维度！

这里写了几种不同的核函数，用来比较，在主函数中都进行了调用

Q: 什么是核函数？

1.高维空间映射与计算难题

我们试图，将样本向量构成的向量映射到高纬度空间，这样在原本维度非线性可分的关系可以在高纬度有几率变为线性可分，于是能构造超平面，更好地将不同类样本区分开。

但是，如何映射呢？

——答案是：先不管，先假设我们映射了，映射规则先隐性表示为$\varphi (X)$（用字母代替一下，直接推导）

2. 高维度距离与高维度内积

我们首先假装我们升维了，现在就要计算高维度的两点距离了（样本点和中心点）。

两点距离，用做差的平方表示，写成向量转置乘法，推到到内积。得到：（具体过程网上都有）
$$<\varphi (X),\varphi (X)>-2<\varphi (A),\varphi (X)>+<\varphi (A),\varphi (A)>$$
这个式子就是高位空间距离的等价式子。<>是计算内积

3. 高纬度内积与低纬度内积

于是我们的目标变成了计算高维度内积。但是我们并不知道高维度向量的具体数值。

这里体现出核方法：

以二维到三维为例，我们可以推导出，高维度的内积，与原空间的向量存在某种关系。而具体是什么样的对应关系，取决于我们向高维度映射的规则是怎样的。（二维的例子网上都在用，就不废话了）

于是我们得到这样一个逻辑：

定义某种映射关系–>最后要计算的高维度内积和原空间内积有某种关系。

至于映射关系具体是什么样的呢？我们不用关心（当然是可以推出来显性公式的），我们计算时候，只会用到最后一步的高维度内积与原空间向量的关系

4. 映射关系与核方法

参与计算的，只有最后一步的高维度内积与原空间向量的关系，于是，我们只需要定义这个关系，这个确定之后，映射关系就会对应地确定下来。

我们管最后一步的高维度内积与原空间向量的关系，叫做核函数，通过这种方法，隐性地确定向高维度的映射关系，我们叫做核方法。

5. 核方法对k-means的影响

体现在计算的代码上，之前的推导关系都不影响我们的代码。只需要在计算距离的函数中，使用核函数，并反推到高维度的距离（其实代码调用时候是正向的顺序）。至于在高位空间中，样本点和中心点到底在哪，我们并不需要知道。

只需要：原维度的样本点坐标、中心点坐标、核函数。

我们就能求出在高维度空间两点的距离。

相当于：通过某种计算方式，我们在原来的样本上，得到一整套新的样本距离数据。这套数据，可以体现出原来距离计算体现不出来的，样本点之前的远近关系。

kernelkmeans类

在k-means基础上有一些改动，来适应封装好的核函数，做改动的地方我注释出来了

from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score
from sklearn.datasets import load_wine
from kernels import *
def eucliden_distance(one_sample,X):
    one_sample = one_sample.reshape(1,-1)
    distances = np.power(np.tile(one_sample,(X.shape[0],1))-X,2).sum(axis=1)
    return distances
#这个欧式距离没用了，留着作为比较吧
def HD_distance(one_sample,centroid,kernel):
    # print("jjjkjkj")
    # print(one_sample)
    # print(centroid)
    d1 = kernel(one_sample,one_sample)
    d2 = kernel(one_sample,centroid)
    d3 = kernel(centroid,centroid)
    return d1-2*d2+d3

class Kmeans():
    '''
    kernel K-means:
    k:int
    the number of kinds to be devided to
    max_iterations: int
    maximum of terms
    varepsilon: float
    Criteria for judging convergence,
    if every distance bentween the last and new center is less than varepsilon,we can say it is convergent
    kernel:str,name of the kernel
    '''
    def __init__(self,k=2,max_iterations = 500,varepsilon = 0.00001,kernel=None):
        self.k = k
        self.max_iterations = max_iterations
        self.varepsilon = varepsilon
        self.kernel = kernel
        np.random.seed(1)
    def init_random_centroids(self,X):
        n_samples,n_features = np.shape(X)
        centroids = np.zeros((self.k,n_features))
        for i in range(self.k):
            centroid = X[np.random.choice(range(n_samples))]
            centroids[i] = centroid
        return centroids
    def _closest_ventroid(self,sample,centroids):
        #distances = eucliden_distance(sample,centroids)
        distances = []
        for centroid in centroids:
            #在这里改成了对每一个中心点单独计算，distance函数只需要计算两个1*13的向量
            distance = HD_distance(sample,centroid,self.kernel)
            distances.append(distance)
        closest_i = distances.index(min(distances))
        return closest_i
    def create_clusters(self,centroids,X):
        clusters = [[]for _ in range (self.k)]
        for samples_i,sample in enumerate(X):
            #这里！是对X的每一条进行计算，传入函数的sample形状是（1，13）
            centroid_i = self._closest_ventroid(sample,centroids)
            clusters[centroid_i].append(samples_i)
        return clusters
    def update_centroids(self,clusters,X):
        n_features = np.shape(X)[1]
        centroids = np.zeros((self.k,n_features))
        for i, cluster in enumerate(clusters):
            centroid = np.mean(X[cluster], axis=0)
            centroids[i] = centroid
        return centroids

    def get_cluster_labels(self,clusters,X):
        y_pred = np.zeros(np.shape(X)[0])
        for cluster_i ,cluster in enumerate(clusters):
            for sample_i in cluster:
                y_pred[sample_i] = cluster_i
        return y_pred
    def predict(self,X):
        centroids = self.init_random_centroids(X)
        for _ in range(self.max_iterations):
            clusters = self.create_clusters(centroids,X)
            former_centroids = centroids
            centroids = self.update_centroids(clusters,X)

            diff = centroids - former_centroids
            if diff.any()<self.varepsilon:
                break
        return self.get_cluster_labels(clusters,X)

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

kernel k-means流程

体现在伪代码上，kernel k-means和k-means差不多

数据：n个m维向量
随机生成k个m维向量，作为初始化的中心点
while（t）：
	for(int i=0;i<n;i++)
		for (int j=0;j<k;j++)
			计算点i到中心点j的距离
			与k-means不同，这里计算距离用核函数得到高维度距离，能体现新的关系
	for(int i=0;i<k;i++)
		1. 找出所有属于自己这个类的点
		2. 在这个类中，重新定位中心点（质心）
1
2
3
4
5
6
7
8
9
10

Main

在主函数中调用了不同的核函数，没用pipeline，懒了

from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score
from sklearn.datasets import load_wine
from kernels import *
from KernelKmans import Kmeans
import os
1
2
3
4
5
6

wine数据集

# 加载数据集
wine = load_wine()
scaler = StandardScaler()
X = scaler.fit_transform(wine.data)
y = wine.target
X.shape
1
2
3
4
5
6

调用不同的kernel

km = Kmeans(k=3,kernel=liner_kernel)
y_pred = km.predict(X)
y[y==0] = -1
y[y==1] = -2
y[y==2] = -3
y_pred[y_pred==0] = -1
y_pred[y_pred==2] = -2
y_pred[y_pred==1] = -3
acc = accuracy_score(y,y_pred)
print('线性核函数聚类吻合度：{:.2f}'.format(acc))

km = Kmeans(k=3,kernel=squared_exponential_kernel)
y_pred = km.predict(X)
y[y==1] = -2
y[y==2] = -3
y_pred[y_pred==0] = -1
y_pred[y_pred==2] = -2
y_pred[y_pred==1] = -3
acc = accuracy_score(y,y_pred)
print('高斯核函数聚类吻合度：{:.2f}'.format(acc))

km = Kmeans(k=3,kernel=polynomial_kernel)
y_pred = km.predict(X)
y[y==1] = -2
y[y==2] = -3
y_pred[y_pred==0] = -1
y_pred[y_pred==2] = -2
y_pred[y_pred==1] = -3
acc = accuracy_score(y,y_pred)
print('三次多项式核函数聚类吻合度：{:.2f}'.format(acc))

km = Kmeans(k=3,kernel=laplacian_kernel)
y_pred = km.predict(X)
y[y==1] = -2
y[y==2] = -3
y_pred[y_pred==0] = -1
y_pred[y_pred==2] = -2
y_pred[y_pred==1] = -3
acc = accuracy_score(y,y_pred)
print('拉普拉斯核函数聚类吻合度：{:.2f}'.format(acc))

os.system("pause")
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
37
38
39
40
41
42

实验结果

其实用了核方法之后，吻合度并没有比k-means好……

好多书上和网站核函数都写的很简略，可能没想到有我这种看不懂的……还有直接把映射手写出来的，二维三维还行，高维度直接写死。

大致理解就先到这里，效果之后有了更深的理解再更新。