Классификация алгоритмов: Классификация алгоритмов — Студопедия

Классификация алгоритмов — Студопедия

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

Линейный алгоритм – это алгоритм, в котором последовательность операций при исполнении совпадает с порядком их следования в записи алгоритма и не зависит от конкретных значений входных данных (выполняются сверху вниз).

Разветвляющийся алгоритм – это алгоритм, в котором последовательность операций определяется проверкой условия.

Циклический алгоритм – это алгоритм, в котором неоднократно повторяются одни и те же предписания.

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

Примеры:

Линейный алгоритм

Вычислить функциюzпо формуле z=ax²+b+cos(ax²+b)-tg(ax²+b)

1) Cоставить математическое уравнение данной задачи:

z=t+cos-tgt, где t=ax²+b

2) Составление алгоритма:

Типы алгоритмов

Что такое алгоритм?

Определение 1

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

Понятие алгоритма появилось еще в IX веке нашей эры и произошло от имени его создателя, известного математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi). Наука, занимающаяся формированием и созданием алгоритмов, называется алгоритмикой.

Классификация алгоритмов

Как правило, основой для классификации алгоритмов является порядок выполнения команд (шагов). На основании данного признака специалисты в данной области выделяют три основных типа алгоритмов:

• Линейные алгоритмы;
• Алгоритмы с разветвлением;
• Циклические алгоритмы.

Каждый из типов алгоритмов имеет свои особенности, которые будут рассмотрены далее.

Линейные алгоритмы

Линейным алгоритмом называется алгоритм, в котором последовательность записанных команд (действий) осуществляется строго согласно порядка их записи без каких-либо изменений. Как правило, такой алгоритм составляется из нескольких базовых структур следования.

Готовые работы на аналогичную тему

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

1. Проснуться;
2. Встать с постели;
3. Обуть тапочки;
4. Зайти в ванную;
5. Почистить зубы;
6. Вернуться в комнату;
7. Застелить постель;
8. Одеться;
9. Приготовить завтрак;
10. Позавтракать.

Т. е. действия выполнятся последовательно, одно за другим. Пример записи линейного алгоритма представлен на рисунке 1.

Рисунок 1. Линейный алгоритм. Автор24 — интернет-биржа студенческих работ

Для составления линейного алгоритма необходимо:

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

Замечание 1

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

Алгоритмы с разветвлением

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

Разветвляющиеся алгоритмы представляют собой алгоритм, последовательность выполнения команд которого находится в зависимости от соответствия заявленному условию. Команда «ветвления» относится к структурным командам. Выполнение такой команды всегда происходит в несколько шагов: проверка заданного условия и дальнейшее исполнение команд по одной из ветвей: «да» или «нет».

Простым примером разветвляющегося алгоритма может выступить алгоритм выбора одежды перед выходом на улицу:

1. Есть ли на улице дождь?
2. Если дождь идет, то необходимо надеть плащ.
3. Если дождя нет, холодно на улице?
4. Если холодно, надеть джемпер;
5. Если не холодно, надеть футболку.

Замечание 2

В структуре такого алгоритма может быть любое количество условий. Таким образом, сначала проверяется выполнение логического выражения (Есть ли на улице дождь?), затем выполняется одно из условий в соответствии с выбором ответа.

Пример записи разветвляющегося алгоритма представлен на рисунке 2.

Рисунок 2. Автор24 — интернет-биржа студенческих работ

Алгоритм с разветвлением

Для составления разветвляющегося алгоритма необходимо:

• Установить какие могут быть варианты операций и их количество;
• Количество условных операторов (которые и отражают заданное условие) должно быть на одну единицу меньше, чем количество существующих вариантов;
• Понять, при соответствии каким из условий будет реализован каждый их установленных вариантов;
• Если в алгоритме существует больше двух условий, то необходимо задать и последовательность проверки данных условий;
• Записать алгоритм, который отражает ввод данных, вычисление, вывод окончательного результата;
• Протестировать полученный алгоритм на предмет его корректного функционирования.

Стоит отметить, разветвляющиеся алгоритмы могут быть как полными, так и неполными. Пример таких алгоритмов представлен на рисунках 3-4.

Рисунок 3. Алгоритм с полным разветвлением. Автор24 — интернет-биржа студенческих работ

Рисунок 4. Алгоритм с неполным разветвлением. Автор24 — интернет-биржа студенческих работ

Разветвляющие алгоритмы встречаются чаще линейных, но не являются самыми популярными и используемыми в сфере программирования.

Циклические алгоритмы

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

Циклические алгоритмы представляют собой алгоритмы, которые обеспечивают выполнение заранее заданного цикла.

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

Пример записи циклического алгоритма представлен на рисунке 5.

Рисунок 5. Циклический алгоритм. Автор24 — интернет-биржа студенческих работ

Для составления циклического алгоритма необходимо:

• Установить, какая из последовательностей операций должна быть в основе цикла;
• Определить вводные данные о количестве повторений тела цикла до начала цикла. Исходя из этих данных, определить какой из видов циклического цикла наиболее целесообразно использовать: цикл с параметром, постусловием или предусловием;
• Установить условие окончания выполнения заданного цикла;
• Установить вводные переменные;
• Записать алгоритм, который отражает ввод данных, вычисление, вывод окончательного результата;
• Протестировать полученный алгоритм на предмет его корректного функционирования.

Волшебное введение в алгоритмы классификации / Блог компании NIX / Хабр

Перевод статьи Брайна Беренда.

Когда вы впервые приступаете к изучению теории анализа и обработки данных, то одними из первых вы изучаете алгоритмы классификации. Их суть проста: берётся информация о конкретном результате наблюдений (data point), на основании которой этот результат относится к определённой группе или классу.

Хороший пример — спам-фильтр электронной почты. Он должен помечать входящие письма (то есть результаты наблюдений) как «спам» или «не спам», ориентируясь на информацию о письмах (отправитель, количество слов, начинающихся с прописных букв, и так далее).

Это пример хороший, но скучный. Спам-классификацию приводят в качестве примера на лекциях, презентациях и конференциях, так что вы наверняка уже не раз слышали о нём. Но что если поговорить о другом, более интересном алгоритме классификации? Каком-то более странном? Более… волшебном?

Всё верно! Сегодня мы поговорим о Распределяющей шляпе (Sorting Hat) из мира Гарри Поттера. Возьмём какие-то данные из сети, проанализируем и создадим классификатор, который будет сортировать персонажей по разным факультетам. Должно получиться забавно!

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

Второе примечание:

Идея этого поста навеяна прекрасной презентацией Брайана Ланга на конференции PyData Chicago 2016. Видеозапись здесь, слайды здесь.

Шаг первый: извлекаем данные из сети

На случай, если последние 20 лет вы провели в пещере: Распределяющая шляпа — это волшебная шляпа, которая помещает поступающих студентов по четырём факультетам Хогвартса: Гриффиндор, Слизерин, Хаффлпафф и Рэйвенклоу. У каждого факультета свои характеристики. Когда шляпу надевают на голову студента, она считывает его разум и определяет, какой факультет подходит ему лучше всего. Согласно этому определению, Распределяющая шляпа — это многоклассовый классификатор (multiclass classifier) (сортирует более чем по двум группам), в отличие от бинарного классификатора (сортирует строго по двум группам), которым является спам-фильтр.

Чтобы распределить студентов по факультетам, нам нужно знать о них определенную информацию. К счастью, достаточно данных есть на harrypotter.wikia.com. На этом сайте лежат статьи почти по всем аспектам вселенной Гарри Поттера, включая описания студентов и факультетов. Приятный бонус: компания Fandom, заведующая сайтом, предоставляет простой в использовании API и массу прекрасной документации. Ура!

Начнём с импортирования pandas и requests. Первые будут использоваться для упорядочивания данных, а последние — для запросов к API на получение данных.

Также нам нужно грамотно пройтись по всем студентам Хогвартса и записать факультеты, по которым они раскиданы Распределяющей шляпой (это будут «реальные данные», с которыми мы будем сравнивать результаты нашей сортировки). На сайте статьи разбиты по категориям, вроде «Студенты Хогвартса» и «Фильмы». API позволяет создавать списки статей в рамках конкретной категории.

Возьмём для примера Рэйвенклоу. Закинем все данные в переменную info и затем положим их во фрейм данных (Data Frame) Pandas.

# Импортирует модули
import pandas as pd
import requests

# Получает статьи из категории Рэйвенклоу
category = 'Ravenclaws'
url = 'http://harrypotter.wikia.com/api/v1/Articles/List?expand=1&limit=1000&category=' + category
requested_url = requests.get(url)
json_results = requested_url.json()
info = json_results['items']
ravenclaw_df = pd.DataFrame(info)

print('Number of articles: {}'.format(len(info)))
print('')
ravenclaw_df.head()

Количество статей: 158

Вы можете проследить полное выполнение анализа с помощью Rodeo!

Примечание:

Если воспользуетесь нашим Python IDE, Rodeo, то просто скопируйте и вставьте вышеприведённый код в Editor или Terminal. Результат вы увидите в окне History или Terminal. Бонус: можно просто перетаскивать окна мышью, меняя их расположение и размер.

На основе этих данных мы узнаем:

• Первым пунктом в списке идёт «Ravenclaw individual infobox». Поскольку это не студент, нам нужно отфильтровать результаты по колонке «Тип».
• К сожалению, в ravenclaw_df не указаны содержания статей… только описания. Чтобы получить содержания, придётся воспользоваться другим видом запроса к API и запрашивать данные на основе ID статей.
• Также мы можем написать цикл, пройтись по всем факультетам и получить один фрейм со всеми необходимыми данными.

# Задаём переменные
houses = ['Gryffindor', 'Hufflepuff', 'Ravenclaw', 'Slytherin']
mydf = pd.DataFrame()

# Получаем ID статей, URL статей и факультеты
for house in houses:
    url = "http://harrypotter.wikia.com/api/v1/Articles/List?expand=1&limit=1000&category=" + house + 's'
    requested_url = requests.get(url)
    json_results = requested_url.json()
    info = json_results['items']

    house_df = pd.DataFrame(info)
    house_df = house_df[house_df['type'] == 'article']
    house_df.reset_index(drop=True, inplace=True)
    house_df.drop(['abstract', 'comments', 'ns', 'original_dimensions', 'revision', 'thumbnail', 'type'], axis=1, inplace=True)
    house_df['house'] = pd.Series([house]*len(house_df))
    mydf = pd.concat([mydf, house_df])

mydf.reset_index(drop=True, inplace=True)

# Выводим результаты
print('Number of student articles: {}'.format(len(mydf)))
print('')
print(mydf.head())
print('')
print(mydf.tail())

Количество статей о студентах: 748

Получение содержаний статей

Имея ID статей, мы можем начать запрашивать содержания. Но некоторые из статей просто ОГРОМНЫ, они содержат невероятное количество подробностей. Вы только взгляните на статьи про Гарри Поттера и Волан-де-Морта!

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

Нижеприведённый код извлекает из каждой статьи раздел «Личность и черты характера» и вычисляет его длину (количество знаков). Затем на основе ID объединяет эти данные с нашим начальным фреймом данных mydf (на это уходит немного времени).

# Циклически проходим по статьям и извлекаем разделы " Личность и черты характера " по каждому студенту
# Если в статье про какого-то студента такого раздела нет, то оставляем пустую строку
# Это займёт несколько минут
text_dict = {}
for iden in mydf['id']:
    url = 'http://harrypotter.wikia.com/api/v1/Articles/AsSimpleJson?id=' + str(iden)
    requested_url = requests.get(url)
    json_results = requested_url.json()
    sections = json_results['sections']
    contents = [sections[i]['content'] for i, x in enumerate(sections) if sections[i]['title'] == 'Personality and traits']

    if contents:
        paragraphs = contents[0]
        texts = [paragraphs[i]['text'] for i, x in enumerate(paragraphs)]
        all_text = ' '.join(texts)
    else:
        all_text = ''
    text_dict[iden] = all_text

# Помещаем данные в DataFrame и вычисляем длину раздела "Личность и черты характера" 
text_df = pd.DataFrame.from_dict(text_dict, orient='index')
text_df.reset_index(inplace=True)
text_df.columns = ['id', 'text']
text_df['text_len'] = text_df['text'].map(lambda x: len(x))

# Снова объединяем текст с информацией о студентах
mydf_all = pd.merge(mydf, text_df, on='id')
mydf_all.sort_values('text_len', ascending=False, inplace=True)

# Создаём новый DataFrame только с теми студентами, про которых есть разделы "Личность и черты характера" 
mydf_relevant = mydf_all[mydf_all['text_len'] > 0]

