Как правильно разделить слова по группам?

Question

[xmoonlight]

В тесте нужно алгоритмически показать: Как именно можно создать 3 кластера похожих по написанию слов из следующего ниже списка слов:
1. ком
2. лом
3. ром
4. сок
5. сом
6. сор
7. соль
8. лось

При том, что "вес" каждого слова до кластеризации должен быть уникальным.
-----
PS: без использования готовых библиотек и встроенных функций языка программирования, если ответ будет представлен в виде кода.

Comments

[Роман]

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

[xmoonlight]

Роман, не уверен, что Левенштейн хорошо справится с короткими, почти одинаковыми словами.
Но, я гляну. Спасибо за подсказку!

[Роман]

xmoonlight, я на самом деле далеко не великий специалист в данном вопросе, и даже возможно что совершенно неправильно понял суть вопроса. Просто предложу вариант как его вижу я:

1. Создаем матрицы признаков для каждого из слов, Для этих целей можно использовать различные подходы. Но мне пока приходит на ум расстояния между слов, рассчитанные разными методами, например такими как (взяты из npm пакета natural):
- Hamming distance
- Jaro–Winkler
- Levenshtein
- Dice's co-efficient
2. Используем методы кластерного анализа для определения устойчивых групп на основе собранных матриц признаков. (вот такую реализацию нашел https://github.com/typeetfunc/claster_analysis, навскидку должна подойти)

Что по поводу сторонних библиотек, то просто посмотреть в них реализацию методов, может появятся мысли как сделать их так сказать лайтверсию.

[xmoonlight]

Роман, крайне грамотный подход!
Добавь в ответ!

[Роман]

xmoonlight, да бог с ним, с ответом. На самом деле я не гонюсь за рейтингом, а просто иногда убиваю тут время.

[xmoonlight]

Роман, Посмотрел это:

вот такую реализацию нашел https://github.com/typeetfunc/claster_analysis, навскидку должна подойти

вообще ничего не нашёл тут.

[Роман]

xmoonlight, извиняюсь, не ту ссылку кинул.
https://github.com/mljs/kmeans

k-means

Что он делает? K-means создает k количество групп из набора объектов таким образом, чтобы члены этой группы были больше похожи. Это популярный метод кластерного анализа для изучения набора данных.

Погодите, что такое кластерный анализ? Кластерный анализ — это семейство алгоритмов, предназначенных для формирования групп, где члены этих групп похожи друг на друга сильнее, чем на тех, кто в этой группе не состоит. Кластеры и группы являются синонимами в мире кластерного анализа.

А можно пример? Ну конечно. Предположим, у нас есть набор данных пациентов. В кластерном анализе они называются признаками. О каждом из пациентов нам известны различные факты: возраст, пульс, кровяное давление, уровень холестерина, и т.д. Это вектор характеристик, представляющий пациента.

Смотрите:

О векторе характеристик можно думать, как о списке известных нам чисел, связанных с пациентом. Этот список также может быть интерпретирован как координаты в многомерном пространстве. Пульс может быть одним измерением, кровяное давление — другим и так далее.

Вы, наверное, задаетесь вопросом:

Учитывая этот набор векторов, как же мы сгруппируем вместе пациентов, близких по возрасту, с похожими значениями пульса, кровяного давления и т.д.?

Хотите узнать лучшее свойство k-means?

Вы лишь задаете количество нужных вам кластеров. K-means заботится обо всем остальном.

Как же k-means заботится обо всем остальном? У k-means есть много вариаций для оптимизации определенных типов данных.

Не вдаваясь в подробности, это происходит примерно так:

k-means выбирает точки в многомерном пространстве для каждого из k кластеров. Их называют центроидами.
Каждый из пациентов будет ближе всего к одному из этих центроидов. Скорее всего, не все из них будут ближе всего к одному и тому же центроиду, так что сформируется несколько кластеров вокруг соответствующих центроидов.
У нас теперь есть k количество кластеров, и каждый из пациентов принадлежит к одному из них.
k-means после этого находит центр каждого кластера, опираясь на членов этих кластеров (используя векторы характеристик пациентов).
Этот центр становится новым центроидом кластера.
Так как центроид теперь в другом месте, пациенты могут оказаться ближе к другому центроиду. Другими словами, они могут перейти в другой кластер.
Шаги 2-6 повторяются до тех пор, пока центроиды больше не изменяются. Это называется конвергенцией.

Это обучение с учителем или без? Большинство считают k-means самообучающимся алгоритмом. Кроме указания количества кластеров, k-means «узнает» кластеры сам по себе, без какой-либо информации о том, к какому кластеру принадлежит тот или иной признак. K-means может, тем не менее, быть полуконтролируемым.

Почему стоит попробовать k-means? Мне кажется, это понятно.

Главным преимуществом k-means является его простота. То, что он прост в реализации, означает, что он обычно быстрее и эффективнее других алгоритмов, особенно при работе с большим набором данных.

К тому же, k-means можно использовать для предварительного кластерного анализа огромных наборов данных, чтобы потом воспользоваться более затратным алгоритмом кластерного анализа на самих кластерах. K-means также может изучать упущенные связи в наборе данных путем резкого изменения k.

Но не все так радужно:

Двумя главными недостатками k-means являются его чувствительность к выбросам и первоначальному выбору центроидов. И последнее, k-means был разработан для работы с непрерывными данными. Вам придется воспользоваться некоторыми уловками для того, чтобы работать с дискретными данными.

Где он используется? Огромное количество реализаций k-means доступны в сети:

Apache Mahout
Julia
R
SciPy
Weka
MATLAB
SAS

Если же деревья решений и кластеризация не произвели на вас впечатление, вам гарантированно понравится следующий алгоритм…

описание взято тут. Там же есть описания еще 9-и методов кластерного анализа, а реализация на конкретном ЯП гуглится по названию.

[xmoonlight]

Роман, не, это не подходит точно.

PS: без использования готовых библиотек и встроенных функций языка программирования, если ответ будет представлен в виде кода.

Там должны быть или пара-тройка формул с описанием, или пара-тройка строк кода, кмк.

[Роман]

xmoonlight, но выбрать подходящий метод, и посмотреть реализацию (с целью сделать свою, упрощенную под задачу) ведь можно?

[xmoonlight]

Роман, там они все используют только одно свойство, а тут минимум 2. Так, что думаю, вряд ли. Смотрю, вот...

[Роман]

xmoonlight, k-means же работает по нескольким признакам?

А можно пример? Ну конечно. Предположим, у нас есть набор данных пациентов. В кластерном анализе они называются признаками. О каждом из пациентов нам известны различные факты: возраст, пульс, кровяное давление, уровень холестерина, и т.д. Это вектор характеристик, представляющий пациента.

просто сформируйте для каждого слова вектор из N признаков

[значение признака 1, значение признака 2, ...., значение признака N]

[xmoonlight]

Роман, проблема в том, что k-means даёт коллизии! В этом вся проблема... (это я тестил)

[Роман]

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

[xmoonlight]

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

[Роман]

xmoonlight, сейчас попробую накидать реализацию, как ее вижу я, совершенно не привязанную к академическим знаниям.

Для этого мне понадобится некоторая информация от вас.

При том, что "вес" каждого слова до кластеризации должен быть уникальным.

1. Про какой вес говориться?
2. Что значит уникальный (можно ли считать что следующие 2 веса уникальны 0.59999 и 0.6?
3. Как этот вес может измениться после кластеризации?

Как именно можно создать 3 кластера похожих по написанию слов из следующего ниже списка слов:

4. Почему именно 3 кластера?
5. Может ли меняться набор слов?
6. Меняется ли требуемое количество кластеров на выходе при изменении набора слов?

7. Должны ли учитываться порядковые номера слов в списке (числовые индексы) при решении задачи?

8. Считать ли строчные и прописные буквы одинаковыми?

[xmoonlight]

Роман, нет доп инфы. это всё задание.

[Роман]

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

в первую группу идут:ком, лом, ром, сом
во вторую группу идут: сок, сом, сор и возможно соль
в третью группу идет: лось

итак имеем одну, неразрешимую коллизию - слово сом, которая равноудалена от слов как первой так и второй групп, к какой группе его отнести? к первой, второй, а может сразу к обоим группам? Математически оно одинаково близко к обоим группам.

Возможно в контексте задания (например на лекции, после которой это задание и было дано) было сказано, что вес совпадения букв в начале слова выше чем в конце?

PS: Вот написал небольшую взвешивалку похожести слов, может у вас какая идея придет.

код

function detSimilarity(w1, w2) {
    const len = Math.max(w1.length, w2.length);
    let summ = 0;
    for (let i1 in w1) {
        c1 = w1[i1];
        let d = len;
        for (let i2 in w2) {
            c2 = w2[i2];
            if (c1 == c2) {
                const t = Math.abs(i1 - i2);
                if (t < d) d = t;
            }
        }
        summ += len - d;
    }
    return summ / Math.pow(len, 2);
}

как работает

[xmoonlight]

Роман, Крайне интересный подход!
Но, как раз, вот, и коллизии тут возникают из-за симметрии главной диагонали..

... было сказано, что вес совпадения букв в начале слова выше чем в конце?

только это:

При том, что "вес" каждого слова до кластеризации должен быть уникальным.

[Роман]

xmoonlight, можно конечно и асимметрию добавить. например так

06 | 03 | 01
-------------
03 | 05 | 02
-------------
01 | 02 | 04

(чем ближе совпадение символов к началу слова тем больше вес данного совпадения.)
При таком подходе слово сом однозначно отойдет ко второй группе

НО какие логические основания для этого могут быть?

[Роман]

xmoonlight, если же делать ассиметрию именно на главной диагонали то получим

detSimilarity(w1, w2) != detSimilarity(w2, w1)

[xmoonlight]

Роман,

НО какие логические основания для этого могут быть?

чтобы это понять, нужно в столбик вывести ВСЕ "веса" слов и убедиться, что они ВСЕ уникальны. А потом - делать выводы по тому, насколько корректны их расстояния между собой.

[Роман]

xmoonlight, осталось только решить каким из миллиона возможных способов рассчитывать веса слов(

[xmoonlight]

Роман, если было бы это так просто сделать - не было бы и этого вопроса...

[Роман]

xmoonlight, тут вопрос не в легко или сложно а в противоречиях(коллизиях) в самом задании. Откуда хоть данное задание родом.

[xmoonlight]

Роман, если бы были коллизии, то и слова были бы одинаковые. Задание дала крупная организация для проверки знаний исполнителя по своему проекту по анализу текстовых данных. Как бы первичный отборочный фильтр (как я понял).

[Роман]

xmoonlight, если найдете или узнаете решение - дайте знать))))

