Расстояния NaN в евклидовой реализации Mahout

Мы используем класс EuclideanDistanceSimilarity для вычисления сходства набора элементов с помощью Hadoop.

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

Я думаю, что отследил это до этой строки в классе EuclideanDistanceSimilarity:

double euclideanDistance = Math.sqrt(normA - 2 * dots + normB);

Значение, передаваемое sqrt, иногда бывает отрицательным, и в этом случае возвращается NaN. Я полагаю, что, возможно, где-то там должен быть Math.abs, но моя математика недостаточно сильна, чтобы понять, как были перестроены евклидовы вычисления, поэтому не уверен, каков будет эффект.

Может ли кто-нибудь объяснить математику лучше и подтвердить,

double euclideanDistance = Math.sqrt(Math.abs(normA - 2 * dots + normB));

было бы приемлемым решением?


hadoop euclidean-distance mahout
person Tom Martin    schedule 26.10.2012    source источник
comment
Интересная реализация, обычно евклидово сходство похоже на (1-sqrt(sum((vector2-vector1)^2))   -  person Thomas Jungblut    schedule 26.10.2012
comment
Где в коде встречается эта строка?   -  person Fred Foo    schedule 26.10.2012
comment
@ThomasJungblut Да, я не совсем понимаю, наверное, это потому, что расчет был распространен. Я могу сказать вам, что в этом случае норма А и норма В представляют собой сумму квадратов каждого вектора, а точки, возможно, являются суммой скалярного произведения, но я не уверен.   -  person Tom Martin    schedule 26.10.2012
comment
@larsmans В SimiliarityReducer он вызывает similarity.similarity. Эта строка находится в EuclideanDistanceSimilarity, который является одним из VectorSimilarityMeasures, который можно подключить через конфигурацию задания Hadoop.   -  person Tom Martin    schedule 26.10.2012

Ответы (1)


arrow_upward
5
arrow_downward

Код находится в org.apache.mahout.math.hadoop.similarity.cooccurrence.measures. EuclideanDistanceSimilarity.

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

Идентификация довольно проста. Пусть C = A - B и пусть a, b и c - длины соответствующих векторов. Нам нужно с. По закону косинусов c2 = a2 + b2 - 2abcos() и ab cos() — это просто значение скалярного произведения. Обратите внимание, что normA в коде на самом деле является квадратом нормы (длины) - действительно должно было быть лучше названо.

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

double euclideanDistance = Math.sqrt(Math.max(0.0, normA - 2 * dots + normB));

Его просто нужно ограничить до 0. Я могу это зафиксировать.

person Sean Owen    schedule 26.10.2012
comment
К вашему сведению, я попробовал это с исправленной версией EuclideanDistanceSimilarity, и, похоже, это помогло. Спасибо, Шон. - person Tom Martin; 30.10.2012