print('Number of useable articles: {}'.format(len(mydf_relevant)))
print('')
mydf_relevant.head()

Количество подходящих статей: 94

Шаг второй: Получение характеристик факультетов с помощью NLTK

Теперь мы знаем количество студентов, надо распределить их по факультетам. Для этого составим список характеристик каждого факультета. Начнём собирать из с harrypotter.wikia.com.

trait_dict = {}
trait_dict['Gryffindor'] = ['bravery', 'nerve', 'chivalry', 'daring', 'courage']
trait_dict['Slytherin'] = ['resourcefulness', 'cunning', 'ambition', 'determination', 'self-preservation', 'fraternity',
                           'cleverness']
trait_dict['Ravenclaw'] = ['intelligence', 'wit', 'wisdom', 'creativity', 'originality', 'individuality', 'acceptance']
trait_dict['Hufflepuff'] = ['dedication', 'diligence', 'fairness', 'patience', 'kindness', 'tolerance', 'persistence',
                            'loyalty']

Обратите внимание, что все слова — существительные. Это хорошо. Нам нужна консистентность при описании черт характера. Некоторые из них были представлены не в виде существительных, так что приведём их к общему порядку:

• «ambitious» (прилагательное) — можно легко заменить на ‘ambition’
• «hard work», «fair play» и «unafraid of toil» — эти фразы тоже можно легко заменить на однословные существительные:
• «hard work» —> ‘diligence’
• «fair play» —> ‘fairness’
• «unafraid of toil» —> ‘persistence’

Получив список характеристик для каждого факультета, можем просто сканировать колонку «Текст» и подсчитать, сколько раз использовались соответствующие слова в описаниях персонажей. Звучит несложно, верно?

К сожалению, это ещё не всё. Вот фраза из раздела «Личность и черты характера» про Невила Лонгботтома:

Когда он был моложе, Невил был неуклюж, забывчив, застенчив, и многие считали, что он плохо подходит для факультета Гриффиндор, потому что он казался робким.

Благодаря поддержке друзей, которым он был очень предан; вдохновению профессора Римуса Люпина предстать перед лицом своих страхов на третьем году обучения; и тому, что мучители его родителей разгуливают на свободе, Невил стал храбрее, увереннее в себе, и самоотверженным в борьбе против Волан-де-Морта и его Пожирателей Смерти.

(When he was younger, Neville was clumsy, forgetful, shy, and many considered him ill-suited for Gryffindor house because he seemed timid.

With the support of his friends, to whom he was very loyal, the encouragement of Professor Remus Lupin to face his fears in his third year, and the motivation of knowing his parents’ torturers were on the loose, Neville became braver, more self-assured, and dedicated to the fight against Lord Voldemort and his Death Eaters.)

Выделенные слова должны засчитываться в пользу каких-то факультетов, но они не будут засчитаны, потому что являются прилагательными. Также не будут учтены слова вроде «bravely» и «braveness». Чтобы наш алгоритм классификации работал правильно, нужно идентифицировать синонимы, антонимы и другие словоформы.

Синонимы

Исследовать синонимы можно с помощью функции synsets из WordNet, лексической базы данных английского языка, включённой в модуль nltk (NLTK — Natural Language Toolkit). “Synset” — это «synonym set», коллекция синонимов, или «лемм». Функция synsets возвращает наборы синонимов, которые ассоциированы с конкретными словами.

Озадачены? Давайте запустим код, а затем разберём его:

from nltk.corpus import wordnet as wn

# Наборы синонимов из разных слов
foo1 = wn.synsets('bravery')
print("Synonym sets associated with the word 'bravery': {}".format(foo1))

foo2 = wn.synsets('fairness')
print('')
print("Synonym sets associated with the word 'fairness': {}".format(foo2))

foo3 = wn.synsets('wit')
print('')
print("Synonym sets associated with the word 'wit': {}".format(foo3))

foo4 = wn.synsets('cunning')
print('')
print("Synonym sets associated with the word 'cunning': {}".format(foo4))

foo4 = wn.synsets('cunning', pos=wn.NOUN)
print('')
print("Synonym sets associated with the *noun* 'cunning': {}".format(foo4))
print('')

# Выводим синонимы ("леммы"), ассоциированные с каждым synset
foo_list = [foo1, foo2, foo3, foo4]
for foo in foo_list:
    for synset in foo:
        print((synset.name(), synset.lemma_names()))

Synonym sets associated with the word ‘bravery’: [Synset(‘courage.n.01’), Synset(‘fearlessness.n.01’)]
Synonym sets associated with the word ‘fairness’: [Synset(‘fairness.n.01’), Synset(‘fairness.n.02’), Synset(‘paleness.n.02’), Synset(‘comeliness.n.01’)]
Synonym sets associated with the word ‘wit’: [Synset(‘wit.n.01’), Synset(‘brain.n.02’), Synset(‘wag.n.01’)]
Synonym sets associated with the word ‘cunning’: [Synset(‘craft.n.05’), Synset(‘cunning.n.02’), Synset(‘cunning.s.01’), Synset(‘crafty.s.01’), Synset(‘clever.s.03’)]
Synonym sets associated with the noun ‘cunning’: [Synset(‘craft.n.05’), Synset(‘cunning.n.02’)]
(‘courage.n.01’, [‘courage’, ‘courageousness’, ‘bravery’, ‘braveness’]) (‘fearlessness.n.01’, [‘fearlessness’, ‘bravery’]) (‘fairness.n.01’, [‘fairness’, ‘equity’]) (‘fairness.n.02’, [‘fairness’, ‘fair-mindedness’, ‘candor’, ‘candour’]) (‘paleness.n.02’, [‘paleness’, ‘blondness’, ‘fairness’]) (‘comeliness.n.01’, [‘comeliness’, ‘fairness’, ‘loveliness’, ‘beauteousness’]) (‘wit.n.01’, [‘wit’, ‘humor’, ‘humour’, ‘witticism’, ‘wittiness’]) (‘brain.n.02’, [‘brain’, ‘brainpower’, ‘learning_ability’, ‘mental_capacity’, ‘mentality’, ‘wit’]) (‘wag.n.01’, [‘wag’, ‘wit’, ‘card’]) (‘craft.n.05’, [‘craft’, ‘craftiness’, ‘cunning’, ‘foxiness’, ‘guile’, ‘slyness’, ‘wiliness’]) (‘cunning.n.02’, [‘cunning’])

Так, мы получили много выходных данных. Рассмотрим некоторые моменты и потенциальные проблемы:

• wn.synsets('bravery') связано с двумя наборами синонимов: один для courage.n.01 и один для fearlessness.n.01. Давайте посмотрим, что это означает:
• Первая часть (‘courage’ и ‘fearlessness’) это слово, вокруг которого выстроен весь конкретный набор синонимов. Назовём его «центральным» словом. То есть все синонимы в данном наборе («леммы») аналогичны по смыслу центральному слову.
• Вторая часть (‘n’) означает «существительное» («noun»). К примеру, набор, ассоциированный со словом «cunning», включает в себя crafty.s.01 и clever.s.03 (прилагательные). Они появились тут потому, что слово «cunning» может быть и существительным, и прилагательным. Чтобы оставить только существительные, можно задать wn.synsets('cunning', pos=wn.NOUN).
• Третья часть (’01’) ссылается на конкретный смысл центрального слова. Например, ‘fairness’ может означать как «соответствие правилам и стандартам», так и «вынесение суждений без дискриминации или нечестности».

Как вы могли заметить, функция synset может предоставлять нежелательные наборы синонимов. Например, со словом ‘fairness’ также ассоциированы наборы paleness.n.02 («иметь от природы светлую кожу») и comeliness.n.01 («хорошо выглядеть и быть привлекательным»). Эти черты явно не ассоциируются с Хаффлпаффом (хотя Невил Лонгботтом и вырос красавчиком), так что придётся вручную исключать такие наборы из нашего анализа.

Перевод: получить синонимы труднее, чем кажется

Антонимы и словоформы

После того, как мы собрали все синонимы, нужно позаботиться об антонимах и разных словоформах (например, применительно к «bravery» — «brave», «bravely» и «braver»). Немало тяжёлой работы можно выполнить в nltk, но всё же придётся вручную набивать деепричастия и прилагательные в сравнительной / превосходной степени.

# Выводим разные леммы (синонимы), антонимы и производные словоформы для наборов синонимов к "bravery"
foo1 = wn.synsets('bravery')
for synset in foo1:
    for lemma in synset.lemmas():
        print("Synset: {}; Lemma: {}; Antonyms: {}; Word Forms: {}".format(synset.name(), lemma.name(), lemma.antonyms(),
                                                                           lemma.derivationally_related_forms()))
        print("")

Synset: courage.n.01; Lemma: courage; Antonyms: [Lemma(‘cowardice.n.01.cowardice’)]; Word Forms: [Lemma(‘brave.a.01.courageous’)]
Synset: courage.n.01; Lemma: courageousness; Antonyms: []; Word Forms: [Lemma(‘brave.a.01.courageous’)]
Synset: courage.n.01; Lemma: bravery; Antonyms: []; Word Forms: []
Synset: courage.n.01; Lemma: braveness; Antonyms: []; Word Forms: [Lemma(‘brave.a.01.brave’), Lemma(‘audacious.s.01.brave’)]
Synset: fearlessness.n.01; Lemma: fearlessness; Antonyms: [Lemma(‘fear.n.01.fear’)]; Word Forms: [Lemma(‘audacious.s.01.fearless’), Lemma(‘unafraid.a.01.fearless’)]
Synset: fearlessness.n.01; Lemma: bravery; Antonyms: []; Word Forms: []

Собираем всё вместе

Следующий код создаёт список синонимов, антонимов и словоформ для каждой характеристики факультетов. Для полноты анализа некоторые из слов могут быть записаны неправильно.

# Вручную выбираем наборы, которые нам подходят
relevant_synsets = {}
relevant_synsets['Ravenclaw'] = [wn.synset('intelligence.n.01'), wn.synset('wit.n.01'), wn.synset('brain.n.02'),
                                 wn.synset('wisdom.n.01'), wn.synset('wisdom.n.02'), wn.synset('wisdom.n.03'),
                                 wn.synset('wisdom.n.04'), wn.synset('creativity.n.01'), wn.synset('originality.n.01'),
                                 wn.synset('originality.n.02'), wn.synset('individuality.n.01'), wn.synset('credence.n.01'),
                                 wn.synset('acceptance.n.03')]
relevant_synsets['Hufflepuff'] = [wn.synset('dedication.n.01'), wn.synset('commitment.n.04'), wn.synset('commitment.n.02'),
                                  wn.synset('diligence.n.01'), wn.synset('diligence.n.02'), wn.synset('application.n.06'),
                                  wn.synset('fairness.n.01'), wn.synset('fairness.n.01'), wn.synset('patience.n.01'),
                                  wn.synset('kindness.n.01'), wn.synset('forgivingness.n.01'), wn.synset('kindness.n.03'),
                                  wn.synset('tolerance.n.03'), wn.synset('tolerance.n.04'), wn.synset('doggedness.n.01'),
                                  wn.synset('loyalty.n.01'), wn.synset('loyalty.n.02')]
relevant_synsets['Gryffindor'] = [wn.synset('courage.n.01'), wn.synset('fearlessness.n.01'), wn.synset('heart.n.03'),
                                  wn.synset('boldness.n.02'), wn.synset('chivalry.n.01'), wn.synset('boldness.n.01')]
relevant_synsets['Slytherin'] = [wn.synset('resourcefulness.n.01'), wn.synset('resource.n.03'), wn.synset('craft.n.05'),
                                 wn.synset('cunning.n.02'), wn.synset('ambition.n.01'), wn.synset('ambition.n.02'),
                                 wn.synset('determination.n.02'), wn.synset('determination.n.04'),
                                 wn.synset('self-preservation.n.01'), wn.synset('brotherhood.n.02'),
                                 wn.synset('inventiveness.n.01'), wn.synset('brightness.n.02'), wn.synset('ingenuity.n.02')]