[Роман]

Если бы небыло условия разбить на группы по схожести написания задача была бы тривиальной. А так они в условии дают жесткое ограничение на используемые признаки а данные содержат неоднозначность по этому умловию.

[Роман]

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

[Роман]

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

[xmoonlight]

Роман,

Но это уже по сути будет подтасовка/жульничество.

Не будет: просто я банально не пройду тест с такими приколами!)) Не зря же они просят не юзать встроенные функции и описывать всё алгоритмически.

[xmoonlight]

Роман,

Создать матрицу 33х33 в которой будут коэффициенты похожести написания самих букв между собой.

не думаю, что прям нужно именно начертание букв смотреть... Хотя, и это тоже может быть вариантом решения.

[Роман]

xmoonlight, вот нашел:

Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем, что метки объектов из обучающей выборки yi изначально не заданы, и даже может быть неизвестно само множество Y

.

Решение задачи кластеризации объективно неоднозначно по ряду причин:

Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области;
Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр[1];
Результат кластеризации существенно зависит от метрики. Однако существует ряд рекомендаций по выбору метрик для определенных классов задач.[2].

таким образом можно выбрать любые признаки, главное обосновать их логичность/разумность. То есть мой вариант несимметричности по второстепенной оси матрицы вполне годен при условии, что будет обоснование утверждения, что совпадение начала слов важнее чем совпадение конца слов. Это можно попытаться доказать на основе анализа механизмов восприятия печатных слов человеком. Думаю что при желании можно нагуглить результаты исследований на данную тему и на них опереться.

