Алгоритм выбора выбранных элементов

У меня есть программное обеспечение, похожее на Pandora, где пользователь может пролистнуть песню вверх или вниз. Программное обеспечение под названием Cavah представляет собой Silverlight + C#, но этот вопрос не зависит от языка и платформы.

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

Я хочу, чтобы мое программное обеспечение выбирало песню для воспроизведения с учетом следующих требований:

  1. Следует отдавать предпочтение песням, на которых стоит большой палец, и регулярно их проигрывать.

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

  3. Пропущенные песни следует проигрывать редко.

  4. Каким бы ни был алгоритм, песни не должны часто повторяться.

Учитывая эти проектные решения, есть ли здесь хороший алгоритм?

У меня есть код, который захватывает все песни, понравившиеся песни и не понравившиеся песни:

var allSongs = ...
var likedSongs = allSongs.Where(s => s.LikedByUser(...));
var dislikedSongs = allSongs.Where(s => s.DislikedByUser(...));

Любые простые идеи по выбору хорошей песни для пользователя?


preferences random algorithm
person Judah Gabriel Himango    schedule 27.07.2010    source источник
comment
Предпочтения других пользователей вообще не учитываются, верно?   -  person grossvogel    schedule 27.07.2010
comment
просто для уточнения... это С#?   -  person Chase Florell    schedule 27.07.2010
comment
Да обоим: предпочтения других пользователей не имеют значения, и да, этому C# + Silverlight. Вы можете увидеть проект вживую по адресу: bit.ly/chavah   -  person Judah Gabriel Himango    schedule 27.07.2010

Ответы (4)


arrow_upward
2
arrow_downward

Вы можете взвешивать песни; скажем, каждая песня имеет оценку 1,0 в начале, 0,5, если минус и 1,5, если лайк. Затем вы выбираете случайный элемент из набора всех оценок, однако его вероятность взвешивается его, гм, весом. Быстрый и грязный подход, о котором я бы подумал, заключается в суммировании всех весов. Выберите случайное число меньше этой суммы. Перебирать все песни, пока CurrentWeight+SongWeight > RandomNumber (иначе CurrentWeight+=SongWeight)

Конечно, вы можете сделать это произвольно более сложным, введя совместную фильтрацию :)

Представьте пять песен. Первые два получили одобрение, следующие один - отрицательный, два нейтральных.

{1: 1.5, 2: 1.5, 3:0.5, 4: 1, 5:1}

В сумме это 5,5. Теперь мы выбираем случайное число ‹ 5,5 и видим: это 2,43789.

Теперь давайте найдем песню, которой принадлежит это случайное число.

Начните с CurrentWeight = 0. Вес первой песни = 1,5. CurrentWeight+1.5 ‹ 2.43789 -> мы продолжаем, но увеличим CurrentWeight на вес этой песни.

Итак, CurrentWeight = 1,5. Вес следующей песни: снова 1,5. Но теперь CurrentWeight+1,5 == 3 > 2,43789. Это значит, что мы выбрали вторую песню!

Что вы делаете здесь, так это выбираете случайное место в строке, но увеличиваете «территорию» в этой строке, которая выберет песню, если песня будет одобрена.

Создает ли это много повторений или нет, в основном зависит от того, насколько сильно вы увеличиваете/уменьшаете вес песен.

person Nicolas78    schedule 27.07.2010
comment
Я не уверен, что понимаю. Не могли бы вы предоставить небольшой образец, демонстрирующий концепцию? Я потерялся ближе к концу. - person Judah Gabriel Himango; 27.07.2010
comment
Один вопрос: будет ли этот метод вводить много повторов, если понравившихся песен всего несколько (скажем, 5)? - person Judah Gabriel Himango; 27.07.2010
comment
Я расширил свой ответ примером, надеюсь, это поможет - person Nicolas78; 27.07.2010
comment
Блин, спасибо большое. Я думаю, это сработает. Я отмечаю ваш как ответ. Я попробую это сегодня вечером. - person Judah Gabriel Himango; 27.07.2010
comment
круто :) хорошо, я немного подумал, и что-то мне не нравится в моем подходе, так это то, что он сравнительно медленный, заставляющий вас перебирать, в среднем sumOfWeights/2 песни для каждого выбора. Если вы можете жить с четными соотношениями между весами, вы также можете просто поместить песни в список и выбрать одну из них — просто поместите те, которые не были оценены дважды (например), те, которые получили одобрение, — три раза, а те, которые подверглись понижению, — один раз (этот приведет к тому же распределению, что и в приведенном выше примере, вы просто не настолько гибки, если хотите изменить эти веса) - person Nicolas78; 28.07.2010
comment
Привет, Николас. Думаю, вам может быть интересно узнать, что я использовал ваш ответ и написал об этом в статье на CodeProject: codeproject.com/KB/silverlight/pandorasilverlight.aspx - person Judah Gabriel Himango; 23.11.2010
comment
Эй, Иуда, спасибо за обновление. Мне придется покопаться в нем в свободное время, похоже, вы использовали некоторые передовые функции С#, которые я еще не использовал. Хороший проект и хорошая статья! А еще очень мотивирует такой результат :) - person Nicolas78; 25.11.2010
comment
Я думаю, вы могли бы использовать Дерево Фенвика, чтобы ускорить поиск. - person Paul Jackson; 06.12.2011

arrow_upward
1
arrow_downward

Я предполагаю, что Pandora использует систему тегов для классификации своих песен. Таким образом, вы разрабатываете профиль музыкальных пристрастий пользователя, отбирая наиболее часто встречающиеся теги «большой палец вверх». К сожалению для вас, они используют обширную базу данных музыки с тегами, чтобы предложить своим пользователям, что, вероятно, сложнее разработать, чем алгоритм для их выбора.

person James    schedule 27.07.2010
comment
Да, я не заинтересован в том, чтобы основывать свой выбор на типе музыки, как это делает Пандора с тегами. Я ищу более простой метод: наиболее понравившиеся песни, некоторые без рейтинга, несколько непонравившихся, с небольшим количеством повторов. - person Judah Gabriel Himango; 27.07.2010

arrow_upward
1
arrow_downward

Вы также можете создать рейтинговую систему для группы/исполнителя и жанра, и на основе каждого «большого пальца вверх» вы можете добавить 1 (или любое другое значение, которое вы решите) как к группе/певцу, так и к жанру. Затем, когда придет время выбирать следующую песню для воспроизведения, вы можете взвесить решение, основываясь на интересе указанного пользователя к группе/исполнителю и/или жанру. И наоборот для "заваленных" песен.

person Ryan    schedule 27.07.2010
comment
Да, я это планирую, но позже. На данный момент я хочу использовать только большой палец вверх / вниз на одной песне, чтобы обосновать свое решение. - person Judah Gabriel Himango; 27.07.2010

arrow_upward
1
arrow_downward

Может быть, что-то вроде этого:

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

2) Создать функцию, которая объединяет потоки в один поток, соблюдая при этом определенные правила. Основным правилом будет желаемое сочетание потоков, скажем, 60% понравившихся, 38% не оцененных, 2% не понравившихся или что-то еще. Вам придется отклоняться от желаемого микса только тогда, когда продолжительность понравившегося потока слишком коротка, чтобы следовать правилу «минимального времени между повторами песни».

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

person grossvogel    schedule 27.07.2010