Данные

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

Данные доступны для скачивания https://cloud.mail.ru/public/GtHV/JNYJbuTV1 Важно: все идентификаторы в данных анонимизированы, попытки деанонимизировать их строжайше запрещены.

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

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

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 together

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

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

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

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

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)
  • Связи скрыты симметрично (т.е., если скрыта связь ID1 -> ID2, то связь ID2 -> ID1 тоже скрыта

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

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

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

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

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

5111 178542 78754
18806 982346 1346 57243

Оценка

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

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

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

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

Перед загрузкой файл необходимо сжать с помощью gzip. Размер загружаемого файла с прогнозом не должен превышать 20 мегабайт.

Расчет метрики NDCG производится примерно таким кодом (убрана валидация и обработка ошибок):


def evaluate(file: File): Double = {
  val inputStream = new FileInputStream(file)
  try {
    val src = Source.fromInputStream(new GZIPInputStream(inputStream)).getLines()
    var accum: Double = 0d
    for (line <- src.map(_.trim) if line.nonEmpty) {
      val ids = line.split("""\s+""")
      val userId: Int = ids.head.toInt
      val predicted: Iterator[Int] = ids.iterator.drop(1).map(_.toInt)
      for (actual <- evaluationSet.get(userId)) {     // Ignore users having no hidden links
        val real = predicted.map(actual.contains).map(if (_) 1d else 0d)
        val rdcg = dcg(real)
        val ideal = (0 until actual.size).iterator.map(_ => 1d) // Ideal output contains all hidden links of this user
        val idcg = dcg(ideal)
        accum += rdcg / idcg
      }
    }
    accum / evaluationSet.size * 1000       // Divide by # of users having hidden links
  } finally {
    inputStream.close()
  }
}

private val logOf2 = math.log(2)

private def log2(d: Double): Double = math.log(d) / logOf2

private def dcg(values: Iterator[Double]): Double = {
  var res: Double = 0
  for ((v, i) <- values.zipWithIndex) {
    val gain = (math.pow(2, v) - 1) / log2(i + 2)
    res += gain
  }
  res
}

Регламент

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

  • Прогноз содержится в текстовом файле, упакованном gzip
  • Каждая строка содержит ID пользователя, для которого предсказываются связи и список кандидатов, разделенные пробелом или символом табуляции
  • Файл содержит только ID пользователей из исходного миллиона. При этом, ID пользователя, для которого предсказываются связи, должен удовлетворять условию: ID % 11 == 7
  • Файл содержит не более 4000000 кандидатов
  • Размер файла не превышает 20Мб

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

Количество засчитанных прогнозов, присланных одним участником ограничивается 100 в течение всего срока онлайн-конкурса. В дальнейшем, прогнозы, посылаемые данным участником, не учитываются.

Чтобы исключить случайную отправку файла прогноза, отправленного ранее, такие прогнозы не учитываются.

Итоговый балл участника определяется как максимальный балл среди всех отправленных им прогнозов. Для получения права на дальнейшее участие в конкурсе требуется набрать не менее 60 баллов.

Пример решения

В качестве примера решения задачи, точность прогноза которого надо превзойти, используется логистическая регрессия, натренированная на трех признаках: количестве общих друзей двух пользователей, разнице в возрасте и факте совпадения или различия полов. Код примера доступен по адресу https://github.com/snahackathon/sh2016

Несмотря на кажущуюся простоту, подсчет такого признака как количества общих друзей на графе миллионного размера уже сопряжен с вычислительными трудностями. Предложенный пример решения выполнен с использованием платформы распределенной обработки данных Apache Spark, но протестирован и на работу в локальном режиме с использованием 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% используем для выбора оптимального порога (ищем максимум F2-score).

  7. Читаем счетчики общих друзей для искомых пользователей (id % 11 == 7) и строим прогноз на основе обученной модели.

  8. Отсекаем пары, не прошедшие порог, сортируем и сохраняем в текстовый файл искомого формата.

{{ l.place }} {{ l.name }} {{ l.score | number : 4 }}
Загружается...
No leaders
{{ l.place }} {{ l.name }} {{ l.score | number : 4 }}
Загружается...
No leaders