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

Ссылка на полную версию Jupyter Notebook находится в следующем репозитории GitHub: https://git.io/JUdR5

О пандемии

Как мы знаем, новый коронавирус (SARS ‐ CoV ‐ 2), вызвавший вспышку в конце 2019 года, представляет собой недавно обнаруженный вирус, тесно связанный с коронавирусами летучих мышей, которые принадлежат к семейству вирусов, вызывающих различные заболевания, от простуды до инфекции дыхательных путей. Этот новый коронавирус SARS ‐ CoV ‐ 2 привел к глобальной вспышке пандемии COVID-19, которая затронула более 200 стран с более чем 10 миллионами случаев заражения, 500 тысячами смертей и их подсчетом. Не похоже, что эта пандемия скоро закончится.

Борьба со вспышкой

Позвольте мне кратко осветить некоторые общие шаги, предпринимаемые правительствами, организациями и местными сообществами для борьбы со вспышкой пандемии COVID-19. Четыре основных усилия заключаются в следующем:

Блокировки

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

Карантин

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

Отслеживание контактов

После того, как человек дал положительный результат на коронавирус, очень важно выявить других людей, которые могли быть инфицированы диагностированными пациентами. Чтобы идентифицировать инфицированных людей, власти составляют список активности диагностированных пациентов за последние 14 дней или около того. Этот процесс называется отслеживанием контактов. В зависимости от страны и местных властей отслеживание контактов осуществляется вручную или цифровыми методами.

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

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

Тестирование на наркотики

Последняя и самая важная попытка излечить болезнь COVID-19 - найти жизнеспособные лекарства. Многие медицинские исследовательские институты и фармацевтические компании уже работают в этом направлении, чтобы вылечить болезнь.

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

Ниже приведены мои наблюдения о некоторых ограничениях при отслеживании контактов вручную.

Ограничения ручного отслеживания контактов

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

Использование технологий искусственного интеллекта для цифрового отслеживания контактов

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

Цифровой метод отслеживания контактов основан на мобильных устройствах (смартфонах), которые полагаются на системы отслеживания, такие как Bluetooth и GPS, для получения информации со смартфона пользователя.

Bluetooth (BLE) в основном передает анонимные идентификаторы со сдвигом во времени на другие близлежащие устройства, так что принимающие устройства затем сохраняют эти идентификаторы в локально сохраненном журнале истории контактов. Система Bluetooth менее эффективна, когда дело доходит до ее неспособности отслеживать людей, которые могли заразиться при прикосновении к поверхности или объектам, к которым прикасался больной человек. Еще один недостаток - это потенциальная неточность Bluetooth в обнаружении событий контакта.

Принимая во внимание, что для отслеживания контактов на основе местоположения используются вышки сотовой связи или GPS, что устраняет некоторые проблемы в Bluetooth, такие как невозможность определения географических точек доступа.

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

Разработка базового алгоритма отслеживания контактов с использованием DBSCAN

Пространственная кластеризация приложений с шумом на основе плотности (DBSCAN) - это алгоритм кластеризации данных на основе плотности, который группирует точки данных в заданном пространстве. Алгоритм DBSCAN группирует точки данных, которые расположены близко друг к другу, и помечает точки данных с выбросами как шум.

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

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

Подготовка набора данных

Набор данных, который я буду использовать, состоит из 4 столбцов / атрибутов, а именно: id, timestamp, latitude и longitude. . Из-за отсутствия реальных данных я использовал генератор JSON для подготовки своего набора данных. С помощью JSON Generator мне удалось создать массив объектов JSON с атрибутами, упомянутыми выше.

Я использовал следующую схему на веб-сайте генератора JSON для создания своего набора данных:

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

Из приведенной выше схемы вы можете наблюдать следующее:

  1. Повторить: используется для указания количества случайных объектов JSON, которые необходимо создать. Первое и второе значения в круглых скобках представляют собой минимальное и максимальное значение. Поскольку я хотел создать максимальное количество случайных объектов JSON, доступных на веб-сайте (а это 100), я выбрал значения 100 для обоих параметров. Если вы хотите, чтобы веб-сайт определил случайное количество создаваемых объектов JSON от 1 до 100, вы можете указать то же значение в круглых скобках.
  2. Id: я указал 10 уникальных имен, которые используются в этом наборе данных.
  3. Метка времени: я предоставил 12 меток времени UNIX, так что каждая метка времени имеет интервал в 1 час (т. е. 3600 секунд).
  4. Широта: я ввел значения широты юго-запада и северо-востока города Бангалора.

