Это вторая из двух статей о нашем недавнем участии в хакатоне по борьбе с пандемией. Наш проект (CoronaRank) был одним из 5 проектов из 230 представленных, выбранных в качестве победителей Spotlight для представления на церемонии закрытия. Читайте технические аспекты нашего решения, более общий обзор хакатона и нашего продукта смотрите в нашей первой статье.

tl;dr

Нынешняя пандемия COVID-19 вызывает отклик у технических сообществ по всему миру. На недавний хакатон по борьбе с пандемией было подано более 200 заявок. Участники поделились своими навыками работы с данными для создания программных решений, которые могли бы помочь сдержать распространение вируса и смягчить его последствия. Решение Appsilon (CoronaRank) вдохновлено Google PageRank и использует данные геолокации в формате Apache Parquet от Veraset для эффективной оценки риска воздействия с использованием моделирования цепей Маркова. Мы использовали R для анализа большой базы данных геолокации и построения алгоритма. Затем CoronaRank был реализован в виде адаптивного веб-приложения Shiny.

Предыстория: баланс между конфиденциальностью и срочностью во время пандемии

Хотя использование данных о местоположении пользователя смартфона может вызвать беспокойство и даже сопротивление, большинство пользователей добровольно разрешили доступ к своей истории местоположений, даже если они не помнят, что использовали эту функцию при первой инициализации своего устройства. Технологические компании утверждают, что эти данные в конечном итоге остаются в руках пользователей, и такие законы, как GDPR в Европе и HIPAA в США, служат для обеспечения соблюдения этого. Несмотря на это, наши данные о геолокации существуют — это факт мира, в котором мы живем. Вопрос в том, как мы можем использовать эти доступные данные во благо?

В Appsilon мы придумали, как эффективно использовать эти данные в условиях нынешнего пандемического кризиса. Ранее в этом месяце мы стали одними из победителей хакатона Datavant Pandemic Response Hackathon с CoronaRank — алгоритмом, вдохновленным Google PageRank, который позволяет оценивать личный риск воздействия COVID-19 с учетом уровня взаимодействия между людьми. . CoronaRank также предоставляет ценную информацию о потенциальных очагах пандемии, учитывая уровень активности человека в этом районе.

Мы разработали решение Proof of Concept, когда поняли, что существующие формы передачи данных о распространении пандемии могут не подходить для информирования людей о том, как принимать повседневные решения, чтобы свести к минимуму свой риск и риск для других. Описательный анализ данных о пандемии в разных регионах мира, безусловно, был полезен, но многие люди не могут относиться к этим абстракциям — экспоненциальная кривая, безусловно, вызывает страх, но мало помогает, когда кому-то еще нужно добираться до работы или решать, куда поехать. покупать продукты. Мы решаем эту проблему (и другие) с помощью CoronaRank.

Наше решение: CoronaRank

Мы решили ответить на вопрос, где в последние две недели находились пациенты с подтвержденным диагнозом COVID-19 (или бессимптомные носители) и какие места могут быть поставлены под угрозу. Это обеспечивает соответствующий уровень личного риска воздействия, который может рекомендовать более сильную изоляцию или возможное раннее вмешательство. Он также может показать пользователям, каких областей следует избегать, если им нужно выйти, например, чтобы купить продукты.

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

​Тепловая карта Нью-Йорка, созданная с помощью CoronaRank. Более темные (красные) кружки обозначают места с повышенным риском.

Человек с высоким уровнем риска (CoronaRank 0,9) недавно посетил ряд районов с высоким уровнем риска на Манхэттене.

Алгоритм CoronaRank

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

Направленный граф

Ориентированный граф можно использовать для визуализации сложных сетей отношений.

Веб-график Интернета

Интернет является одной из таких сетей, и полученное графическое представление называется веб-графом, который описывает связи между страницами всемирной паутины.

Google PageRank

PageRank использует Webgraph для оценки относительной важности всех подключенных веб-сайтов.

Точно так же, как PageRank строится путем оценки того, как страницы отдают «уважение» другим страницам, когда они передают его через гиперссылки, CoronaRank предоставляет индивидуальный показатель риска, поскольку люди могут заразить других «вирусами», когда они передают их через контакт.

График человеческого взаимодействия

Веб-график человеческих взаимодействий

Люди, подобно веб-страницам в Интернете, взаимодействуют друг с другом, образуя сложную сеть. На каждого человека влияет его история взаимодействия с другими людьми, в том числе количество вирусоносителей.

CoronaRank в действии

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

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

Также в соответствии с PageRank, CoronaRank можно настроить, установив вес для ребер. В настоящее время веса установлены так, чтобы отражать количество людей с диагнозом, посещающих данное место, но это можно легко изменить в дальнейшем. Например, для учета количества времени, проведенного на месте.

Управление большим набором данных геолокации с помощью R

Хакатон длился 2 дня. Нам пришлось разрабатывать нашу модель не только в условиях дефицита времени, но и в сложной удаленной рабочей среде со многими отвлекающими факторами, учитывая текущую ситуацию с пандемией. Однако в нашей коммерческой работе мы обнаружили, что R с его отличным соотношением времени и ценности идеально подходит для таких сценариев, и мы пошли дальше и использовали его для проекта CoronaRank.

На протяжении всего хакатона мы использовали данные о местоположении, предоставленные Veraset, но сама модель не зависит от данных. Veraset поделилась с нами данными в формате Apache Parquet, сжатыми с помощью Snappy. Мы использовали Apache Arrow для загрузки данных в R, что было очень просто:

