Авторизация



Напомнить пароль
Регистрация

Блог им. robtecКаким алгоритмом лучше воспользоваться?

Я сам не являюсь IT специалистом. Хотел получить консультацию по решению следующей задачи:
Имеется база из плей-листов музыки (id плей-листа, название трека, исполнитель)
Количество записей в плей-листах варьируется от 1 до 100.
Количество плей-листов измеряется сотнями тысяч.

На входе подается новый плей-лист.
В результате нужно отобрать максимально схожие с ним плей-листы и скомбинировать из них новый список ограниченного размера (предположим 100 записей) предварительно удалив дубликаты.

Вопрос: для отбора схожих плей-листов оптимально ли использовать алгоритм ближайшего соседа? Везде пишут, что он очень требователен к вычислительным ресурсам, а
требуется быстро выдавать результат…

Может существуют уже какие-то стандартные способы решения подобных задач?
  • +5
  • robtec
  • 29 октября 2010, 14:16

Комментарии (28)

rss свернуть / развернуть
  • avatar
  • Mord
  • 29 октября 2010, 14:41
  • #
  • 0
Их существует уже много очень.
Вики знает
свернуть ветку
Сходил по ссылке. Но там речь идет о сортировке данных, и нет ответа на вопрос: как отобрать схожие плей-листы…
свернуть ветку
Конечно. Это вообще никак не задача сортировки, это задача ранжирования, если уж в таком ключе подходить, но лучше не стоит.

Вам прежде всего нужно определить похожесть плейлистов. Если у вас получится дать определение похожим плейлистам — тогда здесь может подойти метод, схожий с методом k ближайших соседей. Эффективность его будет очень сильно зависеть от «правильности» метрики. По производительности это будет не так страшно, асимптотически это линейно по размеру базы данных плейлистов, многое будет зависеть от технологий и способа представления.

Что касается каких-либо стандартных способов — мне о них не известно, но обязательно сообщу вам, если что-нибудь найду/придумаю.
свернуть ветку
Недолго думав, пришла такая идея:

Можно составить некоторые коэффициенты для каждого из признаков (таких как жанр, рейтинг, год выпуска альбома и прочее), затем проводить между всеми плейлистами оценку с помощью этих коэффициентов и выделять «наилучшие», а их слияние производить по рангу, полученному таким образом. Для того, чтобы не перебирать каждый из элементов плейлиста можно воспользоваться каким-либо методом, позволяющим выделить наиболее частые значения признаков, например то, что большинство песен — рок и поп 1970-х. Так снизится размерность каждого плейлиста — что очень неплохо позволит увеличить производительность.
свернуть ветку
Под похожестью я подразумевал максимальное пересечение одинаковых записей в плей-листах.
Наиболее схожими являются те списки, где совпадает несколько треков.
Менее похожие — где есть пересечения в исполнителях.
свернуть ветку
Тогда это гораздо проще и метрика как количество совпадений подходит гораздо лучше.
свернуть ветку
может я не вовремя реагирую на пост… но мне кажется что в подобном случае (когда похожесть плей-листов определяется по количеству одинаковых треков) для сравнения можно использовать нейронную сеть.
свернуть ветку
а как организовать ее? какое у нее быстродействие в сравнении с другими алгоритмами?
свернуть ветку
быстродействие линейное по размеру сети, организовать будет очень трудно

вообще, странноватое применение
свернуть ветку
по моему не особо трудно реализовать, сеть не придётся обучать и ей ни чего не придётся сравнивать, нейрон используется только для взвешивания: взвешивает треки каждого плей-листа — в результате наиболее похожими будут те, чьи веса примерно равны… А если значение веса для каждого листа сохранять, то можно каждый раз сравнивать можно только вес листа. Список треков рассматривается как входной вектор.

