На сегодняшний день мне неизвестны доступные и легко понятные для непосвященного читателя книги по машинному обучению на русском языке. По теме написано много хороших трудов на английском, но по каким-то причинам они не переведены. Данной серией статей я преследую цель сдвинуть вектор ситуации в лучшую сторону. Если читатели положительно воспримет статью, я, по мере сил, постараюсь сделать замкнутый цикл статей по машинному обучению. Целевая аудитория — люди, желающие ознакомиться с основными задачами и методами машинного обучения, и в дальнейшем, возможно, углубить свои знания самостоятельно. Идеальный читатель знаком с основами языка программирования Python и библиотеки NumPy ^[1] или желает в них разобраться. Я постараюсь свести количество математики и простыней из формул к минимуму без ущерба для качества преподносимого материала. Заинтересованный читатель всегда может узнать математическую поднаготную каждого метода в википедии ^[2], на machinelearning.ru ^[3] или в соответствующей литературе.

Введение

В первую очередь хотелось бы избавить некоторых читателей от предрассудков. Машинное обучение не имеет ничего общего с Cyberdyne Systems T-800. Мы не будем совершать попытки разговаривать с компьютером или придавать машинам смысл жизни. Все что мы можем делать при помощи машинного обучения — анализировать данные. Мы не создаем ни киборгов, ни живых существ, а только придаем бесчувственному набору данных некоторый смысл.

Сегодня машинное обучение активно используется во многих областях нашей жизни. Оно применяется для:

• Распознавания речи, жестов, рукописного текста, образов;
• Технической диагностики;
• Медицинской диагностики;
• Обнаружения мошенничества и спама;
• Категоризации документов;
• Финансового надзора;
• Кредитного скоринга;
• Предсказаниея ухода клиентов;
• Ранжирования в информационном поиске;
• Многих других целей.

Что такое машинное обучение?

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

Ключевая терминология машинного обучения

Для того, чтобы понять и лучше запомнить терминологию, рассмотрим пример задачи машинного обучения на примере классификатора птиц. Такой тип систем представляет собой очень интересный подраздел машинного обучения под названием экспертные системы. Создавая программу, которая распознает птиц, мы заменяем орнитолога компьютером. Орнитолог – это эксперт по птицам, поэтому наша система и называется экспертной. В таблице ниже приведены значения для четырех параметров птиц, которые мы решили измерить. Мы выбрали для измерения вес, размах крыльев, наличие перепончатых лап и цвет. На самом деле, обычно измеряют гораздо больше параметров. Это обычная практика – измерить все, что можно и разбираться в важности каждого из параметров уже после. Четыре измеренных нами параметра называются функциями; иногда их называют атрибутами, но мы будем придерживаться термина «функция».

№	Вес	Размах крыльев	Перепончатые лапы	Цвет	Вид
1	1000.1	125.0	нет	коричневый	Buteo jamaicensis
2	3000.7	200.0	нет	серый	Sagittarius serpentarius
3	3300.0	220.3	нет	серый	Sagittarius serpentarius
4	4100.0	136.0	да	черный	Gavia immer
5	3.0	11.0	нет	зеленый	Calothorax lucifer
6	570.0	76.0	нет	черный	Campephilus principalis

Первые две характеристики, указанные в таблице, являются числовыми и могут принимать дробные значения. Третья особенность – перепончатые лапы является бинарной. Четвертая особенность – цвет представляет собой отображение на некоторое множество цветов. Cуществует награда в 50.000$ для того, кто сможет привести биолога к живому Campephilus principalis. Одной из задач машинного обучения является классификация, мы будем иллюстрировать ее при помощи данной таблицы и тот факт, что мы распознали Campephilus principalis приблизит нас к 50.000$. Мы хотим распознать птицу из большого количества других птиц в корыстных целях. Мы могли бы создать кормушку и посадить рядом с ней орнитолога, чтобы тот наблюдал и дал нам знать, когда к ней прилетит нужная нам птица. Однако, это было бы очень долгим процессом.

