Машинное обучение - алгоритм k-ближайших соседей

искусственный интеллект

Алгоритм k-ближайших соседей (kNN) — это классический алгоритм классификации с учителем.Основная идея состоит в том, что если большинство k ближайших соседей выборки в пространстве признаков принадлежат к определенной категории, результаты классификации выборок также принадлежат к этой категории.

1. Шаги алгоритма

  • Подготовка обучающих данных и тестовых данных;
  • определить параметр k;
  • Рассчитайте расстояние между тестовыми данными и каждыми обучающими данными и отсортируйте увеличивающееся отношение расстояния;
  • Выберите k точек с наименьшим расстоянием;
  • Определить частоту появления категории, к которой принадлежат первые k точек;
  • Возвращает наиболее часто встречающийся класс среди первых k точек в качестве предсказанной классификации для тестовых данных.

2. Код Python для реализации kNN

2.1 Реализация алгоритма

# python 3.7.2

from numpy import *
import operator

def kNNClassify(testData, trainData, labels, k):
    dataSize = trainData.shape[0]  # 测试数据矩阵的行数，4
    diffMat = tile(testData, (dataSize, 1)) - trainData  # numpy中的tile用于重复矩阵中的元素，构造和dataSize规格一样
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)  # 计算矩阵的行和
    distances = sqDistances ** 0.5  # 采用欧式距离计算
    sortedDisindexes = distances.argsort()  # 返回排序后对应的索引数据
    classCount = {}
    for i in range(k):
        voteLabel = labels[sortedDisindexes[i]]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)  # 根据第2维进行排序
    return sortedClassCount[0][0]

Предположим, что данные обучения:

trainData= [[1, 1.1], [1, 1], [0, 0], [0, 0.1]]
labels = ['A', 'A', 'B', 'B']

Данные теста:

testData = [[1.1 , 1], [0.1, 0]]

2.2 Настоящий бой: сопоставление объектов на сайтах знакомств

Сяо Шуи просматривает девушек на сайте знакомств и оценивает каждую девушку, которую видит:largeDoses,smallDoses,didntLike, оценка основывается на 3 критериях:

  • Годовой пробег
  • Игры составляют долю времени в сутках
  • Количество съеденных десертов в неделю

1000 единиц связанных данных собираются и сохраняются в файле датированияTestSet.txt.

40920    8.326976    0.953952    largeDoses
14488    7.153469    1.673904    smallDoses
26052    1.441871    0.805124    didntLike
75136    13.147394    0.428964    didntLike
38344    1.669788    0.134296    didntLike
72993    10.141740    1.032955    didntLike
35948    6.830792    1.213192    largeDoses
42666    13.276369    0.543880    largeDoses
67497    8.631577    0.749278    didntLike
35483    12.273169    1.508053    largeDoses
50242    3.723498    0.831917    didntLike
63275    8.385879    1.669485    didntLike
5569    4.875435    0.728658    smallDoses
51052    4.680098    0.625224    didntLike
...
2.2.1 Чтение данных текстового файла и построение матрицы
def file2Matrix(filename):
    love_dictionary = {'largeDoses': 1, 'smallDoses': 0, 'didntLike': -1}
    fr = open('datingTestSet.txt')
    arrayOfLines = fr.readlines()
    numOfLines = len(arrayOfLines)
    dataMatrix = zeros((numOfLines, 3))  # 数据矩阵
    classLabels = []  # 标签数组
    index = 0
    for line in arrayOfLines:
        line = line.strip()
        listFromLine = line.split('\t')
        dataMatrix [index, :] = listFromLine[0:3]
        classLabels.append(love_dictionary.get(listFromLine[-1]))
        index += 1
    return returnMat, classLabels
2.2.2 Обработка нормализации данных

Числовые значения каждого измерения сильно различаются, и прямое использование серьезно повлияет на эффект классификации, поэтому требуется нормализация:
newValue = (oldVlue -min) / (max - min)

def autoNorm(dataSet):
    minVals = dataSet.min(0)  # min(0)返回列的最小值， min(1)返回行的最小值
    maxVals = dataSet.max(0)  # max(0)返回列的最大值， max(1)返回行的最大值
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = normDataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet / tile(ranges, (m, 1))
    return normDataSet

последний звонокkNNClassifyфункцию для проверки. опущено здесь

3. Преимущества и недостатки алгоритма

3.1 Преимущества

  • Простой, понятный, простой в реализации;
  • Подходит для классификации числовых атрибутов;
  • Подходит для задач мультиклассификации (мультимодальных, когда объекты имеют несколько меток классов), kNN превосходит SVM.

3.2 Недостатки

  • Когда выборки несбалансированы, например, размер выборки одного класса велик, а размер выборки других классов очень мал, это может привести к тому, что при вводе новой выборки выборки класса большой емкости среди k соседей выборки составляют большинство, и в классификации появится отклонение.
  • Объем вычислений велик, и для каждого текста, подлежащего классификации, необходимо вычислить его расстояние до всех известных образцов.

4. Стратегия улучшения

Стратегии улучшения в основном делятся на分类效率и分类效果Два направления:

  • Эффективность классификации: атрибуты выборки заранее сокращаются, а атрибуты, оказывающие меньшее влияние на результаты классификации, удаляются. Алгоритм больше подходит для автоматической классификации домена класса с большим размером выборки, а домен класса с небольшим размером выборки более подвержен неправильной классификации.
  • Эффект классификации: ① Используйте взвешенный метод (с выборкой с небольшим расстоянием до соседа с большим весом) для улучшения, например взвешенный метод k ближайших соседей WAkNN (взвешенный скорректированный k ближайших соседей); ② Согласно различным классификациям в обучающий набор Количество файлов, выберите различное количество ближайших соседей для участия в классификации ③ Алгоритм центра класса, найдите расстояние от центра класса каждого образца до тестовых данных и разделите его на ближайший класс.

использованная литература

  • «Машинное обучение в действии»
Категории