Открыть список
Как стать автором
Обновить
3609.31
Рейтинг
RUVDS.com
VDS/VPS-хостинг. Скидка 10% по коду HABR

Взлом по любви. Как математик взломал алгоритм сайта знакомств и нашел идеальную девушку

Блог компании RUVDS.comИнформационная безопасностьЧитальный залЛайфхаки для гиков


Как редактору журнала «Хакер», мне часто приходится писать о взломах. Все подобные случаи обычно связаны с хищением приватной информации, денег, либо и того и другого сразу. Очень редко хакер преследует какие-то иные цели: заявить о себе, отомстить бывшему работодателю или устроить акт вандализма по политическим мотивам. Издание Wired поведало читателям об одной удивительной истории: 35-летний математик из Калифорнии взломал алгоритм сайта знакомств, чтобы найти себе идеальную девушку, причем это ему, как ни странно, удалось. И хотя речь здесь идет не о взломе в классическом понимании, а, скорее, о Data Mining, эта история заслуживает подробного рассказа.

Крис МакКинли (Chris McKinlay) родился в пригороде Бостона, и в 2001 году окончил колледж Миддлбери по специальности «китайский язык». В августе того же года он устроился на полставки переводчиком с китайского в нью-йоркскую компанию, снимавшую офис на 91-м этаже северной башни Всемирного Торгового Центра. Спустя пять недель, 11 сентября 2001 года, Крис должен был явиться на работу к двум часам дня. Он еще крепко спал, когда в 8:46 утра первый самолет врезался в небоскреб, где располагался офис его компании. Увидев по телевизору, как здание Всемирного Торгового Центра падает и оседает на землю в клубах дыма и пыли, Крис крепко задумался о скоротечности нашего земного существования о том, чем он на самом деле хотел бы заниматься в своей жизни.


Крис МакКинли

Старый приятель, учившийся когда-то в Колумбийском университете, заинтересовал Криса блэкджеком — именно в этой карточной игре впервые проявились математические и аналитические способности МакКинли. Бросив переводы, он присоединился к команде профессиональных игроков, и в течение нескольких лет мотался между Нью-Йорком и Лас-Вегасом, считая карты в казино и зарабатывая этим занятием порядка 60 000 долларов в год. Увлекаясь блэкджеком и покером, МакКинли строил математические модели для выработки оптимальных стратегий игры: это занятие приносило ему не только деньги, но и удовольствие.

Пробудившийся благодаря азартным играм глубокий интерес к точным наукам вновь направил Криса в учебную аудиторию: он поступил в магистратуру Калифорнийского университета в Лос-Анжелесе, а позже — получил степень Ph.D. по прикладной математике. Однако еще в процессе написания диссертации по теме «Крупномасштабная обработка данных и параллельные численные методы» МакКинли пришел к выводу, что его по-прежнему устраивает в собственной жизни далеко не все. Главной причиной тревог 35-летнего математика было одиночество.

А не спеть ли мне песню о любви?


Несмотря на то, что в густонаселенном Лос-Анжелесе и ближайших пригородах согласно статистике проживает не менее нескольких миллионов женщин фертильного возраста, Крису МакКинли никак не удавалось отыскать себе подходящую пару, которая могла бы претендовать на почетное звание девушки его мечты. После очередного мучительного расставания и крушения надежд на долгие романтические отношения он зарегистрировался на сайте знакомств OkCupid — одном из самых популярных на североамериканском континенте.

В отличие от знаменитого «Тиндера», появившийся в 2004 году OkCupid (который принадлежит, к слову, тем же самым владельцам) претендует на научный подход в вопросах строительства отношений — как раз то, что нужно ученым, программистам, хакерам и прочим нердам. Сайт, разработанный четырьмя студентами-математиками из Гарвардcкого университета, быстро набрал небывалую популярность в США, попав в ТОП-10 лучших служб знакомств по версии журнала Time за 2007 год. Его основное отличие от других аналогичных площадок заключается в том, что после бесплатной регистрации пользователю предлагается ответить на вопросы нескольких довольно-таки подробных анкет, с помощью которых составляется его психологический портрет. Алгоритмы OkCupid подбирают пары исходя из общих предпочтений, интересов и сходства анкетных данных. Соответственно, чем более подробно заполнен профиль, тем более подходящую кандидатуру способен отыскать сайт знакомств, но тем меньше математических шансов на удачное совпадение.

