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

Задача дана по мотивам лекции сотрудника компании "Одноклассники" Дмитрия Бугайченко для участников школы GO TO. Сама лекция опубликована на YouTube:

В рамках данной задачи вам предлагается раскрыть возраст пользователей социальной сети OK.ru, используя имеющиеся данные об их социальных связях и демографии друзей. Формат данных описан ниже, социальные связи даны для 470 тысяч пользователей, демография для 47 миллионов - те, для кого даны связи, и их друзья. Для 43 тысяч пользователей, из тех для кого даны связи, информация о демографии скрыта - это тестовые пользователи.

Идентификаторы тестовых пользователей записаны в отдельном CSV файле. В рамках задачи возраст этих пользователей надо предсказать. Качество результата будет оцениваться по метрике коэффициент детерминации (R2, https://en.wikipedia.org/wiki/Coefficient_of_determination).

Все предоставляемые данные анонимизированы, деанонимизация данных (восстановление реальных идентификаторов пользователей) запрещена.

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

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

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

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

5504 {(19410,0),(184537,0),(185652,0),(609494,0),(1377433,512),(1527570,0),(1591195,128),(2040791,0),(2112476,0),(2140987,0),(2155616,0),(2262647,1024),(2308685,1024),(2389991,0),(3215324,0),(3591486,0),(4241788,0),(4311469,0),(4317878,0),(4351881,0),(4463936,0),(4579783,0),(5250510,32),(5285085,0),(5618146,1024),(5652998,512),(6066562,1024),(6429418,8),(6526659,0),(7327696,1024),(7440222,256),(7622155,0),(7629448,0),(7838064,0),(8083721,0),(8414559,1024),(8439409,1024),(8608877,0),(9488834,4),(9672820,0),(9826171,0),(10489509,0),(10958560,0),(11631138,0),(11632869,0),(11694855,0),(11727417,0),(12181050,128),(12645522,0),(12655737,0),(12672181,0),(12676543,0),(12912271,0),(12974522,0),(13193962,0),(13308552,0),(13552447,1024),(13666534,0),(13704338,0),(13783702,1024),(14020934,1024),(14044121,0),(14578755,0),(14604008,256),(14674339,1024),(14686923,0),(14738133,0),(14870395,0),(14881870,0),(15790894,288),(15794149,0),(15947686,0),(16075120,32)}
7008 {(7765,0),(10374,0),(50111,0),(67020,0),(563696,0),(1058843,0),(1068319,0),(1071585,0),(1080770,0),(1083478,0),(1153175,0),(2101629,0),(2122017,1),(2137025,0),(2182431,0),(2186681,0),(2222852,0),(2303215,0),(3154841,0),(3167923,0),(3174211,0),(3593674,0),(4034282,0),(4213409,0),(4393332,0),(4593885,128),(5245257,0),(5279642,0),(5279754,0),(5284458,0),(5301837,0),(5359552,0),(5462735,0),(5684459,0),(5692253,0),(6299508,0),(6304885,0),(6309672,0),(6377203,0),(6670171,0),(6965938,0),(7185201,0),(7341527,0),(7345070,0),(7351928,0),(7353080,0),(7359703,0),(7359919,0),(7404369,0),(7463724,0),(7486643,0),(7904630,1),(8208614,0),(8342078,0),(8392720,0),(8407689,0),(8412955,0),(8419788,0),(8425641,0),(8427974,0),(8477709,0),(8520882,0),(8533333,0),(8561916,0),(9437999,0),(9438902,0),(9441601,0),(9456491,0),(9468801,0),(9475664,0),(9528679,512),(9553853,0),(9587089,0),(9616254,0),(9830830,0),(10491792,0),(10503956,0),(10505695,0),(10529511,0),(10558738,0),(10569234,0),(10569757,0),(10886306,0),(11536959,0),(11558213,0),(11562455,0),(11666859,0),(11674725,0),(11852514,0),(12595331,0),(12600027,0),(12609106,0),(12614100,0),(12617840,0),(12626509,0),(12701136,0),(12932978,0),(12975975,0),(13637725,0),(13639454,0),(13658354,0),(13706650,0),(13724975,0),(13732151,0),(13775008,0),(13807010,0),(14331483,0),(14686285,0),(14690543,0),(14697456,0),(14775482,0),(14831227,0),(15031949,0),(15740545,0),(15973921,0)}

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

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.

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

Данные о демографии предоставлены для 47 миллионов пользователей - всех упомянутых в графе, кроме тех для кого возраст надо предсказать, в формате:

userId create_date birth_date gender ID_country ID_Location loginRegion isInGraph

Где:

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

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

7340014 1182842294347 4260 2 10414533690 3522251 0
5242872 1182844194467 4040 1 10395058357 12102614 0
10485735 1182844677813 5243 2 10415971874 4343894 0 0
12582879 1182844833220 3493 2 10414533690 3378551 62 0
5242875 1182845174067 -1798 1 10414533690 328321 56 0
12582881 1182847610733 1142 2 10397571399 392727 0

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

 

Формат решения

Решение принимается в виде файла CSV двумя колонками: ид юзера и прогноз, разделитель ",". Пример:

11010050,6598
23855113,5172
15684951,4446
41287693,5301
45744145,6259