# Функция, получающая разные словоформы из леммы
def get_forms(lemma):
    drfs = lemma.derivationally_related_forms()
    output_list = []
    if drfs:
        for drf in drfs:
            drf_pos = str(drf).split(".")[1]
            if drf_pos in ['n', 's', 'a']:
                output_list.append(drf.name().lower())
                if drf_pos in ['s', 'a']:
                    # Наречия + "-ness" существительные + сравнительные & превосходные прилагательные
                    if len(drf.name()) == 3:
                        last_letter = drf.name()[-1:]
                        output_list.append(drf.name().lower() + last_letter + 'er')
                        output_list.append(drf.name().lower() + last_letter + 'est')
                        output_list.append(drf.name().lower()+'ness')
                        output_list.append(drf.name().lower()+'ly')
                    elif drf.name()[-4:] in ['able', 'ible']:
                        output_list.append(drf.name().lower()+'r')
                        output_list.append(drf.name().lower()+'st')
                        output_list.append(drf.name().lower()+'ness')
                        output_list.append(drf.name()[:-1].lower()+'y')
                    elif drf.name()[-1:] == 'e':
                        output_list.append(drf.name().lower()+'r')
                        output_list.append(drf.name().lower()+'st')
                        output_list.append(drf.name().lower()+'ness')
                        output_list.append(drf.name().lower()+'ly')
                    elif drf.name()[-2:] == 'ic':
                        output_list.append(drf.name().lower()+'er')
                        output_list.append(drf.name().lower()+'est')
                        output_list.append(drf.name().lower()+'ness')
                        output_list.append(drf.name().lower()+'ally')
                    elif drf.name()[-1:] == 'y':
                        output_list.append(drf.name()[:-1].lower()+'ier')
                        output_list.append(drf.name()[:-1].lower()+'iest')
                        output_list.append(drf.name()[:-1].lower()+'iness')
                        output_list.append(drf.name()[:-1].lower()+'ily')
                    else:
                        output_list.append(drf.name().lower()+'er')
                        output_list.append(drf.name().lower()+'est')
                        output_list.append(drf.name().lower()+'ness')
                        output_list.append(drf.name().lower()+'ly')
        return output_list
    else:
        return output_list

# Создаём копию словаря черт характера
# Если этого не сделать, то мы сразу же обновим словарь, по которому проходим циклически, что приведёт к бесконечному циклу
import copy
new_trait_dict = copy.deepcopy(trait_dict)
antonym_dict = {}

# Добавляем синонимы и словоформы в (новый) словарь черт характера; также добавляем антонимы (и их словоформы) в словарь антонимов
for house, traits in trait_dict.items():
    antonym_dict[house] = []
    for trait in traits:
        synsets = wn.synsets(trait, pos=wn.NOUN)
        for synset in synsets:
            if synset in relevant_synsets[house]:
                for lemma in synset.lemmas():
                    new_trait_dict[house].append(lemma.name().lower())
                    if get_forms(lemma):
                        new_trait_dict[house].extend(get_forms(lemma))
                    if lemma.antonyms():
                        for ant in lemma.antonyms():
                            antonym_dict[house].append(ant.name().lower())
                            if get_forms(ant):
                                antonym_dict[house].extend(get_forms(ant))
    new_trait_dict[house] = sorted(list(set(new_trait_dict[house])))
    antonym_dict[house] = sorted(list(set(antonym_dict[house])))

# Выводим некоторые результаты
print("Gryffindor traits: {}".format(new_trait_dict['Gryffindor']))
print("")
print("Gryffindor anti-traits: {}".format(antonym_dict['Gryffindor']))
print("")

Характеристики Гриффиндора: [‘bold’, ‘bolder’, ‘boldest’, ‘boldly’, ‘boldness’, ‘brass’, ‘brassier’, ‘brassiest’, ‘brassily’, ‘brassiness’, ‘brassy’, ‘brave’, ‘bravely’, ‘braveness’, ‘braver’, ‘bravery’, ‘bravest’, ‘cheek’, ‘cheekier’, ‘cheekiest’, ‘cheekily’, ‘cheekiness’, ‘cheeky’, ‘chivalry’, ‘courage’, ‘courageous’, ‘courageouser’, ‘courageousest’, ‘courageously’, ‘courageousness’, ‘daring’, ‘face’, ‘fearless’, ‘fearlesser’, ‘fearlessest’, ‘fearlessly’, ‘fearlessness’, ‘gallantry’, ‘hardihood’, ‘hardiness’, ‘heart’, ‘mettle’, ‘nerve’, ‘nervier’, ‘nerviest’, ‘nervily’, ‘nerviness’, ‘nervy’, ‘politesse’, ‘spunk’, ‘spunkier’, ‘spunkiest’, ‘spunkily’, ‘spunkiness’, ‘spunky’]

Антихарактеристики Гриффиндора: [‘cowardice’, ‘fear’, ‘timid’, ‘timider’, ‘timidest’, ‘timidity’, ‘timidly’, ‘timidness’]

# Проверяем, что словарь черт характера и словарь антонимов не содержат повторов внутри факультетов
from itertools import combinations
def test_overlap(dict):
    results = []
    house_combos = combinations(list(dict.keys()), 2)
    for combo in house_combos:
        results.append(set(dict[combo[0]]).isdisjoint(dict[combo[1]]))
    return results

# Выводим результаты теста; должно получиться "False"
print("Any words overlap in trait dictionary? {}".format(sum(test_overlap(new_trait_dict)) != 6))
print("Any words overlap in antonym dictionary? {}".format(sum(test_overlap(antonym_dict)) != 6))

Есть какие-то повторы в словаре черт характера? False

Повторы в словаре антонимов? False

Шаг третий: Распределяем студентов по факультетам

Пришло время распределить студентов по факультетам! Наш алгоритм классификации будет работать следующим образом:

• Проходит по каждому слову раздела «Личность и черты характера» по каждому студенту.
• Если какое-то слово есть в списке черт, характерных для конкретного факультета, то к баллам этого факультета добавляется 1.
• Если какое-то слово есть в списке античерт, характерных для конкретного факультета, то из баллов этого факультета вычитается 1.
• Студент приписывается к факультету, который наберёт больше всего баллов.
• Если будет ничья, то просто напишет “Tie!”.

Допустим, в разделе «Личность и черты характера» есть лишь предложение «Алиса была храброй». Тогда Алиса получит 1 балл для Гриффиндора и 0 баллов для остальных факультетов. Соответственно, Алиса попадёт в Гриффиндор.

# Импортируем "word_tokenize", разбивающий предложение на слова и пунктуацию
from nltk import word_tokenize

# Функция, распределяющая студентов
def sort_student(text):
    text_list = word_tokenize(text)
    text_list = [word.lower() for word in text_list]
    score_dict = {}
    houses = ['Gryffindor', 'Hufflepuff', 'Ravenclaw', 'Slytherin']
    for house in houses:
        score_dict[house] = (sum([True for word in text_list if word in new_trait_dict[house]]) -
                                  sum([True for word in text_list if word in antonym_dict[house]]))

    sorted_house = max(score_dict, key=score_dict.get)
    sorted_house_score = score_dict[sorted_house]
    if sum([True for i in score_dict.values() if i==sorted_house_score]) == 1:
        return sorted_house
    else:
        return "Tie!"

# Тестируем функцию
print(sort_student('Alice was brave'))
print(sort_student('Alice was British'))

Gryffindor Tie!

Похоже, функция работает. Применим её к нашим данным и посмотрим, что получится!

# Отключаем предупреждение
pd.options.mode.chained_assignment = None

mydf_relevant['new_house'] = mydf_relevant['text'].map(lambda x: sort_student(x))
mydf_relevant.head(20)

print("Match rate: {}".format(sum(mydf_relevant['house'] == mydf_relevant['new_house']) / len(mydf_relevant)))
print("Percentage of ties: {}".format(sum(mydf_relevant['new_house'] == 'Tie!') / len(mydf_relevant)))

Совпадение: 0.2553191489361702
Доля ничьих: 0.32978723404255317

Хм. Мы ожидали других результатов. Давайте выясним, почему Волан-де-Морт попал в Хаффлпафф.

# Текст о Волан-де-Морте
tom_riddle = word_tokenize(mydf_relevant['text'].values[0])
tom_riddle = [word.lower() for word in tom_riddle]

# Вместо вычисления баллов выведем список слов в тексте, совпадающих со словами из словарей черт характера и антонимов
words_dict = {}
anti_dict = {}
houses = ['Gryffindor', 'Hufflepuff', 'Ravenclaw', 'Slytherin']
for house in houses:
    words_dict[house] = [word for word in tom_riddle if word in new_trait_dict[house]]
    anti_dict[house] = [word for word in tom_riddle if word in antonym_dict[house]]

print(words_dict)
print("")
print(anti_dict)

{‘Slytherin’: [‘ambition’], ‘Ravenclaw’: [‘intelligent’, ‘intelligent’, ‘mental’, ‘individual’, ‘mental’, ‘intelligent’], ‘Hufflepuff’: [‘kind’, ‘loyalty’, ‘true’, ‘true’, ‘true’, ‘loyalty’], ‘Gryffindor’: [‘brave’, ‘face’, ‘bold’, ‘face’, ‘bravery’, ‘brave’, ‘courageous’, ‘bravery’]}
{‘Slytherin’: [], ‘Ravenclaw’: [‘common’], ‘Hufflepuff’: [], ‘Gryffindor’: [‘fear’, ‘fear’, ‘fear’, ‘fear’, ‘fear’, ‘fear’, ‘cowardice’, ‘fear’, ‘fear’]}

Как видите, Слизерин набрал (1-0) = 1 баллов, Рэйвенклоу — (6-1) = 5, Хаффлпафф — (6-0) = 6, Гриффиндор — (8-9) = -1.

Интересно отметить, что в разделе «Личность и черты характера» Волан-де-Морта, самом длинном среди всех студентов, со словарями совпало лишь 31 слово. Это означает, что по другим студентам, вероятно, было гораздо больше совпадений. То есть мы принимаем решение о классификации на основании слишком небольшого количества данных, что и объясняет высокую долю ошибок и большое количество ничьих.

Выводы

Созданный нами классификатор работает не слишком хорошо (немногим точнее, чем простое угадывание), но не забывайте, что наш подход был упрощённым. Современные спам-фильтры очень сложны и не классифицируют лишь на основании наличия конкретных слово. Так что наш алгоритм можно улучшить так, чтобы он учитывал больше информации. Вот небольшой список идей:

• Сравнить с факультетами, в которые попадали другие члены семьи этого студента.
• Использовать другие разделы статей, например, «Ранние годы» или введение.
• Вместо маленького списка черт характера и их синонимов создать список наиболее частых слов в разделе «Личность и черты характера» применительно для каждого факультета, и классифицировать на основании этих данных.
• Использовать более сложные методики анализа текстов, вроде анализа тональности текста.

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

Классификация алгоритмов

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

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

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

По способу исполнения выделяют
также

Вспомогательные алгоритмы
— алгоритмы,
целиком используемые в составе других
алгоритмов.
Вспомогательный алгоритм представляет
алгоритм решения некоторой подзадачи
из исходной (основной) задачи.

Вспомогательный алгоритм, записанный
на языке программирования, называется
процедурой или подпрограммой.

Алгоритм
может содержать обращение к самому себе
как вспомогательному
и в этом случае он называется рекурсивным.

Рекурсивные алгоритмы – алгоритмы,
вызывающие сами себя до тех пор, пока
не будет достигнуто некоторое условие
возвращения.

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

Классификация алгоритмов — Студопедия

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

Линейный алгоритм – это алгоритм, в котором последовательность операций при исполнении совпадает с порядком их следования в записи алгоритма и не зависит от конкретных значений входных данных (выполняются сверху вниз).

Разветвляющийся алгоритм – это алгоритм, в котором последовательность операций определяется проверкой условия.

Циклический алгоритм – это алгоритм, в котором неоднократно повторяются одни и те же предписания.

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

Примеры:

Линейный алгоритм

Вычислить функциюzпо формуле z=ax²+b+cos(ax²+b)-tg(ax²+b)

1) Cоставить математическое уравнение данной задачи:

z=t+cos-tgt, где t=ax²+b

2) Составление алгоритма:

9 ключевых алгоритмов машинного обучения простым языком / Хабр

Привет, Хабр! Представляю вашему вниманию перевод статьи «9 Key Machine Learning Algorithms Explained in Plain English» автора Nick McCullum.

Машинное обучение (МО) уже меняет мир. Google использует МО предлагая и показывая ответы на поисковые запросы пользователей. Netflix использует его, чтобы рекомендовать вам фильмы на вечер. А Facebook использует его, чтобы предложить вам новых друзей, которых вы можете знать.

Машинное обучение никогда еще не было настолько важным и, в тоже время, настолько трудным для изучения. Эта область полна жаргонов, а количество разных алгоритмов МО растет с каждым годом.

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

Система рекомендаций(Recommendation system)

Для построения полноценной системы рекомендаций с 0, требуются глубокие знания в линейной алгебре. Из-за чего, если вы никогда не изучали эту дисциплину, вам может быть сложно понять некоторые концепции этого раздела.