Анкеты OkCupid содержат порядка тысячи вопросов, но обычно пользователи выбирают не более 350 из них. Чаще всего они указывают свое отношение к алкоголю, курению и религии, выбирают подходящий возраст, пол и прочие тактико-технические характеристики потенциального партнера. Затем конкретизируют собственные предпочтения в сфере музыки, искусства и кино, а также отвечают на уточняющие вопросы из серии «что из перечисленного больше всего нравится вам в этом фильме?» или «какие черты характера привлекают вас в противоположном поле?». Кроме того, пользователь может указать категорически неприемлемые для него варианты ответов со стороны потенциального партнера, и наоборот те, которые могут его устроить, а еще оценивает субъективную значимость каждого вопроса-критерия по шкале от «неважного» до «обязательного».


>Типичная анкета пользователя на OkCupid.com

Личный опыт Криса МакКинли показал, что с сайтом OkCupid отношения у него как-то не складываются. При наличии миллионов активных пользователей, из которых примерно 80 000 — женщины из Лос-Анжелеса, его профиль совершенно не привлекал внимания противоположного пола. Сайт учитывает совпадения только в том случае, если оба пользователя ответили на одни и те же вопросы анкеты, а выбранные Крисом варианты не пользовались популярностью у девушек. Более того: из предложенных бездушными алгоритмами пары десятков потенциальных невест на сообщения Криса откликнулись лишь несколько. Шесть состоявшихся свиданий подтвердили опасения МакКинли о том, что подобная методика знакомств — пустая трата времени. А раз она не приносит должного результата, нужно менять алгоритм: этот принцип прекрасно работал в мире карточных игр. Почему бы для налаживания личной жизни одного конкретно взятого человека, то есть своей собственной, не воспользоваться достижениями современной науки? — подумал Крис. И решил вооружиться математикой с благородной целью: найти на OkCupid идеальную девушку, построить с ней отношения и обрести, наконец, счастье, о котором он так долго мечтал.

Поразмыслив, МакКинли разработал хитрый план действий. Он решил выяснить, какие именно вопросы в анкетах на сайте OkCupid пользуются популярностью у лос-анжелесских красавиц. Владея этой информацией, он мог бы создать новый профиль, честно ответить на полученный набор самых «рейтинговых» вопросов, и, похрустывая попкорном, выбирать из тысяч анкет калифорнийских девчонок, ответы которых совпали с его собственными. Однако чтобы приготовить рождественскую индейку, нужна как минимум сама индейка, а чтобы «взломать» логику сайта знакомств, требуются исходные данные, причем в достаточном для анализа количестве.

Взломай это!


Для начала Крис собрал полный ассортимент вопросов, которые задает своим пользователям OkCupid, и рассортировал их по тематике. Всего получилось семь групп. Теперь нужно было извлечь данные из анкет пользователей, которые подходили ему в качестве потенциального партнера: гетеросексуальные и бисексуальные женщины в возрасте от 25 до 45 лет. OkCupid дает возможность просмотреть ответы других юзеров, но только на те вопросы, на которые ответил ты сам. Чтобы обойти это ограничение, Крис создал 12 фейковых учетных записей и написал скрипты на Python для управления этими аккаунтами. Поддельные пользователи случайным образом отвечали на определенный блок вопросов в анкете, а затем посещали профайлы девушек, подходивших Крису по возрастным критериям, и собирали их варианты ответов в специально созданную базу данных.