5. Долгота. Точно так же я ввел значения долготы для юго-западной и северо-восточной долготы города Бангалор.

Весь код Python, показанный в этой статье, запускается на локальном блокноте Jupyter.

Анализ данных

Мы будем использовать такие библиотеки, как Pandas для обработки данных, Scikit-learn для машинного обучения, Matplotlib и Seaborn для визуализации данных.

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
%matplotlib inline
import datetime as dt
from sklearn.cluster import DBSCAN

Чтобы преобразовать строку JSON в объект pandas, мы используем:

df = pd.read_json(‘/home/user/folder/live_dataset.json’)

Чтобы получить краткую сводку DataFrame, который печатает информацию о DataFrame, включая dtype индекса, dtypes столбцов, ненулевые значения и использование памяти, мы используем:

df.info()

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

df.describe()

Обратите внимание, что этот метод печатает информацию о DataFrame, включая dtype индекса и dtypes столбца, ненулевые значения и использование памяти.

Давайте вернем первые 5 строк, чтобы проверить, есть ли в объекте нужный тип данных.

df.head()

Проверка уникальных имен в столбце id:

df[‘id’].unique()

который возвращает следующий результат:

array(['Alice', 'Bob', 'Carol', 'David', 'Erin', 'Frank', 'Grace',
       'Heidi', 'Ivan', 'Judy'], dtype=object)

EDA (исследовательский анализ данных)

Давайте проанализируем набор данных, используя диаграмму рассеяния, показывающую id s с их широтой и долготой по оси x ось и ось Y соответственно.

plt.figure(figsize=(8,6))
sns.scatterplot(x=‘latitude’, y=‘longitude’, data=df, hue=‘id’)
plt.legend(bbox_to_anchor= [1, 0.8])

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

sns.jointplot(x=’latitude’, y=’longitude’, data=df, color=’red’, kind=‘kde’)

Давайте теперь использовать коробчатую диаграмму, чтобы визуализировать распределение id s и широт по оси x и оси y соответственно.

sns.boxplot(x=’id’,y=’latitude’,data=df, palette=’coolwarm’)
plt.tight_layout()

Мы можем заметить, что id -Alice имеет выброс, что означает, что она расположена за пределами (усов) коробчатой ​​диаграммы.

Точно так же мы построим график для визуализации распределения id s и долготы по оси x и оси y соответственно.

sns.boxplot(x=’id’,y=’longitude’,data=df, palette=’coolwarm’)
plt.tight_layout()

Создание модели

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

epsilon = 0.0018288 # a radial distance of 6 feet in kilometers
model = DBSCAN(eps = epsilon, min_samples = 2, metric = 'haversine').fit(df[['latitude', 'longitude']])
df['cluster'] = model.labels_.tolist()

Для моего набора данных модель смогла сгенерировать 29 кластеров, из которых от кластера-0 до кластера-28 представлены точки данных с соседними узлами.

labels = model.labels_
fig = plt.figure(figsize=(12,10))
sns.scatterplot(df['latitude'], df['longitude'], hue = ['cluster-{}'.format(x) for x in labels])
plt.legend(bbox_to_anchor = [1, 1])

Кластер -1 из приведенного выше графика представляет шум. Мы продолжим и построим то же самое, но без шума.

ids = df[(df['cluster'] == -1)].index
df.drop(ids, inplace = True)
labels = model.labels_
fig = plt.figure(figsize=(12,10))
sns.scatterplot(df['latitude'], df['longitude'], hue = ['cluster-{}'.format(x) for x in df['cluster']])
plt.legend(bbox_to_anchor = [1, 1])

Выявление зараженных людей:

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

