kmeans算法python实现三类_K-Means 算法总结和 Python 实现

叁歲伎倆 2023-01-09 01:16 145阅读 0赞

在聚类算法中，我们给定训练集 $\{x\{(1)\},...,x\{(m)\}\}$ (醉了，简书的 Markdown 平台不支持数学公式的解析 o(≧口≦)o，可参考我另外的博客)，希望这些输入数据聚类到若干个类簇当中。其中$x\{(1)\}\\in\{Rn\}$，但是每个样本数据没有$y^\{(i)\}$，即没有类标信息，因而这时一个无监督学习问题。

K-Means 主要想法是找到 k 个质心，将离某个质心最近的样本聚类到这个类簇档当中，将所有样本聚类成 k 个类簇(对K-Means 详细的介绍可参考 Wikipedia)。基本算法那如下：

![Image 1][]

Pseudocode of K-Means

第一步，首先随机初始化 k 个质心的位置。

第二步是一个迭代循环的操作:

首先对于每一个样本 $x^\{(i)\}$，找到离该样本最近的质心，将其归类到该质心对应的类簇中，即这里的第 $j$ 个类簇中。

将所有样本都归类到对应的类簇后，需要利用每一个类簇中的样本，重新计算该类簇中所有样本的均值得到新的质心。

循环执行步骤1和步骤2，直至收敛，即迭代过程中质心不再更新。

Python 实现简单的 K-Means 算法如下：

\_\_author\_\_ = 'bin'

\# reference: https://datasciencelab.wordpress.com/2013/12/12/clustering-with-k-means-in-python/

import numpy as np

import random

import matplotlib.pyplot as plt

\# Lloyd's algorithm

\# inner loop step 1

def cluster\_points(X, mu):

clusters = \{\} \# store k centers, type: dict

for x in X:

\# bestmukey is "int" type

\# for i in enumerate(mu):

\# print ((i\[0\], np.linalg.norm(x-mu\[i\[0\]\])))

bestmukey = min(\[(i\[0\], np.linalg.norm(x - mu\[i\[0\]\])) \\

for i in enumerate(mu)\], key=lambda t: t\[1\])\[0\]

\# A new built-in function, enumerate(), will make certain loops a bit clearer.

\# enumerate(thing), where thing is either an iterator or a sequence,

\# returns a iterator that will return (0, thing\[0\]), (1, thing\[1\]), (2, thing\[2\]), and so forth.

\# key=lambda t:t\[1\] is used for sort this dict by t:t\[1\] (the second element in this element)

try:

clusters\[bestmukey\].append(x)

except KeyError:

clusters\[bestmukey\] = \[x\]

return clusters

\# inner loop step 2, (update the mu)

def reevaluate\_centers(mu, clusters):

newmu = \[\]

keys = sorted(clusters.keys())

for k in keys:

print len(clusters\[k\])

newmu.append(np.mean(clusters\[k\], axis=0))

return newmu

def has\_converged(mu, oldmu):

\# A tuple is a sequence of immutable Python objects.

\# tuple is using (), list is using \[\], dict is using \{\}

return (set(\[tuple(a) for a in mu\]) == set(\[tuple(a) for a in oldmu\]))

def find\_centers(X, K):

\# Initialize to K random centers

oldmu = random.sample(X, K)

mu = random.sample(X, K)

while not has\_converged(mu, oldmu):

oldmu = mu

\# Assign all points in X to clusters

clusters = cluster\_points(X, mu)

\# Reevaluate centers (update the centers)

mu = reevaluate\_centers(oldmu, clusters)

return (mu, clusters)

\# The initial configuration of points for the algorithm is created as follows:

def init\_board(N):

\# random.uniform:

\# Draw samples from a uniform distribution

X = np.array(\[(random.uniform(-1, 1), random.uniform(-1, 1)) for i in range(N)\])

return X

\# The following routine constructs a specified number of Gaussian distributed clusters with random variances:

def init\_board\_gauss(N, k):

n = float(N) / k

X = \[\]

for i in range(k):

c = (random.uniform(-1, 1), random.uniform(-1, 1))

s = random.uniform(0.05, 0.5)

x = \[\]

while len(x) < n:

a, b = np.array(\[np.random.normal(c\[0\], s), np.random.normal(c\[1\], s)\])

\# Continue drawing points from the distribution in the range \[-1,1\]

if abs(a) < 1 and abs(b) < 1:

x.append(\[a, b\])

X.extend(x)

X = np.array(X)\[:N\]

return X

if \_\_name\_\_ == "\_\_main\_\_":

X = init\_board(100)

K = 4

mu, clusters = find\_centers(X, K)

x = \[\]

y = \[\]

for i in range(K):

lx = \[\]

ly = \[\]

for l0 in clusters\[i\]:

lx.append(l0\[0\])

ly.append(l0\[1\])

x.append(lx)

y.append(ly)

for i in range(K):

plt.plot(x\[i\], y\[i\], 'o')

plt.plot(mu\[i\]\[0\], mu\[i\]\[1\], 's', markersize=10)

plt.show()

程序中假设 $k=4$，可以看到用均匀分布随机生成的样本，在算法收敛后，成功被聚成了四类。

![Image 1][]

运行结果图

很明显地可出看到 K-Means 有两个较大的问题：

$k$ 值的选择问题，如何确定这个 $k$ 值的大小

如何初始化 $k$ 个质心

这两个方面的内容将在后续的总结中补上，这两个部分一般在面试中只要问到了 K-Means 算法肯定是绕不开的。

另外，K-Means 的优缺点简单总结如下：

优点：

收敛速度快

缺点：

需要调到合适的 $k$ 值

对异常值敏感，不够 robust

需要样本存在均值

只能保证局部最优

吐槽：简书的 Markdown 不支持 LaTeX，数学公式要怎么打出来 o(≧口≦)o

Reference

[Image 1]:

kmeans算法python实现三类_K-Means 算法总结和 Python 实现

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 kmeans聚类算法python实现

相关 Kmeans算法实现

相关 kmeans聚类算法python实例

相关 kmeans算法python实现三类_K-Means 算法总结和 Python 实现

相关 Kmeans、Kmeans++和KNN算法比较

相关 Kmeans、Kmeans++和KNN算法比较

相关 Python机器学习算法实践_自定义实现kmeans

相关 K-means 算法 Kmeans++ 二分Kmeans

相关 KMeans++算法理论和实现

相关 MapReduce实现kmeans算法