[xmoonlight]

Роман, это, конечно, занятно, но мало применимо к данной задаче. И это уже следующий, 2-й шаг.
Ок.
А что делать с первым?!
Как сделать так, чтобы все слова имели уникальные "веса" до кластеризации так, чтобы по ним можно было различать схожесть написания также, как и слова, написанные буквами?

[Роман]

Как сделать так, чтобы все слова имели уникальные "веса" до кластеризации

да очень просто.

Вариант 1.
N мерная система координат. Где N - предполагаемое максимально возможное число букв в слове.
Ттаким образом, любое слово можно выразить вектором, в котором ось - номер позиции буквы в слове, а значение по оси - индекс в алфавите буквы из этой позиции
Вес можно интерпретировать как длину данного вектора

Вариант 2.
N мерная система координат. Где N - число букв в алфавите.
Ттаким образом, любое слово можно выразить вектором, в котором для каждой оси - значением будет либо 0, либо, если буква была в слове то 1. При таком подходе слова мир и рим будут иметь одинаковый вектор. Чтобы этого избежать, можно замнить 1 на индекс буквы в слове.
Вес можно интерпретировать как длину данного вектора

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

[xmoonlight]

Роман, согласен в плане направлений, но вот, что:

хоть и небольшая

не совсем. Это будет полуквадратичная: xy/2. А это довольно большое кол-во коллизий...