def get_infected_names(input_name):
    df = pd.read_json('./testdata/train_dataset.json')
    epsilon = 0.0018288 # a radial distance of 6 feet in kilometers
    model = DBSCAN(eps=epsilon, min_samples=2, metric='haversine').fit(df[['latitude', 'longitude']])
    df['cluster'] = model.labels_.tolist()

    input_name_clusters = []
    for i in range(len(df)):
        if df['id'][i] == input_name:
            if df['cluster'][i] in input_name_clusters:
                pass
            else:
                input_name_clusters.append(df['cluster'][i])
    
    infected_names = []
    for cluster in input_name_clusters:
        if cluster != -1:
            ids_in_cluster = df.loc[df['cluster'] == cluster, 'id']
            for i in range(len(ids_in_cluster)):
                member_id = ids_in_cluster.iloc[i]
                if (member_id not in infected_names) and (member_id != input_name):
                    infected_names.append(member_id)
                else:
                    pass
    return infected_names
  1. eps определяет максимальное расстояние между двумя образцами, чтобы один считался соседним с другим.
  2. min_samples - это количество выборок (или общий вес) в окрестности для точки, которая будет считаться базовой точкой и,
  3. метрика - это метрика расстояния для вычисления сходства между точками данных.

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

Цикл for со строк 8 по 13 добавляет имена всех кластеров, которым принадлежит входное имя. Каждое уникальное имя кластера добавляется в список под названием input_name_clusters.

В строках с 16 по 24 второй цикл for извлекает список всех соседних id, которые принадлежат тем же кластерам, что и input_name. Каждый уникальный id добавляется к инфицированным_names и возвращает его обратно вызывающей функции.

Для моего набора данных модель смогла сгенерировать 29 кластеров, из которых от кластера-0 до кластера-28 представлены точки данных с соседними узлами.

Кластер -1 на приведенном выше графике представляет шум. Мы продолжим и построим то же самое, но без шума.

Выявление инфицированных:

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

Ниже приведены снимки экрана из моей записной книжки Jupyter, на которых показаны результаты поиска потенциально зараженных имен.

Сравнение DBSCAN с использованием k-средних и иерархической кластеризации

  • DBSCAN может формировать кластеры произвольной формы, а также может образовывать кластер, полностью окруженный (но не связанный) с другим кластером.
  • DBSCAN не требует указывать количество кластеров для набора данных, тогда как в k-средних и AgglomerativeClustering все наоборот.
  • DBSCAN формирует кластер на основе плотно упакованных точек данных, указывая eps, который определяет радиус окрестности относительно некоторой точки. В то время как иерархическая кластеризация имеет явное преимущество в том, что для формирования кластера можно использовать любую допустимую меру расстояния. Все, что он использует, - это матрица расстояний.
  • DBSCAN не может хорошо кластеризовать наборы данных с большими различиями в плотности, поскольку комбинация eps-min_samples не может быть выбрана надлежащим образом для всех кластеров. Если данные и масштаб не совсем понятны, выбор значимого порогового значения расстояния eps может быть трудным и требует специальных знаний в предметной области.
  • Алгоритмы иерархической кластеризации разбивают большие группы на более мелкие кластеры, тогда как DBSCAN удерживает их в одном кластере.
  • Кластеризация K-средних (не путать с K ближайших соседей, KNN) - это алгоритм, который подвергается неконтролируемому обучению, для которого необходимо заранее указать количество кластеров (k), т. Е. считается одним из самых больших недостатков этого алгоритма. Чтобы выбрать оптимальное значение k, мы должны следовать методу локтя, который представляет собой эвристический процесс для определения количества кластеров в наборе данных.

Заключение

Из приведенных выше разделов мы можем сказать, что алгоритм кластеризации, такой как DBSCAN, может выполнять кластеризацию точек данных без предварительного знания наборов данных. Мы можем провести такой же кластерный анализ, используя иерархическую кластеризацию и кластеризацию на основе центроидов, которая может определить оптимальное количество кластеров даже при наличии шума и выбросов. DBSCAN может находить нелинейно разделимые кластеры, и этот набор данных не может быть адекватно кластеризован с помощью k-средних или EM-кластеризации Gaussian Mixture.

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

PS: Это мой первый и самый важный пост в блоге о Data Science. Я новичок в этом и очень надеюсь на вашу поддержку и предложения. Не стесняйтесь оставлять любые отзывы!

Об авторе

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

Следуйте за мной в Twitter и LinkedIn.