С нескрываемым удовольствием Крис наблюдал, как его детище принялось шерстить сайт знакомств. Однако вскоре после того, как база наполнилась информацией о первой тысяче аккаунтов, МакКинли столкнулся с серьезной технической проблемой: механизмы безопасности OkCupid зафиксировали подозрительную активность на сайте и принялись банить его ботов одного за другим. За решением этой задачи ученый обратился к своему приятелю — нейробиологу Сэму Торриси, который преподавал ему теорию музыки в обмен на уроки математики. Торриси и сам был завсегдатаем OkCupid. Проникшись идеей, он согласился на предложение Криса установить на собственном компьютере программу, которая фиксировала все его действия при просмотре анкет. Заполучив в свое распоряжение трекинг движений мыши Сэма Торриси, сведения о переходах по ссылкам и данные о скорости нажатия клавиш, МакКинли перепрограммировал ботов таким образом, чтобы они имитировали действия живого пользователя. В результате администрация сайта перестала банить его фейковые аккаунты, и Крис сумел собрать данные 20 000 анкет, содержащих более 6 млн ответов на вопросы. Диссертация была временно заброшена: МакКинли фактически поселился в своей каморке, расположенной в одном из кампусов Калифорнийского университета, и притащил из дома матрац, который раскладывал прямо на столе, когда ему хотелось спать. Изучение данных с сайта знакомств захватило его полностью, превратившись в своего рода маниакальную идею.


То самое здание Калифорнийского университета в Лос-Анжелесе

Собранную информацию предстояло проанализировать, выявив закономерности среди десятков тысяч анкет. Для этого МакКинли использовал модифицированный алгоритм кластеризации под названием K-modes, готовая реализация которого имеется в каталоге PyPi для Python. Алгоритм K-modes, разработанный когда-то исследователями из компании Bell Labs, использует принцип категоризации сущностей на основе заданных параметров. Экспериментируя с этими параметрами, Крис сумел разделить 20 000 наиболее релевантных его запросам анкет на семь отдельных групп в соответствии с результатами анкетирования. Получились выборки, с которыми можно было работать дальше. С помощью ботов МакКинли собрал данные еще 5000 анкет женщин из Лос-Анжелеса и Сан-Франциско, заходивших на OkCupid в течение последнего месяца. Обработка этой выборки с помощью алгоритма K-modes дала похожий результат: анкеты отсортировались в аналогичных пропорциях. Методика сработала!

После этого математику оставалось только проанализировать полученные выборки. Одну из них он отбросил сразу, поскольку там преобладали слишком зрелые для него женщины, другую — из-за того, что хозяйки таких анкет показались ему чересчур зацикленными на религии. Осталось несколько групп: девушки около 25 лет с артистичным складом характера и творческими профессиями — дизайнеры, редакторы, артистки и музыканты, а также смежная группа с аналогичными параметрами, куда входили женщины чуть постарше. Именно психологические профили девушек в этих двух выборках в наибольшей степени соответствовали запросам Криса МакКинли.


В Калифорнийском университете, как и во многих учебных заведениях США, есть своя бейсбольная команда и учатся симпатичные чирлидеры

Осталось сделать следующий шаг к успеху. Крис зарегистрировал на OkCupid два профиля и оптимизировал каждый под соответствующую целевую группу. На странице одного из них он разместил собственное фото в образе спортсмена-верхолаза, сделанное на ближайшем скалодроме, в другом профиле Крис предстал в романтичном образе музыканта, исполняющего на вечеринке песню под гитару. Затем МакКинли подготовил собственную биографию в соответствии с предпочтениями, которые указывали в своих анкетах интересующие его девушки, и выбрал 500 вопросов, пользовавшихся наибольшей популярностью в обеих группах профайлов. На вопросы Крис решил отвечать честно, поскольку от его ответов напрямую зависела релевантность поиска потенциальных партнерш.

А вот при оценке важности каждого вопроса МакКинли все же решил немного сжульничать, доверив расстановку рейтингов скрипту, который использовал в своей работе принципы машинного обучения. Например, на вопрос «Независимо от планов на будущее, что для вас важнее сейчас: секс или любовь?» в обоих профилях он ответил одинаково: «любовь». Но на страничке для более молодой аудитории он, в соответствии с рекомендацией программы, пометил этот вариант ответа как «очень важный», а в профайле, оптимизированном под более зрелых женщин — как «обязательный».

Закончив с анкетами, Крис решил посмотреть, сколько вариантов знакомств предложит ему OkCupid… и не поверил своим глазам. По умолчанию сайт сортирует выдачу по уменьшению степени совпадения психологического профиля и интересов. МакКинли торопливо пролистал несколько страниц, но подходящие ему с точки зрения OkCupid девушки, ответы которых совпали с его собственными более чем на более 90%, все не заканчивались — в выборке оказалось более 10 000 красавиц со всей Америки.

Сайт OkCupid автоматически уведомляет пользователя, когда кто-то просматривает его профиль. Чтобы привлечь к себе внимание, МакКинли написал еще один скрипт, который от имени его аккаунта автоматически открывал анкеты женщин из Лос-Анжелеса разных возрастных групп: 1000 анкет дам в возрасте 41 года, затем еще 1000 на год помладше, и так — до 25-летних девушек. Скрипт обрабатывал строго определенное количество строк собранной Крисом базы в сутки, чтобы избежать возможной блокировки. И женщины стали заглядывать в профиль МакКинли, а потом посыпались первые сообщения. «Ты действительно знаешь китайский?», — писали ему заинтригованные девушки. — «Возможно, у нас много общего, пусть не в области математики, но наверняка в других интересных вещах. Твоя страничка выглядит интригующей!». Это был полный и безоговорочный успех. По крайней мере, Крису так казалось поначалу.

Встреча с реальностью


«30 июня МакКинли принял душ в спортзале Калифорнийского университета в Лос-Анджелесе и проехал на своем потрепанном Nissan через весь город на первое свидание», — рассказывает об этой истории Wired. Однако практическая часть эксперимента оказалась гораздо менее продуктивной, чем теоретическая. Первые три встречи с потенциальными претендентками на роль спутницы жизни закончились ничем: вопреки ожиданиям, у Криса не возникало взаимной симпатии с откликнувшимися на его анкету девушками. На третий раз он и вовсе накидался вместе с новой знакомой пивом в корейском ресторане, а наутро проснулся в гордом одиночестве, зато с жутким похмельем. Немного придя в себя, МакКинли зашел на OkCupid и отправил ей личное сообщение, но девушка не ответила. Реальная жизнь и реальное общение за пределами университетского кампуса оказались немного сложнее программирования и математики, в которых Крис, как выяснилось, разбирался намного лучше.

Этот случай, безусловно, расстроил математика, но не обескуражил его, ведь он по-прежнему получал порядка 20 сообщений ежедневно. Теперь у него появилась возможность выбирать: он игнорировал послания с пошлостями и глупыми шутками, и наоборот, вступал в переписку только с теми девушками, которые подробно рассказывали о себе, обладали чувством юмора или казались ему интересными. Если поначалу он вдумчиво готовился к каждому свиданию, репетировал собственные речи и тщательно продумывал интересные темы для бесед, то вскоре стал относиться к этому проще, устраивая по две встречи в день или просто договариваясь с девушкой пересечься где-нибудь в кафе или на пляже во время обеденного перерыва. В самом начале эксперимента он вступал в длительную переписку, сочиняя для потенциальных избранниц развернутые и подробные письма. Позже стал ограничиваться короткими сообщениями из разряда «Ты классно выглядишь. Хочешь встретиться?». Это работало.

Для экономии времени Крис придумал для себя набор правил, призванных повысить эффективность свиданий. Во-первых, он зарекся употреблять во время романтических встреч алкоголь, памятуя о неприятном опыте с корейским пивом. Во-вторых, решил не назначать рандеву в кино или на концертах — в общем, там, где какие-либо внешние факторы отвлекали бы его и девушку от общения друг с другом. И, наконец, в-третьих, МакКинли пришел к выводу, что лучше завершать знакомство сразу же, как только становится понятно, что он и потенциальная партнерша не подходят друг другу. Длящиеся отношения с туманными перспективами отвлекали его от основной цели — поиска своей единственной любви.