Но не беспокойтесь — scikit-learn библиотека Python позволяет довольно просто построить СР. Так что вам не потребуется таких уж глубоких познаний в линейной алгебре, чтобы построить рабочую СР.

Как работает СР?

Существует 2 основных типа система рекомендаций:

• Основанная на контенте(Content-based)
• Коллаборативная фильтрация(Collaborative filtering)

Основанная на контенте система дает рекомендации, которые базируются на схожести элементов, уже использованных вами. Эти системы ведут себя абсолютно так, как вы ожидаете СР будет себя вести.

Коллаборативная фильтрация СР предоставляет рекоммендации, основанные на знаниях о том как пользователь взаимодействует с элементами(*примечание: за основу взяты взаимодействия с элементами других пользователей, схожих по поведению с данным пользователем). Другими словами, они используют «мудрость толпы»(отсюда и «коллаборативный» в названии метода).

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

Коллаборативная фильтрация СР также обладает уникальной особенностью, которой нет в основанной на контенте ситстеме. А именно, у них есть способность обучаться фичам самостоятельно.

Это значит, что они могут даже начать определять подобие в элементах, основываясь на свойствах или чертах, которые вы даже не предоставляли для работы этой системе.

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

• Основанная на модели
• Основанная на соседстве

Хорошая новость: вам не обязательно знать разницу в этих двух типах коллаборативной фильтрации СР, чтобы быть успешным в МО. Достаточно просто знать, что существует несколько типов.

Подведем итог

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

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

Линейная регрессия (Linear Regression)

Линейная регрессия используется для предсказаний некоторого значения y основываясь на некотором множестве значений x.

История линейной регрессии

Линейная регрессия(ЛР) была изобретена в 1800 году Френсисом Гальтоном. Гальтон был ученым, изучающим связь между родителями и детьми. А конкретнее, Гальтон исследовал связь между ростом отцов и ростом их сыновей. Первым открытием Гальтона стал тот факт, что рост сыновей, как правило, был приблизительно таким же как рост их отцов. Что не удивительно.

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

Гальтон даль этому феномену название — регрессия. В частности, он сказал: » Рост сына имеет тенденцию к регрессии(или к смещению в направлении) среднего роста».

Это привело к целой области в статистике и машинном обучении под названием регрессия.

Математика линейной регрессии

В процессе создания регрессионной модели, все что мы пытаемся сделать — это нарисовать линию настолько близко к каждой точке из набора данных, на сколько это возможно.

Типичный пример такого подхода — «метод наименьших квадратов» линейной регрессии, с помощью которого рассчитывают близость линии в направлении верх-низ.

Пример для иллюстрации:

Когда вы создаете регрессионную модель, ваш конечный продукт — это уравнение, с помощью которого вы можете предсказать значения y для значения x без того чтобы знать значение y наперед.

Логистическая регрессия (Logistic Regression)

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

Что такое логистическая регрессия?

Логистическая регрессия — это модель машинного обучения, использующаяся для решения задач классификации.

Ниже представлено несколько примеров классификационных задач МО:

• Спам электронной почты(спам или не спам?)
• Претензия по страховке автомобиля (выплата компенсации или починка?)
• Диагностика болезней

Каждая из этих задач имеет четко 2 категории, что делает их примерами задач двоичной классификации.

Логистическая регрессия хорошо подходит для решения задач двоичной классификации — мы просто назначаем разным категориям значения 0 и 1 соответственно.

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

Это изображение может помочь понять почему линейная регрессия плохо подходит для двоичной классификации:

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

Вот почему логистическая регрессионная модель полезна. У нее есть изгиб к линии лучшего соответсвия, что делает ее(модель) гораздо более подходящей для предсказаний качественных(категорийных) данных.

Вот пример, который иллюстрирует сравнение линейной и логистической регрессионых моделей на одних и техже данных:

Сигмоида (The Sigmoid Function)

Причина по которой логистическая регрессия имеет изгиб — это тот факт, что для её вычисления не используетя линейное уравнение. Вместо него логистическая регерссионная модель строится на использовании сигмоиды (также называемой логистической функцией, т.к. она используется в логистической регрессии).

Для вас не обязательно досконально запоминать сигмоиду, чтобы преуспеть в МО. Но все-таки иметь некоторое представление об этой функции будет полезно.

Формула сигмоиды:

Главная характеристика сигмоиды, которая стоит того, чтобы с ней разобраться — не важно какое значение вы передадите этой функции, она всегда вернет значение в промежутке 0-1.

Использование логистической регрессионной модели для предсказаний

Чтобы использовать логистическую регрессию для предсказаний, вам, как правило, нужно точно определить точку отсечения. Эта точка отсечения обычно 0.5.

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

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

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

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

В этой таблице TN означает «истинно отрицательно», FN — «ложно отрицательно», FP — «ложно положительно», TP — «истинно положительно».

Матрица ошибок полезна для оценки модели, есть ли в ней «слабые» квадранты в матрице ошибок. Как пример, она может иметь ненормально большое количество ложно положительных результатов.

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

В этом примере диагностики рака, например, вы бы хотели быть точно уверены, что у вашей модели не слишком большое количество ложно положительных результатов, т.к. это будет означать, что чью-то злокачественную опухоль вы диагностировали как доброкачественную.

Подведем итог

В этом разделе у вас было первое знакомство с моделью МО — логистической регрессией.
Вот краткое содержание того, что вы узнали о логистической регрессии:

• Типы задач классификации, которые подходят для решения с помощью логистической регрессии
• Логистическая функция (сигмоида) всегда дает значение от 0 до 1
• Как использовать точки отсечения для предсказания с помощью модели логистической регрессии
• Почему матрица ошибок полезна для измерения эффективности модели логистической регрессии

Алгоритм k-ближайших соседей (K-Nearest Neighbors)

Алгоритм k-ближайших соседей может помочь решить задачу классификации, в случае, когда категорий больше, чем 2.

Что из себя представляет алгоритм k-ближайших соседей?

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

Представьте, что у вас есть данные по высоте и весу футболистов и баскетболистов. Алгоритм k-ближайших соседей может быть использован для предсказания является ли новый игрок футболистом или баскетболистом. Чтобы это сделать, алгоритм определяет К точек данных, ближайших к объекту исследования.

Данное изображение демонстрирует этот принцип с параметром К = 3:

На этом изображении футболисты изображены голубыми отметками, а баскетболисты — оранжевыми. Точка, которую мы пытаемся классифицировать, покрашена в зеленый цвет. Так как большинство (2 из 3) ближайших к зеленой точке отметок окрашены в голубой (футбольные игроки), то значит алгоритм К-ближайших соседей предсказывает, что новый игрок тоже окажется футболистом.

Как построить алгоритм К-ближайших соседей

Основные шаги для построения данного алгоритма:

1. Соберите все данные
2. Вычислите Евклидово расстояние от новой точки данных х до всех остальных точек в множестве данных
3. Отсортируйте точки из множества данных в порядке возрастания расстояния до х
4. Спрогнозируйте ответ, используя ту же категорию, что и большинство К-ближайших к х данных

Важность переменной К в алгоритме К-ближайших соседей

Хотя это может быть не очевидно с самого начала, изменение значения К в данном алгоритме изменит категорию, в которую попадет новая точка данных.

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

Представленная ниже иллюстрация отлично показывает этот эффект:

Плюсы и минусы алгоритма К-ближайших соседей

Чтобы подвести итог знакомства с этим алгоритмом, давайте коротко обсудим достоинства и недостатки его использования.

Плюсы:

• Алгоритм прост и его легко понять
• Тривиальное обучение модели на новых тренировочных данных
• Работает с любым количеством категорий в задаче классификации
• Легко добавить больше данных в множество данных
• Модель принимает только 2 параметра: К и метрика расстояния, которой вы хотели бы воспользоваться (обычно это Евклидово расстояние)

Минусы:

• Высокая стоимость вычисления, т.к. вам требуется обработать весь объем данных
• Работает не так хорошо с категорическими параметрами

Подведем итог

Краткое содержание того, что вы только что узнали о алгоритме К-ближайших соседей:

• Пример задачи на классификацию(футболисты или баскетболисты), которую может решить алгоритм
• Как данный алгоритм использует Евклидово расстояние до соседних точек для прогнозирования к какой категории принадлежит новая точка данных
• Почему значения параметра К важно для прогнозирования
• Плюсы и минусы использования алгоритма К-ближайших соседей

Дерево решений и Случайный лес (Decision Trees and Random Forests)

Дерево решений и случайный лес — это 2 примера древовидного метода. Точнее, деревья решений — это модели МО, используемые для прогнозирования через циклический просмотр каждой функции в наборе данных один за одним. Случайный лес — это ансамбль (комитет) деревьев решения, которые используют случайные порядки объектов в наборе данных.

Что такое древовидный метод?

Перед тем, как мы нырнем в теоретические основы древовидного метода в МО, будет нелишним начать с примера.

Представьте, что вы играете в баскетбол каждый понедельник. Более того, вы всегда приглашаете одного и того же друга пойти поиграть с вами. Иногда друг действительно приходит, иногда нет. Решение приходить или нет зависит от множества факторов: какая погода, температура, ветер и усталость. Вы начинаете замечать эти особенности и отслеживать их вместе с решением вашего друга играть или нет.

Вы можете использовать эти данные для предсказания придет ли ваш друг сегодня или нет. Одна из техник, которой вы можете воспользоваться — это дерево решений. Вот как это выглядит:

У каждого дерева решений есть 2 типа элементов:

• Узлы (Nodes): места, где дерево разделяется в зависимости от значения определенного параметра
• Грани (Edges): результат разделения, ведущий к следующему узлу

Вы можете видеть, что на схеме есть узлы для прогноза (outlook), влажности (humidity) и ветра
(windy). И также грани для каждого потенциального значения каждого из этих параметров.

Вот еще парочка определений, которые вы должны понимать перед тем, как мы начнем:

• Корень (Root) — узел, с которого начинается разделение дерева
• Листья (Leaves) — заключительные узлы, которые предсказывают финальный результат

Теперь у вас есть базовое понимание что такое дерево решений. Мы рассмотрим как построить такое дерево с нуля в следующем разделе.

Как построить дерево решений с нуля

Построение дерева решений сложнее, чем может показаться. Это происходит потому что решение на какие разветвления (характеристики) делить ваши данные (что является темой из области энтропии и получения данных) — это математически сложная задача.

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

В общем случае, специалисты обычно выбирают размер случайного набора характеристик (обозначается m) так, чтобы он был квадратным корнем общего количества характеристик в наборе данных (обозначается р). Если коротко, то m — это квадратный корень из р и тогда конкретная характеристика случайным образом выбирается из m.

Выгоды использования случайного леса

Представьте, что вы работаете с множеством данных, у которого есть одна «сильная» характеристика. Иными словами, в этом множестве данных есть характеристика, которая намного более предсказуема в отношении конечного результата, чем остальные характеристики этого множества.

Если вы строите дерево решений вручную, то имеет смысл использовать эту характеристку для самого «верхнего» разделения в вашем дереве. Это значит, что у вас будет несколько деревьев, прогнозы которых сильно коррелируют.

Мы хотим этого избежать, т.к. использование средней от сильно коррелирующих переменных не снижает значительно дисперсию. Используя случайные наборы характеристик для каждого дерева в случайном лесу, мы декоррелируем деревья и дисперсия полученной модели уменьшается. Эта декорреляция — главное преимущество в использовании случайных лесов в сравнении с деревьями решений, построенными вручную.

Подведем итог

Итак, краткое содержание того, что вы только что узнали о деревьях решений и случайных лесах:

• Пример задачи, решение которой можно спрогнозировать с помощью дерева решений
• Элементы дерева решений: узлы, грани, корни и листья
• Как использование случайного набора характеристик позволяет нам построить случайный лес
• Почему использование случайного леса для декорреляции переменных может быть полезным для уменьшения дисперсии полученной модели

Метод опорных векторов(Support Vector Machines)

Метод опорных векторов это алгоритм классификации (хотя, технически говоря, они также могут быть использованы для решения регрессионных задач), который делит множество данных на категории в местах наибольших «разрывов» между категориями. Эта концепция станет более понятной, если разобрать следующий пример.

Что такое метод опорных векторов?

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

Как МОВ работает?

Давайте капнем поглубже в то, как действительно работает МОВ.

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

МОВ использует геометрию для составления прогнозов по категориям. Конкретнее модель метода опорных векторов сопоставляет точки данных как точки в пространстве и разделяет на отдельные категории так, что они разделяются настолько широким разрывом, насколько возможно. Прогноз принадлежности новых точек данных к определенной категории основывается на том, с какой стороны разрыва находится точка.

