Механизм рекомендации помогает пользователю находить новые и интересные элементы в пуле ресурсов. Существует множество типов рекомендательных алгоритмов, и график может служить основой общего назначения для оценки таких алгоритмов. В этой статье будет продемонстрировано, как построить механизм рекомендации фильмов на основе графов, используя общедоступный набор данных MovieLens , базу данных графов Neo4j и язык обхода графов Gremlin . Не стесняйтесь следовать в консоли Gremlin, поскольку пост будет шаг за шагом переходить от сбора данных к анализу и, в конечном итоге, к обходу.
Набор данных MovieRatings
GroupLens исследовательской группа сделала доступный свод рейтингов фильмов. Существует 3 версии этого набора данных: 100 тысяч, 1 миллион и 10 миллионов оценок. Этот пост использует версию набора данных с рейтингом 1 миллион. Набор данных можно загрузить с веб-сайта MovieRatings (размер ~ 6 мегабайт). Необработанный набор данных состоит из трех файлов: users.dat , movies.dat и ratings.dat . Более подробная информация о деталях каждого файла описана в соответствующем файле README.txt .
Начало работы с Gremlin
Все примеры кода можно вырезать и вставить в
консоль Gremlin или в
класс Groovy / Java в более крупном приложении. Ради простоты просто следуйте указаниям консоли Gremlin. Gremlin 1.3 доступен для скачивания по этому адресу
.
marko$ ./gremlin.sh
\,,,/
(o o)
-----oOOo-(_)-oOOo-----
gremlin>
Создание графика MovieRatings
Перед получением рекомендаций о том, какие фильмы смотреть, важно сначала проанализировать необработанные данные MovieLens в соответствии с определенной выше схемой графика. Хотя это не единственный способ представления данных в виде графа свойств , приведенное выше представление является естественным и полезным для обходов, представленных позже.
Данные будут вставлены в графовую базу данных Neo4j. Приведенный ниже код Gremlin / Groovy создает новый граф Neo4j, удаляет ненужный индекс края по умолчанию и устанавливает в буфере транзакций 1000 мутаций на коммит. Наконец, чтобы облегчить понимание данных, карта жестко закодирована, что позволит представлять занятие пользователя в виде строки вместо целочисленного идентификатора.
g = new Neo4jGraph('/tmp/movieRatings')
g.dropIndex("edges")
g.setMaxBufferSize(1000)
occupations = [0:'other', 1:'academic/educator', 2:'artist',
3:'clerical/admin', 4:'college/grad student', 5:'customer service',
6:'doctor/health care', 7:'executive/managerial', 8:'farmer',
9:'homemaker', 10:'K-12 student', 11:'lawyer', 12:'programmer',
13:'retired', 14:'sales/marketing', 15:'scientist', 16:'self-employed',
17:'technician/engineer', 18:'tradesman/craftsman', 19:'unemployed', 20:'writer']
Разбор данных фильма
Файл movie.dat содержит список фильмов. Каждая строка необработанного файла имеет 3 столбца: movieId , заголовок и роды .
marko$ more -n6 movies.dat 1::Toy Story (1995)::Animation|Children's|Comedy 2::Jumanji (1995)::Adventure|Children's|Fantasy 3::Grumpier Old Men (1995)::Comedy|Romance 4::Waiting to Exhale (1995)::Comedy|Drama 5::Father of the Bride Part II (1995)::Comedy
Код для анализа этих данных в Neo4j и в соответствии с схематической схемой представлен ниже. Детали кода оставлены на усмотрение заинтересованного читателя. Для других достаточно просто скопировать и вставить этот код в консоль Gremlin, чтобы двигаться вперед.
new File('movies.dat').eachLine {def line ->
def components = line.split('::');
def movieVertex = g.addVertex(['type':'Movie', 'movieId':components[0].toInteger(), 'title':components[1]]);
components[2].split('\\|').each { def genera ->
def hits = g.idx(T.v)[[genera:genera]].iterator();
def generaVertex = hits.hasNext() ? hits.next() : g.addVertex(['type':'Genera', 'genera':genera]);
g.addEdge(movieVertex, generaVertex, 'hasGenera');
}
}
Разбор пользовательских данных
Файл users.dat содержит список пользователей. Каждая строка исходного файла имеет 5 столбцов: идентификатор пользователя , пол , возраст , род занятий и почтовый индекс . Для простоты схемы поле почтового индекса будет игнорироваться.
ml-1m$ more -n6 users.dat 1::F::1::10::48067 2::M::56::16::70072 3::M::25::15::55117 4::M::45::7::02460 5::M::25::20::55455
new File('users.dat').eachLine {def line ->
def components = line.split('::');
def userVertex = g.addVertex(['type':'User', 'userId':components[0].toInteger(), 'gender':components[1], 'age':components[2].toInteger()]);
def occupation = occupations[components[3].toInteger()];
def hits = g.idx(T.v)[[occupation:occupation]].iterator();
def occupationVertex = hits.hasNext() ? hits.next() : g.addVertex(['type':'Occupation', 'occupation':occupation]);
g.addEdge(userVertex, occupationVertex, 'hasOccupation');
}
Анализ парсинга данных
Файл ratings.dat содержит оценки, предоставленные пользователем для фильмов, которые они смотрели. Каждая строка необработанного файла имеет 4 столбца: userId , movieId , звезды (1-5 рейтинговая шкала) и отметка времени . Поле метки времени будет игнорироваться.
ml-1m$ more -n6 ratings.dat 1::1193::5::978300760 1::661::3::978302109 1::914::3::978301968 1::3408::4::978300275 1::2355::5::978824291
Учитывая, что существует 1 миллион оценок, этот фрагмент кода займет минуту или около того, чтобы оценить. Для тех, кто имеет дело с большими наборами данных и Neo4j, возможно использовать Neo4jBatchGraph, который является новым с Blueprints 1.0.
new File('ratings.dat').eachLine {def line ->
def components = line.split('::');
def ratedEdge = g.addEdge(g.idx(T.v)[[userId:components[0].toInteger()]].next(), g.idx(T.v)[[movieId:components[1].toInteger()]].next(), 'rated');
ratedEdge.setProperty('stars', components[2].toInteger());
}
Чтобы зафиксировать любые данные, оставшиеся в буфере транзакций, успешно остановите текущую транзакцию. Теперь данные сохраняются на диск. Если вы планируете покинуть консоль Gremlin, сначала убедитесь, что
g.shutdown () на графике.
g.stopTransaction(TransactionalGraph.Conclusion.SUCCESS)
Прежде чем перейти к рекомендательным алгоритмам, давайте убедимся, что график выглядит правильно.
gremlin> g.V.count() ==>9962 gremlin> g.E.count() ==>1012657 gremlin> g.V[[type:'Movie']].count() ==>3883 gremlin> g.V[[type:'Genera']].count() ==>18 gremlin> g.V[[type:'User']].count() ==>6040 gremlin> g.V[[type:'Occupation']].count() ==>21 gremlin> occupations.size() ==>21
В качестве стороны : Каково распределение профессий среди пользователей?
gremlin> m = [:]
gremlin> g.V[[type:'User']].out('hasOccupation').occupation.groupCount(m) >> -1
==>null
gremlin> m.sort{a,b -> b.value <=> a.value}
==>college/grad student=759
==>other=711
==>executive/managerial=679
==>academic/educator=528
==>technician/engineer=502
==>programmer=388
==>sales/marketing=302
==>writer=281
==>artist=267
==>self-employed=241
==>doctor/health care=236
==>K-12 student=195
==>clerical/admin=173
==>scientist=144
==>retired=142
==>lawyer=129
==>customer service=112
==>homemaker=92
==>unemployed=72
==>tradesman/craftsman=70
==>farmer=17
Как насчет среднего возраста?
gremlin> g.V[[type:'User']].age.mean() ==>30.639238410596025
Обход графика MovieLens
Теперь, когда данные MovieLens были проанализированы и представлены в виде графика, данные готовы для просмотра (то есть запроса). Существует два основных типа рекомендаций: совместная фильтрация и рекомендации на основе контента.
В коллективной фильтрации поведение пользователей по рейтингу / симпатии / предпочтению коррелируется, чтобы рекомендовать избранное одного пользователя другому, подобному пользователю.
Мне нравятся фильмы, которые тебе нравятся, какие еще фильмы тебе нравятся, которых я не видел?
С рекомендациями на основе контента , если какой-то конкретный элемент нравится, то его функции анализируются, чтобы найти другие элементы с аналогичными функциями.
Мне нравятся романтические комедии о зомби, какие еще есть романтические комедии о зомби?
Базовая совместная фильтрация
В этом разделе будет создан еще более сложный обход, чтобы объяснить основы совместной фильтрации на основе графов и дать подсказку о вариациях, которые могут быть включены в соответствии с требованиями конкретной области. Давайте начнем с фильма История игрушек .
gremlin> v = g.idx(T.v)[[title:'Toy Story (1995)']] >> 1 ==>v[1] gremlin> v.map() ==>movieId=1 ==>title=Toy Story (1995) ==>type=Movie
- Какие пользователи дали Toy Story более 3 звезд? (вернуть только 5 результатов)
gremlin> v.inE('rated').filter{it.getProperty('stars') > 3}.outV.userId[0..4]
==>v[3902]
==>v[3912]
==>v[3916]
==>v[3918]
==>v[3920]
Этот обход не дает полезной информации. Однако, когда он используется в более широком выражении пути, применяется совместная фильтрация.
- Какие пользователи дали Toy Story более 3 звезд, а какие другие фильмы они дали более 3 звезд? (вернуть только 5 результатов)
gremlin> v.inE('rated').filter{it.getProperty('stars') > 3}.outV.outE('rated').filter{it.getProperty('stars') > 3}.inV.title[0..4]
==>One Flew Over the Cuckoo's Nest (1975)
==>Erin Brockovich (2000)
==>Bug's Life, A (1998)
==>Ben-Hur (1959)
==>Christmas Story, A (1983)
- Начните с Истории игрушек — v
- Получите входящие номинальные ребра — inE
- Отфильтруйте те ребра, у которых свойство звезды меньше 4 — filter {it.getProperty (‘stars’)> 3}
- Получить хвостовые вершины пользователя оставшихся ребер — outV
- Получите оценки краев этих пользовательских вершин — outE («рейтинг»)
- Отфильтруйте те ребра, у которых свойство звезды меньше 4 — filter {it.getProperty (‘stars’)> 3}
- Получить головные вершины фильма из оставшихся ребер — inV
- Получить свойство title строки этих вершин фильма — title
- Выпускать только первые 5 заголовков — [0..4]
Что означает совокупность этих атомных шагов? — высоко оцененный . С Gremlin можно работать на более высоком уровне абстракции, используя определенные пользователем шаги . Шаг, определенный ниже, называется corated и объединяет все эти атомарные шаги.
gremlin> Gremlin.defineStep('corated',[Vertex,Pipe], { def stars ->
_().inE('rated').filter{it.getProperty('stars') > stars}.outV.outE('rated').filter{it.getProperty('stars') > stars}.inV})
==>null
gremlin> v.corated(3).title[0..4] ==>One Flew Over the Cuckoo's Nest (1975) ==>Erin Brockovich (2000) ==>Bug's Life, A (1998) ==>Ben-Hur (1959) ==>Christmas Story, A (1983)
Этот обход вернет список фильмов. Обратите внимание, что в этом списке много дубликатов. Это связано с тем, что пользователям, которые любят Toy Story, также нравятся многие другие фильмы. Это сходство человеческого поведения является то, что используется в алгоритмах рекомендаций.
- Сколько фильмов с высокой оценкой в Toy Story являются уникальными?
gremlin> v.corated(3).count() ==>268493 gremlin> v.corated(3).uniqueObject.count() ==>3353
Принимая во внимание, что существует 268 493 дорожки с высокой оценкой от Истории игрушек до других фильмов, и только 3 353 из этих фильмов являются уникальными, эти дубликаты можно использовать в качестве механизма ранжирования — в конечном счете, рекомендации.
- Какие фильмы наиболее высоко оценены с Toy Story? (верните 10 лучших)
gremlin> m = [:]
gremlin> v.corated(3).title.groupCount(m) >> -1
==>null
gremlin> m.sort{a,b -> b.value <=> a.value}[0..9]
==>Toy Story (1995)=1655
==>Star Wars: Episode V - The Empire Strikes Back (1980)=1000
==>Star Wars: Episode IV - A New Hope (1977)=998
==>American Beauty (1999)=949
==>Matrix, The (1999)=925
==>Raiders of the Lost Ark (1981)=922
==>Silence of the Lambs, The (1991)=887
==>Saving Private Ryan (1998)=878
==>Back to the Future (1985)=876
==>Shawshank Redemption, The (1994)=875
Лучший результат имеет смысл. Это говорит, что люди, которые любят Toy Story, также любят Toy Story. Чтобы удалить эти рефлексивные пути, просто отфильтруйте «Историю игрушек».
gremlin> m = [:]
gremlin> v.corated(3).filter{it != v}.title.groupCount(m) >> -1
==>null
gremlin> m.sort{a,b -> b.value <=> a.value}[0..9]
==>Star Wars: Episode V - The Empire Strikes Back (1980)=1000
==>Star Wars: Episode IV - A New Hope (1977)=998
==>American Beauty (1999)=949
==>Matrix, The (1999)=925
==>Raiders of the Lost Ark (1981)=922
==>Silence of the Lambs, The (1991)=887
==>Saving Private Ryan (1998)=878
==>Back to the Future (1985)=876
==>Shawshank Redemption, The (1994)=875
==>Toy Story 2 (1999)=871
Это все хорошие фильмы, которые обычно считаются «хорошими». Однако обратите внимание, что обход рекомендаций начинается не с конкретного пользователя, а с конкретного фильма (например, История игрушек). Если вместо этого обход начинается с конкретного пользователя, то применяется базовая совместная фильтрация.
Учитывая пользователя, какие фильмы им нравятся, кому еще нравятся эти фильмы, и какие другие фильмы нравятся тем пользователям, которые еще не понравились этому первоначальному пользователю.
Выражение этого в Гремлин оставлено в качестве упражнения для более чем случайно заинтересованного читателя. Не стесняйтесь, напишите мне свое решение для комментариев (или опубликуйте его в списке рассылки Gremlin-Users ).
Микширование в содержательной рекомендации
В предыдущем разделе возвращались в целом хорошие фильмы. Однако, если я родитель и хочу найти хороший фильм, такой как «История игрушек», для моих детей, я бы, наверное, не хотел, чтобы они смотрели « Молчание ягнят» . Чтобы исправить эту ситуацию, можно объединить совместную фильтрацию и рекомендации на основе контента в обход, который дает фильмы «История игрушек хороших» того же рода.
gremlin> v.out('hasGenera').genera
==>Animation
==>Children's
==>Comedy
- Какие фильмы наиболее высоко оценены Toy Story и имеют общие роды с Toy Story? (верните 10 лучших)
gremlin> m = [:]
gremlin> x = [] as Set
gremlin> v.out('hasGenera').aggregate(x).back(2).corated(3).filter{it != v}.out('hasGenera').retain(x).back(2).title.groupCount(m) >> -1
==>null
gremlin> m.sort{a,b -> b.value <=> a.value}[0..9]
==>American Beauty (1999)=949
==>Back to the Future (1985)=876
==>Toy Story 2 (1999)=871
==>Princess Bride, The (1987)=851
==>Groundhog Day (1993)=843
==>Shakespeare in Love (1998)=807
==>Forrest Gump (1994)=775
==>Men in Black (1997)=747
==>E.T. the Extra-Terrestrial (1982)=737
==>Bug's Life, A (1998)=700
Этот рейтинг имеет смысл, но, тем не менее, для удушающе обеспокоенного родителя фильмы, такие как American Beauty (классифицированные как комедия), не могут считаться подходящими для детей. Как насчет того, чтобы рассматривать только те фильмы, которые имеют все те же роды, что и история игрушек?
- Какие фильмы наиболее высоко оценены с Toy Story, которые разделяют все роды с Toy Story? (верните 10 лучших)
gremlin> m = [:]
gremlin> x = [] as Set
gremlin> v.out('hasGenera').aggregate(x).back(2).corated(3).filter{it != v}.filter{it.out('hasGenera')>>[] as Set == x}.title.groupCount(m) >> -1
==>null
gremlin> m.sort{a,b -> b.value <=> a.value}[0..9]
==>Toy Story 2 (1999)=871
==>Bug's Life, A (1998)=700
==>Chicken Run (2000)=465
==>American Tail, An (1986)=140
==>Aladdin and the King of Thieves (1996)=39
==>American Tail: Fievel Goes West, An (1991)=37
==>Rugrats Movie, The (1998)=34
==>Adventures of Rocky and Bullwinkle, The (2000)=21
==>Saludos Amigos (1943)=4
Вывод
Рекомендация — популярный метод, используемый для отделения пшеницы от плевел . Для систем с многочисленными элементами, помогающими пользователю находить элементы, которые не только удовлетворяют их вкусы, но также и их мгновенные потребности , могут использоваться представленные алгоритмы. Важно отметить, что на некотором уровне абстракции совместная фильтрация и рекомендации на основе контента совпадают. Эта идея становится очевидной, если учесть, что рейтинги — это еще одна особенность предмета. В частности, фильмы с высоким рейтингом являются особенностями этого фильма. Эта идея достигает гибкости структуры данных графа свойств и понятия абстрактных / предполагаемых / производных отношений .
Приведенная ниже позиция представляет темы рекомендаций, которые могут быть дополнительно изучены заинтересованным читателем. График позволяет аналитику разрезать и нарезать данные различными способами. При наличии достаточного количества данных (много типов вещей и много типов отношений) можно сделать множество сопоставлений. Это сила шаблона обхода графа .
- Используйте родовые таксономии для изучения обобщения и спецификации родов.
- Определите, является ли пол значимым фактором в предпочтении фильмов.
- Рекомендовать фильмы с фильтрацией по профессии (или возрасту) пользователя.
- Смешайте другие функции фильма, такие как режиссер, актеры и рейтинги фильмов.
- Использует коллекцию стартовых фильмов (например, «Учитывая историю игрушек и большие неприятности в маленьком Китае ,…»). Поймите, что один пользователь может рассматриваться как ссылка на такую коллекцию (фильмы, которые они высоко оценили).
- «Что предпочитают пользователи, которым не нравятся те же фильмы, что и мне?»
- «Что нравится пользователям, кому нравятся фильмы, которые мне не нравятся?» (не совместная фильтрация)
- Используйте пол, почтовый индекс и рейтинги, чтобы рекомендовать пользователям дату просмотра фильма («смотреть фильм X с пользователем Y »).
- Используйте фильтры диапазона (например, [0..100] ) или случайные блуждания для детального контроля скорости выполнения (т. Е. Выборки пути).
Статьи по Теме
Родригес М.А., Уоткинс Дж. Вера в алгоритм. Часть 2. Вычислительная эвдамоника. Материалы Международной конференции по интеллектуальным и информационным системам, основанным на знаниях –820, апрель 2009 г.
Родригес, М. А., Нойбауэр, П., « Шаблон обхода графа», Управление данными графа: методы и приложения, ред. S. Sakr, E. Pardede, IGI Global, ISBN: 9781613500538, август 2011 г.
Родригес М.А., Аллен Д.У., Шинавье Дж., Эберсол Г., « Система рекомендаций для поддержки процесса научной коммуникации », KRS-2009-02, апрель 2009 г.
Источник : http://markorodriguez.com/2011/09/22/a-graph-based-movie-recommender-engine/