Блог им. robtec → Каким алгоритмом лучше воспользоваться?
Я сам не являюсь IT специалистом. Хотел получить консультацию по решению следующей задачи:
Имеется база из плей-листов музыки (id плей-листа, название трека, исполнитель)
Количество записей в плей-листах варьируется от 1 до 100.
Количество плей-листов измеряется сотнями тысяч.
На входе подается новый плей-лист.
В результате нужно отобрать максимально схожие с ним плей-листы и скомбинировать из них новый список ограниченного размера (предположим 100 записей) предварительно удалив дубликаты.
Вопрос: для отбора схожих плей-листов оптимально ли использовать алгоритм ближайшего соседа? Везде пишут, что он очень требователен к вычислительным ресурсам, а
требуется быстро выдавать результат…
Может существуют уже какие-то стандартные способы решения подобных задач?
Имеется база из плей-листов музыки (id плей-листа, название трека, исполнитель)
Количество записей в плей-листах варьируется от 1 до 100.
Количество плей-листов измеряется сотнями тысяч.
На входе подается новый плей-лист.
В результате нужно отобрать максимально схожие с ним плей-листы и скомбинировать из них новый список ограниченного размера (предположим 100 записей) предварительно удалив дубликаты.
Вопрос: для отбора схожих плей-листов оптимально ли использовать алгоритм ближайшего соседа? Везде пишут, что он очень требователен к вычислительным ресурсам, а
требуется быстро выдавать результат…
Может существуют уже какие-то стандартные способы решения подобных задач?
- +5
- robtec
- 29 октября 2010, 14:16
Комментарии (28)
rss свернуть / развернутьВики знает
свернуть ветку
свернуть ветку
Вам прежде всего нужно определить похожесть плейлистов. Если у вас получится дать определение похожим плейлистам — тогда здесь может подойти метод, схожий с методом k ближайших соседей. Эффективность его будет очень сильно зависеть от «правильности» метрики. По производительности это будет не так страшно, асимптотически это линейно по размеру базы данных плейлистов, многое будет зависеть от технологий и способа представления.
Что касается каких-либо стандартных способов — мне о них не известно, но обязательно сообщу вам, если что-нибудь найду/придумаю.
свернуть ветку
Можно составить некоторые коэффициенты для каждого из признаков (таких как жанр, рейтинг, год выпуска альбома и прочее), затем проводить между всеми плейлистами оценку с помощью этих коэффициентов и выделять «наилучшие», а их слияние производить по рангу, полученному таким образом. Для того, чтобы не перебирать каждый из элементов плейлиста можно воспользоваться каким-либо методом, позволяющим выделить наиболее частые значения признаков, например то, что большинство песен — рок и поп 1970-х. Так снизится размерность каждого плейлиста — что очень неплохо позволит увеличить производительность.
свернуть ветку
Наиболее схожими являются те списки, где совпадает несколько треков.
Менее похожие — где есть пересечения в исполнителях.
свернуть ветку
свернуть ветку
свернуть ветку
свернуть ветку
вообще, странноватое применение
свернуть ветку
Правда если в базе песен есть одинаковые треки с разными названиями, (типа КлёвыйТрек и Клевыйт рек), то придётся добавить ещё слой, который будет определять похожесть треков… что усложнит задачу
свернуть ветку
А уж с треками с похожими названиями сеть усложнится далеко не так, что в ней появится новый слой (подразумевается перцептрон?), а гораздо сильнее.
свернуть ветку
извиняюсь, что не ответил сразу… был далеко от интернетов последние несколько дней.
свернуть ветку
1. а как ИНС будет взвешивать треки?
2. сколько нейронов в скрытом слое?
3. сколько в выходном и чем они являются относительно задачи? (какое их место, смысл...)
свернуть ветку
свернуть ветку
Тогда следующий вопрос: объясните мне разницу между вашей «нейронной сетью» (которая состоит из несвязанных нейронов или вообще одного нейрона, на который все пихается) и матрицей весовых коэффициентов для треков/плейлистов? И в чем состоит преимущество использования вашей «ИНС»? В том, что это ИИ и будет работать интеллектуальнее и быстрее? Или может в более воодушевляющем названии? Я не понимаю, поясните.
свернуть ветку
свернуть ветку
свернуть ветку
свернуть ветку
свернуть ветку
свернуть ветку
свернуть ветку
Вот это да
свернуть ветку
свернуть ветку
свернуть ветку
Ближайший сосед если считается, то как правило с евклидовым растоянием, но так как у нас сравнительно мало элементов в самом листе, то оно больше говорит есть ли схожий элемент или нет. На этом можно сэкономить вычисления, просто введя подсчет (суммирование) очков для плэйлиста.
свернуть ветку
В общем идея с коэффициентами blackburn (весами атрибутов) + реляционная алгебра
1. Выбираете данные для i-го треклиста, считаете взвешенную оценку конкретного трека (если данные не числовые, то не н_о_р_м_ируете в некотором диапазоне, а просто н_у_м_еруете)
2. Тоже самое для входного листа
3. Делаете какой-нить OUTER JOIN
4. Совпадения записываете в другую табличку
5. Возвращаетесь на 1ый пункт, делаете тоже самое для (i + 1)-го листа
А потом выбираете из получившейся таблицы первые 100…
Только совпадения будут полные… Тут надо докумекать чуть, как по-хорошему сделать…
Но вроде видится, что будет работать)
Запросы делаются достаточно быстро… В процедурку забахаете в цикл и пусть крутится))
Как-то так)
свернуть ветку
есть таблица треков, есть таблица плейлистов и между ними таблица соответствий между первой и второй таблицами. Тогда, во-первых, меньше места будет тратиться на каждый из плейлистов в БД, во-вторых, алгоритм поиска похожих плейлистов будет проще и быстрее.
свернуть ветку
свернуть ветку