Вот пример визуализации, который поможет вам понять интуицию МОВ:

Как вы можете наблюдать, если новая точка данных падает на левую от зеленой линии сторону, то она будет отнесена к «красным», а если на правую — то к «синим». Эта зеленая линия называется гиперплоскостью, и является важным термином для работы с МОВ.

Давайте посмотрим следующее визуальное представление МОВ:

На этой диаграмме гиперплоскость обозначена как «оптимальная гиперплоскость» (optimal hyperplane). Теория метода опорных векторов дает такое определение оптимальной гиперплоскости — это гиперплоскость, которая максимизирует поле между двумя ближайшими точками данных из разных категорий.

Как вы видите, граница поля действительно затрагивает 3 точки данных — 2 из красной категории и 1 из синей. Эти точки, которые соприкасаются с границей поля, и называются опорными векторами — откуда и пошло название.

Подведем итог

Вот краткий очерк того, что вы только что узнали о методе опорных векторов:

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

Метод К-средних (K-Means Clustering)

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

• Сегментация клиентов для маркетинговых групп
• Классификация документов
• Оптимизация маршрутов доставки для таких компаний, как Amazon, UPS или FedEx
• Выявление и реагирование на криминальные локации в городе
• Профессиональная спортивная аналитика
• Прогнозирование и предотвращение киберпреступлений

Главная цель метода К-средних — разделить множество данных на различимые группы таким образом, чтобы элементы внутри каждой группы были схожи между собой.

Вот визуальное представление того, как это выглядит на практике:

Мы изучим математическую составляющую метода К-средних вследующем разделе этой статьи.

Как работает метод К-средних?

Первый шаг в работе метода К-средних — это выбор количества групп на которое вы хотите разделить ваши данные. Этим количеством и является значение К, отраженное в названии алгоритма. Выбор значения К в методе К-средних очень важен. Чуть позже мы обсудим как выбрать правильное значение К.

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

• Вычисление центроида (центр тяжести) каждого кластера взяв средний вектор точек в этом кластере
• Переотнести каждую точку данных к кластеру, центроид которого ближе всего к точке

Выбор подходящего значения К в методе К-средних

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

Для использования этого метода, первое, что вам необходимо сделать, это вычислить сумму квадратов отклонений(sum of squared errors) — СКО для вашего алгоритма для группы значений К. СКО в методе К-средних определена как сумма квадратов расстояний между каждой точкой данных в кластере и центром тяжести этого кластера.

В качестве примера этого шага, вы можете вычислить СКО для значений К 2, 4, 6, 8 и 10. Далее вы захотите сгенерировать график СКО и этих значений К. Вы увидите, что отклонение уменьшается с увеличением значения К.

И это имеет смысл: чем больше категорий вы создадите на основе множества данных — тем более вероятно, что каждая точка данных окажется близко к центру кластера этой точки.

С учетом сказанного, основная идея метода локтя — это выбрать значение К при котором СКО резко замедлит темпы снижения. Это резкое снижение образует «локоть» на графике.

Как пример, вот график СКО относительно К. В этом случае, метод локтя предложит использовать значение К примерно равное 6.

Важно, что К=6 просто оценка приемлемого значения К. Не существует «лучшего» значения К в методе К-средних. Как и многие вещи в области МО, это очень зависящее от ситуации решение.

Подведем итог

Вот краткий очерк того, что вы только что узнали в этом разделе:

• Примеры задач МО без учителя, которые возможно решить методом К-средних
• Базовые принципы метода К-средних
• Как работает метод К-средних
• Как использовать метод локтя для выбора подходящего значения параметра К в данном алгоритме

Метод главных компонент (Principal Component Analysis)

Метод главных компонент используется для преобразования набора данных c множеством параметров в новый набор данных с меньшим количеством параметров и каждый новый параметр этого набора данных — это линейная комбинация раннее существующих параметров. Эти преобразованные данные стремятся обосновать большую часть дисперсии оригинального набора данных с гораздо большей простотой.

Что такое метод главных компонентов?

Метод главных компонент (МГК) — это техника МО, которая используется для изучения взаимосвязей между наборами переменных. Другими словами, МГК изучает наборы переменных для того, чтобы определить базовую структуру этих переменных. МГК еще иногда называют факторным анализом.

На основании этого описания вы можете подумать, что МГК очень схож с линейной регрессией. Но это не так. На самом деле, эти 2 техники имеют несколько важных отличий.

Различия линейной регрессии и МГК

Линейная регрессия определяет линию наилучшего соответствия через набор данных. Метод главных компонентов определяет несколько ортогональных линий наилучшего соответствия для набора данных.

Если вы не знакомы с термином ортогональный, то это просто означает, что линии находятся под прямым углом друг к другу, как север, восток, юг и запад на карте.

Давайте рассмотрим пример, чтобы помочь вам понять это лучше.

Взгляните на метки осей на этом изображении. Главный компонент оси х объясняет 73% дисперсии в этом наборе данных. Главный компонент оси у объясняет около 23% дисперсии набора данных.

Это означает, что 4% дисперсии остается необъясненными. Вы можете уменьшить это число добавляя больше главных компонент в ваш анализ.

Подведем итог

Краткое содержание того, что вы только что узнали о методе главных компонент:

• МГК пытается найти ортогональные факторы, которые определяют изменчивость в наборе данных
• Разницу между линейной регрессией и МГК
• Как выглядит ортогональные главные компоненты, визуализированные в наборе данных
• Что добавление дополнительных главных компонент может помочь объяснить дисперсию более точно в наборе данных

Как выбирать алгоритмы для машинного обучения Microsoft Azure / Блог компании Microsoft / Хабр

В статье вы найдете шпаргалку по алгоритмам машинного обучения Microsoft Azure, которая поможет вам выбрать подходящий алгоритм для ваших решений предиктивной аналитики из библиотеки алгоритмов Microsoft Azure. А также вы узнаете, как ее использовать.

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

Шпаргалка по алгоритмам машинного обучения Microsoft Azure

Скачать шпаргалку по алгоритмам машинного обучения Microsoft Azure можно здесь.

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

Эти рекомендации созданы на основе отзывов и советов множества специалистов по анализу данных и экспертов по машинному обучению. Мы не во всем согласны друг с другом, но постарались обобщить наши мнения и достичь консенсуса. Большинство спорных моментов начинаются со слов «Смотря по обстоятельствам…» 🙂

Как использовать шпаргалку

Читать метки пути и алгоритма на схеме нужно так: «Для метка пути> использовать лгоритм>». Например, «Для speed использовать two class logistic regression». Иногда можно использовать несколько ветвей. Иногда ни одна из них не будет идеальным выбором. Это всего лишь рекомендации, поэтому не беспокойтесь о неточностях. Некоторые специалисты по анализу данных, с которыми мне удалось пообщаться, говорят, что единственный верный способ найти лучший алгоритм — попробовать их все.

Вот пример эксперимента из Cortana Intelligence Gallery, в котором пробуются несколько алгоритмов с одними и теми же данными и сравниваются результаты.

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

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

Обучение с учителем

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

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

• Классификация. Когда данные используются для прогнозирования категории, обучение с учителем называется классификацией. В этом случае происходит назначение изображения, например «кот» или «собака». Когда есть только два варианта выбора, это называется двухклассовой классификацией. Когда категорий больше, например, при прогнозировании победителя турнира NCAA March Madness, это называется многоклассовой классификацией.
• Регрессия. Когда прогнозируется значение, например, в случае с курсом акций, обучение с учителем называется регрессией.
• Фильтрация выбросов. Иногда нужно определить необычные точки данных. Например, при обнаружении мошенничества под подозрение попадают любые странные закономерности трат средств с кредитной карты. Возможных вариантов так много, а примеров для обучения так мало, что практически невозможно узнать, как будет выглядеть мошенническая деятельность. При фильтрации выбросов просто изучается нормальная активность (с помощью архива допустимых транзакций) и находятся все операции с заметными отличиями.

Обучение без учителя

В рамках обучения без учителя у объектов данных нет меток. Вместо этого алгоритм обучения без учителя должен организовать данные или описать их структуру. Для этого их можно сгруппировать в кластеры, чтобы они стали более структурированными, или найти другие способы упростить сложные данные.

Обучение с подкреплением

В рамках обучения с подкреплением алгоритм выбирает действие в ответ на каждый входящий объект данных. Через некоторое время алгоритм обучения получает сигнал вознаграждения, который указывает, насколько правильным было решение. На этом основании алгоритм меняет свою стратегию, чтобы получить наивысшую награду. В настоящее время в машинном обучении Azure нет модулей обучения с подкреплением. Обучение с подкреплением распространено в роботехнике, где набор показаний датчика в определенный момент времени является объектом, и алгоритм должен выбрать следующее действие робота. Кроме того, этот алгоритм подходит для приложений в Интернете вещей.

Советы по выбору алгоритма

Точность

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

Время обучения

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

Линейность

Во многих алгоритмах машинного обучения используется линейность. Алгоритмы линейной классификации предполагают, что классы можно разделить прямой линией (или ее более многомерным аналогом). Здесь речь идет о логистической регрессии и метод опорных векторов (в машинном обучении Azure). Алгоритмы линейной регрессии предполагают, что распределение данных описывается прямой линией*. Эти предположения подходят для решения ряда задач, но в некоторых случаях снижают точность.

Ограничение нелинейных классов — использование алгоритма линейной классификации снижает точность

Данные с нелинейной закономерностью — при использовании метода линейной регрессии возникают более серьезные ошибки, чем это допустимо

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

Количество параметров

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

Также в машинном обучении Azure есть модульный блок подбора параметров, который автоматически пробует все комбинации параметров с указанной вами степенью детализации. Хоть этот способ и позволяет опробовать множество вариантов, однако чем больше параметров, тем больше времени уходит на обучение модели.

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

Количество признаков

В некоторых типах данных признаков может быть гораздо больше, чем объектов. Это обычно происходит с данными из области генетики или с текстовыми данными. Большое количество признаков препятствует работе некоторых алгоритмов обучения, из-за чего время обучения невероятно растягивается. Для подобных случаев хорошо подходит метод опорных векторов (см. ниже).

Особые случаи

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

Свойства алгоритма:

• — демонстрирует отличную точность, короткое время обучения и использование линейности.

○ — демонстрирует отличную точность и среднее время обучения.

Примечания к алгоритму

Линейная регрессия

Как мы уже говорили, линейная регрессия рассматривает данные линейно (или в плоскости, или в гиперплоскости). Это удобная и быстрая «рабочая лошадка», но для некоторых проблем она может быть чересчур простой. Здесь вы найдете руководство по линейной регрессии.

Данные с линейным трендом

Логистическая регрессия

Пусть слово «регрессия» в названии не вводит вас в заблуждение. Логистическая регрессия — это очень мощный инструмент для двухклассовой и многоклассовой классификации. Это быстро и просто. Поскольку вместо прямой линии здесь используется кривая в форме буквы S, этот алгоритм прекрасно подходит для разделения данных на группы. Логистическая регрессия ограничивает линейный класс, поэтому вам придется смириться с линейной аппроксимацией.

Логистическая регрессия для двухклассовых данных всего с одним признаком — граница класса находится в точке, где логистическая кривая близка к обоим классам

Деревья, леса и джунгли

Леса решающих деревьев (регрессия, двухклассовые и многоклассовые), джунгли решающих деревьев (двухклассовые и многоклассовые) и улучшенные деревья принятия решений (регрессия и двухклассовые) основаны на деревьях принятия решений, базовой концепции машинного обучения. Существует много вариантов деревьев принятия решений, но все они выполняют одну функцию — подразделяют пространство признаков на области с одной и той же меткой. Это могут быть области одной категории или постоянного значения, в зависимости от того, используете ли вы классификацию или регрессию.

Дерево принятия решений подразделяет пространство признаков на области с примерно одинаковыми значениями

Поскольку пространство признаков можно разделить на небольшие области, это можно сделать так, чтобы в одной области был один объект — это грубый пример ложной связи. Чтобы избежать этого, крупные наборы деревьев создаются таким образом, чтобы деревья не были связаны друг с другом. Таким образом, «дерево принятия решений» не должно выдавать ложных связей. Деревья принятия решений могут потреблять большие объемы памяти. Джунгли решающих деревьев потребляют меньше памяти, но при этом обучение займет немного больше времени.

Улучшенные деревья принятия решений ограничивают количество разделений и распределение точек данных в каждой области, чтобы избежать ложных связей. Алгоритм создает последовательность деревьев, каждое из которых исправляет допущенные ранее ошибки. В результате мы получаем высокую степень точности без больших затрат памяти. Полное техническое описание смотрите в научной работе Фридмана.

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

