Как использовать алгоритм кластеризации и анализ близости (LOF baed) для обнаружения выбросов / аномалий в текстовых твитах Twitter. Сравнение двух подходов
Обнаружение аномалий / выбросов - одна из очень популярных тем в мире машинного обучения. Это относится к процессу «обучения без учителя». Здесь у нас нет никаких предварительных знаний о шаблонах данных, в отличие от «контролируемого обучения». «Аномалия или выброс» - это точка данных, которая не очень похожа на другие точки данных во всем нашем наборе данных. В этой статье я рассмотрю два подхода к поиску посторонних твитов из данных Twitter и их сравнения.
Я буду использовать Python, Sci-kit learn, библиотеку pyod от pypi.org, Gensim, NLTK для решения этой проблемы.
Получение данных и описание проблемы
Для этой задачи я буду использовать данные репозитория машинного обучения UCI - Новости здоровья в наборе данных Twitter . Этот набор данных содержит различные наборы образцов твитов из различных новостных каналов, таких как CNN, NYTimes, CBC и т. д. Определенно это текстовые данные, а твиты представляют собой не что иное, как одну или две строки текста со ссылкой на источник новостей. Ниже код Python может считывать загруженные данные (для моей статьи я использовал только nytimeshealth.txt. Существуют также файлы txt из других источников новостей) из вышеупомянутого источника:
def _read_all_health_tweets():
all_tweets = {}
file = open(‘../../data/Health-Tweets/nytimeshealth.txt’, ‘r’)
lines = file.readlines()
for index, line in enumerate(lines):
parts = line.split(sep=’|’, maxsplit=2)
tweet = “”.join(parts[2:len(parts)])
all_tweets[index] = tweet
file.close()
return all_tweets
Если указанный выше python «dict» преобразован в pandas «dataframe» и отображается с помощью «IPython-Jupiter Notebook», то первые 9 записей будут выглядеть, как показано ниже:
Всего в файле 6245 твитов. Совершенно очевидно, что не все твиты относятся к «Новостям здоровья», и многие из них могут иметь произвольную тематику. Теперь наша проблема: «Можем ли мы определить те твиты, которые не имеют такого отношения к здравоохранению?». Или лучшее, что мы можем сделать, используя термины машинного обучения «обобщение постановки проблемы», т. Е. «Можем ли мы идентифицировать n самых необычных твитов?», Где «n» может быть параметром, задаваемым пользователем. Здесь проблема заключается в том, что данные полностью «неклассифицированы / не помечены» (т. Е. Каждый твит не имеет метки «выброс / не выброс», и мы не можем обучить стандартную модель машинного обучения с этими данными), что делает его «неконтролируемым» по своей природе. . Теперь я представлю два подхода к ее решению: один основан на «кластеризации», а другой - «на основе близости». Но перед этим необходимо предварительно обработать текстовые данные твита, чтобы подготовить их для использования в любом алгоритме машинного обучения. Я расскажу об этом в разделе ниже.
Предварительная обработка и создание векторной модели пространства (Doc2Vec)
Первым шагом предварительной обработки будет преобразование каждого текстового твита в токены массива и удаление нежелательных символов, стоп-слов и т. Д.
Вторым шагом будет преобразование каждого массива токенов, соответствующих каждому текстовому твиту, в числовые векторы. Этот шаг известен как «создание векторной космической модели». Существуют стандартные модели векторного пространства, такие как «Tf-Idf», «Word2Vec», «Doc2Vec» и т. Д. Этот вектор работает как вектор признаков документа и определяет, сколько функций будет в нем. Я использовал «Doc2Vec» в качестве модели для этой проблемы, потому что каждый обзор можно рассматривать как отдельный документ, а «Doc2Vec» действительно хорошо работает для понимания контекстного значения текста (по сравнению с Tf-Idf, который представляет собой не что иное, как чистую частоту- на основе модели).
Следующий фрагмент кода Python работает как этап конвейера для создания Doc2Vec для документа:
from sklearn.pipeline import Pipeline
from gensim.models.doc2vec import TaggedDocument, Doc2Vec
from sklearn.base import BaseEstimator
from gensim.parsing.preprocessing import preprocess_string
from sklearn import utils
from tqdm import tqdm
class Doc2VecTransformer(BaseEstimator):
def __init__(self, vector_size=100, learning_rate=0.02, epochs=20):
self.learning_rate = learning_rate
self.epochs = epochs
self._model = None
self.vector_size = vector_size
self.workers = multiprocessing.cpu_count() — 1
def fit(self, x, y=None):
tagged_x = [TaggedDocument(preprocess_string(item), [index]) for index, item in enumerate(x)]
model = Doc2Vec(documents=tagged_x, vector_size=self.vector_size, workers=self.workers)
for epoch in range(self.epochs):
model.train(utils.shuffle([x for x in tqdm(tagged_x)]), total_examples=len(tagged_x), epochs=1)
model.alpha -= self.learning_rate
model.min_alpha = model.alpha
self._model = model
return self
def transform(self, x):
arr = np.array([self._model.infer_vector(preprocess_string(item))
for index, item in enumerate(x)])
return arr
from sklearn.pipeline import Pipeline
tweets_dict = _read_all_health_tweets()
tweets = tweets_dict.values()
pl = Pipeline(steps=[('doc2vec', Doc2VecTransformer())])
vectors_df = pl.fit(tweets).transform(tweets)
vectors_df
«Vectors_df» будет напечатан следующим образом:
Сверху видно, что «Doc2Vec» генерирует 2D-массив. Каждая строка соответствует каждому текстовому твиту. Столбцы 2D-массива - это фактические векторы функций «Doc2Vec». Здесь нет столбцов, равных 100, что задается параметром vector_size, и это не приводит к отсутствию функций. Этот параметр может быть настроен или предоставлен извне. Таким образом, при таком подходе каждый текстовый твит преобразуется в массив числовых функций. Эти особенности имеют виртуальный характер и их трудно визуализировать физически.
«Doc2Vec» для документа создается путем обучения нейронной сети по соседнему слову случайно выбранного слова и наоборот. Здесь только изученные веса скрытого слоя вызывают беспокойство и принимаются как значения «Doc2Vec». Фактически существует два метода: распределенная память (DM) и распределенный пакет слов (DBOW). Для получения более подробной информации вы можете воспользоваться следующими ресурсами:
Анализ размерности и основные компоненты
Вышеупомянутое преобразование «Doc2Vec» дает 100 векторов признаков для каждого текстового твита. Но такие методы анализа, как кластеризация и факторы выбросов, слишком большое количество функций могут испортить реальную цель. Рекомендуется сохранить размер вектора «Doc2Vec» от 100 до 300. Таким образом, всегда лучше выполнять проекцию компонента более высокого измерения над «Doc2Vec», чтобы увидеть, какие компоненты являются важными, а какие нет. «PCA» идеально подходит для этого. Я провел анализ 10 основных компонентов и увидел, что только первые 2 объясняют достаточную дисперсию.
Теперь может возникнуть один вопрос: «Почему я не оставил‘ vector_size ’в‘ Doc2Vec ’как 2 или 3 вместо 100. Излишних сложностей PCA можно было бы избежать». Ответ - «Нет». Если я оставлю "vector_size" равным 3, то многие скрытые функции будут подавлены в "Doc2Vec". Также может возникнуть проблема слишком ранней конвергенции. Вот почему предпочтительнее позволить «Doc2Vec» генерировать все векторы определенного размера, а затем применять PCA.
def analyze_tweets_pca(n_pca_components):
tweets_dict = _read_all_health_tweets()
tweets = tweets_dict.values()
doc2vectors = Pipeline(steps=[('doc2vec', Doc2VecTransformer())]).fit(tweets).transform(tweets)
pca = PCA(n_components=n_pca_components)
pca_vectors = pca.fit_transform(doc2vectors)
print('All Principal Components ..')
print(pca_vectors)
for index, var in enumerate(pca.explained_variance_ratio_):
print("Explained Variance ratio by Principal Component ",
(index+1), " : ", var)
analyze_tweets_pca(n_pca_components=10)
Он производит следующий вывод:
Итак, я возьму только первые 2 основных компонента (дисперсия почти 99,7% объясняется первыми 2) для оценки кластеризации и фактора локальных выбросов в следующих разделах. При этом размерность уменьшается, а также может повышаться точность кластеризации и анализа близости.
Подход на основе кластеризации (k-средних)
Кластеризация - один из самых популярных методов «обучения без учителя». Я использовал стандартный алгоритм «k-средних». Для обнаружения выбросов с использованием «kmeans» концепция «Silhoutte Score» очень важна.
Оценка Silhoutte: определяется соотношением межкластерного и внутрикластерного расстояний, например:
где,
b (i) = наименьшее среднее расстояние от точки данных «i» до всех точек в любом другом кластере, членом которого «i» не является
a (i) = среднее расстояние между точкой данных «i». и все другие точки данных в том же кластере
Во всех приведенных выше определениях расстояния рассчитываются как обратная косинусу подобия между векторами PCA, поскольку оно менее чувствительно к величине и предпочтительнее, чем «евклидово» или обобщенное «расстояние Минковского» для текстовой аналитики.
Среднее значение «баллов силуэта» для всех точек данных является общим «баллом силуэта» для конкретной настройки кластера. Его значение находится в диапазоне от -1 до 1. Более положительное значение указывает на хорошую настройку кластера. Теперь из «Силуэтных баллов» отдельных точек данных можно сделать три вывода, как описано ниже:
Значение, близкое к -1: точка данных неправильно помещена в кластер, которому в идеале она не должна принадлежать. По сути, это «вставка».
Значение, близкое к 0: точка данных не должна принадлежать ни к какому кластеру и должна быть отделена. Это «выброс» или «аномалия».
Значение, близкое к 1: точка данных идеально размещена в правом кластере.
Из второго пункта, приведенного выше, ясно, что обнаружение выбросов из настройки кластера - это не что иное, как обнаружение точек данных, чьи значения «Silhouette Score» наиболее близки к нулю. Сортировка всех абсолютных значений «Silhouette Score» в порядке возрастания даст вероятные n выбросов. Видно, что эти точки обычно лежат между пограничными областями кластеров. Потому что концептуально они не принадлежат ни к каким кластерам.
Для этого сначала следует выполнить кластеризацию с оптимальным значением «k» для алгоритма «k-средних». Оптимальный «k» - это тот, для которого «Оценка силуэта» всей настройки кластера становится максимальной или близкой к +1. Это можно определить, попробовав использовать набор значений «k». Я использовал «k-средних» с двумя «основными компонентами» с наибольшей дисперсией.
def determine_anomaly_tweets_k_means(top_n):
tweets_dict = _read_all_health_tweets()
tweets = tweets_dict.values()
pl = Pipeline(steps=[('doc2vec', Doc2VecTransformer()),
('pca', PCA(n_components=2)),
('kmeans', OptimalKMeansTextsClusterTransformer(min_k=2, max_k=5))])
pl.fit(tweets)
pca_vectors, cluster_labels = pl.transform(tweets)
silhouette_values = silhouette_samples(X=pca_vectors, labels=cluster_labels, metric='cosine')
tweet_index_silhouette_scores = []
absolute_silhouette_scores_tweet_index = []
for index, sh_score in enumerate(silhouette_values):
absolute_silhouette_scores_tweet_index.append((abs(sh_score), index))
tweet_index_silhouette_scores.append((index, sh_score))
sorted_scores = sorted(absolute_silhouette_scores_tweet_index, key=sort_key)
top_n_silhouette_scores = []
pca_vectors_anomalies = []
print("Top ", top_n, " anomalies")
for i in range(top_n):
abs_sh_score, index = sorted_scores[i]
index_1, sh_score = tweet_index_silhouette_scores[index]
top_n_silhouette_scores.append((index, sh_score))
print(tweets_dict[index])
print('PCA vector', pca_vectors[index])
pca_vectors_anomalies.append(pca_vectors[index])
print('Silhouette Score: ', sh_score)
print("..................")
plot_tweets_k_means_clusters_with_anomalies(pca_vectors=pca_vectors, pca_vectors_anomalies=pca_vectors_anomalies,
cluster_labels=cluster_labels)
plot_scatter_silhouette_scores(top_n_silhouette_scores=top_n_silhouette_scores,
tweets_dict=tweets_dict,
silhouette_score_per_tweet=tweet_index_silhouette_scores)
determine_anomaly_tweets_k_means(top_n=5)
Он производит следующие выходные данные и график:
Из приведенного выше Рис. 1 видно, что выбросы (точки в форме «треугольника» синего цвета) лежат в пограничной области кластеров. Рис. 2 представляет собой не что иное, как «диаграмму разброса силуэта», а выбросы показаны в виде «красных точек», и это доказывает, что выбросы имеют «показатель силуэта», близкий к нулю.
Подход на основе фактора локальных выбросов (близости)
Прежде чем приступить к подробному обсуждению, необходимо дать несколько определений некоторых показателей, приведенных ниже:
- Nk (A): набор k-ближайших соседей точки данных A
- k-distance (A): k-е ближайшее расстояние от соседей
- достижимое расстояние (A, B): достижимое расстояние между точками данных A и B задается этими формулами.
- local-reachable-density (A) или lrd (A): величина, обратная среднему достижимому расстоянию точки данных A от ее соседей, и определяется формулами ниже:
- local-outlier-factor (A) или lof (A): средняя локальная-достижимая-плотность соседей, деленная на локальную-достижимую-плотность точки данных A, и определяется по формулам ниже:
В приведенных выше определениях все «расстояния» даны методом обратного косинусоподобия, аналогично подходу «k-средних».
С помощью lrd (A) можно получить среднее расстояние перемещения для достижения соседей или любого кластера точек данных из A. Чем ниже значение lrd (A), тем ниже его достижимость, т. Е. Это указывает на то, что точка данных находится лежит далеко от других.
По lof (A) можно сравнить lrd точки A с ее соседями. Если «lrd» соседей выше, то эта конкретная точка данных находится далеко от плотной области, и, следовательно, «выброс» и его «показатель выброса» задаются значением «lof». Обычно lof ›1 означает« вероятный выброс ».
После вычисления значений «LOF» для всех точек данных сортировка их в порядке убывания даст первые n вероятных выбросов с «n» в качестве входного параметра. Я применил то же самое к предварительно обработанным данным «Твиттера» с двумя основными компонентами, дающими наибольшую дисперсию, и получил наибольшее количество выбросов.
from matplotlib import pyplot as plt
from pyod.models.lof import LOF
class LOFDetectionTransformer(BaseEstimator):
def __init__(self):
self._model = None
def fit(self, x, y=None):
self._model = LOF(metric='cosine')
self._model.fit(x)
return self
def transform(self, x):
return self._model.decision_scores_
def determine_anomaly_tweets_lof(top_n):
tweets_dict = _read_all_health_tweets()
tweets = tweets_dict.values()
pl = Pipeline(steps=[('doc2vec', Doc2VecTransformer()),
('pca', PCA(n_components=2)),
('lof', LOFDetectionTransformer())])
pl.fit(tweets)
scores = pl.transform(tweets)
tweet_index_decision_scores = []
decision_scores_tweet_index = []
for index, score in enumerate(scores):
decision_scores_tweet_index.append((score, index))
tweet_index_decision_scores.append((index, score))
sorted_scores = sorted(decision_scores_tweet_index, key=sort_key, reverse=True)
top_n_tweet_index_decision_scores = []
print("Top ", top_n, " anomalies")
for i in range(top_n):
score, index = sorted_scores[i]
top_n_tweet_index_decision_scores.append((index, score))
print(tweets_dict[index])
print('Decision Score: ', score)
print("..................")
plot_scatter_lof(tweets_dict=tweets_dict, tweet_index_decision_scores=tweet_index_decision_scores,
top_n_tweet_index_decision_scores=top_n_tweet_index_decision_scores)
determine_anomaly_tweets_lof(top_n=5)
Вызов функции, приведенной выше, показывает, что текстовые твиты с наиболее высокими значениями пяти выбросов с более высокими «оценками решения» (параметр «top_n») производят следующие выходные данные и график.
Здесь «Decison Scores» - это не что иное, как масштабированные «lof» значения точек данных. Все выбросы на приведенном выше графике рассеяния показаны как точки, обведенные красным кружком. Алгоритм «LOF» зависит от двух важных параметров, как указано ниже.
n-соседи: Нет соседей, которые следует учитывать вокруг точки данных для вычисления «k-расстояния» и «lrd». Обычно его значение равно 20, но очень часто его значение определяется знанием предметной области.
загрязнение: отношение выброса к общей численности популяции. Обычно его значение равно 0,1, но, как и выше, его значение также зависит от знания предметной области. «Загрязнение» играет очень важную роль в определении «порогового уровня» в популяции. «Threshold lof» может использоваться, чтобы решить, является ли новая точка данных выбросом или нет (в нашем случае новый текстовый твит, которого нет в обучающем наборе)
Сравнение двух подходов
Оба подхода «кластеризация k-средних» и «LOF» имеют некоторые преимущества и недостатки. В обоих случаях случайность вывода можно увидеть в нескольких прогонах. В первую очередь это происходит из-за генерации "Doc2Vec" и перетасовки там.
Преимущества подхода «кластеризация k-средних»:
i) Предварительное знание или знание предметной области данных не требуется. Параметры «k» можно определять динамически. Подходит для тех случаев, когда отсутствуют знания о данных.
Недостатки подхода "кластеризация k-средних":
i) Время работы больше. Само по себе определение оптимального "k" занимает довольно много времени.
ii) Не работает, если форма кластера не сферическая. Фактически, в этом случае «Силуэтная оценка» сама начнет давать неверные результаты.
iii) Немного сложно определить выброс в случае невидимых данных.
Преимущества подхода LOF:
i) Очень хорошо работает в случае данных произвольной формы. Это аналог «DBSCAN» и работает по той же концепции «локальной близости».
ii) Время работы меньше.
iii) Для невидимых данных тоже работает неплохо. Он может пометить как «выпадающий / не выпадающий» новые данные, которых не было в обучающем наборе.
Недостатки метода LOF:
i) Требуется знание предметной области для параметров: «загрязнение» и «n_neighbours».
Итак, очевидно, что эти два подхода фактически дополняют друг друга. Кто-то должен досконально разобраться в бизнес-сценарии использования, прежде чем принимать какое-либо решение о выборе того или иного подхода.
Кодовую базу для решения можно найти здесь.
Моя страница в Linkedin: https://www.linkedin.com/in/avishek-nag-957a0015/
Недавно я написал книгу по ML (https://twitter.com/bpbonline/status/1256146448346988546)
Ссылки:
- Фактор местного выброса - http://www.dbs.ifi.lmu.de/Publikationen/Papers/LOF.pdf
- алгоритм k-средних - https://www.datascience.com/blog/k-means-clustering
- Анализ основных компонентов - https://towardsdatascience.com/a-one-stop-shop-for-principal-component-analysis-5582fb7e0a9c
Эта история опубликована в The Startup, крупнейшем предпринимательском издании Medium, за которым следят +444 678 человек.
Подпишитесь, чтобы получать наши главные новости здесь.
