Не делайте лишнего

В реализации алгоритма k-средних основная операция — вычисление расстояния между двумя векторами ||a - c||. Очевидный способ это сделать, используя библиотеку MTJ

new SparseVector(vector).add(-1, centroid).norm(Vector.Norm.Two)

Увидев в профайлере, что на метод add() приходится около 90% всех вычислений, возникает естественное желание попытаться его ускорить. Как работает этот метод? Для этого нам надо понять, как вообще устроен SparseVector.

Для хранения разреженного вектора заводится два массива: массив индексов и массив значений.

index	12	15	86	87	90	125	234	235
value	1.42	1.2	0.01	0.43	1.23	2.41	2.55	0.143

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

Как можно складывать такие вектора? Самый очевидный способ (который и реализован в классе SparseVector) выглядит так:

public void add(int index, double value) {
 check(index);

 int i = getIndex(index);
 data[i] += value;
}

В getIndex() ищется место индекса в массиве и, при необходимости, создается место под новый. Его алгоритмическая сложность O(log(n)), где n длина вектора, к которому мы добавляем. При этом нельзя забывать о достаточно большой константе связанной с раздвижением массива. Соответственно, общая сложность получается O(m log(n)), где m длина вектора, который мы добавляем.

Конечно же, сразу хочется реализовать сложение векторов с помощью слияния двух массивов за O(m + n). Вот только для некоторых m и n такое слияние будет даже медленнее чем первый способ. Например, для n = 100 и m = 20 (самые обычные значения во многих задачах).

Как же нам улучшить производительность вычисления нормы разности векторов? Ответ прост, нам же совершенно не нужно вычислять разность векторов, это лишняя операция. Надо лишь на каждом шаге алгоритма слияния массивов вычислять очередное слагаемое нормы. Так мы избавляемся от затратной операции записи в массив и лишней операции чтения. После такой оптимизации скорость работы выросла в 3-4 раза.

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

Документы-вектора можно представить несколькими способами, выбрав разные значения в качестве их элементов:

1. 0 или 1, в зависимости от наличия слова в документе
2. Число слов в документе
3. TF*IDF данного слова

Как правило для документов с малым числом слов (или же просто с набором атрибутов) лучше подходят первые два способа, а для более-менее больших документов на естественном языке TF*IDF.

Полученную сильно разреженную матрицу надо не только хранить в памяти, но и иметь возможность эффективно выполнять разные операции над ними. Библиотек для работы со sparse matrices на Java не так много, а самое плохое, что я не нашел никаких benchmarks. Достаточно удобной в использовании мне показалась Matrix Toolkits for Java.

Радикально ускорить алгоритм можно с помощью уменьшения словаря, убрав из него слова мало влияющие на результат. Как правило, достаточно всего 20-30% слов, чтобы алгоритм работал с практически такой же точностью. Один из самых простых cпособов уменьшения словаря состоит в том, чтобы выбирать слова с наибольшей функцией качества:
n — число всех документов
fi — частота встречаемости слова в i-ом документе.

Существует некий порог размера словаря, начиная с которого алгоритм k-средних начинает работать очень плохо. Обычно он лежит как раз в диапазоне 20-30%. Нужный размер проще всего подобрать экспериментальным путем.

Метод k-средних для обучения классификаторов Байеса

Алгоритм k-средних (k-means clustering) — очень быстрый, простой и достаточно точный метод кластеризации объектов. Идея заключается в минимизации суммарного отклонения по каждому кластеру:
Здесь, Si — k кластеров, μi — центроид i-го кластера. На каждой итерации алгоритма мы перемещаем каждый вектор в кластер с ближайшим центроидом. Хотя не существует каких-либо оценок сложности алгоритма, на практике хватает он сходится за достаточно малое число итераций.

У метода k-средних есть два серьезных недостатка:

1. Необходимо заранее знать точное число кластеров.
   
2. Качество результата сильно зависит от выбора начального разбиения.

Поэтому, обычно, сначала применяют какой-либо другой метод кластеризации (например, Principal Direction Divisive Partitioning) для определения числа кластеров и получения начального разбиения.

Что будет если применить метод k-средних к задаче обучения классификаторов Байеса на некачественных данных? Действительно, ведь у нас уже есть готовы набор категорий-кластеров и начальное разбиение по ним. Я провел простой эксперимент. Тестовый набор включал в себя три категории документов, условно их можно назвать "Information Retrieval" (С₁), "Java" (C₂) и "HTML" (C₃). Сами документы представляют собой короткие (несколько предложений) отрывки из статей в Википедии. Обучающую выборку я составил следующим образом: к каждой категории были отнесены 100 документов из нее самой и по 15 документов из двух других. После чего я применил Байеса ко всем 390 документам: 62 из них были классифицированны неправильно. Алгоритм k-средних разложил документы в обучающей выборке следующим образом:

C₁ = 129 * C₁ + 2 * C₂
C₂ = 1 * C₁ + 127 * C₂ + 4 * C₃
C₃ = 1 * C₂ + 126 * C₃

Заново обученный Байес ошибся уже всего в 5 случаях!

Байес для сужения области поиска

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