Нейронные сети и восприятие

Нейронные сети — это алгоритмы обучения, которые созданы на основе модели человеческого мозга и направлены на решение многоклассовой, двухклассовой и регрессионной задач. Их существует огромное множество, но в машинном обучении Azure нейронные сети принимают форму направленного ациклического графика. Это означает, что входные признаки передаются вперед через последовательность уровней и превращаются в выходные данные. На каждом уровне входные данные измеряются в различных комбинациях, суммируются и передаются на следующий уровень. Эта комбинация простых расчетов позволяет изучать сложные границы классов и тенденции данных будто по волшебству. Подобные многоуровневые сети выполняют «глубокое обучение», которое служит источником вдохновения для технических отчетов и научной фантастики.

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

Границы, изучаемые нейронными сетями, бывают сложными и хаотичными

Однослойный перцептрон — это ответ нейронных сетей на увеличение времени обучения. В нем используется сетевая структура, которая создает линейные классовые границы. По современным стандартам звучит примитивно, но этот алгоритм давно проверен на деле и быстро обучается.

Методы опорных векторов

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

Стандартная граница класса опорной векторной машины увеличивает поле между двумя классами

Еще один продукт от Microsoft Research — двухклассовые локальные глубинные методы опорных векторов. Это нелинейный вариант методов опорных векторов, который отличается скоростью и эффективностью памяти, присущей линейной версии. Он идеально подходит для случаев, когда линейный подход не дает достаточно точных ответов. Чтобы обеспечить высокую скорость, разработчики разбивают проблему на несколько небольших задач линейного метода опорных векторов. Подробнее об этом читайте в полном описании.

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

Байесовские методы

Байесовские методы отличаются очень нужным качеством: они избегают ложных связей. Для этого они заранее делают предположения о возможном распределении ответа. Также для них не нужно настраивать много параметров. Машинное обучение Azure предлагает Байесовские методы как для классификации (двухклассовая классификация Байеса), так и для регрессии (Байесова линейная регрессия). При этом предполагается, что данные можно разделить или расположить вдоль прямой линии.

Кстати, точечные машины Байеса были разработаны в Microsoft Research. В их фундаменте лежит великолепная теоретическая работа. Если вас заинтересует эта тема, читайте статью в MLR и блог Криса Бишопа (Chris Bishop).

Особые алгоритмы

Если вы преследуете конкретную цель, вам повезло. В коллекции машинного обучения Azure есть алгоритмы, которые специализируются в прогнозировании рейтингов (порядковая регрессия), прогнозирование количества (регрессия Пуассона) и выявлении аномалий (один из них основан на анализе главных компонентов, а другой — на методах опорных векторов). А еще есть алгоритм кластеризации (метод k-средних).

Выявление аномалий на основе PCA — огромное множество данных попадает под стереотипное распределение; под подозрение попадают точки, которые сильно отклоняются от этого распределения

Набор данных разделяется на пять кластеров по методу k-средних

Также есть многоклассовый классификатор «один против всех», который разбивает проблему классификации N-класса на двухклассовые проблемы класса N-1. Точность, время обучения и свойства линейности зависят от используемых двухклассовых классификаторов.

Два двухклассовых классификатора формируют трехклассовый классификатор

Кроме того, Azure предлагает доступ к мощной платформе машинного обучения под названием Vowpal Wabbit. VW отказывается от категоризации, поскольку может изучить проблемы классификации и регрессии и даже обучаться от частично помеченных данных. Вы можете выбрать любой из алгоритмов обучения, функций потерь и алгоритмов оптимизации. Эта платформа отличается эффективностью, возможностью параллельного выполнения и непревзойденной скоростью. Она без труда справляется с большими наборами данных. VW была запущена Джоном Лэнгфордом (John Langford), специалистом из Microsoft Research, и является болидом «Формулы-1» в океане серийных автомобилей. Не каждая проблема подходит для VW, но если вы считаете, что это верный для вас вариант, то затраченные усилия обязательно окупятся. Также платформа доступна в виде автономного открытого исходного кода на нескольких языках.

Последние материалы из нашего блога по данной теме

1. Azure понятным языком (шпаргалка).
2. Грузовики и рефрижераторы в облаке (кейс).

Напоминаем, что попробовать Microsoft Azure можно здесь.

Если вы увидели неточность перевода, сообщите, пожалуйста, об этом в личные сообщения.

*UPD

Так как в тексте автора присутствует неточность, дополняем материал (спасибо @fchugunov)

Линейная регрессия применяется не только для определения зависимости, которая описывается прямой линией (или плоскостью), как указано в статье. Зависимость может описываться и более сложными функциями. Например, для функции на втором графике может быть применен метод полиномиальной регрессии (разновидность линейной регрессии). Для этого входные данные (например значение x) преобразуются в набор факторов [x, x², x³,..], а метод линейной регрессии уже подбирает коэффициенты к ним.

алгоритмов классификации | Типы алгоритмов классификации

Идея алгоритмов классификации довольно проста . Вы предсказываете целевой класс, анализируя обучающий набор данных. Это одна из самых, если не , самая важная концепция , которую вы изучаете, когда изучаете Data Science .

В этом блоге обсуждаются следующие концепции:

Что такое классификация?

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

Примеры целевого класса:

• Анализ данных клиента, чтобы предсказать, купит ли он компьютерные аксессуары (Целевой класс: Да или Нет)
• Классификация фруктов по таким характеристикам, как цвет, вкус, размер, вес ( Целевые классы: яблоко, апельсин, вишня, банан)
• Гендерная классификация по длине волос (целевые классы: мужской или женский)

Давайте разберемся с концепцией алгоритмов классификации с гендерной классификацией с использованием длины волос (ни в коем случае Я пытаюсь стереотипировать по полу, это только пример).Чтобы классифицировать пол (целевой класс) с использованием длины волос в качестве параметра характеристики, мы могли бы обучить модель, используя любые алгоритмы классификации, чтобы придумать некоторый набор граничных условий, которые можно использовать для различения мужского и женского пола с использованием длины волос в качестве тренировки. особенность. В случае гендерной классификации граничным условием может быть правильное значение длины волос. Предположим, что значение длины волос с дифференцированной границей равно 15,0 см, тогда мы можем сказать, что если длина волос на меньше 15.0 см , тогда пол может быть мужской или женский.

Алгоритмы классификации против алгоритмов кластеризации

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

Элементы группы Примеры:

• При группировке документов с одинаковым языком (Документы на одном языке составляют одну группу.)
• При категоризации новостных статей (Статьи той же новостной категории (спорт) составляют одну группу)

Давайте разберемся с концепцией кластеризации гендерных групп на примере длины волос. Чтобы определить пол, можно использовать разные меры сходства для разделения мужского и женского пола. Это можно сделать, найдя сходство между двумя длинами волос и удерживая их в одной группе, если сходство меньше (Разница в длине волос меньше) .Тот же процесс может продолжаться до тех пор, пока вся длина волос не будет правильно сгруппирована в две категории.

Основная терминология в алгоритмах классификации

• Классификатор: Алгоритм, который сопоставляет входные данные с определенной категорией.
• Модель классификации: Модель классификации пытается сделать некоторый вывод из входных значений, данных для обучения. Он предскажет метки / категории классов для новых данных.
• Признак: Признак — это индивидуальное измеримое свойство наблюдаемого явления.
• Бинарная классификация: Задание классификации с двумя возможными результатами. Например: Половая классификация (мужской / женский)
• Многоклассовая классификация: Классификация с более чем двумя классами. При мультиклассовой классификации каждому образцу присваивается одна и только одна целевая метка. Например: животное может быть кошкой или собакой, но не обоими одновременно.
• Классификация с несколькими метками: Задача классификации, при которой каждый образец сопоставляется с набором целевых меток (более одного класса). Например: новостная статья может быть о спорте, человеке и месте одновременно.

Применение алгоритмов классификации

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

Типы алгоритмов классификации

Алгоритмы классификации можно в целом классифицировать следующим образом:

• Линейные классификаторы
  • Логистическая регрессия
  • Наивный байесовский классификатор
  • Линейный дискриминант Фишера

  932 932 Опорные векторные машины

  • Наименьшие квадраты поддерживают векторные машины
• Квадратичные классификаторы
• Оценка ядра
• Деревья решений
• Нейронные сети Обучающее векторное квантование

Ниже приведены примеры нескольких популярных алгоритмов классификации.

Логистическая регрессия

Каким бы запутанным ни было название, можете не сомневаться. Логистическая регрессия — это классификация, а не алгоритм регрессии. Он оценивает дискретные значения (двоичные значения, такие как 0/1, да / нет, истина / ложь) на основе заданного набора независимых переменных. Проще говоря, он в основном предсказывает вероятность возникновения события, подгоняя данные к логит-функции . Следовательно, она также известна как логит-регрессия .Полученные значения всегда лежат в пределах от 0 до 1, так как он предсказывает вероятность.

Попробуем разобраться в этом на другом примере.

Допустим, на вашем тесте по математике есть сумма. У него может быть только 2 результата, верно? Либо вы решите ее, либо нет (и давайте не будем брать здесь баллы за метод). А теперь представьте, что вам дают широкий диапазон сумм в попытке понять, какие главы вы хорошо поняли. Результат этого исследования будет примерно таким: если вам предложат задачу, основанную на тригонометрии, вы с 70% вероятностью ее решите.С другой стороны, если это арифметическая задача, вероятность получить ответ составляет всего 30%. Это то, что вам предоставляет логистическая регрессия.

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

 шансы = p / (1-p) = вероятность наступления события / вероятность наступления события ln (odds) = ln (p / (1-p)) logit (p) = ln (p / (1-p) ) = b0 + b1X1 + b2X2 + b3X3 .... + bkXk) 

В приведенном выше уравнении p — это вероятность наличия интересующей характеристики.Он выбирает параметры, которые увеличивают вероятность наблюдения значений выборки, а не минимизируют сумму квадратов ошибок (как в обычной регрессии).

Многие из вас могут задаться вопросом, зачем нужно вести журнал? Для простоты скажем, что это один из лучших математических способов воспроизвести ступенчатую функцию. Я могу пойти на это более подробно, но это превзойдет цель этого блога.

R-код:

 x <- cbind (x_train, y_train)
# Обучите модель с помощью обучающих наборов и проверьте результат
логистика <- glm (y_train ~., data = x, family = 'binomial')
резюме (логистика)
#Predict Output
предсказанный = прогнозируемый (логистический, x_test) 

Есть много различных шагов, которые можно попробовать, чтобы улучшить модель:

• включить условия взаимодействия
• удалить признаки
• методы регуляризации
• использовать нелинейную модель

Деревья решений

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

На изображении выше вы можете видеть, что население разделено на четыре разные группы на основе нескольких атрибутов, чтобы определить, «будут ли они играть или нет».

R-Code:

 библиотека (rpart)
x <- cbind (x_train, y_train)
# выращивать дерево
fit <- rpart (y_train ~., data = x, method = "class")
резюме (подходит)
#Predict Output
прогнозируемый = прогнозируемый (соответствие, x_test) 

Наивный байесовский классификатор

Это метод классификации, основанный на предположении независимости между предикторами или так называемой теореме Байеса .Проще говоря, наивный байесовский классификатор предполагает, что наличие определенной функции в классе не связано с наличием какой-либо другой функции.

Например, фрукт может считаться яблоком, если он красный, круглый и имеет диаметр около 3 дюймов. Даже если эти характеристики зависят друг от друга или от наличия других характеристик, наивный байесовский классификатор будет рассматривать все эти свойства как независимые факторы, влияющие на вероятность того, что этот фрукт является яблоком.

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

Теорема Байеса обеспечивает способ вычисления апостериорной вероятности P (c | x) из P (c) , P (x) и P (x | c) . Выражение для апостериорной вероятности следующее.

Здесь

• P ( c | x ) - апостериорная вероятность класса ( цель ) для данного предиктора (атрибут ).
• P ( c ) - априорная вероятность класса .
• P ( x | c ) - это вероятность, которая представляет собой вероятность предсказателя с учетом класса .
• P ( x ) - априорная вероятность предсказателя .

Пример: Давайте рассмотрим пример, чтобы лучше понять это. Итак, у меня есть тренировочный набор данных о погоде, а именно солнечная, пасмурная и дождливая погода, и соответствующая двоичная переменная Play.Теперь нам нужно определить, будут ли игроки играть или нет, в зависимости от погодных условий. Чтобы выполнить это, выполните следующие действия.

Шаг 1: Преобразуйте набор данных в таблицу частот