read_full_data <- function(dataDir = "veraset-03-22") {
 print(glue("Reading {dataDir}..."))
 purrr::keep(dir(dataDir), ~ grepl(".*snappy.parquet$", .)) %>%
   purrr::map(~ arrow::read_parquet(paste0(dataDir, "/", .), as_tibble = TRUE)) %>%
   dplyr::bind_rows()
}

Хотя загрузка данных не представляла особой сложности, сам размер набора данных усложнял работу с ним. Несжатые данные RAW за один день для Нью-Йорка (в центре нашего Proof of Concept — «сеть» для нашего веб-графа) занимают более 3 ГБ ОЗУ. Манипулирование данными такого размера для нескольких дат в R не является тривиальной задачей. Особенно, когда нам нужно предварительно обработать данные, создать графики, вычислить веса для ребер графа и т. д.

Apache Arrow позволяет нам уменьшить размер потребляемой оперативной памяти с помощью:

data <- read_parquet("data.parquet", 
  as_data_frame = FALSE,
  col_select = dplyr::all_vars()
)

Таким образом мы загружаем только метаданные о наборе данных. К сожалению, мы узнали об этом только после хакатона во время одного из внутренних технических переговоров Appsilon. Формат Паркет позволил нам эффективно обрабатывать файлы в конвейере dplyr без необходимости загрузки всего набора данных в рабочую память.

Вычисление и визуализация CoronaRank

Как только мы загрузили данные, мы перешли к вычислению CoronaRank. В исходных данных было всего 3 столбца: timestamp, cid и geohash. Geohash — это, по сути, широта и долгота, заключенные в одно значение. Чтобы сгенерировать фрейм данных с описанием графа, узлами и ребрами или перейти от журналов к графу, мы выполнили следующие шаги:

  • Создайте узел для каждого cid.
  • Создайте узел для каждой локации (мы разбили локации на сетку — на практике мы просто округляли широту и долготу до определенной цифры).
  • Создайте ребро между узлами, если человек (cid) находился в заданном месте.

На этом этапе становится очевидной разница между PageRank и CoronaRank. В PageRank ребра направлены (одна страница ссылается на другую). В CoronaRank график ненаправленный (человек посещает локацию ≡ локацию посещает человек).

Чтобы дополнительно учесть тот факт, что ситуация с пандемией быстро меняется, а сам граф является массивным, мы ввели веса для ребер графа. Вес определяет, является ли конкретное преимущество рискованным. Чем выше вес, тем заразнее край. И наоборот, меньший вес указывает на то, что край менее заразен.

Мы использовали данные из The New York Times о количестве случаев в округе для наших первоначальных весов. Ребрам с местами с большим количеством случаев (на округ) были присвоены более высокие веса.

Псевдокод для нашего решения:

coronaRank <- function(data) {
  edges <- dplyr::select(data, geohash, id) %>% distinct()
  # calculating weights for edges:
  risk_profile <- build_ny_counties_risk_profile()
  weights_edges <- risk_for_locations(risk_profile, edges$geohash)
  graph <- graph_from_edgelist(as.matrix(edges), directed = FALSE)     
  coronarank <- igraph::page_rank(graph, algo = "prpack", 
                  directed = FALSE, damping = 0.99, 
                  weights = weights_edges)
  tibble(
    node = names(coronarank$vector),
    score = coronarank$vector
  )
}

Обратите внимание, что мы установили демпфирование («вероятность телепортации») на относительно большое число, потому что мы предполагаем, что отслеживание данных GSM достаточно точное.

Полное решение доступно здесь: https://github.com/Appsilon/covid-hackathon (условия хакатона и нехватка времени привели к тому, что код был функциональным, но более низкого качества)

Решение для отслеживания контактов Google и Apple и CoronaRank

Наша реализация CoronaRank — это всего лишь Proof of Concept. После отправки нашего решения мы были рады видеть, что Google и Apple объявили о своем сотрудничестве по использованию технологии отслеживания контактов и для борьбы с пандемией.

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

Одним из недостатков этого решения является то, что не все пользователи смартфонов iOS или Android подпишутся на услугу, а некоторые могут предоставить неточную информацию.

Хотя наше решение требует использования данных геолокации для преодоления этой проблемы, оно предоставляет пользователю дополнительную информацию о степени риска заражения вирусом с учетом их прошлых взаимодействий. Сочетание этого подхода с подходом Google и Apple позволит информировать даже тех пользователей, у которых нет приложения или которые не знают, что они могли быть раскрыты. Как и в нашем приложении, это потребует обеспечения конфиденциальности данных и мер безопасности в качестве приоритета.

Вывод

Хакатон по реагированию на пандемию был отличным опытом. Было очень приятно увидеть более 230 заявок со всего мира, что говорит о том, насколько серьезно техническое сообщество относится к ответственности за использование своих навыков для общего блага. Мы считаем, что это также была хорошая возможность продемонстрировать возможности R для быстрой разработки работающего продукта, и хотели бы отметить все компании и организации, предоставившие ресурсы, данные и поддержку на протяжении всего хакатона.

Мы надеемся получить финансирование или партнерство с признанным учреждением государственной службы, чтобы донести наше решение до граждан. Узнайте больше о наших планах на будущее в нашем предыдущем сообщении в блоге.

Наконец, я хочу поблагодарить своих замечательных товарищей по команде (включая эпидемиолога Ewa Knitter) и наших близких, включая мою жену — мы бы не смогли участвовать и побеждать без вашей поддержки. Мы также хотим отметить сообщество открытого исходного кода, которое создало инструменты, позволяющие быстро разрабатывать передовое программное обеспечение. Особая благодарность людям, работавшим над Apache::Arrow, igraph, Leaflet, Shiny и пакетом sf R.

Следуйте за нами, чтобы узнать больше