以简单的 Iris 数据集做测试，实现了 K-means++ 聚类算法，并与 sklearn 中自带的 KNN 算法进行比较
标题本来是 K-Means&KNN，把 & 改成了和，因为标题中出现特殊符号 & 会导致我的 sitemap 生成错误…

简介

K-Means 是简单的基于划分的聚类方法，要解决的问题是，现在有 n 个样本 (点集 X)，将他们的特征向量投射到高维空间中，根据空间分布可以大致划分成几个子空间，每个子空间中的点属于同一类，现在需要计算出每个点所在的类，大致思想就是随机选择 k 个点 (中心点集 C) 作为中心点，其余的点自己站队：离 k 个中心点里哪个点最近就站那个点的队，即和那个中心点划分到同一类中，这样就能形成 k 个类，重复上过程，期间引入一个损失评估，比如以各个类中的点到这个类中心点距离的和作为评估指标，当指标小于某一程度或者指标变化小于某一程度就停止重复
KNN 则比较简单粗暴，其思想类似于民主投票。KNN 不训练数据，选定一个值 K，对于每一个需要预测的向量，在已知类别的数据集中找到与这个向量最近的 K，这 K 个点中拥有最多点个数的类别就是预测类别，即让离某个点最近的 K 个点投票决定这个点的类别，哪个类别的点票数多就是哪个类别

K-means++

k-means++ 在 k-means 上优化了初始 k 个点的选择。原始算法是随机取 k 个点，显然这样随机不确定性太大，比较好的 k 个点的选择方案应该是他们离彼此尽量远，但不能太远。尽量远，就能尽可能贴近最终理想中心点分布；不能太远，是为了防止将一些错误点孤立点作为中心点
算法上的实现是先随机从 X 集中取第一个中心点，之后反复以下过程取中心点
- 计算每个点 $c_{i}$ 到已经选出的中心点 $k_{1}, k_{2} \dots$ 的距离，选取最小的一个距离作为 $c_{i}$ 的距离，这个距离的意义即 $c_{i}$ 作为下一个中心点时离其他中心点至少有多远
- 将 $c_{1}, c_{2}, c_{3} \dots$ 的距离归一化，并排成一条线
- 这条线长度为 1，分成了许多段，每一段的长度就代表了这一段所代表的点的距离在归一化中所占的比例，距离越大，比例越大
- 在 (0,1) 之间随机取一个数，这个数所在的段区间所代表的点就是下一个中心点，将其加入中心点集 C，接着重复找下一个中心点
可以看出，如果距离够远，在线上被随机抽到的可能越大，符合我们的需求

K-Means 代码实现

¶ 数据检视

Iris 是鸢尾花分类数据集，150 个样本，均匀分成 3 类，每一个样本有 4 个属性

¶ 初始化数据

初始化数据

def init():
    iris = load_iris()
    X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.25, random_state=33)
    ss = StandardScaler()
    X_train = ss.fit_transform(X_train)
    X_test = ss.fit_transform(X_test)
    return X_train, X_test, y_train, y_test, iris

¶k-means++ 初始化 k 个点

D2 是每个点的距离 (即之前定义的里其他中心点至少有多远)
probs 归一化
cumprobs 将归一化的概率累加，排列成一条线

def initk(X_train, k):
    C = [X_train[0]]
    for i in range(1, k):
        D2 = scipy.array([min([scipy.inner(c - x, c - x) for c in C]) for x in X_train])
        probs = D2 / D2.sum()
        cumprobs = probs.cumsum()
        r = scipy.rand()
        for j, p in enumerate(cumprobs):
            if r < p:
                i = j
                break
        C.append(X_train[i])
    return C

¶ 损失评估

在这里用每个类内点到中心点距离平方和的总和作为损失评估

def evaluate(C, X_train, y_predict):
    sum = 0
    for i in range(len(X_train)):
        c = C[y_predict[i]]
        sum += scipy.inner(c - X_train[i], c - X_train[i])
    return sum

¶ 聚类