Шаг 2: Создайте таблицу правдоподобия, найдя такие вероятности, как Вероятность пасмурности = 0,29 и вероятность игры равна 0,64 .

Шаг 3: Теперь используйте наивное байесовское уравнение, чтобы вычислить апостериорную вероятность для каждого класса.Класс с самой высокой апостериорной вероятностью является результатом предсказания.

Проблема: Игроки будут играть в солнечную погоду. Верно ли это утверждение?

Мы можем решить эту проблему, используя описанный выше метод, поэтому P (Да | Солнечно) = P (Солнечно | Да) * P (Да) / P (Солнечно)

Здесь у нас P (Солнечно | Да) = 3/9 = 0,33 , P (Солнечно) = 5/14 = 0,36 , P (Да) = 9/14 = 0,64

Сейчас, P (Да | Солнечно) = 0.33 * 0,64 / 0,36 = 0,60 , что имеет большую вероятность.

Наивный байесовский метод использует аналогичный метод для прогнозирования вероятности различного класса на основе различных атрибутов. Этот алгоритм в основном используется при классификации текста и при проблемах с несколькими классами.

R-Code:

 библиотека (e1071)
x <- cbind (x_train, y_train)
# Модель примерки
fit <-naiveBayes (y_train ~., data = x)
резюме (подходит)
#Predict Output
предсказанный = предсказать (соответствие, x_test) 

KNN (k- Ближайшие соседи)

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

В то время как три прежние функции расстояния используются для непрерывных переменных, функция расстояния Хэмминга используется для категориальных переменных. Если K = 1 , то случай просто присваивается классу его ближайшего соседа.Иногда выбор K оказывается проблемой при моделировании kNN.

Вы можете легко понять KNN, взяв пример из нашей реальной жизни. Если вам в классе нравится девочка / мальчик, о которых у вас нет информации, вы можете поговорить с их друзьями и социальными кругами, чтобы получить доступ к их информации!

R-Code:

 библиотека (knn)
x <- cbind (x_train, y_train)
# Модель примерки
fit <-knn (y_train ~., data = x, k = 5)
резюме (подходит)
#Predict Output
предсказано = предсказать (соответствует, x_test) 

Что следует учитывать перед выбором KNN:

• KNN требует больших вычислительных ресурсов
• Переменные должны быть нормализованы, иначе переменные более высокого диапазона могут привести к смещению
• Прежде чем приступить к работе для kNN, как выброс, удаление шума

SVM (машина опорных векторов)

В этом алгоритме мы строим каждый элемент данных как точку в n-мерном пространстве (где n - количество имеющихся у вас функций) с значение каждого объекта является значением конкретной координаты.

Например, если бы у нас было только две характеристики, такие как высота и длина волос человека, мы сначала построили бы эти две переменные в двухмерном пространстве, где каждая точка имеет две координаты (эти координаты известны как опорные векторы )

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

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

R-Code:

 библиотека (e1071)
x <- cbind (x_train, y_train)
# Модель примерки
fit <-svm (y_train ~., данные = х)
резюме (подходит)
#Predict Output
предсказанный = предсказать (соответствует, x_test) 

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

.

7 типов алгоритмов классификации

Целью этого исследования является объединение 7 наиболее распространенных типов алгоритмов классификации вместе с кодом Python: логистическая регрессия, наивный байесовский метод, стохастический градиентный спуск, K-ближайших соседей, дерево решений, случайный лес и машина опорных векторов.

1 Введение

1.1 Классификация структурированных данных

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

Несколько терминологий, встречающихся в машинном обучении - классификация:

• Классификатор: Алгоритм, сопоставляющий входные данные с определенной категорией.
• Модель классификации: Модель классификации пытается сделать некоторые выводы из входных значений, данных для обучения.Он предскажет метки / категории классов для новых данных.
• Элемент: Элемент - это индивидуальное измеримое свойство наблюдаемого явления.
• Бинарная классификация: Задание на классификацию с двумя возможными результатами. Например: половая принадлежность (мужской / женский)
• Многоклассовая классификация: Классификация с более чем двумя классами. При многоклассовой классификации каждому образцу присваивается одна и только одна целевая метка.Например: животное может быть кошкой или собакой, но не одновременно
• Классификация с несколькими метками: Задача классификации, в которой каждый образец сопоставляется с набором целевых меток (более одного класса). Например: новостная статья может быть о спорте, человеке и месте одновременно.

Ниже приведены этапы построения модели классификации:

• Инициализировать классификатор, который будет использоваться.
• Обучить классификатор: Все классификаторы в scikit-learn используют метод подгонки (X, y), чтобы соответствовать модели (обучению) для заданных данных поезда X и метки поезда y.
• Предсказать цель: Для немаркированного наблюдения X, прогноз (X) возвращает прогнозируемую метку y.
• Оценить модель классификатора

1.2 Источник и содержание набора данных

Набор данных содержит зарплаты. Ниже приводится описание нашего набора данных:

• классов: 2 («> 50K» и «<= 50K»)
• атрибутов (столбцов): 7
• экземпляров (рядов): 48 842

Эти данные были взяты из базы данных бюро переписи населения по адресу:

http: // www.census.gov/ftp/pub/DES/www/welcome.html

1.3 Исследовательский анализ данных

2 типа алгоритмов классификации (Python)

2.1 Логистическая регрессия

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

Преимущества: Логистическая регрессия предназначена для этой цели (классификации) и наиболее полезна для понимания влияния нескольких независимых переменных на одну конечную переменную.

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

2,2 Наивный Байес

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

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

Недостатки: Наивный байесовский метод известен как плохой оценщик.

2.3 Стохастический градиентный спуск

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

Достоинства: Оперативность и простота внедрения.

Недостатки: Требует ряда гиперпараметров и чувствителен к масштабированию функций.

2,4 K-ближайших соседей

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

Преимущества: Этот алгоритм прост в реализации, устойчив к зашумленным обучающим данным и эффективен при больших объемах обучающих данных.

Недостатки: Необходимо определить значение K, а затраты на вычисления высоки, так как необходимо вычислить расстояние каждого экземпляра до всех обучающих выборок.

2.5 Дерево решений

Определение: Учитывая данные атрибутов вместе с их классами, дерево решений создает последовательность правил, которые могут использоваться для классификации данных.

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

Смотрите также

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

2.6 Случайный лес

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

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

Недостатки: Медленное прогнозирование в реальном времени, сложность в реализации и сложный алгоритм.

2.7 Машина опорных векторов

Определение: Машина опорных векторов - это представление обучающих данных в виде точек в пространстве, разделенных на категории как можно более широким пробелом.Затем новые примеры отображаются в том же пространстве и предсказываются как принадлежащие к категории, в зависимости от того, на какую сторону пропасти они попадают.

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

Недостатки: Алгоритм не дает напрямую оценок вероятностей, они вычисляются с использованием дорогостоящей пятикратной перекрестной проверки.

3 Заключение

3.1 Сравнительная таблица

• Точность: (истинно положительный + истинно отрицательный) / общая популяция
  • Точность - это отношение правильно спрогнозированных наблюдений к общему количеству наблюдений. Точность - это наиболее интуитивно понятный показатель производительности.
  • Истинно-положительное: количество правильных прогнозов о том, что событие является положительным
  • Истинно отрицательное число: количество правильных прогнозов о том, что возникновение отрицательное.
• F1-Оценка: (2 x точность x отзыв) / (точность + отзыв)
  • F1-Score - это средневзвешенное значение точности и отзыва, используемое во всех типах алгоритмов классификации.Таким образом, эта оценка учитывает как ложные срабатывания, так и ложные отрицательные результаты. F1-Score обычно более полезен, чем точность, особенно если у вас неравномерное распределение классов.
  • Точность: Когда прогнозируется положительное значение, как часто прогноз оказывается правильным?
  • Напомним: если фактическое значение положительное, как часто прогноз верен?

Расположение кода: https://github.com/f2005636/Classification

3.2 Выбор алгоритма

(Типы алгоритмов классификации)

Если вам понравилась эта история, присоединяйтесь к нашему сообществу Telegram.

Кроме того, вы можете написать для нас и стать одним из 500+ экспертов, которые написали статьи на AIM. Поделитесь своими номинациями здесь.

Рохит Гарг

Рохит Гарг имеет почти 7-летний опыт работы в области анализа данных и машинного обучения.Он много работал в области прогнозного моделирования, анализа временных рядов и методов сегментации. Рохит имеет BE от BITS Pilani и PGDM от IIM Raipur.

.

Введение в алгоритмы классификации - DZone AI

Поприветствуйте алгоритмы классификации!

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

Вам также может понравиться:
Лучшие алгоритмы машинного обучения, которые вы должны знать, чтобы стать специалистом по данным

Что такое классификация?

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

Примеры целевого класса:

• Анализ данных клиента, чтобы предсказать, купит ли он компьютерные аксессуары (Целевой класс: Да или Нет)
• Классификация фруктов по таким признакам, как цвет, вкус, размер, вес (Целевые классы: яблоко, апельсин, вишня, банан)
• Гендерная классификация по длине волос (Целевые классы: мужской или женский)

Давайте разберемся с концепцией алгоритмов классификации с гендерной классификацией с использованием длины волос (я ни в коем случае не пытаюсь стереотипировать по полу, это только пример).Чтобы классифицировать пол (целевой класс) с использованием длины волос в качестве параметра характеристики, мы могли бы обучить модель, используя любые алгоритмы классификации, чтобы придумать некоторый набор граничных условий, которые можно использовать для различения мужского и женского пола, используя длину волос в качестве функция обучения. В случае гендерной классификации граничным условием может быть правильное значение длины волос. Предположим, что значение длины волос с дифференцированной границей составляет 15,0 см, тогда мы можем сказать, что если длина волос на меньше 15.0 см , тогда пол может быть мужской или женский.

Алгоритмы классификации и алгоритмы кластеризации

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

Примеры групповых позиций:

• При группировании документов с одинаковым языком (Документы на одном языке составляют одну группу.)
• При классификации новостных статей (Статьи той же новостной категории (спорт) составляют одну группу)

Давайте разберемся с концепцией кластеризации полов на примере длины волос. Для определения пола можно использовать разные меры сходства, чтобы разделить мужской и женский пол на категории. Это можно сделать, обнаружив сходство между двумя длинами волос и удерживая их в одной группе, если сходство меньше (разница в длине волос меньше). Тот же процесс может продолжаться до тех пор, пока вся длина волос не будет правильно сгруппирована в две категории.

Основная терминология в алгоритмах классификации

• Классификатор: Алгоритм, который сопоставляет входные данные с определенной категорией.
• Модель классификации: Модель классификации пытается сделать некоторые выводы из входных значений, данных для обучения. Он предскажет метки / категории классов для новых данных.
• Характеристика: Характеристика - это индивидуальное измеримое свойство наблюдаемого явления.
• Бинарная классификация: Задача классификации с двумя возможными результатами. Например: половая принадлежность (мужской / женский)
• Многоклассовая классификация: Классификация с более чем двумя классами. При мультиклассовой классификации каждому образцу присваивается одна и только одна целевая метка. Например: животное может быть кошкой или собакой, но не обоими одновременно.
• Классификация с несколькими метками: Задача классификации, в которой каждый образец сопоставляется с набором целевых меток (более одного класса). Например: новостная статья может быть о спорте, человеке и месте одновременно.

Применение алгоритмов классификации

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

Типы алгоритмов классификации

Алгоритмы классификации можно в целом классифицировать следующим образом:

• Линейные классификаторы
  • Логистическая регрессия
  • Наивный байесовский классификатор
  • Линейный дискриминант Фишера
• Опорные векторные машины
  • Наименьшие квадраты поддерживают векторные машины
• Квадратичные классификаторы
• Оценка ядра
• Деревья принятия решений
• Нейронные сети
• Обучающее векторное квантование

Примеры нескольких популярных алгоритмов классификации приведены ниже.

Логистическая регрессия

Каким бы запутанным ни было название, можете не сомневаться. Логистическая регрессия - это классификация, а не алгоритм регрессии. Он оценивает дискретные значения (двоичные значения, такие как 0/1, да / нет, истина / ложь) на основе заданного набора независимых переменных. Проще говоря, он в основном предсказывает вероятность возникновения события, подгоняя данные под логит-функцию . Следовательно, она также известна как логит-регрессия .Полученные значения всегда лежат в пределах от 0 до 1, так как он предсказывает вероятность.

Давайте попробуем разобраться в этом на другом примере.