Если копнуть чуть глубже, с помощью такого метода можно превратить линейную зависимость скорости работы самого Байеса от числа категорий в логарифмическую. Для этого надо построить классификатор похожий на decision tree, в котором решение в узлах будет приниматься с помощью Байеса. Формула для расчета вероятностей в таком классификаторе остается точно такой же, мы просто подставляем туда другие данные. Если объект принадлежит какой-либо категории, то он принадлежит и всем ее родителям, соответственно, слово описывающее объект также принадлежит всем родителям категории. При этом вероятность для каждого слова в категории надо считать относительно "братьев" этой категории, а не всех категорий сразу.

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

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

РОМИП'2006

19-го октября в Суздале пройдет четвертый РОМИП. Тем временем, на сайте семинара уже доступны труды участников. Приятного чтения!

Обучение классификатора на некачественных данных

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

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

1. Неточная или неправильная классификация сущностей по категориям.
2. Само дерево категорий может недостаточно точно и/или избыточно отражать реальный мир.

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

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

Если же у нас не очень много данных (или очень много свободного времени), их можно вообще классифицировать вручную. Не очень много это, действительно, не очень много, у меня не получалось заставить себя обработать больше двух тысяч записей. Соответственно, для больших массивов нам нужно попытаться сделать некоторую выборку таким образом, чтобы в нее попало как можно большее число плохих записей. Использовать в качестве критерия "нехорошести" итоговую вероятность не получится, как большие, так и маленькие ее значения в данном случае очень мало говорят о качестве результата классификации. Гораздо лучшей выборкой оказываются те записи, для которых полученная категория отличается от исходной. На практике, размер такой выборки может быть от 1 до 10 процентов от общего числа обучающих записей. Что же она поможет нам узнать:

1. Если классификатор сработал правильно, можно предположить, что большая часть подобных записей уже лежит в правильной категории. Для слов из этой записи можно немного повысить вес, пометить ее как "подтвержденную".
2. Если же классификатор выдал неправильный результат, как правило, это означает обратное: значительной части похожих записей присвоена неправильная категория. Чтобы как можно быстрее вытащить их на белый свет, стоит повысить вес для слов гораздо сильнее, чем в предыдущем случае. На практике, хороший результат достигался умножением на 25.

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

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

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

Поправки к прошлому посту

Степа указал мне на две мои ошибки в прошлом посте:

1. Не нужно делать специальный класс обертку над String, можно использовать метод intern(), который как раз и вернет нужную нам строку-синглтон.
2. Оказывается результат работы hashCode() у класса String кэшируется. Это, кстати, объясняет почему прирост производительности получился таким маленьким. Я ожидал на порядок больше.

HashMap со строковыми ключами

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

public double calculateProbability(String[] tokens) {
   double probability = this.probability;
   for (String token : tokens) {
       Double partProbability = words.get(token);
       if (partProbability != null) {
           probability *= partProbability;
       } else {
           probability *= LOW_PROBABILITY;
       }
   }
   return probability;
}

В данном случае words это HashMap<String, Double>, вероятности для каждого слова в данной категории. Получение элемента по ключу в HashMap работает быстро, за константное время.

Если прогнать классификатор под профайлером, то основное время придется как раз на вызов метода get(). Как он работает: для ключа вычисляется его хэш-код, по этому хэшу достается список пар ключ-значение, который последовательно проходится в поисках ключа равного данному. Как можно ускорить работу hashCode() и equals() для класса String? Ответ прост! Надо заменить их на Object.hashCode() и Object.equals() (что эквивалентно ==). Для этого нужно всего лишь вместо объектов String хранить в words обертку-синглтон над String и передавать в calculateProbability() массив таких оберток вместо String[]. Это простое решение дает прирост производительности примерно на 100%.

Классификация по Байесу

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

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

W — слово, C — категория
count(C, W) — количество слов W в описаниях книг из категории C
count(C, books) — количество книг в категории C

Нормализация по числу книг нужна, чтобы не терять в общей массе маленькие категории с большой встречаемостью слова. Например, в категории C1 "Тракторы в поэзии 20-го века" есть 30 книг, в описаниях которых слово "трактор" встречается 60 раз. А в категории C2 "Спецтехника", соответственно, 6000 книг и 1000 раз встречается слово "трактор". Таким образом, без нормализации:

P(C1, "трактор") = 60 / (1000 + 60) ~ 0.056
P(C2, "трактор") = 1000 / (1000 + 60) ~ 0.944

Что однозначно относит слово "трактор" в категорию С2. Если использовать нормализацию, мы получаем:

P(C1, "трактор") ~ 0.925
P(C2, "трактор") ~ 0.075

Эти числа уже гораздо ближе к жизни.

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

Здесь P(C) это априорная вероятность встречаемости категории C, которая равна отношению числа книг в C к общему числу книг. С помощью этого множителя мы учитываем, что книги о "Спецтехнике" встречаются гораздо чаще, чем "Тракторы в поэзии". Необходимо отметить, что P(C|word) может быть нулем, если слово не встретилось в категории ни одного раза, в таком случае обычно подставляют в формулу какое-либо маленькое значение.

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