Также, мы могли бы автоматизировать этот процесс – создать много кормушек с камерами, подключенными к компьютеру и распознающими приближающихся птиц. Мы могли бы поставить кормушку на весы для определения веса птицы и написать код компьютерного зрения, определяющий ее размах крыльев, тип лап и цвет. Тогда у нас была бы вся информация о птице. Но как мы можем определить Campephilus principalis ли это или другая особь? Задача определения типа называется задачей классификации и в машинном обучении есть много алгоритмов, которые хорошо с ней справляются. В нашем примере классы – это виды птиц. Мы можем упростить задачу определив всего два класса – Campephilus principalis и все остальные.

Предположим, что мы выбрали алгоритм машинного обучения, чтобы использовать его для классификации. Далее нам нужно обучить этот алгоритм. Для обучения мы кормим алгоритм известными данными, известными как обучающая выборка. Обучающей выборкой называется множество обучающих примеров, которые мы используем для обучения нашего алгоритма. Таблица, приведенная выше является обучающей выборкой из 6 элементов. Каждый учебный элемент представляет собой 4 функции и 1 целевую переменную. Целевая переменная это то, что должен предсказывать обученный алгоритм. В задачах классификации целевая переменная является дискретной, а в задачах регрессии она непрерывна. Для обучающей выборки целевая переменная известна. Машина учится находить некоторую связь между значениями функций и целевой переменной. В задаче классификации значения целевых переменных называются классами и предполагается, что их число конечно.

Изначально программе на вход подается обучающая выборка и программа учится. Затем программе на вход подают некоторый набор тестов, для которого значения целевых переменных известны. Эти известные значения в идеально обученной программе должны 100%-но совпадать с значениями, определенными программой. На практике 100%-е попадание недостижимо и мы должны измерить точность алгоритма.

Предположим, что мы протестировали нашу программу классификации птиц и она удовлетворяет нашим критериям точности. Можем ли мы увидеть то, чему машина обучилась (знания)? Ответ на этот вопрос зависит от обстоятельств. Некоторые алгоритмы используют знания, которые легко интерпретируются человеком, некоторые – нет. Знания могут быть представлены в виде набора правил, распределения вероятностей или примера из обучающей выборки. В некоторых случаях нас интересует не создание экспертной системы, а только знания, которые машина получает в результате обучения.

Основные задачи машинного обучения

Теперь мы опишем основные задачи машинного обучения и зададим базу, которая позволит нам легко превратить алгоритм машинного обучения в работающую систему. Например, рассмотренная нам выше задача классификации заключается в предсказании класса некоторого объекта. Еще одной задачей машинного обучения является регрессия. Регрессия это прогнозирование числового значения. Большинство из вас, наверное уже знакомо с задачей регрессии на примере проведения наиболее подходящей линии через множество точек. Задачи классификации и регрессия являются примерами обучения с учителем. Противоположностью обучения с учителем является обучение без учителя. В задачах обучения без учителя нет целевой переменной, которую можно было бы соотнести с данными. Примером такого обучения является задача кластеризации, в которой мы группируем элементы по схожести. Другим примером машинного обучения без учителя может быть снижение размерности данных.

Существует множество алгоритмов для решения каждой задачи машинного обучения. Каким образом можно выбрать правильный для конкретного случая? Во-первых, вы должны рассмотреть ваши цели. Хотите ли вы узнать вероятность того, что завтра пойдет дождь или же желаете разделить избирателей по группам интересов. Какие данные у вас есть и какие можно собрать? Для того, чтобы определиться с классом вашей задачи можно воспользоваться следующей блок-схемой:

Этапы разработки алгоритмов машинного обучения

