Поиск наилучшей последовательности просмотра списка 250 лучших фильмов с помощью языка Wolfram Language (Mathematica)


    Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь (архив, ~76 МБ).

    Введение


    Некоторое время назад, если быть точным — 515 дней, вышел пост Маттиаса Одисио (Matthias Odisio) под названием “Random and Optimal Mathematica Walks on IMDb’s Top Films” (Случайные и оптимальные блуждания Mathematica по списку 250 лучших фильмов по версии IMDB). В нем рассказывается о том, каким образом можно получить оптимальную последовательность просмотра фильмов из соответствующего списка, основанную на близости жанров фильмов и близости постеров фильмов с точки зрения цвета.

    In[1]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_2.png

    Out[1]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_3.png

    Идея этого поста показалась мне довольно интересной, но мне захотелось её существенно расширить и углубить, следуя нескольким идеям:

    • Построить более совершенную функцию, оценивающую близость фильмов, так как мне кажется, что построение функции расстояния между фильмами на основе близости постеров фильмов по использующимся в них цветам и жанрам фильмов не достаточно объективно. Мне представляется разумным построить функцию расстояния между фильмами на основе нескольких факторов: жанров фильма, описания фильма, актерского состава, режиссера(-ов), года производства, сценариста(-ов) и пр.

    • В статье Маттиаса использовались лишь данные Wolfram|Alpha, что, безусловно, упрощает задачу и компактизирует код. Мне же хочется рассказать о том, как можно использовать в расчетах данные, взятые откуда угодно, например, полученные с помощью веб-парсинга со страниц Википедии, подгруженные из текстовых баз данных и т. п.

    Я не буду рассказывать в этой статье о том, как построить оптимальную последовательность просмотра списка 250 лучших фильмов КиноПоиска по той причине, что просто не хочется иметь проблем с условиями использования данного ресурса, которые довольно четко говорят (см. п. 6), что просто взять их список фильмов и произвести его анализ без их согласия не получится. При этом применить алгоритмы, которые я приведу ниже для этого списка довольно просто. Также мне хотелось бы отметить, что во время моей работы с одной из отечественных кинокомпаний для их нужд на языке Wolfram Language был написан парсер, который подгружал информацию о фильмах с сайта КиноПоиск (юридическая сторона вопроса была улажена) для последующего автоматического формирования рекламного буклета о нескольких тысячах фильмов, права на которые принадлежали этой компании. Ниже вы можете видеть пример одной такой полностью автоматически созданной страницы буклета (приведена неокончательная версия, ввиду NDA).

    Пример страницы
    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_4.png

    В данной статье будет использоваться информация о фильмах, представленная в Википедии, что позволит избежать любых проблем с правообладателями. Это с одной стороны усложняет задачу (парсер с централизованного хранилища вроде IMDB или КиноПоиска написать проще), но в тоже время позволяет построить некоторые дополнительные, интересные, программы.

    Импорт данных с сайта Википедии


    Для начала, подгрузим символьное представление HTML кода страницы Википедии “250 лучших фильмов по версии IMDb” (в документе отобразим при этом лишь часть результата с помощью функции Short):

    In[2]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_5.gif

    Out[3]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_6.png

    Теперь выделим ссылки на фильмы, приведенные на странице в таблице:

    In[4]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_7.png

    Out[4]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_8.png

    Создадим функцию, которая подгрузит и сохранит символьное представление HTML кода страниц каждого из фильмов:

    In[5]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_9.gif

    Вспомогательные функции


    Создадим набор вспомогательных функций, который понадобится нам для обработки погруженного символьного HTML:

    • Функция для удаления HTML-оберток, оставляющая только данные:

    In[8]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_10.png

    • Функция, которая определяет, может ли быть некоторая строка словом на русском языке (т. е. состоит из букв русского алфавита или дефиса):

    In[9]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_11.png

    In[10]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_12.gif

    • Функция, которая определяет, может ли быть некоторая строка словом на русском или английском языке (т. е. состоит из букв русского, английского алфавита или дефиса):

    In[12]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_13.png

    In[13]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_14.gif

    • Функция, преобразующая (в строке) заглавные буквы русского алфавита в прописные:

    In[15]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_15.png

    In[16]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_16.png

    • Для анализа описаний фильмов нам потребуется информация о словах русского языках и связях между формами одного и того же слова. Подгрузим морфологический словарь русского языка, созданный академиком Андреем Анатольевичем Зализняком:

    In[17]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_17.png

    Out[17]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_18.png

    • Обработаем данные словаря, составив на его основе список слов русского языка (russianWords) и список правил замены форм слов русского языка в их стандартную форму (russianWordsStandardForm):

    In[18]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_19.png

    В словаре содержится 2 645 347 слов:

    In[19]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_20.gif

    Out[19]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_21.png

    Out[20]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_22.png

    • Создадим функцию, которая проверяет, содержится ли слово в словаре, а также функцию, преобразующую русское слово в его стандартную форму:

    In[21]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_23.png

    In[22]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_24.png

    Примеры работы функций:

    In[23]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_25.png

    Out[23]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_26.png

    In[24]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_27.png

    Out[24]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_28.png

    • Создадим функцию, которая будет устанавливать, является ли слово прилагательным:

    In[25]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_29.png

    In[26]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_30.png

    Обработка данных


    Теперь можно обработать данные каждого из фильмов. При этом на выходе в переменной filmsData будет храниться база данных информации о фильмах, построенная на основе функции Association, что позволит нам очень легко обращаться к данным.

    In[27]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_31.png

    In[29]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_32.gif

    Пример обращения к сформированной базе по номеру фильма:

    In[31]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_33.png

    Out[31]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_34.png

    Пример обращения с запросом о режиссёре и годе выхода каждого из фильмов:

    In[32]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_35.png

    Out[32]//Short=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_36.png

    Немного статистики на основе данных


    Для начала, просто сформируем коллаж из постеров всех фильмов:

    In[33]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_37.png

    Out[33]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_38.png

    Построим распределение количества фильмов в зависимости от года:

    In[34]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_39.png

    Out[34]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_40.png

    Построим распределение фильмов по их продолжительности:

    In[35]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_41.png

    Out[35]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_42.png

    Построим распределение фильмов по их продолжительности и году выпуска:

    In[36]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_43.png

    Out[36]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_44.png

    Первые 10 актеров по количеству фильмов, в которых они сыграли:

    In[37]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_45.png

    Out[37]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_46.png

    Первые 10 режиссёров по количеству фильмов, которые они сняли:

    In[38]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_47.png

    Out[38]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_48.png

    Первые 10 сценаристов по количеству фильмов, сценарий к которым они написали:

    In[39]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_49.png

    Out[39]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_50.png

    Первые 10 композиторов по количеству фильмов, музыку к которым они написали:

    In[40]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_51.png

    Out[40]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_52.png

    Первые 10 стран по количеству фильмов, которые были в них сняты:

    In[41]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_53.png

    Out[41]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_54.png

    Первые 10 жанров по количеству фильмов, которые к ним относятся:

    In[42]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_55.png

    Out[42]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_56.png

    Для тех, кого интересуют жанры кино, могу порекомендовать написанную некоторое время назад статью “Фильмы и Mathematica: импорт и обработка информации из базы данных IMDB”, в которой, в частности, получено следующее распределение фильмов по жанрам:

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_57.png

    Функция, определяющая расстояние между фильмами


    Для определения меры различия двух списков объектов мы будем использовать обобщение коэффициента (меры) Чекановского-Съёренсена:

    In[43]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_58.gif

    Пример:

    In[45]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_59.png

    Out[45]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_60.png

    Для определения близости описаний с помощью этого коэффициента создадим функцию, выбирающую из описания фильма слова русского языка с переводом их в стандартную форму:

    In[46]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_61.png

    Пример работы функции (дополнительно было посчитана частота каждого слова с помощью функции Tally, при этом частоты были отсортированы по их уменьшению):

    In[47]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_62.png

    Out[47]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_63.png

    Теперь создадим функцию, определяющую степень близости фильмов между собой. Она представляет собой нормированную на единицу сумму нескольких параметров с разными весами. Всего взято 11 параметров (степеней) сходства: описание фильма, жанр(-ы), режиссёр, сценарист(-ы), актёры, оператор(-ы), композитор(-ы), страна(-ы) производства, год выхода, длительность, близость постеров. При этом можно задавать им разные веса, но по умолчанию они будут одинаковы.

    In[48]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_64.gif

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

    In[62]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_65.png

    Вычислим все меры близости (расстояния) между фильмами:

    In[63]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_66.png

    Анализ связей между фильмами


    Изучим связи между фильмами с помощью методов теории графов, а именно с помощью теории о структуре комьюнити в графах. Для этого создадим функцию на основе CommunityGraphPlot:

    In[64]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_67.png

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

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_68.png

    In[65]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_69.png

    Out[65]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_70.png

    In[66]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_71.png

    Out[66]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_72.png

    In[67]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_73.png

    Out[67]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_74.png

    In[68]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_75.png

    Out[68]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_76.png

    In[69]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_77.png

    Out[69]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_78.png

    In[70]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_79.png

    Out[70]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_80.png

    In[71]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_81.png

    Out[71]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_82.png

    In[72]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_83.png

    Out[72]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_84.png

    Построение оптимальной последовательности просмотра фильмов


    Мы проделали довольно большую работу и теперь, наконец, можем построить оптимальную последовательность просмотра фильмов:

    In[73]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_85.png

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

    In[74]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_86.png

    Таблица оптимальной последовательности просмотра фильмов из списка 250 лучших фильмов по версии IMDb
    Out[74]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_87.png

    Также, можно отобразить её в виде плаката из постеров (последовательность просмотра фильмов при этом будет слева направо, сверху вниз):

    In[75]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_88.png

    Out[75]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_89.png

    Мы может также рассмотреть оптимальные последовательности по отдельным критериям:

    Последовательность просмотра на основе описания фильма
    In[76]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_90.png

    Out[76]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_91.png

    Последовательность просмотра на основе жанра фильма
    In[77]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_92.png

    Out[77]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_93.png

    Последовательность просмотра на основе актерского состава фильма
    In[78]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_94.png

    Out[78]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_95.png

    Последовательность просмотра на основе режиссёра фильма
    In[79]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_96.png

    Out[79]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_97.png

    Последовательность просмотра на основе сценаристов фильма
    In[80]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_98.png

    Out[80]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_99.png

    Последовательность просмотра на основе композиторов фильма
    In[82]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_102.png

    Out[82]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_103.png

    Последовательность просмотра на основе длительности фильма
    In[83]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_104.png

    Out[83]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_105.png

    Последовательность просмотра на основе постера фильма
    In[84]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_106.png

    Out[84]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_107.png

    Последовательность просмотра на основе страны производства фильма
    In[85]:=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_108.png

    Out[85]=

    Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_109.png

    Заключение


    Надеюсь, что мой пост смог заинтересовать вас, а некоторые идеи и программы, представленные в нем окажутся вам полезны. Безусловно, можно придумать множество путей применения этих алгоритмов, их дальнейшего расширения и совершенствования. Многие вещи были специально упрощены мной, так как не все готовые коды могут быть выложены полностью в свободном доступе. Думаю, что если вам будет интересно, вы можете самостоятельно создать парсер с КиноПоиска или IMDB напрямую (в последнем случае вам может помочь статья о подгрузке и анализе информации из баз данных IMDB, выложенных этим ресурсов в свободном доступе) и на его основе уже произвести еще более подробный и качественный анализ кино, а также улучшить полученную в этой статье оптимальную последовательность просмотра фильмов. Надеюсь, что все эти задачи заинтересуют и вас!

    Ресурсы для изучения Wolfram Language (Mathematica) на русском языке: http://habrahabr.ru/post/244451
    Wolfram Research 45,82
    Wolfram Language, Mathematica, Wolfram Alpha и др.
    Поделиться публикацией
    Комментарии 36
    • +5
      Я долго думал, как описать этот пост и его автора, но цензурного ничего в голову не лезет…
      Просто шикарно.
    • +5
      Побег из Шоушенка везде на 1м месте?
      • +1
        Просто потому, что с него начинается поиск последовательности.
        • +3
          Насколько я вижу, вся магия происходит в FindShortestTour. Какой конкретно алгоритм используется — сходу непонятно — в том числе непонятно, предполагается ли, что путь должен быть замкнутым и минимизируется длина цикла — хотя на первый взгляд, по условию задачи — речь не о цикле, а о поиске кратчайшего пути обхода N точек. Если это так, то это в чистом виде задача коммивояжёра и там оптимальное решение не всегда будет начинаться с одной и той же точки.

          Тривиальный контрпример: поиск кратчайшего пути на 3 точках A, B, C, где |AB|=1, |BC|=10, |AC|=1 => кратчайший путь B-A-C (он же C-A-B) длины 2, а любой путь, начинающийся с A будет очевидно длиннее (A-B-C или A-C-B — все получается по 11).
          • +1
            Путь замкнут, но, естественно, последний элемент списка устранен, чтобы не дублировать первый (функция Most).

            В эту функцию «зашито» несколько методов: «AllTours», «CCA», «Greedy», «GreedyCycle», «IntegerLinearProgramming», «OrOpt», «OrZweig», «RemoveCrossings», «SpaceFillingCurve», «SimulatedAnnealing» и «TwoOpt».

            Ввиду того, что число точек в данной задаче невелико, автоматически применяется «IntegerLinearProgramming».
            • 0
              Вообще, я так понимаю, если хочется решить таки задачу «побывать в каждой точке полного графа ровно 1 раз с минимальной стоимостью», то это она по сути сводится к задаче коммивояжера => получению гамильтонова цикла => дополнительному поиску, какое ребро в этом цикле выгоднее всего разорвать (очевидно, ребро с максимальной стоимостью), чтобы, соответственно, запустить путь начиная с одной точки разрыва, чтобы он в итоге пришел в другую точку.

              Я так понимаю, это должно быть в целом несложно дореализовать в вашем алгоритме в Mathematica?
              • 0
                Это и сделано.
                Для этого служат 3 основные функции: FindShortestTour, FindHamiltonianCycle и HamiltonianGraphQ.
                • 0
                  Где же сделано-то? В filmsOptimalSequence по сути единственное, что делается — это вызывается Most(FindShortestTour(...)). В свою очередь FindShortestTour ищет цикл, а вот где его оптимально разорвать — никто не ищет, Most тупо разрывает на последнем элементе (т.е. по сути — первом попавшемся). Если его разорвать на каком-то другом элементе — вероятно, общая сумма расстояний между фильмами в цепочке будет ниже.
                  • 0
                    Может быть я выразился не очень ясно. FindShortestTour решает задачу коммивояжера.
            • 0
              Что касается вашего контрпримера — неравенство треугольника не выполнено.
              В каком пространстве этот путь будет существовать, чтобы существовал такой треугольник?
              • 0
                Никто не говорил, что это длины прямых в двумерном пространстве. Это могут быть просто стоимости, времена путешествия или какие-то подобные метрики. Есть 3 города и прямая дорога между B и C проходит через горный перевал, поэтому ехать 10 часов. Если объехать с заедом в A, т.е. B-A-C, то получается всего 2 часа.
                • –3
                  Тогда и расстояние между B и C будет 2 часа, а не 10. Неравенство треугольника о том и говорит, что расстояние есть кратчайший путь.
              • 0
                Вот простейшее решение задачи, о которой говорите вы:



                Код для копирования
                distanceMatrix={{\[Infinity],1,1},{1,\[Infinity],10},{1,10,\[Infinity]}};
                distance[pts_]:={pts,Total[Extract[distanceMatrix,Partition[pts,2,1]]]};
                fspf=FindShortestPath[WeightedAdjacencyGraph[distanceMatrix]];
                distance /@ Select[fspf@@@Subsets[{1,2,3},{2}],Length[#]==Length[distanceMatrix]&]
                • 0
                  Ну, это по сути совсем полный перебор, если я правильно понимаю. Сколько будет вычисляться такое на графе фильмов из 250 точек? Есть подозрение, что очень долго.
                  • 0
                    Я написал вам, что это простейшая реализация.
          • +1
            Интересная Огромная, интересная и сложная реализация, но не проще ли было бы распарсить через регулярки лишь imdb на любой прикладном языке, залить это дело в ДБ (к примеру MySQL), а далее проявить магию SQL для получения тех или иных выборок?
            Конечно графики придется реализовывать через сторонний софт или библиотеки (например на JS+CSS).
            • +4
              IMDb не имеет статей на русском, к сожалению. Так как я хотел включить в анализ описаний фильмов в функцию расстояния, то это критично. Про КиноПоиск я написал в начале — не очень хочется иметь дело с юр. вопросами, хотя полный парсер с него у меня есть, но показывать его нет возможности.

              Что касается баз данных — то можно их подключать к Mathematica (Database Connectivity), но в рамках данной статьи это излишне, так как можно очень удобно пользоваться встроенным форматом баз данных (Association и Dataset).

              В целом то, о чем говорите вы — скорее второй шаг после того, как все R&D сделано в Mathematica, и то, только если необходимо все ставить на «промышленные рельсы». Идея статьи — именно возможность быстрой разработки новых объектов, алгоритмов, реализация идей.
              • +15
                распарсить через регулярки
                лишь imdb
                залить это дело в ДБ (к примеру MySQL)
                проявить магию SQL
                графики придется реализовывать через сторонний софт или библиотеки (например на JS+CSS).

                Хм, пожалуй нет, не проще.
              • +1
                Стоило учесть серии фильмов. IV и V эпизоды Звёздных Войн, например, рядом, а VI от них фильмов через двадцать. С Властелином Колец, кстати, удачно получилось, хоть порядок и перепутан.
                • +1
                  Да, согласен с вами. Это интересная идея и ее можно было бы сделать через анализ названий, на основе уже имеющихся конструкций:

                  In[1]:=



                  Out[3]:=



                  Код для копирования
                  filmSeriesQ[PatternSequence[{i_,j_}]/;i>j]:=filmSeriesQ[{j,i}]

                  filmSeriesQ[{i_,j_}]:=filmSeriesQ[{i,j}]=Module[{lcs,f1,f2,replaceEnd,whiteSpaceCount},
                  {f1,f2}=filmsData[[{i,j},«название»]];

                  replaceEnd=StringReplace[#,":"~~___:>""]&;

                  lcs=replaceEnd[LongestCommonSubsequence@@{f1,f2}];

                  whiteSpaceCount=StringCount[StringTrim@lcs," "]+1;

                  Quiet@If[Or[UnsameQ@@(StringSplit[#][[1;;whiteSpaceCount]]&/@{lcs,replaceEnd@f1}),StringLength[lcs]<=4],

                  False,

                  And[StringMatchQ[f1,lcs~~x___],StringMatchQ[f2,lcs~~x___],Or@@(StringMatchQ[#,lcs~~x___/;Not[StringFreeQ[x,Alternatives@@({":"}~Join~(ToString/Range[0,9]))]]]&/@{f1,f2}),

                  Equal@@(StringFreeQ[#,"."]&/@{f1,f2})]]];

                  filmsData[[#,«название»]]&/@(DeleteDuplicates/@(Flatten/Gather[DeleteDuplicates[Sort/Cases[Table[{i==j,filmSeriesQ[{i,j}],{i,j}},{i,1,Length[wikiFilmPagesData]},{j,1,Length[wikiFilmPagesData]}],{False,True,x_}:>x,Infinity]],Intersection[#1,#2]=!={}&]))
                • +12
                  Это все весьма занимательно, но не имеет отношения к заголовку. В чем оптимальность какой-либо из придуманных последовательностей? Почему я должен захотеть посмотреть фильмы в порядке близости их постеров? Я получу какой-то особенный кайф при этом?

                  Я ожидал увидеть какой-то глубокий анализ на основе массива оценок, например те, кто смотрят такой-то драматический фильм сразу после такого-то комедийного, ставят выше в среднем оценки, таким образом метрикой оптимальности последовательности будет ожидаемый средний балл при просмотре всех 250 фильмов, интегральный показатель полученных впечатлений.
                  • +1
                    Анализ постеров — это несущественный элемент статьи и построенной метрики. Жаль, что вы обратили на это внимание, хотя я специально вначале говорил недостатки метрики, созданной в статье Маттиаса.

                    Довольно серьезный показатель — анализ описаний фильмов.

                    То о чем говорите вы — потребовало бы подгрузки комментариев всех фильмов (но уже с КиноПоиска) и доступа к статистике переходов и оценок пользователей (хотя бы на том же сайте). Реализовать это — более чем возможно, но не в рамках статьи и исходники и подробное описание таких проектов уже вряд ли можно выкладывать, так как это в принципе это уже — коммерческий продукт — для тех же телекомпаний, которые хотят зимними вечерами привлечь к экранам как можно больше людей, предлагая им оптимально показывать фильмы (не обязательно топовые).
                    • +3
                      В комментарии я намекнул, что если фильмы похожие, даже по идее/сюжету, вовсе не значит что их надо смотреть подряд. Умозрительно кажется, что даже скорее наоборот, чтобы одна тема не надоедала. Хотя кратчайший обход очень легко превратить в длиннейший.
                      • +3
                        Вы можете заменив функцию расстояния f на 1-f смотреть максимально разные фильмы.
                        Если хотите, развейте идею поста в предложенном вами направлении, думаю, это будет интересно.
                      • 0
                        Можно было проследить еще авторов правок к статьям в википедии. Какой-никакой, но уже человеческий фактор группировки.
                    • +4
                      Статья любопытная, но ничего общего с заголовком не имеющая. Эти 250 фильмов можно смотреть в любом порядке (не считая фильмов с сиквелами). Плохих фильмов в этом списке нет, в общем-то. Shuffle — и вперёд!
                      • –3
                        Не хотите спрятать под спойлер краткое изложение сюжета Интерстеллара? ) А то вдруг кто-то еще не посмотрел?
                        • –1
                          Крутейшая статья по wolfram language за последнее время, однозначно. Правда, как по мне, можно было обойтись без такого количества изображений, по крайней мере, без графов, которые по смыслу полностью повторяют таблички из ячеек out с 37 по 41. Да, красиво. Но нужно? Вряд ли. У человека, незнакомого с языком, может сложиться впечатление, что это просто язык для создания красивых визуализаций, а никак не для решения серьёзных научных или инженерных задач.
                          • 0
                            Спасибо за похвалу, но позволю себе не согласиться. Графы все же отражают структуру связей между фильмами, в то время как пути — это всего лишь сухая выжимка в виде оптимального гамильтонова пути.

                            Соглашусь, что обилие картинок может создать такое впечатление, правда, думаю, лишь при беглом просмотре.
                            • 0
                              Конечно, вдумчивый просмотр кода показывает совсем другое. :) Он шикарен, я вновь восхищен. Мне до вас еще как до Луны пешком. :)
                          • +1
                            Как-то странно алгоритм предлагает смотреть «крёстных отцов». Сперва второй, а потом первый. Причём сразу один за другим :)
                            • 0
                              Выше AraneusAdoro по сути говорил об этом, в ответе приведен код для получения серий фильмов, так что можно затем учитывать их последовательность или рассматривать их как единое целое.
                            • 0
                              Интересно было бы сравнить с анализом английских описаний — там, по идее, связи будут больше, и может даже другие, поскольку обилие русских синонимов умещаются в двух словах.
                            • 0
                              Офигенно! Осталось только теперь найти время все это посмотреть.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое