Студенческий контест по Machine Learning Обучающие задачи Первый открытый контест ok.ru: Возраст по графу По мотивам онлайн-игр Задача с секретом Предсказание ССЗ ok.ru: Связи пользователей Прогноз отклика аудитории на интернет-опрос Telecom Data Cup Ответы Mail.ru (Хакатон, МФТИ) SNA Hackathon - Коллаборативная система SNA Hackathon - Картинки SNA Hackathon - Тексты
Участники
  • 1
    Никита Киселев
  • 2
    Юрий Коломейцев
  • 3
    Владислав Мац
  • 4
    Алексей Васильев
  • 5
    Антон Жевнерчук
Задача "Раскрыть связи пользователей"

Данные

Социальный граф (trainGraph)

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

ID_пользователя1 {(ID_друга1,маска1), (ID_друга2,маска2),...}

Матрица партиционирована по ID пользователя на 16 файлов, каждый из которых сжат GZip­ом. Пары в списке связей отсортированы по ID друга (по возрастанию). Пример записей из графа:

1424 {(846,0),(1691,256),(2338,0),(4950,0),(7238,0),(7433,0)}
4128 {(49747,0),(53568,0),(61734,1024),(274477,0),(307631,0),(365098,1024)}

В маске связи могут быть установлены следующие биты:

1. Love
2. Spouse
3. Parent
4. Child
5. Brother/Sister
6. Uncle/Aunt
7. Relative
8. Close friend
9. Colleague
10. Schoolmate
11. Nephew
12. Grandparent
13. Grandchild
14. College/University fellow
15. Army fellow 
16. Parent in law
17. Child in law
18. Godparent
19. Godchild
20. Playing together

Помимо перечисленных битов 1-20 в маске отношений может быть установлен 0-й бит. Этот бит играет чисто техническую роль и не имеет практического смысла. В итоге, например, отношение типа Child может кодироваться числами 16 или 17.

Демография пользователей (coreDemography)

Данные о демографии предоставлены для тех же пользователей, что и информация о социальных связях в формате:

userId create_date birth_date gender ID_country ID_Location loginRegion

Где:

  • userId — идентификатор пользователя
  • create_date — дата создания пользовательского аккаунта (количество миллисекунд от 01.01.1970)
  • birth_date — дата рождения пользователя (количество дней от 01.01.1970, может быть отрицательным!)
  • gender — пол пользователя (1 — мужчины, 2 — женщины)
  • ID_country — идентификатор страны, указанной в профиле
  • ID_Location — идентификатор региона/города, указанный в профиле.
  • loginRegion — идентификатор региона, откуда чаще всего логинится пользователь (может отсутствовать!)

Пример данных:

16460783 1182885174073 486 2 10414533690 1078547 85
16467391 1176953226317 4669 2 10414533690 1384327 85
16467889 1169816093060 6861 2 10414533690 33438 
16468013 1172074147460 5360 2 10415971874 4000749 1
16471027 1182034019343 6311 2 10414533690 3047069 11
16474162 1173115608560 5567 2 10414533690 3868434 36
16476386 1151057658677 4351 2 10414533690 3385314 11

Демография партиционирована по той же схеме, что и граф, но не сжата (передается в виде открытых текстов). 

Задача

Для пользователей из файла prediction.csv часть связей в предоставленном социальном графе скрыта и задачей участников является максимально полно и точно раскрыть их. Скрытые связи удовлетворяют следующим условиям:

  • Оба пользователя принадлежат к исходным 107474 пользователей
  • Хотя бы один из пользователей имеет ID, остаток от деления которого на 11 равен 7 (ID % 11 == 7)
  • Связи скрыты симметрично (т.е., если скрыта связь ID1 -> ID2, то связь ID2 -> ID1тоже скрыта

Из всех связей, удовлетворяющих указанным условиям, сокрытию подверглось порядка 10%. Связи требуется предсказывать только для пользователей из файла prediction.csv. То есть, включать в прогноз симметричные связи не нужно.

Результаты прогноза нужно представить в формате CSV файла вида:

ID_пользователя1,"ID_кандидата1.1 ID_кандидата1.2 ID_кандидата1.3" 
ID_пользователя2,"ID_кандидата2.1 ID_кандидата2.2"

Список кандидатов в каждой строке должен быть отсортирован по предсказанной релевантности кандидатов (по убыванию, саму релевантность при этом в файл писать не надо).

Пример результатов:

2405,"11441387 14673913 12880802 12284483"
2669,"5862934 3996243 1358375 7716458 548171 8153785 7747238 6766906"

Оценка

Результаты участников буду оцениваться с помощью метрики Normalized Discounted Cumulative Gain (NDCG). Метрика будет рассчитываться отдельно по каждому из пользователей, для которых есть скрытые связи, а затем усредняться и домножаться на 1000 для удобства отображения.

Если для какого-либо пользователя из контрольной выборки не будет предложено ни одного кандидата, то значение метрики для него будет считаться за 0.

Пользователи из контрольной выборки, у которых не было скрыто ни одной связи, не учитываются при расчете метрики

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

К рассмотрению принимаются прогнозы, удовлетворяющие следующим критериям:

  • Прогноз содержится в текстовом файле
  • Каждая строка содержит ID пользователя, для которого предсказываются связи и список кандидатов
  • Файл содержит ровно одну строку для всех ID пользователей из файла prediction.csv
  • Рекомендованные списки кандидатов не содержат дубликатов
  • Файл содержит не более 1000000 кандидатов
  • Размер файла не превышает 3Мб

Файлы с прогнозами, не удовлетворяющие указанным условиям, не оцениваются.