k-prototype聚类是一种用于混合数据类型聚类的算法，由Jain和Dubes在1988年提出。它主要用于同时包含连续属性和离散属性的数据集。k-prototype算法可以看作是k-means算法的扩展，它将k-means算法的思想应用于混合数据类型，通过为连续属性和离散属性分别定义距离函数来处理这两种不同类型的数据。
k-prototype算法的基本步骤如下：
- 初始化：选择k个原型（prototype），每个原型是一个包含连续属性和离散属性的向量。
- 分配：对于数据集中的每个对象，计算其与每个原型的相似度，并将其分配给相似度最高的原型。相似度计算包括连续属性的距离和离散属性的不匹配度。
- 更新：根据分配到每个原型的对象，更新原型的值。对于连续属性，取分配给该原型的对象的连续属性的平均值；对于离散属性，取分配给该原型的对象中出现频率最高的离散值。
- 迭代：重复步骤2和3，直到原型不再发生变化或达到预设的迭代次数。
- 输出：最终得到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
