Лучшие метрики расстояния помимо Левенштейна для упорядоченных наборов слов и последующей кластеризации

Question

Я пытаюсь решить проблему, которая включает сравнение большого количества наборов слов, каждый из которых содержит большое, упорядоченное количество слов из набора слов (всего около 600+, очень высокая размерность!) Для сходства, а затем кластеризация их в отдельные группы. Решение должно быть как можно более без присмотра.

Данные выглядят как

[яблоко, банан, апельсин ...]
[Яблоко, банан, виноград ...]
[Желе, анис, апельсин ...]
[Клубника, банан, апельсин ...]
... и т.д.

Порядок слов в каждом наборе имеет значение ([Apple, Banana, Orange] отличается от [Apple, Orange, Banana]

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

Мои вопросы:

• Является ли Левенштейн наиболее подходящей метрикой расстояния для этой задачи?
• Является ли средняя / медоидная кластеризация прототипа лучшим способом для группировки?
• Я еще не особо задумывался над проверкой выбора 'k' в кластеризации. Будет ли оценка кривой кластеризации SSE лучшим способом для этого?
• Есть ли недостатки в моей методологии?
• В качестве дополнения к решению в будущем, учитывая данные обучения, у кого-нибудь может возникнуть идея о назначении вероятностей для кластерных назначений? Например, набор 1 имеет 80% вероятности оказаться в кластере 1 и т. Д.

Надеюсь, мои вопросы не кажутся слишком глупыми или ответы до боли очевидны, я относительно новичок в интеллектуальном анализе данных.

Спасибо!

Answer 1

Да, Левенштейн - очень подходящий способ сделать это. Но если последовательности сильно различаются по размеру, вам может быть лучше нормализовать эти расстояния путем деления на сумму длин последовательностей - в противном случае вы обнаружите, что наблюдаемые расстояния имеют тенденцию к увеличению для пар длинных последовательностей, чьи «среднее расстояние» (в смысле среднего расстояния между соответствующими подстроками длины k для некоторого малого k) является постоянным.

Пример. Можно сказать, что пара ([Apple, Banana], [Carrot, Banana]) имеет то же "среднее" расстояние, что и ([Apple, Banana, Widget, Xylophone], [Carrot, Banana, Yam, Xylophone]), поскольку каждый второй элемент соответствует обоим, но необработанное расстояние Левенштейна в последней паре будет в два раза больше.

Также имейте в виду, что Левенштейн не делает специальных поправок для «перемещений блоков» : если вы берете строку и перемещаете одну из ее подстрок на достаточное расстояние, то получающаяся пара (оригинальной и измененные строки) будет иметь ту же оценку Левенштейна, как если бы 2-я строка имела совершенно разные элементы в той позиции, куда была перемещена подстрока. Если вы хотите принять это во внимание, попробуйте вместо этого использовать расстояние на основе сжатия . (Хотя я и говорю, что это полезно для вычисления расстояний без учета порядка, оно, конечно, способствует упорядоченному сходству, а не беспорядочному подобию.)

Answer 2

Проверьте SimMetrics на sourceforge для платформы, поддерживающей различные метрики, которые можно использовать в качестве средства для оценки лучших для задачи.

для коммерчески действительной версии проверьте K-Similarity от K-Now.co.uk.