Коэффициент сходства

[Сержик]

Помогите студенту!!! дали задание по программированию и не могу сообразить, суть не в программировании, а в математики задания...
Мне надо написать программу, а в ней должна быть ещё кое-какая функция и вот я не могу её написать толком без помощи математики...
Короче так, суть задачи.
Есть пользователи (пользователь1 пользователь2 пользователь3), есть объект, в котором много элементов (А Б В Г Д ...). Пользователи посещают эти элементы и вот нужно найти похожих пользователей, которые посещали примерно тоже количество и сегмент элементов...
Допустим такое сочетание
пользователь1: 2А-1Б-3В-1Г (2 раза посещал А, 1 раз - Б и т.д)
пользователь2: 2А-1Б-2В-2Г
пользователь3: 1А-1Б-3В
Рассматриваем пользователя3 и нужно сравнить его с пользователем1 на сходство.. вот как?
Так вот я то думал сделать или мож вывести 'коэффициент сходства', но не знаю как..
Коеф. при идентичности равн. 1, а как вывести этот коефициент без понятия...

[PAV]

Без понимания предметной области ответ дать сложно. Правильнее рассуждать в терминах расстояний между последовательностью: при точном совпадении расстояние равно нулю, а при частичном - положительное. Чем больше расстояние, тем меньше сходство.

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

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

[Сержик]

Нет, от общего числа посещений не нужно искать сходство, именно нужно узнать похож ли пользователь на другого(других) или рассчитатьрейтинг по всем пользователям относительно одного !!! но только по посещениям элементов А, Б и других!!!
Я думал использовать такую формулу коеф. сходства
(посещаемость пользоват3) * 2
К = ---------------------------------------------------------------------------------
(посещаемость пользоват1)+ (посещаемость пользоват3)

Но это общая посещаемость, а нужно чтоб учитывалась посещаемость по элементам... как его сделать?

[PAV]

Ну, простейший способ - расстояние Хемминга, применяемое или к вектору количеств посещений, или долей.

Можно взять также обычное евклидово расстояние или расстояние Махаланобиса.

Можно придумать и другие. Есть различные расстояния между распределениями вероятностей.

[Сержик]

насчёт векторов, это будет выглядеть так..?
допустим соотношение посещение пользователя3(п3) с п1 и п2 это будут длины векторов п3п1 и п3п1, а координатами будут посещаемость элементов (А Б В), сравнивая их длины мы можем найти сходство, идентичность будет равняться 0... то есть можно выставить рейтинг сходства пользователя с другими...
ну пока вреде так, больше ничего ешо не могу придумать

[VAL]

Сержик
Прочитал Ваши объяснения, но так и не понял следует ли считать похожими пользователей векторы посещений у которых, например, такие: $(20,30,21,25)$ и $(4,7,5,5)$?
Если да, то лучшей мерой похожести, будет, на мой взгляд, коэффициент корреляции (пирсоновский или еще какой-нибудь).
Если же пользователи, в приведенном примере не должны считаться похожими из-за разной активновсти, то мерой похожести могут служить различные расстояния (см. рекомендации PAVа), а может... все равно коэффициент корреляции, но домноженный на отношение длины меньшего вектора к длине большего.

[Sherpa]

А если рассматривать посещения, как координаты точки в многомерном пространстве. Затем просто сравнивать удалённость точек друг от друга.

[Mikhail Sokolov]

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

[PAV]

И постарайтесь писать более внятно, грамотно и подробно, желательно поясняя свои рассуждения примерами, потому что в подобном телеграфном стиле

Сержик в сообщении #150695 писал(а):

допустим соотношение посещение пользователя3(п3) с п1 и п2 это будут длины векторов п3п1 и п3п1, а координатами будут посещаемость элементов (А Б В), сравнивая их длины мы можем найти сходство, идентичность будет равняться 0

я лично толком ничего не понял.

[Сержик]

Я не сверхматематик, а начинающий программист и не разбираюсь в теориях расстояние Хемминга(прогуглил кое понял), расстояние Махаланобиса(не нашел пока ничего про это). Знаю то, чему научили.

Объясняю подробно.
Есть n пользователей (Пn), и есть элементы A, Б, В, Г, Д.. Пользователи посещают эти элементы.
"Показателями схожести" - сегмент элементов и частота посещаемости этих элементов. То есть Пользователь 1 и Пользователь 2 будут сравниваться по тем элементам, которые они посещают и частоту посещения этих элементов.
Если к примеру, Пользователь 1 посещал: 2А-1Б-3В-1Г
а Пользователь2 -> 2А-1Б-3В-1Г, это идентичные пользователи
Если Пользователь2 -> 1К-1Л-4М-1Н, это совсем не идентичные пользователи (нет совпадений) и рассматривать как таково не нужно.
Если Пользователь2 -> 2А-1Б-2В-2Г, неидентичны, но похожи и из этого нужно построить рейтинг схожести этих пользователей... вот я и хотел бы высчитать какой-то коэффициент схожести

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

[e7e5]

Сержик писал(а):

Допустим такое сочетание
пользователь1: 2А-1Б-3В-1Г (2 раза посещал А, 1 раз - Б и т.д)
пользователь2: 2А-1Б-2В-2Г
пользователь3: 1А-1Б-3В
Рассматриваем пользователя3 и нужно сравнить его с пользователем1 на сходство.. вот как?

Допустим
Джо - в понедельник едет в паб Дублина и берет темное пиво
- во вторник не едет никуда, отдыхает дома
-в среду идет в местный паб за Гинесом
и.т.д

Его приятель Крис- прямая противоположность ( относительно чего?)
в понедельник едет в Дублин на работу и пьет чай
-во вторник снова едет на работу в Дублин и пьет крепкий чай
- в среду едет в Дублин и пьет очень крепкий чай.

Друг Криса - Алан
в понедельник едет в паб Дублина и берет светлое пиво
во вторник отсыпается дома
в среду идет в местный паб встретить Джо

Среди всех этого нужно найти наиболее похожие?
Крис в каком-то смысле похож на Джо, не так ли? Почему?

[Sherpa]

Я тут ещё немного подумал, и вот более конкретно: можно просто для каждой пары сравнивать посещаемость каждого ресурса ипутем взятия модуля разницы. Другими словами, если один пользователь будет вектором 1-2-3-4-5, а второй - 1-5-1-5-1, например. Получим 0-3-2-1-4 и в какой-нибудь матрице будем писать длину этого вектора. Причем элемент матрицы [i,j] будет показывать похожесть i-го и j-го пользователей.

[Сержик]

Sherpa спасибо, но к чему тут матрицы?