Допустим, на вашем тесте по математике есть сумма. У него может быть только 2 результата, верно? Либо вы решите ее, либо нет (и давайте не будем брать здесь баллы за метод). А теперь представьте, что вам дают широкий диапазон сумм в попытке понять, какие главы вы хорошо поняли. Результат этого исследования будет примерно таким: если вам предложат задачу, основанную на тригонометрии, вы с 70% вероятностью ее решите.С другой стороны, если это арифметическая задача, вероятность получить ответ составляет всего 30%. Это то, что вам предоставляет логистическая регрессия.

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

  шансы = p / (1-p) = вероятность наступления события / вероятность наступления события ln (odds) = ln (p / (1-p)) logit (p) = ln (p / (1-p) ) = b0 + b1X1 + b2X2 + b3X3 .... + bkXk)  

В приведенном выше уравнении p - это вероятность наличия интересующей характеристики.

Он выбирает параметры, которые максимизируют вероятность наблюдения значений выборки, а не минимизируют сумму квадратов ошибок (как в обычной регрессии).

Многие из вас могут задаться вопросом, зачем же вести журнал? Для простоты скажем, что это один из лучших математических способов воспроизвести ступенчатую функцию. Я могу пойти на это более подробно, но это превзойдет цель этого блога.

  x <- cbind (x_train, y_train)
# Обучите модель с помощью обучающих наборов и проверьте результат
логистика <- glm (y_train ~., data = x, family = 'binomial')
резюме (логистика)
#Predict Output
прогнозируемый = прогнозируемый (логистический, x_test)  

Есть много разных шагов, которые можно попробовать, чтобы улучшить модель:

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

Деревья решений

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

На изображении выше вы можете видеть, что население разделено на четыре разные группы на основе нескольких атрибутов, чтобы определить, «будут ли они играть или нет».

 Библиотека  (rpart)
x <- cbind (x_train, y_train)
# выращивать дерево
fit <- rpart (y_train ~., data = x, method = "class")
резюме (подходит)
#Predict Output
предсказано = предсказать (соответствует, x_test)  

Наивный байесовский классификатор

Это метод классификации, основанный на предположении о независимости между предикторами или так называемой теореме Байеса . Проще говоря, Наивный байесовский классификатор предполагает, что наличие определенной функции в классе не связано с наличием какой-либо другой функции.

Например, фрукт может считаться яблоком, если он красный, круглый и имеет диаметр около 3 дюймов. Даже если эти характеристики зависят друг от друга или от наличия других характеристик, наивный байесовский классификатор будет рассматривать все эти свойства как независимые факторы, влияющие на вероятность того, что этот фрукт является яблоком.

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

Теорема

Байеса обеспечивает способ вычисления апостериорной вероятности P (c | x) из P (c) , P (x) и P (x | c) . Выражение для апостериорной вероятности следующее.

Здесь,

• P ( c | x ) - апостериорная вероятность класса ( target ) с учетом предиктора ( атрибут ).
• P ( c ) - априорная вероятность класса .
• P ( x | c ) - это вероятность, которая представляет собой вероятность предиктора с учетом класса .
• P ( x ) - это априорная вероятность предиктора .

Пример: Давайте рассмотрим пример, чтобы лучше понять это. Итак, у меня есть тренировочный набор данных о погоде, а именно солнечная, пасмурная и дождливая погода, и соответствующая двоичная переменная Play.Теперь нам нужно определить, будут ли игроки играть или нет, в зависимости от погодных условий. Чтобы выполнить это, выполните следующие действия.

Шаг 1: Преобразуйте набор данных в таблицу частот

Шаг 2: Создайте таблицу правдоподобия, найдя такие вероятности, как Вероятность пасмурности = 0,29 и вероятность игры равна 0,64 .

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

Задача: Игроки будут играть в солнечную погоду. Верно ли это утверждение?

Мы можем решить эту проблему, используя описанный выше метод, поэтому P (Да | Солнечно) = P (Солнечно | Да) * P (Да) / P (Солнечно)

Здесь мы имеем P (Солнечно | Да) = 3/9 = 0,33 , P (Солнечно) = 5/14 = 0,36 , P (Да) = 9/14 = 0,64

Сейчас, P (Да | Солнечно) = 0.33 * 0,64 / 0,36 = 0,60 , что имеет большую вероятность.

Наивный байесовский метод использует аналогичный метод для прогнозирования вероятности разных классов на основе различных атрибутов. Этот алгоритм в основном используется при классификации текста и при проблемах с несколькими классами.

Код R:

 Библиотека  (e1071)
x <- cbind (x_train, y_train)
# Модель примерки
fit <-naiveBayes (y_train ~., data = x)
резюме (подходит)
#Predict Output
предсказано = предсказать (соответствует, x_test)  

KNN (k- Ближайшие соседи)

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

В то время как три прежние функции расстояния используются для непрерывных переменных, функция расстояния Хэмминга используется для категориальных переменных. Если K = 1 , то случай просто относят к классу его ближайшего соседа.Иногда выбор K оказывается проблемой при моделировании kNN.

Вы можете легко понять KNN, взяв пример из нашей реальной жизни. Если вам в классе нравится девочка / мальчик, о которых у вас нет информации, вы можете поговорить с их друзьями и социальными кругами, чтобы получить доступ к их информации!

  библиотека (knn)
x <- cbind (x_train, y_train)
# Модель примерки
fit <-knn (y_train ~., data = x, k = 5)
резюме (подходит)
#Predict Output
предсказано = предсказать (соответствует, x_test)  

На что следует обратить внимание перед выбором KNN:

• KNN требует больших вычислительных ресурсов
• Переменные должны быть нормализованы, иначе переменные более высокого диапазона могут привести к смещению
• Работает на стадии предварительной обработки перед переходом на кНН как выброс, удаление шума

SVM (машина опорных векторов)

В этом алгоритме мы строим каждый элемент данных как точку в n-мерном пространстве (где n - количество имеющихся у вас функций), причем значение каждой функции является значением конкретной координаты.

Например, если бы у нас было только две характеристики, такие как рост и длина волос человека, мы сначала построили бы эти две переменные в двухмерном пространстве, где каждая точка имеет две координаты (эти координаты известны как опорные векторы )

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

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

 Библиотека  (e1071)
x <- cbind (x_train, y_train)
# Модель примерки
fit <-svm (y_train ~., данные = х)
резюме (подходит)
#Predict Output
предсказано = предсказать (соответствует, x_test)  

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

Дополнительная литература

Введение в машинное обучение для разработчиков

Машинное обучение в коробке (часть 3): стили обучения алгоритму

.

Машинное обучение: типы алгоритмов классификации

Помните теорему о запрете бесплатного обеда? Нет, это не о еде (пока). Но если вы голодны, перекусите перед чтением этого поста - я не хочу, чтобы вы пускали слюни на клавиатуру.

Напомню - ни один алгоритм не является оптимальным по множеству всех возможных ситуаций. Алгоритмы машинного обучения - это тонкие инструменты, которые вы настраиваете в зависимости от набора задач, особенно в управляемом машинном обучении.

Сегодня мы увидим, как работают популярные алгоритмы классификации, и поможем нам, например, выбирать и сортировать замечательные, сочные помидоры.

Как работает классификация

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

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

Компьютеры такие же! Чтобы классификационная модель научилась точно предсказывать результаты, требуется множество обучающих примеров.

4 типа классификации

Двоичная

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

Чем вы занимаетесь? Очевидно, вы используете кодирование меток и в этом случае присваиваете 1 «красному» и 0 «не красному». Сортировка помидоров никогда не была такой простой.

Мультикласс

Что вы видите на этой фотографии?

Красный бифштекс Помидоры. Помидоры черри. Коктейльные помидоры.Фамильные помидоры.

Здесь нет черного и белого, «нормального» и «ненормального», как в бинарной классификации. Мы приветствуем к нашему столу всевозможные чудесные овощи (или ягоды).

Что вы, вероятно, не знаете, если не являетесь поклонником приготовления помидоров , так это того, что не все помидоры одинаково хороши для одного и того же блюда. Красные помидоры из бифштекса идеально подходят для сальсы, но их нельзя мариновать. Помидоры черри подходят для салатов, но не для пасты. Поэтому важно знать , с какими вы имеете дело.

Классификация по мультиклассу помогает нам отсортировать все помидоры из коробки независимо от того, сколько в них классов.

Multi-label

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

Для работы с этим типом классификации вам необходимо построить модель, которая может прогнозировать несколько выходных данных.

Для распознавания объектов на фотографиях требуется классификация с несколькими метками.Например, если вам нужно идентифицировать на одном изображении не только помидоры, но и различные другие объекты: яблоки, цукини, лук и т. Д.

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

Вы также можете попробовать использовать отдельный алгоритм для каждого класса, чтобы прогнозировать метки для каждой категории.

Несбалансированная

Мы работаем с несбалансированной классификацией, когда примеры в каждом классе распределены неравномерно.

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

Я рекомендую вам посетить фантастический блог Machine Learning Mastery, где вы можете прочитать о различных типах классификации и изучить множество других материалов по машинному обучению.

Шаги по построению модели классификации

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

1. Выберите классификатор. Вам нужно выбрать один из алгоритмов машинного обучения, который вы будете применять к своим данным.
2. Обучаю. Вам необходимо подготовить набор обучающих данных с помеченными результатами (чем больше примеров, тем лучше).
3. Предсказать результат. Используйте модель, чтобы получить некоторые результаты.
4. Оцените модель классификатора.Рекомендуется подготовить набор данных для проверки, которые вы не использовали во время обучения, для проверки результатов.

Давайте теперь посмотрим на наиболее широко используемые алгоритмы классификации.

Самые популярные алгоритмы классификации

Scikit-Learn - одна из лучших библиотек машинного обучения для Python. Так что, если вы хотите построить свою модель, проверьте ее. Он обеспечивает доступ к широко используемым классификаторам.

Логистическая регрессия

Логистическая регрессия используется для двоичной классификации.

Этот алгоритм использует логистическую функцию для моделирования вероятности наступления результата. Это наиболее полезно, когда вы хотите понять, как несколько независимых переменных влияют на одну конечную переменную.

Пример вопроса: приведут ли уровни осадков и состав почвы к процветанию или безвременной гибели томатов?

Логистическая регрессия имеет ограничения; все предикторы должны быть независимыми, и не должно быть пропущенных значений. Этот алгоритм не сработает, если нет линейного разделения значений.

Наивный байесовский алгоритм

Наивный байесовский алгоритм основан на теореме Байеса. Вы можете применить этот алгоритм для двоичной и мультиклассовой классификации и классифицировать данные на основе исторических результатов.

Пример задачи: мне нужно отделить гнилые помидоры от свежих по их внешнему виду.

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

Используя теорему Байеса, можно сказать, как возникновение события влияет на вероятность другого события.

k-ближайших соседей

kNN означает «k-ближайший сосед» и является одним из простейших алгоритмов классификации.

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

Пример: я хочу спрогнозировать вид помидора из вида похожих на него помидоров.

Чтобы классифицировать входы с использованием k-ближайших соседей, необходимо выполнить ряд действий:

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

Дерево решений

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

Вот пример:

Вы продолжаете разбивать пространство возможностей, пока не достигнете нижней части дерева. Каждый узел решения имеет две или более ветвей.Листья в приведенной выше модели содержат решение о том, подходит человек или нет.

Пример: у вас есть корзина с разными помидорами, и вы хотите выбрать правильный, чтобы улучшить свое блюдо.

Типы деревьев принятия решений

Существует два типа деревьев. Они основаны на характере целевой переменной:

• Дерево решений категориальной переменной.
• Дерево решений с непрерывной переменной.

Следовательно, деревья решений хорошо работают как с числовыми, так и с категориальными данными.Еще один плюс использования деревьев решений в том, что они не требуют небольшой подготовки данных.

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

Случайный лес

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

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

Узнайте больше о том, как работают случайные леса, в блоге Towards Data Science.

Машина опорных векторов

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

Гиперплоскость можно представить в виде линии (для двумерного пространства). Когда вы пересекаете трехмерное пространство, нам становится трудно визуализировать модель.

Точки данных, расположенные по разные стороны гиперплоскости, относятся к разным классам.

Пример: автоматическая система сортировки томатов по форме, весу и цвету.

Выбранная гиперплоскость напрямую влияет на точность результатов. Итак, мы ищем плоскость, которая имеет максимальное расстояние между точками данных обоих классов.

SVM показывают точные результаты с минимальной вычислительной мощностью, когда у вас много функций.

Подводя итоги

Как видите, машинное обучение может быть таким же простым, как сбор овощей в магазине. Но следует помнить о многих деталях, если вы не хотите все испортить. Следите за обновлениями нашего блога, Twitter и Medium, чтобы узнать больше о машинном обучении.

.