Предпосылки.
Проходя курсы и изучая материалы по машинному обучению и обработке натуральных языков я конечно же неоднократно сталкивался с задачами в которых нужно было применять классификаторы. Самым простым случаем классификатора, который мне попался, был пример из лекции про Sentiment Analysis с помощью которого решалась задача бинарной классификации текса (позитивный или негатиыный). Я выполнил это задание, чему-то научился, но мне этого было мало, и я набросал прототип и поставил пару эксперементов с использованием мультиклассового Naive Bayes классификатора. В этой статье я хочу описать то, что и как получилось.
Пишу в основном, чтобы не забыть. Этот материал уже слегка устарел для меня, так как я переехал в своих эксперементах на другие классификаторы (преимущественно на support vector machine), но будет полезно задокументировать, потому что окончательно забудется.
Внимание! Весь код в статье ни капли не причесанный и кое-где вообще stupid steps, это остатки от разных правок и эксперементов, так что критика неуместна. (Кроме основной логики, если кто то сюда случайно забредет и найдет ошибку, буду благодарен за подсказку).
Нужно подготовить данные и написать программу для обучения на этих данных. То есть реализовать алгоритм машинного обучения с учителем. За основу взят наивный веройтностный алгоритм в англоязычной лиетратуре называемый naive bayes classifier. Почему именно этот алгоритм? Потому что он наиболее прост и понятен. А в условиях реального продакшна может оказаться эффективнее других ввиду легкой операции classify (правильнее будет сказать, с относительно невысокой сложностью алгоритма или линейной Big-O нотацией). Предметная область - анализ текстов. Нужно научить программу определять жанр текста. Как и в большинтсве решений с машинным обучением алгоритм работает в два этапа: train и classify. Рассмотрим реализацию прототипа.
На этапе обучения нужны данные, причем от их качества зависит эффектвность работы классификатора. В данном случае нам нужны тексты отсотрированные по жанрам (пока речь идет о любых отличимых жанрах). В компьютерной лингвистике тексты используемые для обучения принто называть корпусами. В качестве корпусов на стадии разработки я взял материалы с компакт диска "библиотека в кармане", который был весьма популярен среди любителей читать в электронке в эпоху, когда широкополосного интернета под рукой небыло. Исходные корпуса были в виде отдельных файлов разложенных по папкам с названием жанра.
Как мы видим, данные не сбалансированны по объему, однако алгоритм будет учитывать это, так как это аналогично реальной жизни.
Так как на этапе разработки желательно чтобы алгоритм быстренько пробегал, для разработки взяты 4 жанра. Выглядят папки так:
Проходя курсы и изучая материалы по машинному обучению и обработке натуральных языков я конечно же неоднократно сталкивался с задачами в которых нужно было применять классификаторы. Самым простым случаем классификатора, который мне попался, был пример из лекции про Sentiment Analysis с помощью которого решалась задача бинарной классификации текса (позитивный или негатиыный). Я выполнил это задание, чему-то научился, но мне этого было мало, и я набросал прототип и поставил пару эксперементов с использованием мультиклассового Naive Bayes классификатора. В этой статье я хочу описать то, что и как получилось.
Пишу в основном, чтобы не забыть. Этот материал уже слегка устарел для меня, так как я переехал в своих эксперементах на другие классификаторы (преимущественно на support vector machine), но будет полезно задокументировать, потому что окончательно забудется.
Внимание! Весь код в статье ни капли не причесанный и кое-где вообще stupid steps, это остатки от разных правок и эксперементов, так что критика неуместна. (Кроме основной логики, если кто то сюда случайно забредет и найдет ошибку, буду благодарен за подсказку).
Постановка задачи.
Нужно подготовить данные и написать программу для обучения на этих данных. То есть реализовать алгоритм машинного обучения с учителем. За основу взят наивный веройтностный алгоритм в англоязычной лиетратуре называемый naive bayes classifier. Почему именно этот алгоритм? Потому что он наиболее прост и понятен. А в условиях реального продакшна может оказаться эффективнее других ввиду легкой операции classify (правильнее будет сказать, с относительно невысокой сложностью алгоритма или линейной Big-O нотацией). Предметная область - анализ текстов. Нужно научить программу определять жанр текста. Как и в большинтсве решений с машинным обучением алгоритм работает в два этапа: train и classify. Рассмотрим реализацию прототипа.
Train
На этапе обучения нужны данные, причем от их качества зависит эффектвность работы классификатора. В данном случае нам нужны тексты отсотрированные по жанрам (пока речь идет о любых отличимых жанрах). В компьютерной лингвистике тексты используемые для обучения принто называть корпусами. В качестве корпусов на стадии разработки я взял материалы с компакт диска "библиотека в кармане", который был весьма популярен среди любителей читать в электронке в эпоху, когда широкополосного интернета под рукой небыло. Исходные корпуса были в виде отдельных файлов разложенных по папкам с названием жанра.
oleksandr@ulabs:~/repos/K-R/Classification/local_data/all_genres/data$ du -s * 11424 ADVENTUR 4452 DETECT 11420 DOCUMENT 16908 DRAMA 14176 FANTAST 10268 JOURNAL 3868 PHYLOS 8564 RELIGION 3496 SONGS 4536 TALES 2516 TEACHER
Как мы видим, данные не сбалансированны по объему, однако алгоритм будет учитывать это, так как это аналогично реальной жизни.
Так как на этапе разработки желательно чтобы алгоритм быстренько пробегал, для разработки взяты 4 жанра. Выглядят папки так:
oleksandr@ulabs:~/repos/K-R/Classification/corpuses/genres_data_eng$ du -s * 14824 ADVENTUR 13008 DOCUMENT 20372 DRAMA 16976 FANTAST
Названия папок принимаем как название жанров, их содержимое - как корпуса для обучения. Код для train этапа следующий:
def learn(self, genre, words): if genre not in self.genres: self.genres[genre] = 0 self.genres[genre] += len(words) for word in words: if not word in self.vocabulary: self.vocabulary[word] = {} if not genre in self.vocabulary[word]: self.vocabulary[word][genre] = 1 else: self.vocabulary[word][genre] += 1
Вообще то принято этот метод называть train, но по скольку это не существенно, пойдем дальше.
По сути тут мы запоминаем частоты слов для разных жанров, а так же общее количество слов использованных в обучении для каждого из жанров (для последующей нормализации, которая и позволяет не обращать внимание на объемы корпусов различных жанров).
На этапе классификации код выглядит так:
Стоит обратить внимание на следующие моменты. Все вероятности вычисляются в логарифмической форме. Она и более читабельная, и к тому же влечет за собой меньшую погрешность вычислений (скорее всего, не уверен...). Так же важно учитывать сглаживание. Пименен самый простой метод Лапласа.
Общий код классификатора:
Теперь немного о клиентском коде для этого классификатора, который я использовал для эксперементов.
Задачи клиентского кода:
Итак. Имеется полноценный код.
Попробуем проанализировать что получилось на тестовых данных.
Немного о тестовых данных. Получены они таким образом. Из изначальных данных для обучения изьято примерно 10% данных и они в обучении не участвуют. После полноценного обучения на оставшихся данных мы собственно и меряем эффектиыность классификатора.
Результаты измерения таковы:
RESULT:
53
6
0.898305084746
Их смысл следующий. Было правильно классифицированно 53 файла (они примерно сбалансированны по размеру), неправильно 6, и эффективность классфификатора характеризуется циферкой 89.8 % правильного распознавания. Выглядит достаточно круто для примитивного классификатора, и, признаюсь, удачные данные попались. Положа руку на сердце, в общем случае чаще сталкиваешься показателями с 54% или 62%. Но и эти результаты получены без читов. Так что классификатор может реально эффективно работать.
Внимание! это есть не совсем правильно измеренные показатели, в норме нужно использовать канонические Recall, Precision и прочие...
В продакшине применять такого типа классификатор вполне можно, особенно если это веб сервис, так как на стадии классификации алгоритм имеет сложность O(N) (N это кол-во слов в классифицируемом тексте).
При необходимости получить более качественный классификатор стоит рассматривать SVM, я продолжаю с ним эксперементировать, но об этом, возможно, в другой раз.
Еще хотел бы сказать, что проверил аглоритм на реальных данных взятых из продакшна. В момент написания кода я работал в компании grammarly, и у меня имелся доступ к реальным данным. Результат на них конечно получился заметно ниже, ввиду их невысокого качества (специально собранных данных небыло и пришлось косвенно выделять их из кэша на продакшн сервере), но тоже вполне эффективно отрабатывал алгоритм.
Меня несколько вдохновило то, что это был мой первый (и пока единственный) успешный опыт использования MapReduce и Hadoop, так как локально провести перпроцессинг данных оказалось затруднительно ввиду их относительно большого объема, скрипт который я пытался запусткать для перпроцесссинга локалььно собирался выполняться 6 дней, я его запустил на выполнение и сел писать hadoop реализацию. Написал быстрее, чем пробежал мой скрипт. Поэтому у меня теперь есть хоть и маленткий, но опыт использования Map Reduce.
По сути тут мы запоминаем частоты слов для разных жанров, а так же общее количество слов использованных в обучении для каждого из жанров (для последующей нормализации, которая и позволяет не обращать внимание на объемы корпусов различных жанров).
Classify
На этапе классификации код выглядит так:
def classify(self, words): result = {} for g in self.genres: result[g] = 0 #print result #print len(self.vocabulary) for word in words: if word in self.vocabulary: for genre in self.genres: if genre in self.vocabulary[word]: k = (self.vocabulary[word][genre] + 1.0) / (self.genres[genre] + len(self.vocabulary)) result[genre] += math.log(k) else: result[genre] += math.log(1.0 / (self.genres[genre] + len(self.vocabulary))) else: for genre in self.genres: result[genre] += math.log(1.0 / (self.genres[genre] + len(self.vocabulary))) sigma = 0 for g in self.genres: sigma += self.genres[g] for g in self.genres: result[g] += math.log(self.genres[g]/float(sigma)) # print result return result
Стоит обратить внимание на следующие моменты. Все вероятности вычисляются в логарифмической форме. Она и более читабельная, и к тому же влечет за собой меньшую погрешность вычислений (скорее всего, не уверен...). Так же важно учитывать сглаживание. Пименен самый простой метод Лапласа.
Classifier as is
Далее я добавил ряд вспомогательных вещей таких как- разбиение на слова по регулярному выражению (к слову, тут нужно было бы использовать качественный токенизатор, а еще лучше приводить все словоформы к леммам, но для прототипа это не очень нужно)
- Умение сериализовать и десериализовать результаты обучения (чтобы не обучать каждый раз). Тут нужно сказать, что прототип не делает ряда важных вещей. Не фильтрует Stop Words. Не фильтрует слова с низкой входимостью. И то и другое потенцильно снижает качество работы классификатора и производительность. Однако, опять же, простим это лаботарорному прототипу.
- Возможность не только получить окончательное решение о принадлежности к какому-то классу, но и получить значения вероятностей по принадлежности к каждому из классов (жанров).
Общий код классификатора:
__author__ = 'Oleksandr Korobov' import string import sys import json import re import math class Classifier: def __init__(self): self.genres = {} self.vocabulary = {} self.__load_learnt_data() def learn(self, genre, words): if genre not in self.genres: self.genres[genre] = 0 self.genres[genre] += len(words) for word in words: if not word in self.vocabulary: self.vocabulary[word] = {} if not genre in self.vocabulary[word]: self.vocabulary[word][genre] = 1 else: self.vocabulary[word][genre] += 1 def classify(self, evaluated_text): words = self.do_pre_processing(evaluated_text) result = {} for g in self.genres: result[g] = 0 for word in words: if word in self.vocabulary: for genre in self.genres: if genre in self.vocabulary[word]: k = (self.vocabulary[word][genre] + 1.0) / (self.genres[genre] + len(self.vocabulary)) result[genre] += math.log(k) else: result[genre] += math.log(1.0 / (self.genres[genre] + len(self.vocabulary))) else: for genre in self.genres: result[genre] += math.log(1.0 / (self.genres[genre] + len(self.vocabulary))) sigma = 0 for g in self.genres: sigma += self.genres[g] for g in self.genres: result[g] += math.log(self.genres[g]/float(sigma)) # print result return result def remember(self): g = json.dumps(self.genres) v = json.dumps(self.vocabulary) #print g, v gnr = open('./genre.dat', 'w') vcb = open('./vocabulary.dat', 'w') #print os.system('ls') gnr.write(g) vcb.write(v) gnr.close() vcb.close() print "saved..." def __load_learnt_data(self): try: g = open('./genre.dat', 'r').read() v = open('./vocabulary.dat', 'r').read() self.genres = json.loads(g) self.vocabulary = json.loads(v) except: pass finally: pass def is_already_trained(self): return len(self.genres) > 0 and len(self.vocabulary) > 0 def isAscii(self, s): for c in s: if c not in string.ascii_letters: return False return True def do_pre_processing(self, text): return filter( lambda w: 20 > len(w) > 1 and self.isAscii(w), re.split( '[\n!?/\\\(\).,` :;\-\[\]\'_"0-9@#$%\^&\*\t]' , text)) def document_class(self, doc): genres_values = self.classify(doc) decision_value = -sys.float_info.max decision = '' for r in genres_values: if genres_values[r] > decision_value: decision_value = genres_values[r] decision = str(r) return decision
Теперь немного о клиентском коде для этого классификатора, который я использовал для эксперементов.
Client
Задачи клиентского кода:
- Инстанцировать классификатор
- Провести обучение (или дообучение) на основе имеющихся корпусов (тут делаем работу с файловой системой и т.п.)
- Поробовать определить жанр какого-то случайного текста
- При желании сделать некоторые метрики. Должен отметить, что существуют академически верные метрики для определения качества классификатора, но в данном коде метрики примитивны, хотя и легко могут быть приведены к каноническим требованиям.
__author__ = 'Oleksandr Korobov' import os import re import string import sys from classifier import Classifier from measurement import MeasureClassifier classify = Classifier() def process_genres(path): genres = os.listdir(path) print "Found genres:", genres for genre in genres: files = os.listdir(os.path.join(path, genre)) #print files for file in files: words = classify.do_pre_processing(open(os.path.join(path, genre, file)).read().lower()) classify.learn(genre, words) import argparse parser = argparse.ArgumentParser(description='Genre classifier') parser.add_argument('--path', help='Folder to load genres learning data from') args = parser.parse_args() path = args.path if not classify.is_already_trained(): if path is None: print """ Please specify root with genres folder""" else: process_genres(path) print classify.genres else: print 'using loaded data' test_text = open('../test_data/test_fan.txt').read() #test_text = 'he has kill her. she was in love' #test_text = 'it was the best trip in my life. a lot of new countries apes parrots following' print classify.document_class(test_text.lower()) classify.remember() # measurement script evaluate_data_path = path + '_measure' print evaluate_data_path measure = MeasureClassifier(evaluate_data_path, classify) measure.evaluate()
Metrics and measurements
Код дополнительного класса для получения метрик:import os import sys __author__ = 'oleksandr' class MeasureClassifier: def __init__(self, test_data_path, classifier): self.classifier = classifier self.test_data_path = test_data_path if not os.path.exists(test_data_path): print "couldn't find test data" return test_genres = os.listdir(test_data_path) self.test_data = {} for test_genre in test_genres: self.test_data[test_genre] = map( lambda name: os.path.normpath(test_data_path + '/' + test_genre + '/' + name), os.listdir(os.path.normpath(test_data_path + '/' + test_genre))) def evaluate(self): trues = 0 falses = 0 for test_genre in self.test_data: for doc in self.test_data[test_genre]: result = self.classifier.document_class(open(doc).read()).upper() print result == test_genre.upper(), result, test_genre.upper() if result == test_genre.upper(): trues += 1 else: falses += 1 print 'RESULT:', trues, falses, trues/float(trues+falses)
Итак. Имеется полноценный код.
Попробуем проанализировать что получилось на тестовых данных.
Test Run
Вот, собственно результат выполнения тестового кода:/usr/bin/python2.7 /home/oleksandr/repos/K-R/Classification/naive_classifier/test.py --path /home/oleksandr/repos/K-R/Classification/local_data/for_metrics/data
Found genres: ['ADVENTUR', 'DRAMA', 'FANTAST', 'DOCUMENT']
{'DRAMA': 3536700, 'DOCUMENT': 1810141, 'ADVENTUR': 2583094, 'FANTAST': 2702071}
FANTAST
saved...
/home/oleksandr/repos/K-R/Classification/local_data/for_metrics/data_measure
True DRAMA DRAMA
True DRAMA DRAMA
False ADVENTUR DRAMA
True DRAMA DRAMA
True DRAMA DRAMA
True DRAMA DRAMA
False ADVENTUR DRAMA
True DRAMA DRAMA
True DRAMA DRAMA
True DRAMA DRAMA
False ADVENTUR DRAMA
True DRAMA DRAMA
True DRAMA DRAMA
True DRAMA DRAMA
True DOCUMENT DOCUMENT
False FANTAST DOCUMENT
True DOCUMENT DOCUMENT
True DOCUMENT DOCUMENT
True DOCUMENT DOCUMENT
True DOCUMENT DOCUMENT
True DOCUMENT DOCUMENT
True DOCUMENT DOCUMENT
True DOCUMENT DOCUMENT
False FANTAST DOCUMENT
True DOCUMENT DOCUMENT
True DOCUMENT DOCUMENT
True DOCUMENT DOCUMENT
True DOCUMENT DOCUMENT
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True ADVENTUR ADVENTUR
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
False ADVENTUR FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
True FANTAST FANTAST
RESULT: 53 6 0.898305084746
Process finished with exit code 0
Немного о тестовых данных. Получены они таким образом. Из изначальных данных для обучения изьято примерно 10% данных и они в обучении не участвуют. После полноценного обучения на оставшихся данных мы собственно и меряем эффектиыность классификатора.
Результаты измерения таковы:
RESULT:
53
6
0.898305084746
Их смысл следующий. Было правильно классифицированно 53 файла (они примерно сбалансированны по размеру), неправильно 6, и эффективность классфификатора характеризуется циферкой 89.8 % правильного распознавания. Выглядит достаточно круто для примитивного классификатора, и, признаюсь, удачные данные попались. Положа руку на сердце, в общем случае чаще сталкиваешься показателями с 54% или 62%. Но и эти результаты получены без читов. Так что классификатор может реально эффективно работать.
Внимание! это есть не совсем правильно измеренные показатели, в норме нужно использовать канонические Recall, Precision и прочие...
В продакшине применять такого типа классификатор вполне можно, особенно если это веб сервис, так как на стадии классификации алгоритм имеет сложность O(N) (N это кол-во слов в классифицируемом тексте).
При необходимости получить более качественный классификатор стоит рассматривать SVM, я продолжаю с ним эксперементировать, но об этом, возможно, в другой раз.
Еще хотел бы сказать, что проверил аглоритм на реальных данных взятых из продакшна. В момент написания кода я работал в компании grammarly, и у меня имелся доступ к реальным данным. Результат на них конечно получился заметно ниже, ввиду их невысокого качества (специально собранных данных небыло и пришлось косвенно выделять их из кэша на продакшн сервере), но тоже вполне эффективно отрабатывал алгоритм.
Меня несколько вдохновило то, что это был мой первый (и пока единственный) успешный опыт использования MapReduce и Hadoop, так как локально провести перпроцессинг данных оказалось затруднительно ввиду их относительно большого объема, скрипт который я пытался запусткать для перпроцесссинга локалььно собирался выполняться 6 дней, я его запустил на выполнение и сел писать hadoop реализацию. Написал быстрее, чем пробежал мой скрипт. Поэтому у меня теперь есть хоть и маленткий, но опыт использования Map Reduce.
Комментариев нет:
Отправить комментарий