-
Notifications
You must be signed in to change notification settings - Fork 0
/
assigment.txt
149 lines (147 loc) · 11.2 KB
/
assigment.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
Про данные и задачу
Социальный граф
Представленный для анализа фрагмент социального графа включает информацию о
связях одного миллиона пользователей, попавших в двух шаговую окрестность сотни
случайно выбранных пользователей. Граф сохранен в формате разреженной матрицы, где
по каждой связи есть информация о её типе (родственник, друг и т.д.) в виде битовой
маски. Каждая строка матрицы соответствует друзьям одного пользователя и имеет
формат:
ID_пользователя1 {(ID_друга1,маска1), (ID_друга2,маска2),…}
Матрица партиционирована по ID пользователя на 16 файлов, каждый из которых
сжат GZipом.
Пары в списке связей отсортированы по ID друга (по возрастанию). Пример
записей из графа:
102416
{(5362439,0),(7321627,0),(7345280,0),(9939258,0),(9976393,0),(11260492,0),(11924364,0),(
16498676,0),(16513827,0),(21716731,0),(21826340,0),(23746537,0),(23751503,0),(24412936
,0),(24423533,0),(30287856,0),(32321147,0),(34243036,0),(37592142,0),(39485706,0),(4150
5243,0),(42791620,0),(52012206,0),(52671472,0),(54652307,0),(57293803,0),(59242794,0),(
59252048,0),(62535397,0),(62563866,0),(62567154,0),(64588902,0)}
102608
{(4167808,32784),(6019974,32),(6152844,16),(9570536,64),(10699806,33),(13290514,0),(15
064491,128),(16432948,512),(24473204,0),(24655822,0),(25833075,256),(28000951,64),(308
34507,2048),(34567533,16),(35766667,0),(37385121,0),(40123805,512),(43134386,1024),(45
439608,0),(45484652,0),(47562525,0),(52378153,256),(52403136,512),(52493894,1024),(534
83990,0),(54048767,0),(54286279,2048),(57401158,0),(57956631,0),(58183281,0),(61117236
,32),(61898065,0),(61936634,0),(64512205,512),(65014849,0),(65112662,0),(65259449,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 games together
Помимо перечисленных битов 120
в маске отношений может быть установлен, а
может и нет 0й
бит. Этот бит играет чисто техническую роль и не имеет физического
смысла. В итоге, например, отношение типа Child может кодироваться числами 16 или 17.
Данные были подготовлены с использованием инструмента Apache Pig и содержат 2
соответствующие файлы с заголовками, позволяющие участникам использовать этот
инструмент и для предварительной обработки/фильтрации данных.
Демография пользователей
Данные о демографии предоставлены для того же миллиона пользователей, что и
информация о социальных связях в формате
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 – идентификатор региона, откуда чаще всего логинится
пользователь (может отсутствовать!)
Пример данных:
44053078 1166032023073 3067 1 10414533690 2423601 99
12495764 1177932393270 1138
2 10405172143 188081
25646929 1165304175170 3756 2 10414533690 3953941 22
25646999 1160728984480 3884 2 10414533690 241372 120
12495833 1176909723643 3363 2 10414533690 2724941 11
Демография партиционирована по той же схеме, что и граф, но не сжата (передается
в виде открытых текстов). Так же может быть обработана с помощью Apache Pig или
любого другого инструмента, поддерживающего CSV.
Задача
Часть связей в предоставленном социальном графе скрыта и задачей участников
является максимально полно и точно раскрыть их. Сокрытие связей коснулось только
пользователей из исходного миллиона, остаток от деления ID которых на 11 равен 7 (id %
11 == 7), сокрытию подверглось порядка 10% связей для каждого из этих пользователей.
Были скрыты только ведущие в исходный миллион связи.
Результаты прогноза нужно представить в формате CSV файла вида
ID_пользователя1 ID_кандидата1.1 ID_кандидата1.2 ID_кандидата1.3
ID_пользователя2 ID_кандидата2.1 ID_кандидата2.2
2 http://pig.apache.org
Записи в файле отсортированы по ID пользователя (по возрастанию), а затем по
предсказанной релевантности кандидатов (по убыванию, саму релевантность при этом в
файл писать не надо). Пример результатов:
5111 178542 78754
18807 982346 1346 57243
Результаты участников буду оцениваться с помощью метрики Normalized Discounted
Cumulative Gain (NDCG) . Метрика будет рассчитываться отдельно по каждому из 3
пользователей, для которых есть скрытые связи, а затем усредняться. Записи в файле
результата, не имеющие отношения к пользователям со скрытыми связями, при оценке
результата учитываться не будут. Если по какомуто
пользователю не будет предложено
ни одного кандидата, то значение метрики для него будет считаться за 0.
Перед загрузкой файл необходимо сжать с помощью gzip. Размер загружаемого
файла с прогнозом не должен превышать 4 миллиона рекомендованных кандидатов или
20 мегабайт в сжатом виде.
Пример решения
В качестве примера решения задачи, точность прогноза которого надо превзойти,
используется логистическая регрессия4, натренированная на трех признаках: количестве
общих друзей двух пользователей, разнице в возрасте и факте совпадения или различия
полов. Код примера доступен по адресу https://github.com/snahackathon/sh2016
Несмотря на кажущуюся простоту, подсчет такого признака как количества общих
друзей на графе миллионного размера уже сопряжен с вычислительными трудностями.
Предложенный пример решения выполнен с использованием платформы распределенной
обработки данных Apache Spark5, но протестирован и на работу в локальном режиме с
использованием 4х
ядер и 8 гигабайт памяти. Общая схема решения выглядит
следующим образом:
1. Считаем общих друзей
a. Разворачиваем граф из формы A1>(
B1,B2,...) в форму
B1>(
A1,..),B2>(
A1,...) и сохраняем (этот шаг необходим, так как исходный
граф не симметричен!).
b. Для каждой записи вида B1>(
A1,A2,A3…) генерируем пары
(A1,A2),(A2,A3) и т.д., а затем считаем количество упоминаний каждой из
пар (за один раз не получится изза
пиковых нагрузок на память и диск при
шафле – делаем в несколько заходов, партиционируя по A1).
2. Выбираем фрагмент полученных счетчиков для тренировки модели (~1%).
3. Фильтруем исходный граф, оставляя только связи внутри миллиона пользователей,
упомянутых в левой части, и переводим в вид списка пар (это список
положительных примеров для тренировки регрессии).
4. Втягиваем демографию пользователей в память.
5. Объединяем три набора данных (счетчик общих друзей, демографию и признак
наличия связи).
6. На 10% полученного набора обучаем регрессию, а оставшиеся 90% используем для
выбора оптимального порога (ищем максимум F2measure6).
3 https://en.wikipedia.org/wiki/Discounted_cumulative_gain#Normalized_DCG
4 https://en.wikipedia.org/wiki/Logistic_regression
5 http://spark.apache.org
6 https://en.wikipedia.org/wiki/F1_score
7. Читаем счетчики общих друзей для искомых пользователей (id % 11 == 7) и строим
прогноз на основе обученной модели.
8. Отсекаем пары, не прошедшие порог, сортируем и сохраняем в текстовый файл
искомого формата.