Правда если в базе песен есть одинаковые треки с разными названиями, (типа КлёвыйТрек и Клевыйт рек), то придётся добавить ещё слой, который будет определять похожесть треков… что усложнит задачу
свернуть ветку
Если сеть не нужно обучать — то её можно заменить обычной функцией. Да и кроме того вектором треков не получится сравнить два плейлиста.
А уж с треками с похожими названиями сеть усложнится далеко не так, что в ней появится новый слой (подразумевается перцептрон?), а гораздо сильнее.
свернуть ветку
согласен — возможно сильнее, и я не подразумеваю перцептрон.
извиняюсь, что не ответил сразу… был далеко от интернетов последние несколько дней.
свернуть ветку
у меня 3 вопроса)
1. а как ИНС будет взвешивать треки?
2. сколько нейронов в скрытом слое?
3. сколько в выходном и чем они являются относительно задачи? (какое их место, смысл...)
свернуть ветку
такс)… я предпологаю, для решения использовать НС в которой все нейроны независимы. каждый нейрон взвешивает свой трек, взвешивает разумеется какойлибо функцией активации. После этого другой нейрон (или этот же) взвешивает плей-листы. В качестве входного вектора первому нейрону подаются значения ASCII кодов из заголовка трека, второй нейрон получает на вход веса треков полученные предидущим нейроном. Такой вариант можно реализовать линейно, когда один нейрон взвесит все треки, а потом все плей-листы. я даже что то подобное на досуге накодил… мне кажеться что выглядет убого… но в итоге, если результат сортирую по возрастанию веса плейлистов, то рядом стоят те плейслисты в которых имеется три одинаковых трека изи пяти… (я не стал забивать в свою псевдо БД много инфы — 10ть треков и пять листов из них, по пять треков в каждом)
свернуть ветку
ммдаа… больше слов не нахожу.
Тогда следующий вопрос: объясните мне разницу между вашей «нейронной сетью» (которая состоит из несвязанных нейронов или вообще одного нейрона, на который все пихается) и матрицей весовых коэффициентов для треков/плейлистов? И в чем состоит преимущество использования вашей «ИНС»? В том, что это ИИ и будет работать интеллектуальнее и быстрее? Или может в более воодушевляющем названии? Я не понимаю, поясните.
свернуть ветку
что то ведь должно задать эту матрицу весовых коэффициентов) этим как раз занимаются нейроны, больше они, по большому счёту, ничего не делают) преимущество: простота распараллеливания, с помощью того же OpenMP… или любой другой технологии
свернуть ветку
ну хорошо) а нейроны вы как задатите?) будете классы в с++ ваять?) а не проще тупо массив двумерный)) не? и параллельте его обработку сколько влезет)
свернуть ветку
пара структур: «трек» и «трек-лист»,… или класс с наследником) это не принципиально, а нейрон — это функция, которая взвешивает их содержимое по каким-нибудь правилам
свернуть ветку
Вооот… Добрались наконец) Похожий вопрос я уже озвучивал выше) Зачем называть взвешивающую функцию нейроном?)) Модно? Ну и что, что они оба реализуют возможно схожий функционал?… и кстати) По каким-нибудь правилам, это по каким? Может вы новую модель нейрона придумали, а мы тут еще ничего не знаем) Рассказывайте скорее!
свернуть ветку
не думаю что я что-нибудь новое придумал, использовал гауссиан для определения веса, на вход подавал сумму входных сигналов. входной сигнал для взвешивания трека — вектор из кодов ASCII, а для взвешивания трек-листа вектор из полученных на пред идущем этапе весов треков
свернуть ветку
простите, не гауссиан, а сигмоид :[
свернуть ветку
нейрон — это функция, которая взвешивает их содержимое по каким-нибудь правилам

Вот это да
свернуть ветку
А ты, я смотрю, не выдержал)))
свернуть ветку
как blackburn появится в сети — кину ему ссылку. или сам увидит. может и сможет чем помочь) я не в курсе
свернуть ветку
Большое значение имеет как индексированны эти плэйлисты.

Ближайший сосед если считается, то как правило с евклидовым растоянием, но так как у нас сравнительно мало элементов в самом листе, то оно больше говорит есть ли схожий элемент или нет. На этом можно сэкономить вычисления, просто введя подсчет (суммирование) очков для плэйлиста.
свернуть ветку
Знаете… Я тут подумал.
В общем идея с коэффициентами blackburn (весами атрибутов) + реляционная алгебра
1. Выбираете данные для i-го треклиста, считаете взвешенную оценку конкретного трека (если данные не числовые, то не н_о_р_м_ируете в некотором диапазоне, а просто н_у_м_еруете)
2. Тоже самое для входного листа
3. Делаете какой-нить OUTER JOIN
4. Совпадения записываете в другую табличку
5. Возвращаетесь на 1ый пункт, делаете тоже самое для (i + 1)-го листа

А потом выбираете из получившейся таблицы первые 100…

Только совпадения будут полные… Тут надо докумекать чуть, как по-хорошему сделать…
Но вроде видится, что будет работать)

Запросы делаются достаточно быстро… В процедурку забахаете в цикл и пусть крутится))
Как-то так)
свернуть ветку
База управляется вами? Если так, то лучше было бы ее переделать по такому формату:
есть таблица треков, есть таблица плейлистов и между ними таблица соответствий между первой и второй таблицами. Тогда, во-первых, меньше места будет тратиться на каждый из плейлистов в БД, во-вторых, алгоритм поиска похожих плейлистов будет проще и быстрее.
свернуть ветку
Всем спасибо. Когда соберу базу еще обращусь.
свернуть ветку
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.