С ростом количества встреч аналитический ум МакКинли стал подмечать в происходящем кое-какие закономерности. Большинство юных девушек из группы «25+» проживали в восточной части Лос-Анжелеса и имели, как правило, более двух татуировок. Эту группу Крис назвал «Tatoo». Одинокие женщины старшего возраста часто оказывались обладательницами целого выводка собак среднего размера, которых они обожали. Таких кандидаток он решил называть «Dog». Некоторые девчонки знакомились только с новичками на сайте OkCupid, этих он отнес к группе «Зеленые». Другие были склонны к приключениям, их он окрестил по имени одной яркой представительницы данной категории — «Саманты». Всего подобных групп набралось семь.


Точный расчет и математический анализ — залог счастливой любви. Или нет? Иллюстрация Wired

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

К концу лета МакКинли провел 55 встреч, информацию о которых тщательно и кропотливо фиксировал в специально заведенном для этих целей «лабораторном журнале». Но только в трех случаях знакомство привело к повторному свиданию, и лишь одно повлекло за собой третье. Крис был в отчаянии: он почти поверил в то, что где-то в его математические расчеты закралась ошибка, ставящая под угрозу весь ход эксперимента.


Счастливая парочка — Крис МакКинли и Кристин Тьен Ван

Однажды утром в строке номер 88 лабораторного журнала Криса МакКинли появилась очередная запись: Кристин Тьен Ван, 28 лет, художница, студентка магистратуры факультета изящных искусств Калифорнийского университета Лос-Анжелеса, активистка, борющаяся за отмену тюрем. Совпадение их анкет составляло 91%. Они встретились в саду университетского кампуса и отправились в суши-бар, расположенный на территории колледжа. Там Кристин призналась своему спутнику, что внесла кое-какие изменения в собственный профиль и ответы на сайте знакомств, чтобы найти с помощью OkCupid как можно больше интересных парней. В порыве откровенности Крис поведал ей в ответ свою историю — всю как есть, ничего не скрывая. Он рассказал ей о том, что девушка стала очередной невольной участницей его математического эксперимента. «Это звучало ужасно цинично», — призналась потом Тьен Ван изданию Wired, — «настолько, что мне все это чертовски понравилось!». За первой встречей последовала вторая, затем третья, а спустя две недели молодые люди удалили свои анкеты на сайте OkCupid.

Happy End


После этого счастливого знакомства Крис вернулся к написанию заброшенной было диссертации и успешно защитил ее, получив докторскую степень. Сейчас он преподает математику в родном университете Лос-Анжелеса и мечтает снова поступить в аспирантуру — на сей раз музыкальном направлении. Кристин Тьен Ван окончила магистратуру и уехала на годовую стажировку в Катар. Она поддерживает связь с Крисом по скайпу, и время от времени навещает его в Калифорнии.

«Думаю, то, что я сделал, — это всего лишь автоматизированный, основанный на машинном обучении алгоритм, в целом повторяющий действия обычного пользователя сайта знакомств», — признался корреспонденту Wired Крис МакКинли. — «Каждый человек так или иначе пытается создать на OkCupid идеальный профиль, просто не у всех имеется столь же большой объем исходных данных для анализа».

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

Их отношения, начавшиеся в сети, получили свое закономерное развитие в том же формате: Крис сделал своей подруге предложение во время одного из сеансов связи по скайпу, и она ответила согласием. Надеемся, у них все будет хорошо, и Крис с Кристин станут жить как в сказке — долго и счастливо. Ведь математические алгоритмы OkCupid с высокой точностью определили, что они идеально подходят друг другу, и, похоже, не ошиблись. Ибо математика — точная наука, которая ошибается нечасто.

Теги:ruvdsokcupidвзломприложения для знакомствматематика
Хабы: Блог компании RUVDS.com Информационная безопасность Читальный зал Лайфхаки для гиков
Всего голосов 112: ↑98 и ↓14 +84
Просмотры60.5K

Похожие публикации

Лучшие публикации за сутки

Информация

Дата основания
Местоположение
Россия
Сайт
ruvds.com
Численность
11–30 человек
Дата регистрации
Представитель
ruvds

Блог на Хабре