基于K-prototype算法聚类

k-prototype聚类是一种用于混合数据类型聚类的算法，由Jain和Dubes在1988年提出。它主要用于同时包含连续属性和离散属性的数据集。k-prototype算法可以看作是k-means算法的扩展，它将k-means算法的思想应用于混合数据类型，通过为连续属性和离散属性分别定义距离函数来处理这两种不同类型的数据。

k-prototype算法的基本步骤如下：

第一步：从数据集X中随机选择k个数据对象作为初始的聚类中心；
第二步：根据混合距离的相异度测算公式计算每个点到各聚类中心的距离，将其划分到距离最近的类中，每一次划分结束后，更新聚类中心。
第三步：当数据集中所有的对象都分配到相应的类后，重新计算这些数据对象到当前聚类中心的混合距离，然后更新聚类中心。
第四步：重复步骤三，直到经过新一轮计算之后聚类中心不再发生大的变化为止。
代码实现步骤如下：

from numba import jit
import pandas as pd
import numpy as np
import random
from collections import Counter

## 定义数值型变量的距离（欧式距离）
def dist(x, y):
    return np.sqrt(sum((x-y)**2))
## 计算分类变量的距离（海明威距离）
def sigma(x, y):
    return len(x) - sum(x == y)

## 区分数值变量和分类变量,并随机生成聚类中心
def findprotos(data, k):
    #data = df
    m, n = data.shape
    # 生成聚类中心的行号
    num = random.sample(range(m), k)
    O = []
    C = []
    for i in range(n):
        try:
            if isinstance(data.iloc[0, i], int) or isinstance(data.iloc[0, i], float) or isinstance(data.iloc[0, i], np.int64):
                O.append(i)
            elif isinstance(data.iloc[0, i], str):
                C.append(i)
            else:
                raise ValueError("the %d column of data is not a number or a string column" % i)
        except TypeError as e:
            print(e)
    # 数值型变量
    O_data = data.iloc[:, O]
    # 分类型变量
    C_data = data.iloc[:, C]
    # 随机数值型数据（聚类中心）
    O_protos = O_data.iloc[num, :]
    # 随机分类型数据（聚类中心）
    C_protos = C_data.iloc[num, :]
    return O, C, O_data, C_data, O_protos, C_protos
## data: 待聚类的数据
## k: 类别数
## max_iters： 最大迭代次数
## 
#gamma = 1
#k = 3
#data = pd.DataFrame(df)

def KPrototypes(data, k, max_iters  ,  gamma ):
    # m: 数据的行数,n:数据的列数
    m, n = data.shape
    # O: 数值型变量的列号；   C：分类型变量的列号
    # O_data： 数值型数据；  C_data：分类型数据
    # O_protos：初始聚类中心的数值型数据； C_protos：聚类中心的 
    O, C, O_data, C_data, O_protos, C_protos = findprotos(data, k)
    cluster = None
    # clusterShip: 按行号存储每个样本的聚类类别
    clusterShip = []
    # 每个聚类类别的样本个数
    clusterCount = {}
    
    sumInCluster = {}
    freqInCluster = {}
    for i in range(m):
        mindistance = float('inf')
        # 此处循环每个点和各个聚类中心的关系
        for j in range(k):
            # 对数值型变量计算欧式距离，对分类型变量计算海明威距离
            # 计算每个点到各个聚类中心的距离，把他聚到距离他最近的类中去
            distance = dist(O_data.iloc[i,:], O_protos.iloc[j,:]) + gamma * sigma(C_data.iloc[i,:], C_protos.iloc[j,:])
            if distance < mindistance:
                mindistance = distance
                cluster = j
        clusterShip.append(cluster)
        if  clusterCount.get(cluster) == None:
            clusterCount[cluster] = 1
        else:
            clusterCount[cluster] += 1
        # 此处循环各个列的和，用来更新各个类的中心
        for j in range(len(O)):
            if sumInCluster.get(cluster) == None:
                sumInCluster[cluster] = [O_data.iloc[i,j]] + [0] * (len(O) - 1)
            else:
                sumInCluster[cluster][j] += O_data.iloc[i,j]
            O_protos.iloc[cluster,j] = sumInCluster[cluster][j] / clusterCount[cluster]
        for j in range(len(C)):
            if freqInCluster.get(cluster) == None:
                freqInCluster[cluster] = [Counter(C_data.iloc[i,j])] + [Counter()] * (len(C) - 1)
            else:
                freqInCluster[cluster][j] += Counter(C_data.iloc[i,j])
            # 出现次数最多的那个值,作为聚类中心
            C_protos.iloc[cluster,j] = freqInCluster[cluster][j].most_common()[0][0]
    max_iters = 10
    for t in range(max_iters):
        for i in range(m):
            mindistance = float('inf')
            for j in range(k):
                distance = dist(O_data.iloc[i,:], O_protos.iloc[j,:]) + gamma * sigma(C_data.iloc[i,:], C_protos.iloc[j,:])
                if distance < mindistance:
                    mindistance = distance
                    cluster = j
            # 重新判断某个点属于哪个类，如果不再属于以前的类，则把这个点的类别更新，且更新类的个数的dict
            if clusterShip[i] != cluster:
                oldCluster = clusterShip[i]
                clusterShip[i] = cluster
                clusterCount[cluster] += 1
                clusterCount[oldCluster] -= 1
                # 把这个点的坐标加到新的类别中，把它的值从之前的类中减掉
                for j in range(len(O)):
                    sumInCluster[cluster][j] += O_data.iloc[i,j]
                    sumInCluster[oldCluster][j] -= O_data.iloc[i,j]
                    O_protos.iloc[cluster,j] = sumInCluster[cluster][j] / clusterCount[cluster]
                    O_protos.iloc[oldCluster, j] = sumInCluster[oldCluster][j] / clusterCount[oldCluster]
                # 查找分类变量的聚类中心
                for j in range(len(C)):
                    freqInCluster[cluster][j] += Counter(C_data.iloc[i,j])
                    freqInCluster[oldCluster][j] -= Counter(C_data.iloc[i,j])
                    C_protos.iloc[cluster,j] = freqInCluster[cluster][j].most_common()[0][0]
                    C_protos.iloc[oldCluster,j] = freqInCluster[oldCluster][j].most_common()[0][0]
    return clusterShip , O_protos , C_protos

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121