[Роман]

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

[xmoonlight]

Роман, речь - про каждое слово. Как они уникальны, если слова мир и рим? Как вот посчитать так, чтобы они отличались (именно прям расчёт покаж)?

[Роман]

xmoonlight, вот надумал способ совместить вектор и вес.
Берем 34-ную систему счисления, в которой условно счислительный базис (34) это числа от нуля до 33 (номер буквы в алфавите). Таким образом получим:
вектор по варианту 1.
вес это представление слова в виде числа. Например слово aa будет представленно как 1*34+1, слово бa как 2*34+1, слово aб как 1*34+2. По сути тот же вектор, только запакованный, но так как это обычное число - то оно же и вес. Притом вес уникальный для каждого уникального слова. Расстояние можно считать как между векторами, так и простой арифметикой между весами. Признаками соответственно будут разницы между условных "едениц", "десятков", "сотен" и т.д.

[Роман]

xmoonlight, ну в первом варианте вектора у каждого из слов будут уникальны, во втором уникальны с поправкой "чтобы этого избежать, можно заменить 1 на индекс буквы в слове.". А в комментарии выше показал как для первого варианта сделать уникальным не только вектор но еще и вес.

[xmoonlight]

Роман, О! Вариант! Погоняю ща на js..

[Роман]

xmoonlight, если возник вопрос почему базис не 33 а 34, потому чтобы слова "a", "аа", "ааа" были не равны между собой. Расстояния рассчитанные между векторами варианта 1 и между представлениями этих векторов в системе счисления 34 будут конечно разными в числовом выражении, но и те и другие сохранят взаимосвязь между словами.

[Роман]

xmoonlight, убежал спать, 2 дня не спал, у малого зубы режутся)

[Лев Забудкин]

Роман, это всё применимо в сжатии данных, которые открыты более 60 лет назад, а к данной задаче это не применимо и тупо, когда можно просто всё решить имея на руках то, чего достигла наука, а не Ваши сраные калькуляторы.

[xmoonlight]

Роман, видишь такое - значит это адепт хабр-сообщества: не обращай внимания просто...

[xmoonlight]

Роман, Погонял, но вот теперь в чём проблема: несоответствие написания слов (похожесть), когда они длинные... Давай в почте лучше...

[Роман]

xmoonlight, можно и в почте, но лучше телега или дискорд или вайбер на крайняк, почту я раз в год смотрю (ужасно ее не люблю)

[xmoonlight]

Роман, отписал в почту...

[Роман]

xmoonlight, ответил