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

В реализации алгоритма 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 результатов с наибольшей вероятностью, среди которых уже ищем окончательный ответ.

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

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

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

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%.