k-means算法理解与图像分割
基于模式识别的课程作业要求基于K均值聚类算法实现聚类模型并对其性能进行深入分析．为何老师将该算法命名为C均值聚类？特别说明此份报告仅供参考性质并建议避免完全照搬他人内容
k-means算法介绍
k-means算法又被称作k-均值聚类算法。具体步骤如下：首先，在数据集中随机选择k个样本作为初始质心（cluster centers），然后计算每个样本与这些质心之间的距离。接着, 将每个样本分配到与其最近的那个特定质心中对应的质心所组成的那个群组。最后, 在每一步迭代后重新计算每个新形成的群组的新质心位置。
根据以上描述，可以得出算法的基本步骤：
- 设定常数K值，并随机选择初始质心作为基准点
-
当质心位置停止变化时, 进行迭代运算
- 评估样本与当前各质心中的相似程度
- 将样本分配至与其最接近的类别中
- 更新新的质心位置
-
输出最终的质心以及每个类
-
import numpy as np
import matplotlib.pyplot as plt
import random
#加载数据
def loadData(filename):
dataSet = []
with open(filename) as fr:
for l in fr.readlines():
indata = l.strip().split('\t')
dataSet.append([float(x) for x in indata])
dataSet = np.array(dataSet)
return dataSet
#欧式距离
def disEclud(vec1, vec2):
return ((vec1 - vec2) ** 2).sum(axis = 1) ** 0.5
#初始化类心
def initCent(dataSet, k):
m, n = np.shape(dataSet)
centroids = dataSet[random.sample(range(m), k)]
return centroids
def kMeans(dataSet, k):
m = dataSet.shape[0]
#类心
centroids = initCent(dataSet, k)
#分类
clusterAssment = np.zeros(m)
clusterChange = np.array(centroids)
while True:
for i in range(m):
dis = disEclud(dataSet[i], centroids)
clusterAssment[i] = dis.argmin()
for cent in range(k):
centroids[cent] = dataSet[np.where(clusterAssment == cent)].mean(axis = 0)
if (centroids == clusterChange).all():
break
else:
clusterChange = np.array(centroids)
continue
return centroids, clusterAssment
train_x, label = loadData('test.txt')
center, classSet = kMeans(train_x, 3)
plt.scatter(train_x[:, 0], train_x[:, 1], c = p, marker = ">")
plt.scatter(a[:, 0], a[:, 1], s = 200, c = 'r', marker = '*')
代码解释
作业内容：对wine数据集进行聚类
该任务的数据源为：http://archive.ics.uci.edu/ml/index.html。我们需要对这一份数据源实施聚类分析。该数据集包含178个样本，并将它们划分为三类。值得注意的是，该数据集共包含十三个子数据集，在这些子数据集中共有十四列特征。其中共有十四列特征需要参与聚类过程，并且在聚类的时候应当排除第一列的分类结果。
import numpy as np
import matplotlib.pyplot as plt
import random
#加载数据
def loadData(filename):
dataSet = []
with open(filename) as fr:
for l in fr.readlines():
indata = l.strip().split(',')
dataSet.append([float(x) for x in indata])
dataSet = np.array(dataSet)
train_x = np.array(dataSet[:,1::])
train_y = np.array(dataSet[:,0])
return train_x, train_y
#数据归一化处理
def dataNormalized(dataSet):
dataSetMin = dataSet.min(axis = 0)
print(dataSetMin.shape)
dataSetMax = dataSet.max(axis = 0)
dataSet = (dataSet - dataSetMin) / (dataSetMax - dataSetMin)
return dataSet
#欧式距离
def disEclud(vec1, vec2):
return ((vec1 - vec2) ** 2).sum(axis = 1) ** 0.5
#初始化类心
def initCent(dataSet, k, initmode=0, initcenter):
#分为3种方法，通过initmode改变
m, n = np.shape(dataSet)
if initmode == 0: #随机选取中心
centroids = dataSet[random.sample(range(m), k)]
elif initmode == 1: #自定义类心
centroids = np.array(initcenter)
else:
#随机选取一些数据，求出他们的平均数，作为类心
centroids = np.zeros((k, n))
for i in range(k):
centroids[i] = dataSet[random.sample(range(m), m // k)].mean()
return centroids
def kMeans(dataSet, k, mindif = 0, initmode = 0, initcenter = []):
'''
mindif:前后类心改变的最小阈值
initmode:初始化类心方式
initcenter:自定义初始化类心
'''
m, n = dataSet.shape
minLimit = np.zeros((k, n))
minLimit.fill(mindif)
#初始类心
centroids = initCent(dataSet, k, initmode, initcenter)
#分类结果
clusterAssment = np.zeros(m)
#用于判断类心是否改变
lastcent = np.zeros(centroids.shape)
while True:
#重新聚类
for i in range(m):
dis = disEclud(dataSet[i], centroids)
clusterAssment[i] = dis.argmin()
#更新类心
for cent in range(k):
centroids[cent] = dataSet[np.where(clusterAssment == cent)].mean(axis = 0)
#判断是否停止迭代
if (abs(centroids - lastcent) <= minLimit).all():
break
else:
lastcent = np.array(centroids)
continue
return centroids, clusterAssment
#求众数
def mode(train_x):
train_x = train_x.astype(np.int64)
counts = np.bincount(train_x)
return np.argmax(counts)
#测试数据
def test(classSet, train_y, k):
label = np.array(train_y)
for i in range(1, k+1):
categorySet = classSet[np.where(train_y == i)]
category = mode(categorySet)
label[np.where(train_y == i)] = category
return (classSet == label).sum() / classSet.shape
train_x, label = loadData('wine.data.txt')
train_x = dataNormalized(train_x)
center, classSet = kMeans(train_x, 3, initmode=2)
print(test(classSet, label, 3))
代码解释输出：
[0.9494382]
#采用第３中初始类心的方法，可以稳定在这个数据左右．
#如果是随机初始类心的话，最高的准确率可达到．0.96
代码解释k-means算法的优缺点
优点：简单，对簇型数据分类较好
缺点：
对于离群数据与孤立样本具有高度敏感性 ，可以通过基于LOF方法进行离群数据识别 ，在识别出异常数据后进行清理 ，并重新执行聚类过程 ，从而降低异常数据与边缘样本对聚类结果的影响程度
ｋ值选取不确定 ，可以通过ISODATA算法改进．
初始聚类中心是决定最终分类结果的关键因素 ，这些改进方案包括k-means++算法和二分K-means算法．
该聚类方法专为处理具有球状分布特征的数据而设计．其核心原因在于其在计算距离时采用欧氏度量方式，在这种情况下会形成一个超球体形状．而对于分布呈现非均匀特性的数据集，则更适合采用基于密度的方法进行聚类分析；例如DBSCAN算法是一种常用的方法
k-means适用于连续数据 ．采用k-modes算法，可实现对离散数据的快速聚类．
大量数据的处理往往会导致耗时较长。具体而言，在这种情况下（即当数据量很大且迭代次数较多时），算法的时间复杂度将显著提升。在传统的K-Means算法中使用每轮迭代时需要计算所有样本点至质心的距离。这样的计算方式会导致耗时较长。
- （１）elkan K-均值聚类算法通过优化距离度量实现了对冗余运算的有效避免并提升了运行效率；当处理的数据呈现高维稀疏特征时该方法无法得到有效应用。
- （２）改进型Mini Batch K-均值算法基于抽样策略能够在较短时间内显著加快收敛速度但会伴随一定的分类精度损失这种损失通常处于可接受范围内。为了解决这一问题我们通常会重复执行此过程并根据多次实验结果选择最优的聚类方案以提高最终分类效果。
k-means算法与图像分割
图像分割属于图像处理技术中的一种重要手段。该技术旨在将一幅图象划分为多个互不重叠的区域组别，并本质上可被看作是对像素进行分类的过程。通常所采用的图象分割方法大致可分为：
- 基于边缘的技术
- 基于区域的技术
基于聚类算法的图像分割属于基于区域的技术。
具体的原理是 ：对图像的像素值进行聚类，颜色相近的像素会形成一类．
主要依赖于PIL和scikit-learn库。我编写的k-means算法在初始质心选择不当时往往难以有效分离数据集。因此转向了基于scikit-learn库实现的k-means算法。
PIL主要用到以下几个函数：
#打开图片
q = Image.open('test2.jpg')
#图片显示
q.show()
#转换图片格式，灰度图
q = q.convert('L')
#图片的属性
im.format, im.size, im.mode
#ｒｇｂ通道分离
r,g,b = q.split()
#取得像素点的值
q.getpixel((4,4))
#改变像素点的值
q.putpixel(xy, color)
#创建新图
Image.new(mode, size)
#保持图
im.save("save.gif","GIF")
代码解释以下是图像分离全部代码
from PIL import Image
from sklearn.cluster import KMeans
q = Image.open('test2.jpg')
q.show()
m, n = q.size
q1 = np.array(q)
#这里有坑，注意q.size和q1.shape的值不一样，横竖跌倒
q1 = q1.reshape((m*n, 3))
k = ８
y = KMeans(n_clusters = k).fit_predict(q1)
centroids = np.zeros((k, 3))
#计算类心值，之后填充图像
for cent in range(k):
centroids[cent] = q1[np.where(y == cent)].mean(axis = 0)
ynew = y.reshape((n, m))
pic_new = Image.new("RGB", (m, n))
for i in range(m):
for j in range(n):
pic_new.putpixel((i, j), tuple([int(x) for x in centroids[ynew[j][i]]]))
pic_new.show()
代码解释原图是：
聚类之后的图：ｋ ＝ ８
分离出来的苹果：