1. Сбор данных. Вы можете собирать данные при помощи парсера сайта, используя RSS или API. Вы можете собрать или купить устройство измерения скорости ветра, уровня сахара в крови или любое другое, отправляющее данные вам. Существует бесчисленное множество других способов сбора данных. Для экономии времени и сил можно использовать публично доступные данные.
2. Подготовка входных данных. Если у вас уже есть данные, необходимо убедиться что они находятся в пригодном для использования виде. Приведение данных к пригодному для использования виду, как правило, тривиальная задача по сравнению со сбором данных.
3. Анализ входных данных. Вы можете увидеть некоторые закономерности, глядя на данные. Например, наличие нескольких точек, значительно отличающихся от общей массы. Возможно, в ваших данных есть лишние и недостоверные элементы, которые необходимо удалить.
4. Обучение алгоритма. На этом этапе машина проходит обучение. Вы кормите алгоритм хорошими данными, полученными на 1-3 этапах и получаете информацию или знания. В случае использования обучения без учителя этот шаг пропускается.
5. Тестирование алгоритма. На этом шаге находит применение информация, полученная на предыдущем этапе. Во время тестирования вы проверяете насколько хорошо алгоритм справляется со своей задачей. В случае обучения с учителем у вас есть некоторые известные значения, которые можно использовать для проверки. В случае обучения без учителя, вам, возможно, придется использовать другие методики тестирования качества работы алгоритма. В любом случае, если вы не удовлетворены результатами, вы можете вернуться к шагу 4, что-то изменить и попробовать снова. Возможно вы поймете, что проблема в данных и вернетесь к шагу 1.
6. Использование результата. На этом шаге вы из алгоритма делаете работающую программу, если его работа на шагах 1-5 вас устраивает.

Классификация методом k ближайших соседей (kNN)

Первым рассмотренным нами алгоритмом будет метод k ближайших соседей. Он очень эффективен и его легко понять.

Теория

Плюсы метода: высокая точность, не требует предположений о данных, нечувствителен к аномалиям в данных.
Минусы: объем вычислений, требуется много памяти.
Работает с: численными и номинальными значениями.

Рассмотрим принцип работы метода. Изначально у нас есть обучающая выборка элементов, для каждого из которых известно в какой класс он попадает. Когда мы получаем новый элемент, класс которого неизвестен, мы смотрим на его положение относительно уже известных элементов. Далее мы смотрим на TOP K (K обычно целое число меньшее 20) наиболее близких элементов (ближайших соседей). Наконец, мы определяем новый элемент в тот класс, большинство элементов из которого находятся в TOP K.

Существует несколько модификаций алгоритма:

1. Метод ближайшего соседа это самый простой алгоритм классификации. Классифицируемый объект относится к тому классу, которому принадлежит ближайший объект обучающей выборки.
2. Метод k ближайших соседей. Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей — ближайших к нему объектов обучающей выборки. В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.
3. Метод взвешенных ближайших соседей. В задачах с числом классов 3 и более нечётность уже не помогает, и ситуации неоднозначности всё равно могут возникать. Тогда i-му соседу приписывается вес, как правило, убывающий с ростом ранга соседа. Объект относится к тому классу, который набирает больший суммарный вес среди ближайших соседей.

Практика

Теперь мы напишем на Python функцию, реализующую классификацию методом k ближайших соседей. Псевдокод функции выглядит следующим образом:

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

По шагам напишем алгоритм на Python. С целью сделать повествование понятным читателю, не знакомому с библиотекой NumPy, мы разделим программу на несколько функций. Наш алгоритм принимает на вход 4 аргумента. x — элемент для классификации, dataSet — матрица обучающих примеров, labels — названия классов элементов из dataSet, и k — число ближайших соседей. Мощность (число элементов) labels, по определению, должна быть равна мощности dataSet. Мы вычисляем расстояние между двумя элементами A и B, как Евклидово расстояние по формуле:

Напишем функцию, которая будет принимать на вход x и dataSet и возвращать отсортированные расстояния от каждого элемента из dataSet до x.

