Как использовать сложный сетевой полуконтролируемый метод для маркировки ваших данных

Объем доступных данных быстро растет, что, с одной стороны, отлично подходит для моделей и практиков машинного обучения, поскольку позволит разрабатывать новые решения в этой области. С другой стороны, большая часть этих данных не маркируется, а процесс маркировки обычно дорог и громоздок [1].

Учитывая тот факт, что большинство решений для машинного обучения ограничены парадигмой контролируемого обучения, возникает большая проблема: как работать с таким объемом неразмеченных данных?

Чтобы попытаться решить эту проблему, была создана полууправляемая парадигма. Его внимание сосредоточено на попытке работать с небольшим набором размеченных данных и большим объемом неразмеченных данных, чтобы делать прогнозы.

В этом посте мы рассмотрим инструмент обучения с полуучителем: распространение меток. Мы узнаем, как мы можем использовать сложные сети и библиотеку sknet для распространения меток на наши немаркированные данные.

Модульность в сложных сетях

Чтобы распространять метки, используя сложные сети, мы должны сначала понять, что такое мера модульности и как она связана с обнаружением сообщества в сетях.

Сообщество — это область графа, плотно связанная внутри себя, но редко связанная с другими областями сети. Обнаружение таких сообществ представляет собой неконтролируемую проблему NP-Complete и может рассматриваться как проблема кластеризации с точки зрения традиционного машинного обучения.

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

Используя модульность, были созданы неконтролируемые алгоритмы для обнаружения сообщества. Алгоритм, который нам будет полезен, — это модульный жадный алгоритм.

Модульность Жадный алгоритм

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

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

Для использования этого алгоритма матрица, известная как матрица приращения модульности, определяется следующим образом:

В этой матрице дельта Qij обозначает приращение модульности в случае слияния сообществ i и j.

Алгоритм распространения метки

Алгоритм Modularity Label Propagator сильно зависит от описанного выше алгоритма Greedy Modularity. Идея здесь в том, что мы можем использовать его для распространения меток, которые у нас есть, на немаркированные данные таким образом, чтобы мы создавали сплоченные группы внутри нашей сети.

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

  • Мы начинаем с L помеченных узлов в сети
  • Каждый узел сети определяется как сообщество
  • На каждом шаге мы объединяем сообщества, максимизируя модульность, используя матрицу приращения модульности
  • Если слияние невозможно (скоро мы увидим, почему), мы переходим ко второму по величине элементу в матрице и так далее.
  • Мы повторяем до тех пор, пока ни один узел в сети не будет не помечен

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

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

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

При этом ожидается, что все наши экземпляры будут помечены.

Использование распространителя меток со sknet

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

pip install scikit-net

Теперь, когда библиотека установлена, давайте импортируем необходимые библиотеки. Кроме того, мы собираемся импортировать набор данных Iris, который мы будем использовать для распространения наших меток:

from sklearn.datasets import load_iris
from sknet.network_construction import KNNConstructor
from sknet.semi_supervised import ModularityLabelPropagation
X, y = load_iris(return_X_y = True)
y[10:30] = np.nan
y[70:90] = np.nan
y[110:130] = np.nan

Обратите внимание, что мы устанавливаем для некоторых экземпляров Iris значение NaN, так алгоритм узнает, какие метки отсутствуют.

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

knn_c = KNNConstructor(k=5, sep_comp=False)

Здесь важно отметить, что мы используем для параметра set_comp значение False. Этот параметр определяет, следует ли вставлять метки данных в отдельные компоненты. Поскольку мы хотим распространять наши метки, мы не можем позволить себе не иметь ребер между разными метками, потому что это связало бы NaN только друг с другом.

Наконец, мы создадим экземпляр распространителя и подгоним его к данным:

propagator = ModularityLabelPropagation()
propagator.fit(X, y, constructor=knn_c)

Затем можно получить доступ к сгенерированным меткам с помощью:

propagator.generated_y

Если мы посмотрим на весь код, у нас есть только:

from sklearn.datasets import load_iris
from sknet.network_construction import KNNConstructor
from sknet.semi_supervised import ModularityLabelPropagation
X, y = load_iris(return_X_y = True)
knn_c = KNNConstructor(k=5, sep_comp=False)
y[10:20] = np.nan
y[70:80] = np.nan
y[110:120] = np.nan
propagator = ModularityLabelPropagation()
propagator.fit(X, y, constructor=knn_c)
propagator.generated_y

Разумеется, что некоторые из этих меток будут неверны. Как и в случае с каждым алгоритмом машинного обучения, не будет решения со 100% точностью. Однако этот метод обеспечивает очень хорошую отправную точку для маркировки ваших данных.

Если вы хотите узнать больше об этом алгоритме, проверьте номер ссылки [1].

Подробнее о библиотеке sknet

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

Надеюсь, вам понравится и протестировать библиотеку!

[1] Сильва, Т.С., Чжао, Л., Полууправляемое обучение, управляемое мерой модульности в сложных сетях (2012), Нейрокомпьютинг. 78. 30–37. 10.1016/j.neucom.2011.04.042.