非监督学习之聚类算法（2）--基于划分
2019-04-04 本文已影响34人
Byte猫
基于划分的方法（Partition-based Methods）：其原理简单来说就是，想象你有一堆散点需要聚类，想要的聚类效果就是“类内的点都足够近，类间的点都足够远”。
首先你要确定这堆散点最后聚成几类，然后挑选几个点作为初始中心点，再然后依据预先定好的启发式算法（Heuristic Algorithms）给数据点做迭代重置（Iterative Relocation），直到最后到达“类内的点都足够近，类间的点都足够远”的目标效果。
基于划分的聚类多适用于中等体量的数据集，不妨理解成数据集越大，越有可能陷入局部最小。
以下是几种常用的划分聚类算法
一、K-means算法
K-means算法（K均值聚类）是集简单和经典于一身的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。
k-means算法的基础是最小误差平方和准则，各类簇内的样本越相似，其与该类均值间的误差平方越小，对所有类所得到的误差平方求和，即可验证分为k类时，各聚类是否是最优的。
1、执行步骤
step 1：随机选取 k个聚类质心点
我们需要选择最初的聚类点（或者叫质心），这里的选择一般是随机选择的（在数据范围内随机选择，或者是随机选择数据中的点）。这些点的选择会很大程度上影响到最终的结果，也就是说运气不好的话就到局部最小值去了。
step 2：重复计算误差平方和过程直到收敛
2、优缺点
（1）优点
- 简单，速度快，易于理解和实现；（容易解释，基于距离的聚类算法）
- 时间复杂度低
计算复杂度低，为O(Nmq)，N是数据总量，m是类别（即k），q是迭代次数。一般来讲m、q会比N小得多，那么此时复杂度相当于O(N)，在各种算法中是算很小的
（2）缺点
- 需要提前确定k值
k-means初始簇中心点对算法影响较大，如果初始值不太好，可能对结果产生较大的影响
改进算法为k-means++、intelligentk-means、genetick-means； - 对噪声和离群值非常敏感
改进算法为k-medoids和k-medians； - 只能用于数值类型数据，不适用于标签类型数据
改进算法为k-modes； - 不能解决非凸（non-convex）数据
改进算法为kernelk-means。 - 仅适用于球心数据分布，不能识别非球形的簇。
- 对非均衡数据集（类别规模差异太明显）效果不好。比如总共有A、B两类，A类有1000个点，B类有100个点。
- 数据比较大时收敛比较慢
3、代码实现
# coding=utf-8
'''
k-means算法
'''
import numpy as np
import math
import matplotlib.pyplot as plt
flag = 1
#==============================================
# 计算距离
#==============================================
def euclidean_dist(p, q):
'''
欧式距离(L2范数)
INPUT -> 长度一致的向量1、向量2
'''
p = np.mat(p)
q = np.mat(q)
return math.sqrt(np.sum(np.power(p-q, 2)))
#==============================================
# 初始化簇中心
#==============================================
def cluster_init(dataSet, k):
'''
中心点初始化
INPUT -> 数据集、聚类中心数
'''
centers = []
while len(centers) < k: # 总共要k个质心
index = np.random.randint(0, len(dataSet)-1)
if index not in centers:
centers.append(index)
return np.array([dataSet[i] for i in centers])
#==============================================
# 更新簇中心点
#==============================================
def cluster_update(dataset):
'''
计算簇的均值点
INPUT -> 簇集
'''
return sum(np.array(dataset)) / len(dataset)
#==============================================
# 算法核心部分
#==============================================
def kMeans(dataSet, center, k):
'''
k-Means算法
INPUT -> 数据集、初始化中心点、聚类中心数
'''
global flag
# 聚类结果
output = []
for _ in range(k):
temp = []
output.append(temp)
# 计算每个点到各中心点的距离
for i in dataSet:
temp = []
for j in center:
temp.append(euclidean_dist(i, j))
output[temp.index(min(temp))].append(i)
# 更新聚类中心点
updated_center = np.array([cluster_update(s) for s in output])
# 打印聚类过程
print('------------------------第'+str(flag)+'次迭代--------------------------')
for i in range(k):
print('第'+str(i+1)+'组:', output[i], end='\n')
if (center == updated_center).all():
print('已收敛，执行结束')
else:
flag += 1
# 递归调用
center = updated_center
kMeans(dataSet, center, k)
return updated_center, output
#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
x = [np.random.randint(0, 100) for _ in range(100)]
y = [np.random.randint(0, 100) for _ in range(100)]
points = [[i,j] for i,j in zip(x,y)]
initial_center = cluster_init(dataSet=points, k=5)
center, output = kMeans(dataSet=points, center=initial_center, k=5)
print(center)
print(output)
二、k-modes算法
为了解决K-means只能处理数值型数据的情况，有了K-means的变种算法——K-modes
K-modes是数据挖掘中针对分类属性型数据进行聚类采用的方法，其算法思想比较简单，时间复杂度也比K-means、K-medoids低。
将原本K-means使用的欧式距离替换成字符间的汉明距离。
1、执行步骤
假设有N个样本，共有M个属性，均为离散的，聚类目标数为K
step 1:在总体n个样本点中任意选取k个点C1,C2...Ck（Ci是长度为M的向量，Ci=[Ci(1),Ci(2),...,Ci(M)]）
step 2:对于每个样本，分别比较其与这k个中心之间的距离
step 3:将样本划分到距离最小的簇，在全部的样本都被划分完毕之后，重新确定簇中心，簇中心的每一个分量都更新为该簇中的众数
step 4:重复步骤2和3，直到总距离（各个簇中样本与各自簇中心距离之和）不再降低，返回最后的聚类结果
2、优缺点
（1）优点
- 支持处理非数值型数据
（2）缺点
- 不能反映对象间的潜在的相似关系,特别是当数据量很大或数据集很复杂时,不能更好的区分样本间的差异
3、代码实现
# coding=utf-8
'''
k-modes算法
'''
import numpy as np
import math
import matplotlib.pyplot as plt
flag = 1
#==============================================
# 计算距离
#==============================================
def hanming_dist(p, q):
'''
汉明距离
INPUT -> 长度一致的向量1、向量2
'''
p = np.mat(p)
q = np.mat(q)
smstr = np.nonzero(p-q)
return np.shape(smstr)[1]
#==============================================
# 初始化簇中心
#==============================================
def cluster_init(dataSet, k):
'''
中心点初始化
INPUT -> 数据集、聚类中心数
'''
centers = []
while len(centers) < k: # 总共要k个质心
index = np.random.randint(0, len(dataSet)-1)
if index not in centers:
centers.append(index)
return np.array([dataSet[i] for i in centers])
#==============================================
# 重新选定簇中心
#==============================================
def cluster_update(dataset):
'''
重新选定簇中心
INPUT -> 簇集
'''
dataset = np.array(dataset)
dataset = dataset.T
center = []
for line in dataset:
dictnum = {}
for i in line:
if i in dictnum.keys():
dictnum[i] += 1
else:
dictnum.setdefault(i, 1)
center.append(max(dictnum, key=dictnum.get))
return np.array(center)
#==============================================
# 算法核心部分
#==============================================
def kModes(dataSet, center, k):
'''
k-Modes算法
INPUT -> 数据集、初始化中心点、聚类中心数
'''
global flag
# 聚类结果
output = []
for _ in range(k):
temp = []
output.append(temp)
# 计算每个点到各中心点的距离
for i in dataSet:
temp = []
for j in center:
temp.append(hanming_dist(i, j))
output[temp.index(min(temp))].append(i)
# 更新聚类中心点
updated_center = np.array([cluster_update(s) for s in output])
# 打印聚类过程
print('------------------------第'+str(flag)+'次迭代--------------------------')
for i in range(k):
print('第'+str(i+1)+'组:', output[i], end='\n')
if (center == updated_center).all():
print('已收敛，执行结束')
else:
flag += 1
# 递归调用
center = updated_center
kModes(dataSet, center, k)
return updated_center, output
#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
a = [np.random.randint(0, 3) for _ in range(50)]
b = [np.random.randint(0, 3) for _ in range(50)]
c = [np.random.randint(0, 3) for _ in range(50)]
d = [np.random.randint(0, 3) for _ in range(50)]
e = [np.random.randint(0, 3) for _ in range(50)]
points = [[a,b,c,d,e] for a,b,c,d,e in zip(a,b,c,d,e)]
initial_center = cluster_init(dataSet=points, k=5)
center, output = kModes(dataSet=points, center=initial_center, k=5)
print(center)
print(output)