def distances(x, dataSet):
    dataSetSize = dataSet.shape[0]    #shape[0] возвращает число элементов по нулевой оси
    diff = tile(x, (dataSetSize,1)) - dataSet    #Получаем расстояние по осям. tile строит массив из повторений
    sqDiff = diff ** 2    # Получаем квадраты расстояний по осям
    sqDistances = sqDiff.sum(axis = 1)    # Получаем сумму квадратов расстояний по осям
    distances = sqDistances ** 0.5    # Извлекаем корень
    return distances    # Возвращаем список номеров элементов по возрастанию расстояния до x

Вызывая функцию, на тестовых данных получаем следующий результат:

print distances([0,0],array([[0,1],[1,0],[2,2],[1,1]]))
# Выведет [ 1.00000000, 1.00000000, 2.82842712, 1.41421356]

Далее напишем функцию, сортирующую элементы из dataSet по возрастанию расстояний до элемента x. Функция будет принимать на вход только distances = distances(x, dataSet)

def sortedDistances(distances):
    sortedDistances = distances.argsort()    # Сортируем по возрастанию. Получаем список номеров элементов.
    return sortedDistances    # Возвращаем список номеров элементов по возрастанию расстояния до x

Вызывая функцию, на тестовых данных получаем следующий результат:

distances = distances([0,0],array([[0,1],[1,0],[2,2],[1,1]]))
print sortedDistances(distances)
# Выведет [0, 1, 3, 2]

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

def classify(sortedDistances, labels, k):
    classCount = {}    # Создаем пустой словарь (TOP классов)
    for i in arange(k):    # Для k первых элементов
        votelabel = labels[sortedDistances[i]]    # Определим класс k-го по близости элемента
        classCount[votelabel] = classCount.get(votelabel,0) + 1    # Добавим 1 к встречаемости этого класса
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)    # Отсортируем
    return sortedClassCount[0][0]    # Выведем наиболее часто встречающийся

Вызывая функцию, на тестовых данных получаем следующий результат:

distances = distances([0,0],array([[0,1],[1,0],[2,2],[1,1]]))
print sortedDistances(distances)distances = distances([0,0],array([[0,1],[1,0],[2,2],[1,1]]))
sortedDistances = sortedDistances(distances)
print classify(sortedDistances, {0:'one',1:'one',2:'three',3:'four'},3)
# Выведет 'one'

Таким образом мы определили класс нового элемента. Часто новый элемент добавляют в dataSet. Алгоритм теперь можно записать в виде одной функции.

from numpy import *
import operator

