Метрика Javascript Clusterfck

Итак, я перевожу старую визуализацию данных на новую платформу, и я немного застрял в их функции сортировки сообщества. В исходном коде похоже, что автор использует агломеративную кластеризацию с калькулятором косинусного сходства. Я решил, что лучший способ приблизиться к этому в Javascript — создать дерево с clusterfck, используя мою пользовательскую функцию подобия косинуса в качестве метрики. Дерево сортирует ПОЧТИ правильно для каждого набора данных, которые я передаю. (Но из-за спецификаций проекта «почти» недостаточно). Я проверил свой алгоритм, и все выглядит правильно, но когда я сравниваю свои результаты, используя косинусное сходство и евклидово расстояние, я получаю тот же результат сортировки.

Что может быть причиной этого? Я думаю, что могу передать что-то неправильно, и clusterfck передает евклидов по умолчанию. Ниже приведен кусок моего кода. Кто-нибудь может проверить? (Кроме того, есть ли более простой способ вычисления косинусного сходства? Я не думаю, что в JS есть встроенный скалярный продукт).

clusters = clusterfck.hcluster(relationArray, clusterfck.cosSim2, clusterfck.SINGLE_LINKAGE);
postOrder(clusters);
function postOrder(t) {
i++;
if (t == null) {
    return;
} else {
    postOrder(t.left);
    postOrder(t.right);
    if (t.left == null && t.right == null) {
        communityArr.push(t.canonical[0]);
    } else {
        return;
    }
}
}

function cosSim2(arr1, arr2) {
var d1 = 0,
    d2 = 0,
    cos = 0;
for(var i = 0; i < arr1.length; i++) {
    d1 += Math.pow(arr1[i], 2);
}

for(var j = 0; j < arr2.length; j++) {
    d2 += Math.pow(arr2[j], 2);
}

d1 = Math.sqrt(d1);
d2 = Math.sqrt(d2);

for(var j = 0; j < arr2.length; j++) {
    if (arr1[j] == null) {
        cos += 0;
    } else {
        cos += arr1[j] * arr2[j];
    }
}
var cosSimilarity = cos / (d1 * d2);
return cosSimilarity;
}

javascript trigonometry euclidean-distance similarity
person 1080p    schedule 25.07.2012    source источник
comment
Не совсем ответ, но могу я спросить вас, как работает ваш алгоритм cosSim? Я прочитал о косинусном сходстве, и это звучит как то, что мне нужно, но я еще не уверен, как его использовать. Мой текущий алгоритм сравнения текста слишком медленный, и я не могу его ускорить, если не разобью его на разные части, которые все можно оптимизировать.   -  person Fabdrol    schedule 07.12.2012

Ответы (1)


arrow_upward
3
arrow_downward

Я полагаю, что этот ответ слишком запоздал для вас. Но на случай, если кто-то еще наткнется на это:

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

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

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

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

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

function cosDist(arr1, arr2) {
    return 1 - cosSim2(arr1, arr2);
}

Эта новая функция cosDist имеет значения от 0 до 2, одинаковые векторы будут иметь расстояние 0 (как и ожидалось), а самые удаленные (т.е. непохожие) будут иметь расстояние 2.

И еще одно примечание: статья в Википедии http://en.wikipedia.org/wiki/Cosine_similarity указывает, что этот cosDist не является правильной метрикой расстояния в математическом смысле (неравенство треугольника здесь обычно не выполняется), но, исходя из моего опыта, на практике это не проблема при использовании этой функции для иерархической кластеризации. И так часто используется. Тем не менее, есть способ получить настоящую метрику расстояния из косинуса, также упомянутый в той же статье Википедии: ="Угловое расстояние и сходство">https://en.wikipedia.org/wiki/Cosine_similarity#Angular_distance_and_similarity

person holg3r    schedule 11.12.2013