Алгоритм кластеризации k-средних машинного обучения (реализация на Python)

машинное обучение искусственный интеллект Python алгоритм

Алгоритм kNN был кратко представлен в прошлый раз, Короче говоря, путем вычисления расстояния между целевым значением и выборочными данными выберите k ближайших значений и используйте значение классификации с большой вероятностью появления для представления классификации целевого значения Алгоритм относительно прост в реализации и относится к методу обучения с учителем. В этой статье мы кратко познакомим вас с алгоритмом кластеризации k-средних, который, в отличие от предыдущих, представляет собой метод обучения без учителя. В машинном обучении есть две большие проблемы: классификация и кластеризация. Классификация заключается в обучении какой-либо обучающей машины классифицировать образцы неизвестного класса в соответствии с некоторыми заданными образцами с известными метками классов. Это контролируемое обучение. Кластеризация относится к незнанию заранее метки категории любого образца в надежде разделить группу неизвестных категорий образцов на несколько категорий с помощью некоторого алгоритма, который в машинном обучении называется неконтролируемым обучением.

алгоритм кластеризации k-средних

Обычно выборки делятся на разные категории в соответствии с определенным расстоянием или сходством между выборками, что называется кластеризацией. Например, для заданного набора данных некоторые данные (двумерные, всего 80) выглядят следующим образом:

1.658985    4.285136
-3.453687   3.424321
4.838138    -1.151539
-5.379713   -3.362104
0.972564    2.924086

Его визуализация выглядит следующим образом:

image.png
Из состояния распределения можно приблизительно узнать, что его можно сгруппировать в 4 кластера. Конечная цель — отметить 4 разных кластера разными цветами. Использование алгоритма k-средних для достижения следующего:

  1. Случайным образом выберите k точек в качестве начальных центроидов.
  2. Для каждой точки выборки найдите расстояние от точки k отдельно. В эту категорию попадает тот, у кого наименьшее расстояние.
  3. В это время для полученных k категорий пересчитайте новые центроиды.
  4. Когда центроид, полученный на шаге 3, имеет небольшую ошибку относительно предыдущего центроида, классификация завершается. Используемые формулы очень просты, а код подробно описан позже.

реализация кода на питоне

# 数据初始化
import numpy as np
import random
import re
import matplotlib.pyplot as plt

def loadDataSet():
    dataSet = np.loadtxt("dataSet.csv")
    return dataSet

def initCentroids(dataSet, k):
    # 从数据集中随机选取k个数据返回
    dataSet = list(dataSet)
    return random.sample(dataSet, k)

В соответствии с шагом 2 рассчитайте расстояние и классифицируйте его, классифицируйте его по кратчайшему расстоянию до разных центроидов и сохраните его в словаре.

def minDistance(dataSet, centroidList):

    # 对每个属于dataSet的item， 计算item与centroidList中k个质心的距离，找出距离最小的，并将item加入相应的簇类中
    clusterDict = dict() #dict保存簇类结果
    k = len(centroidList)
    for item in dataSet:
        vec1 = item
        flag = -1
        minDis = float("inf") # 初始化为最大值
        for i in range(k):
            vec2 = centroidList[i]
            distance = calcuDistance(vec1, vec2)  # error
            if distance < minDis:
                minDis = distance
                flag = i  # 循环结束时， flag保存与当前item最近的蔟标记
        if flag not in clusterDict.keys():
            clusterDict.setdefault(flag, [])
        clusterDict[flag].append(item)  #加入相应的类别中
    return clusterDict  #不同的类别

def getCentroids(clusterDict):
    #重新计算k个质心
    centroidList = []
    for key in clusterDict.keys():
        centroid = np.mean(clusterDict[key], axis=0)
        centroidList.append(centroid)
    return centroidList  #得到新的质心

Рассчитайте среднеквадратичную ошибку между каждым набором кластеров, чтобы измерить эффект кластеризации.

def getVar(centroidList, clusterDict):
    # 计算各蔟集合间的均方误差
    # 将蔟类中各个向量与质心的距离累加求和
    sum = 0.0
    for key in clusterDict.keys():
        vec1 = centroidList[key]
        distance = 0.0
        for item in clusterDict[key]:
            vec2 = item
            distance += calcuDistance(vec1, vec2)
        sum += distance
    return sum

#测试聚类效果，并可视化
def test_k_means():
    dataSet = loadDataSet()
    centroidList = initCentroids(dataSet, 4)
    clusterDict = minDistance(dataSet, centroidList)
    # # getCentroids(clusterDict)
    # showCluster(centroidList, clusterDict)
    newVar = getVar(centroidList, clusterDict)
    oldVar = 1  # 当两次聚类的误差小于某个值是，说明质心基本确定。

    times = 2
    while abs(newVar - oldVar) >= 0.00001:
        centroidList = getCentroids(clusterDict)
        clusterDict = minDistance(dataSet, centroidList)
        oldVar = newVar
        newVar = getVar(centroidList, clusterDict)
        times += 1
        showCluster(centroidList, clusterDict)

if __name__ == '__main__':
    # show_fig()
    test_k_means()

Как и выше, когда ошибка между двумя рассчитанными центроидами находится в пределах 0,00001, кластеризацию можно считать завершенной. Запустите функцию:

image.png
image.png
image.png
image.png

Из результатов видно, что при непрерывной итерации эффект кластеризации становится все лучше и лучше, пока он не становится меньше ошибки, и кластеризация завершается.

Пожалуйста, обратитесь к github за полным кодом и данными:
github:k-means

Суммировать

  • неконтролируемое обучение
  • алгоритм k-средних
  • Минимизация квадрата разности характеризует тесноту векторов внутри кластера.

Ссылки: (с введением формулы)
Реализация Python алгоритма кластеризации средних значений кластеризации (k-средних)
Алгоритм машинного обучения и практика Python (5) Кластеризация k-средних (k-means)

Категории