def kNN(x, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diff = tile(x, (dataSetSize,1)) - dataSet
    sqDiff = diff ** 2
    sqDistances = sqDiff.sum(axis=1)
    distances = sqDistances ** 0.5
    sortedDistances = distances.argsort()
    classCount = {}
    for i in arange(k):
        votelabel = labels[sortedDistances[i]]
        classCount[votelabel] = classCount.get(votelabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

print kNN([0,0],array([[0,1],[1,0],[2,2],[1,1]]),{0:'one',1:'one',2:'three',3:'four'},3)

Как проверить классификатор

Мы построили алгоритм классификации на основе метода ближайших соседей. Но, как и следовало ожидать, он не всегда классифицирует элементы верно. Существуют различные способы изучения того, как часто алгоритм ошибается. Кроме того есть разные настройки, которые влияют на производительность классификатора. Для анализа работы классификатора вы можете запустить его на некотором наборе данных, классы которых известны и сравнить полученный результат с вашим. Для получения частоты ошибок вы можете разделить их количество на общее число классифицируемых элементов. Значение 0 означает, что ваш классификатор работает идеально, а 1 говорит о том, что классификатор всегда неправ.

Пример из жизни. Улучшение сайта знакомств

Для каждого посетителя сайта знакомств всех зарегистрированных пользователей можно разделить на три группы:

• люди, которые ему не нравятся
• люди, которые ему нравятся, но не сильно
• люди, которые ему очень нравятся

Алгоритм использования kNN для улучшения реккомендаций сайта знакомств:

1. Сбор данных: Текстовый файл нам предоставлен
2. Подготовка данных: Парсинг текстового файла при помощи Python
3. Анализ данных: Используем Matplotlib для построения 2D графиков наших данных
4. Обучение: Не требуется для kNN
5. Тестирование: Проверим работу алгоритма на известном наборе данных
6. Использование: Написание программы, которая позволит классифицировать каждого пользователя сайта

Этап 1. Сбор данных

Текстовый файл с данными можно скачать по ссылке ^[4].

Этап 2. Подготовка данных

Данные находятся в файле dataset.txt, и представляют собой 1000 записей по одной записи в строке. В каждой строке есть информация о количестве полетов на самолете за год, часов, проведенных за видеоиграми и килограмм съеденного мороженого. Также, в каждой строке есть класс, к которому принадлежит человек. Чтобы наш алгоритм мог понимать данные, их необходимо распарсить. Для этого напишем функцию file2matrix, которая принимает на входе название файла и возвращает матрицу обучающих примеров и вектор классов.

def file2matrix(filename):
    file = open(filename)    # Открываем файл
    numberOfLines = len(file.readlines())    # Считаем количество строк в файле
    data = zeros((numberOfLines,3))    # Создаем нулевую матрицу нужной размерности
    labels = []    # Создаем пустой вектор классов
    file = open(filename)    # Открываем файл
    index = 0
    for line in file.readlines():    # Для каждой строки из файла
        line = line.strip()    # Считываем ее
        listFromLine = line.split('t')    # Разделяем строку по табуляциям
        data[index,:] = listFromLine[0:3]       # Заносим данные index-строку матрицы
        label = 1
        if listFromLine[-1] == "didntLike":
            label = 1
        elif listFromLine[-1] == "smallDoses":
            label = 2
        elif listFromLine[-1] == "largeDoses":
            label = 3
        labels.append(label)    # Добавляем числовой эквивалент класса в вектор классов
        index += 1
    return data,labels

Теперь у нас есть данные в том виде, в котором с ними можно работать.

Этап 3. Анализ данных

Теперь мы построим диаграмму рассеивания при помощи Python библиотеки Matplotlib. Напишем функцию, которая будет визуализировать данные.

def plot(data, labels):
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(data[:,1], data[:,2], 15.0 * array(labels), 15.0 * array(labels))
    plt.show()

data,labels = file2matrix('dataset.txt')
plot(data, labels)

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

def plot(data, labels):
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(data[:,0], data[:,1], 15.0 * array(labels), 15.0 * array(labels))
    plt.show()

data,labels = file2matrix('dataset.txt')
plot(data, labels)

График примет следующий вид:

Этап 4. Нормализация числовых значений

Поскольку количество съедаемого мороженого в неделю и число миль, которые человек пролетает на самолете за год — величины разных порядков, эти числовые значения необходимо нормализовать. Обычно диапазон нормализации выбирается от 0 до 1 или от -1 до 1. Для масштабирования значений от 0 до 1 необходимо применить следующую формулу:

Для нормализации напишем следующую функцию:

def norm(data):
    min = data.min(0)    # Находим минимальный элемент
    max = data.max(0)    # Находим максимальный элемент
    range = max - min    # Находим диапазон значений
    norm = zeros(shape(data))    # Создаем нулевую матрицу для нормализованых значений
    m = data.shape[0]    # Считаем число элементов в матрице данных
    norm = (data - tile(min, (m,1)))/tile(range,(m,1))    # Заполняем матрицу для нормализованных значений
    return norm, range, min

Этап 5. Тестирование классификатора

Теперь, когда у нас есть пригодные для использования данные мы готовы к проверке нашего классификатора. Оценка точности алгороитма является одной из ключевых задач в машинном обучении. Один из способов тестирования — взять, например, 90% данных для обучения классификатора и оставить 10% для его тестирования. Существуют и более продвинутые способы оценки точности. Важно, чтобы 10% данных для тестирования были выбраны случайным образом. Наши данные хранятся без определенной последовательности, а, значит, мы можем взять первые или последние 10% выборки.

Ранее я упоминал, что частота ошибок классификатора измеряется числом от 0 до 1, которое определяется как число ошибок, деленное на общее число классификаций. Для тестирования алгоритма мы напишем следующую функцию:

def test():
    ratio = 0.1
    data, labels = file2matrix('dataset.txt')
    norm, range, min = normal(data)
    m = norm.shape[0]
    testCount = int(m*ratio)
    errors = 0.0
    for i in arange(testCount):
        result = kNN(norm[i,:],norm[testCount:m,:], labels[testCount:m],3)
        print "Алгоритм решил, что элемент принадлежит классу: %d, на самом деле класс: %d" % (result,labels[i])
        if (result != labels[i]):
            errors += 1.0
    print "Общая частота ошибок: %f" % (errors/float(testCount))

В результате работы функции мы получим следующий результат:

Алгоритм решил, что элемент принадлежит классу: 3, на самом деле класс: 3
Алгоритм решил, что элемент принадлежит классу: 2, на самом деле класс: 2
…
Алгоритм решил, что элемент принадлежит классу: 2, на самом деле класс: 2
Алгоритм решил, что элемент принадлежит классу: 1, на самом деле класс: 1
Алгоритм решил, что элемент принадлежит классу: 3, на самом деле класс: 1
Общая частота ошибок: 0.050000

Классификатор ошибается всего в 5% случаев. Не плохо. Результат можно улучшить поэксперементировав с количеством соседей в kNN и размером обучающей выборки.

Этап 6. Создание работающей системы

Теперь, когда нас устраивает результат тестирования алгоритма мы можем написать программу, классифицирующую человека по параметрам. Для этого напишем следующую функцию:

def classifyPerson():
    results = ['не нравится','немного нравится', 'сильно нравится']
    games = float(raw_input("сколько времени человек проводит за видеоиграми?"))
    miles = float(raw_input("сколько миль он летает в год?"))
    iceCream = float(raw_input("сколько литров мороженого в неделю он съедает?"))
    data,labels = file2matrix('dataset.txt')
    norm, range, min = normal(data)
    arr = array([miles, games, iceCream])
    classResult = kNN((arr - min)/range,norm,labels,3)
    print "Человек ", results[classResult - 1]

Таким образом мы получили работающий классификатор. Весь его исходный код:

from numpy import *
import operator
import matplotlib
import matplotlib.pyplot as plt

def kNN(x, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(x, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    sortedDistances = distances.argsort()
    classCount = {}
    for i in arange(k):
        votelabel = labels[sortedDistances[i]]
        classCount[votelabel] = classCount.get(votelabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

def file2matrix(filename):
    file = open(filename) 
    numberOfLines = len(file.readlines()) 
    data = zeros((numberOfLines,3)) 
    labels = [] 
    file = open(filename)
    index = 0
    for line in file.readlines(): 
        line = line.strip()
        listFromLine = line.split('t')  
        data[index,:] = listFromLine[0:3]   
        label = 1
        if listFromLine[-1] == "didntLike":
            label = 1
        elif listFromLine[-1] == "smallDoses":
            label = 2
        elif listFromLine[-1] == "largeDoses":
            label = 3
        labels.append(label)
        index += 1
    return data,labels

def plot(data, labels):
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(data[:,1], data[:,2], 15.0 * array(labels), 15.0 * array(labels))
    plt.show()

# Отрисовка графика
# data,labels = file2matrix('dataset.txt')
# norm, range, min = normal(data)
# plot(norm, labels)

def normal(data):
    min = data.min(0) 
    max = data.max(0)  
    range = max - min
    norm = zeros(shape(data))
    m = data.shape[0]
    norm = (data - tile(min, (m,1)))/tile(range,(m,1))
    return norm, range, min

def test():
    ratio = 0.1
    data, labels = file2matrix('dataset.txt')
    norm, range, min = normal(data)
    m = norm.shape[0]
    testCount = int(m*ratio)
    errors = 0.0
    for i in arange(testCount):
        result = kNN(norm[i,:],norm[testCount:m,:], labels[testCount:m],3)
        print "Алгоритм решил, что элемент принадлежит классу: %d, на самом деле класс: %d" % (result, labels[i])
        if (result != labels[i]):
            errors += 1.0
    print "Общая частота ошибок: %f" % (errors/float(testCount))

def classifyPerson():
    results = ['не нравится','немного нравится', 'сильно нравится']
    games = float(raw_input("сколько времени человек проводит за видеоиграми?"))
    miles = float(raw_input("сколько миль он летает в год?"))
    iceCream = float(raw_input("сколько литров мороженого в неделю он съедает?"))
    data,labels = file2matrix('dataset.txt')
    norm, range, min = normal(data)
    arr = array([miles, games, iceCream])
    classResult = kNN((arr - min)/range,norm,labels,3)
    print "Человек ", results[classResult - 1]

classifyPerson()

Пример из жизни. Система распознавания рукописных цифр.

Мы собираемся распознавать рукописные символы при помощи нашего kNN классификатора. Мы будем работать только с цифрами от 0 до 9, чтобы упростить задачу. Все цифры были обработаны и преобразованы в текстовый формат размером 32x32 символа.

Скачать набор рукописных символов можно по ссылке ^[5]. Цифры представляют собой немного модифицированную версию рукописных цифр, взятых в UC Irvine Machine Learning Repository ^[6].

Алгоритм использования kNN для распознавания цифр:
Сбор данных: Текстовые файлы с преобразованными символами предоставлены
Подготовка данных: Необходимо написать функцию преобразующую данные из файла в Python вектор
Анализ данных: Мы посмотрим на преобразованные данные в оболочке Python, чтобы убедиться в корректности результата 2 шага
Обучение: Не требуется для kNN
Тестирование: Проверим работу алгоритма на известном наборе данных
Использование: Не будем рассматривать в данном примере, ввиду сложности.

Этап 1. Подготовка данных

Для того, чтобы мы могли работать с данными не изменяя наш классификатор, нам необходимо преобразовать 32x32 матрицу в файлах в 1x1024 вектор. Для этого напишем следующую функцию:

def img2vector(filename):
    result = zeros((1,1024))
    file = open(filename)
    for i in range(32):
        line = file.readline()
        for j in range(32):
            result[0,32*i+j] = int(line[j])
    return result

Этап 2. Тестирование kNN для распознавания цифр

Теперь, когда у нас есть данные в пригодном для использования виде, мы можем написать функцию, которая будет тестировать работу kNN на тестовых данных:

from numpy import *
import operator
from os import listdir

def test():
    labels = []
    trainingList = listdir('digits/trainingDigits')
    m = len(trainingList)
    training = zeros((m,1024))
    for i in arange(1,m,1):
        fileName = trainingList[i]    # Берем название файла
        string =  fileName.split('.')[0]   # Оставляем только часть до .txt
        number = int(string.split('_')[0])    # Определяем какое в файле число
        labels.append(number)    # Получаем список из классов для каждого файла
        training[i,:] = img2vector('digits/trainingDigits/%s' % fileName)    # Получаем список всех цифр
    testList = listdir('digits/testDigits')
    errors = 0.0
    m = len(testList)
    for i in range(1,m,1):
        fileName = testList[i]
        string = fileName.split('.')[0]
        number = int(string.split('_')[0])
        tests = img2vector('digits/testDigits/%s' % fileName)
        result = kNN(tests, training, labels, 3)
        print "Классификатор распознал цифру: %d, на самом деле это цифра: %d" % (result, number)
        if (result != number):
            errors += 1.0
    print "nОбщее число ошибок: %d" % errors
    print "nЧастота ошибок: %f" % (errors/float(m))

test()

Заключение

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

Заинтересовавшимся темой читателям рекомендую статью на machinelearning.ru ^[7]

Автор: Mllnr

Источник ^[8]