初始化 k 个中心点后，所有的点就可以分类
重新在每个类中取中心点，在这里取一个类中所有点坐标平均作为中心点坐标

def cluster(C, X_train, y_predict, k):
    sum = [0, 0, 0, 0] * k
    count = [0] * k
    newC = []
    for i in range(len(X_train)):
        min = 32768
        minj = -1
        for j in range(k):
            if scipy.inner(C[j] - X_train[i], C[j] - X_train[i]) < min:
                min = scipy.inner(C[j] - X_train[i], C[j] - X_train[i])
                minj = j
        y_predict[i] = (minj + 1) % k
    for i in range(len(X_train)):
        sum[y_predict[i]] += X_train[i]
        count[y_predict[i]] += 1
    for i in range(k):
        newC.append(sum[i] / count[i])
    return y_predict, newC

¶ 主函数

计算损失，更新 k 个中心点，再站队 (聚类) 一次
重复，直到损失变化小于 10%
每次迭代显示新旧损失，显示损失变化
最后输出分类结果

def main():
    X_train, X_test, y_train, y_test, iris = init()
    k = 3
    total = len(y_train)
    y_predict = [0] * total
    C = initk(X_train, k)
    oldeval = evaluate(C, X_train, y_predict)
    while (1):
        y_predict, C = cluster(C, X_train, y_predict, k)
        neweval = evaluate(C, X_train, y_predict)
        ratio = (oldeval - neweval) / oldeval * 100
        print(oldeval, " -> ", neweval, "%f %%" % ratio)
        oldeval = neweval
        if ratio < 0.1:
            break

    print(y_train)
    print(y_predict)
    n = 0
    m = 0
    for i in range(len(y_train)):
        m += 1
        if y_train[i] == y_predict[i]:
            n += 1
    print(n / m)
    print(classification_report(y_train, y_predict, target_names=iris.target_names))

KNN 代码

直接使用了 sklearn 中的 KNeighborsClassifier

from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report


def init():
    iris = load_iris()
    X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.25, random_state=33)
    ss = StandardScaler()
    X_train = ss.fit_transform(X_train)
    X_test = ss.fit_transform(X_test)
    return X_train, X_test, y_train, y_test, iris


def KNN(X_train, X_test, y_train, y_test, iris):
    knc = KNeighborsClassifier()
    knc.fit(X_train, y_train)
    y_predict = knc.predict(X_test)
    print(knc.score(X_test, y_test))
    print(classification_report(y_test, y_predict, target_names=iris.target_names))


def main():
    X_train, X_test, y_train, y_test, iris = init()
    KNN(X_train, X_test, y_train, y_test, iris)

if __name__ == "__main__":
    main()

预测结果

指标说明
对于二分类，四种情况的总数：对的预测成对的 TP; 对的预测成错的 FN；错的预测成对的 FP；错的预测成错的 TN
$精确率 : P = \frac{T P}{T P + F P} 召回率 : R = \frac{T P}{T P + F N} 1 F 值 : \frac{2}{F_{1}} = \frac{1}{P} + \frac{1}{R}$
K-Means 程序输出
预测正确率：88.39%
平均精确率：89%
召回率：0.88
F1 指标：0.88
KNN 程序输出
预测正确率：71.05%
平均精确率：86%
召回率：0.71
F1 指标：0.70
原始分类
可以看到这个数据集本身在空间上就比较方便聚类划分
预测分类

改进

¶ 未知 k 的情况

以上是我们已知鸢尾花会分成 3 类，加入我们不知道有几类呢？毕竟 k-means 是无监督学习，可以在无标签的情况下计算，自然标签的个数我们也极有可能不知道，那么如何确定 k?
一种方式是 canopy 算法
待补充

topbookcc's Blog

机器学习入门：K-Means 和 KNN

简介

K-means++

K-Means 代码实现

¶ 数据检视

¶ 初始化数据

¶k-means++ 初始化 k 个点

¶ 损失评估

¶ 聚类

¶ 主函数

KNN 代码

预测结果

改进

¶ 未知 k 的情况

¶ 空类的处理

¶ 不同距离计算方式

¶ANN 算法