Автоматическое распознавание спам-сообщений пользователей социальной сети Twitter

Московский Физико-Технический Институт (Государственный университет)

Факультет управления и прикладной математики. Кафедра системного программирования.









Дипломная работа.

Автоматическое распознавание спам-сообщений пользователей социальной сети Twitter



Выполнила: Студентка 075 группы Соколова Евгения Александровна

Научные руководители: к.ф.–м.н. Турдаков Денис Юрьевич м.н.с. ИСП РАН Коршунов Антон Викторович













Mocква

2014

Содержание Аннотация …....................................................................................................................................... 3
Введение ….......................................................................................................................................... 4 1 Постановка задачи …............................................................................................................. 5 2 Введение в структуру Twitter …........................................................................................... 6

3 Исследование поведения спамеров и политики Twitter относительно спама …........ 7

3.1 Распространенность спама в Twitter …...................................................................... 7

3.2 Техники, применяемые спамерами в Twitter …......................................................... 7

      3.3 Политика Twitter относительно спама …................................................................... 8 4 Обзор существующих решений …...................................................................................... 10
4.1 Признаки используемые в машинном обучении с учителем ….............................. 10

4.1.1 Графовые признаки …........................................................................................ 11

4.1.2 Профильные признаки …................................................................................... 11

4.1.3 Признаки на основе взаимодействия ….......................................................... 11

4.1.4 Единицы измерения некоторых признаков …................................................. 11

4.1.5 Оценки значимости признаков …..................................................................... 13

4.2 Используемые классификаторы …............................................................................ 13

4.3 Прочие методы определения спама …...................................................................... 13

4.4 Существующие реализации ….................................................................................. 14

4.5 Выводы ….................................................................................................................... 14

5 Исследование и построение решения задачи ….............................................................. 15

5.1 Общее описание алгоритма машинного обучения для обнаружения спама ….... 15

5.2 Признаки машинного обучения …............................................................................ 15

5.2.1 Базовый метод …................................................................................................ 16

5.2.2 Дополнительные признаки …........................................................................... 16

5.2.2.1 Спам-слова …............................................................................................ 16

5.2.2.2 Профильные признаки …......................................................................... 17

5.2.2.3 Единицы измерения некоторых признаков …........................................ 17

5.2.2.4 Твитовые признаки …............................................................................... 18

5.2.2.5 Признаки на основе тематического моделирования …......................... 18

5.3 Алгоритмы машинного обучения …......................................................................... 19

5.4 Эксперимент …........................................................................................................... 19




1

5.4.1 Набор данных	20

5.4.1.1 Существующие наборы данных	20

5.4.1.2 Создание собственного набора данных	20

5.4.1.3 Ресэмплинг …............................................................................................ 22

5.4.2 Меры качества …................................................................................................. 23

5.4.3 Результаты эксперимента …............................................................................... 24

5.4.5 Анализ значимости признаков …...................................................................... 25

6 Описание практической части …....................................................................................... 26

6.1 Обоснование выбранного инструментария ….......................................................... 26

6.2 Общая схема работы …............................................................................................... 27

          6.3 Архитектура системы …............................................................................................. 28 Заключение ….................................................................................................................................... 29 Список литературы …...................................................................................................................... 30










































2

Аннотация.

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
















































3

Введение

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

      Анализ данных социальной сети Twitter имеет множество приложений, например, некоторые новости могут появиться и быть отслеженными в сети Twitter раньше, чем на новостных каналах. При анализе данных социальной сети контент, генерируемый спамерами может затруднять анализ данных. Кроме того, присутствие в социальной сети спамеров может представлять опасность для благонадежных пользователей.

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


































4

1 Постановка задачи

   Целью работы является исследование и разработка методов автоматического распознавания спам-сообщений в социальной сети Твиттер. В задаче были выделены следующие подзадачи:

   1. Исследование техник, используемых спамерами, а также мер, применяемых Twitter относительно спама.

   2. Проведение анализа существующих методов распознавания спама, а также способов оценки их эффективности.

3. Разработка методов автоматического распознавания спама.

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












































5

2 Введение в структуру Twitter

      Twitter — онлайн социальная сеть, позволяющая пользователям писать короткие сообщения, могущие быть увиденными и прокомментированными любым другим пользователем социальной сети (микроблоггинг). Особенностью Twitter является ограничение на длину сообщения в 140 символов. Структура Twitter представляет собой направленный граф, где пользователи — узлы, а ребра отражают отношения между ними.

Некоторые определения:

Статус (твит) — сообщение длиной до 140 символов, могущее содержать ссылки, а также хэштеги и упоминания; Ретвит — использование статуса, созданного другим пользователем;
Хэштег — специально зарезервированный символ #, употребляемый перед словом, обозначающим принадлежность к определенной теме; Упоминание — специально зарезервированный символ @, употребляемый перед именем пользователя;

В Twitter пользователь может формировать связь с другими пользователями. Различные виды связей показаны на Рисунке 1.
Друг: пользователь B является другом пользователя А; Фолловер: пользователь С является фолловером пользователя А;

Пользователи А и В находятся в отношении «взаимной дружбы» если являются друзьями (и, соответственно, фолловерами друг друга).












Рис. 1 Отношения между пользователями в Twitter













6

3 Исследование поведения спамеров и политики Twitter относительно спама

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

3.1 Распространенность спама в Twitter

      Результаты исследований показывают, что более 3% сообщений в Twitter являются спамом [1],[2], около 8% всех ссылок указывают на вредоносный контент [3]. Также сообщается, что более 90% всех спам-статусов содержат ссылки [4].

3.2 Техники, применяемые спамерами в Twitter

       В силу ограниченности длины статуса 140 символами и ограничения на отправление личных сообщений кому-либо, кроме фолловеров (https://support.twitter.com/articles/14606-posting-or-deleting-direct-messages), спамеры распространяют вредоносный контент преимущественно посредством ссылок. Twitter трансформирует все ссылки посредством собственного сервиса по сокращению URL, что позволяет спамерам не затрачивать дополнительных усилий на маскировку источника.

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

1. атака собственных фолловеров (любой статус пользователя автоматически появляется в новостной ленте его фолловеров) [5], [6]
2. использование упоминаний (твит с упоминанием пользователя появляется в новостной ленте упомянутого) [6]
3. покупка фолловеров с целью формирования видимости благонадежности аккаунта [5], покупка ретвитов [3]
4. атака пользователей, чьи твиты содержат слова релевантные проводимой спам-кампании [5]
5. использование в твитах популярных поисковых слов (техника напоминает SEO) [6]

6. эксплуатация хэштегов популярных тем [6], [7], создание спамерских тем [3]



7

7. изменение частей URL, с целью создания видимости различия ссылок [5],[8]

8. атака фолловеров знаменитости посредством упоминания ее в своих твитах [5]

9. использование специальных приложений, таких как TweetAttacks (ныне заблокирован Twitter, ныне http://www.tweetattackspro.com/) и TweetAdder(http://www.tweetadder.com/), облегчающих использование техник 4, 8 [5]

10. взлом аккаунтов пользователей (подбором паролей или фишингом) и рассылка спама от их лица [3], [7]
11. копирование твитов знаменитостей с добавлением спам-ссылки [3]

12. использование сервисов для сокращения ссылок (может быть сформирована длинная цепь перенаправлений) [3]

3.3 Политика Twitter относительно спама

Хотя алгоритм борьбы со спамом в Twitter не афишируется, чтобы не облегчить его обход, раздел «Abuse and Spam» Twitter rules
(Правила Twitter, https://support.twitter.com/articles/18311-the-twitter-rules) содержит перечисление действий, за которые аккаунт может быть заблокирован. Данный список позволяет составить некоторое представление о принципах борьбы Twitter со спамом. Некоторые условия, могущие служить поводом для блокировки аккаунта, перечисленные в правилах Twitter:
1. Создание множественных аккаунтов

2. Публикация ссылок на вредоносный контент

3. Создавать статусы, содержащие преимущественно ссылки

4. Создавать дублированные статусы от имени одного или разных аккаунтов

5. Создавать множественные нерелевантные статусы в темах, в т.ч. популярных

6. Использование множественных упоминаний в целях привлечения внимания к аккаунту, сервису или ссылке
7. Многочисленные блокировки и жалобы на спам со стороны других пользователей Несмотря на предупреждение о блокировке за вышеперечисленные действия, Twitter по тем или иным причинам блокирует далеко не все аккаунты, удовлетворяющие одному или нескольким из вышеперечисленных условий. Так, существует список спамерских аккаунтов [13], на странице источника которого указано, что автор регулярно отправляет списки обнаруженных спамерских аккаунтов в группу Twitter по борьбе со спамом.


8

Список был создан в 2009 году, тем не менее, лишь 27% из 632 аккаунтов были заблокированы Twitter к 2013.

































































9

4 Обзор существующих решений

      Методы обнаружения спама в социальных сетях берут начало с техник классификации сообщений электронной почты на спамерские и легитимные.
Техники варьируются от надстроек над SMTP, анализа последовательностей его транзакций и составления черных списков отправителей до идентификации спам-сообщений по определенным правилам, и, наконец применения различных методов машинного обучения: байесовской классификации, нейросетей, марковских моделей [10]. Среди традиционные методов классификации для электронной почты наиболее популярны Наивный байесовский классификатор и SVM, как признанные наилучшими для категоризации текстов [11].

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

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

В следующих подразделах рассматриваются признаки и классификаторы, используемые

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

4.1 Признаки используемые в машинном обучении с учителем

        Признаки подразделяются на следующие категории: «графовые» (отражающие характер и количество связей пользователя с соседями), «профильные» (описывающие данные, отраженные в профиле пользователя), взаимодействия (отражающие активность пользователя) и «твитовые» (описывают свойства содержания статусов пользователя). Легко видеть, что большинство из них должны отражать использование пользователем каких-либо техник, описанных в п.3.2. Ниже приводятся описания признаков, ранее использовавшихся в работах по определению спама в Twitter, с разделением по категориям, а также указанием источника.







10

4.1.1 Графовые признаки

1. Количество друзей [4]

2. Количество фолловеров [4], [14], [15]

3. Отношение количества фолловеров к количеству друзей [4]

R=
Nfollowers

4.  Репутация

N followers +N friends
[4]

Также в качестве признаков могут использоваться такие графовые характеристики как «обоюдность» - отношение кол-ва взаимных к кол-ву исходящих ссылок для

вершины пользователя в социальном графе [9], [18]; «локальный коэффициент кластеризации»

LC=

2?ev?

, где  Kv   — количество входящих и исходящих вершин для v,
ev
– кол-во


K v (Kv?1)















ребер на соседях v [18]; «промежуточная центрированность»
BC=
1

?

?st (v )
,







?st








(n?1)(n?2) s=v=t ?V




где  ?st
— кол-во кратчайших путей от s к t,  ?st (v )  кол-во тех из них, что проходят через v

[18].














4.1.2 Профильные признаки

1. Количество статусов пользователя [4]

2. Возраст аккаунта в днях [4]

3. Имя аккаунта содержит спам-слова [4]


4.1.3 Признаки на основе взаимодействия

1. Количество статусов-ответов от пользователя [4]

2. Количество упоминаний на пользователя [15]

3. Количество уникальных упомянутых пользователей [15]

4. Количество статусов, проретвиченных другими пользователями [14]
5. Показатель взаимодействия	IR= N tweets in reply to friends +Nretweets    [16]
Ntotal

4.1.4 Твитовые признаки

1. Процент статусов, содержащих ссылки [4], [16], среди последних двадцати [14], [16]

2. Количество хэштэгов по отношению к количеству слов (минимальное,	медиана,


11

максимальное, среднее арифметическое) [4]


3.
Количество ссылок по отношению к количеству слов (минимальное, медиана,
максимальное, среднее арифметическое) [4], [17]


4.
Количество символов в статусе (минимальное, медиана, максимальное,
среднее
арифметическое) [4]


5.
Количество хэштегов в статусе (минимальное, медиана, максимальное,
среднее
арифметическое) [4]


6.
Количество упоминаний в статусе (минимальное, медиана, максимальное,
среднее
арифметическое) [4]


7.
Количество  цифр  в  статусе  (минимальное,  медиана,  максимальное,  среднее
арифметическое) [4]


8.
Количество ссылок в статусе (минимальное, медиана, максимальное,

среднее
арифметическое) [4]


9.
Количество  слов  в  статусе  (минимальное,  медиана,  максимальное,  среднее
арифметическое) [4]


10. Количество ретвитов статуса (минимальное, медиана, максимальное,
среднее
арифметическое) [4]


11. Промежуток времени между статусами (минимальный, медиана,
максимальный,
среднее арифметическое) [4]


12. Количество уникальных статусов среди последних двадцати [14]


13. Количество статусов, содержащих упоминания [15], среди последних
двадцати
[14]


14. Количество статусов, содержащих хэштеги [15], среди последних
двадцати [14]

15. Количество использованных в статусах хэштегов [15], [17]

16. Количество использованных в статусах уникальных хэштегов [15]

17. Количество использованных в статусах ссылок [15]

18. Количество использованных в статусах уникальных ссылок [15]

19. Средняя частота повторения ссылок [15]

20. Процент статусов, содержащих спам-слова [4]










12

4.1.5 Оценки значимости признаков

      В работе [15] значимость признаков оценивалась с использованием прироста информации, наиболее значимыми (в порядке убывания) оказались признаки 17,13, 3, 16, 2. Также производилась оценка значимости по ухудшению результатов классификации для классификаторов Naive Bayesian, Jrip и J48 при удалении оцениваемого признака. Таким образом было заключено, что для Twitter важны признаки, характеризующие использование пользователем ссылок и упоминаний.
В работе [17] оценка по методу хи-квадрат показала наибольшую значимость признаков

3, 8 и 15.


4.2 Используемые классификаторы

      При решении задачи по определению спамеров в социальных сетях традиционно используются следующие классификаторы: NB, SVM, C4.5, Random Forest, J48. Наилучшие результаты показал Random Forest [18].

4.3 Прочие методы определения спама

      Существуют альтернативные методы обнаружения спама в социальных сетях, в частности, подход, основанный на тенденции спамеров образовывать связи друг с другом [9], предложен алгоритм поиска спамеров CIA — на основе начального множества отслеживаются остальные спамеры распространением «оценки зловредности» на основе социальных связях пользователей и семантических связей их статусов. Тем не менее, алгоритм CIA позиционируется не как полноценный алгоритм детектирования, а как «легковесный алгоритм вывода и ранжирования», могущий быть встроенным в систему обнаружения спамеров в комбинации с другими методами.
       В работе [12] предлагается находить потенциальных спамеров как пользователей, имеющих достаточно большое количество дублированных (почти в точности) у других пользователей статусов. Для выявления дублированных твитов среди набора твитов всех пользователей в наборе данных используется метод LHS, позволяющий оценить коэффициент схожести Жаккара для n-грамм над словами в статусах. Твиты, для которых коэффициент Жаккара превышает 0.8, считаются дубликатами. Использование данного метода в детектировании спамеров предполагает дальнейшую классификацию на основе свойств сообщений и профилей, характерных для спамеров, имеющих дублированные статусы.


13

4.4 Существующие реализации

      Существует бесплатное приложение TwitBlock (http://twitblock.org/) - фильтр «мусора» для Twitter и массовой блокировки аккаунтов. Позволяет находить спамеров среди друзей пользователя, или пользователей, недавно его упомянувших. Требует авторизации, таким образом, невозможен анализ данных социальной сети Twitter, получаемых через API, кроме как для собственных аккаунтов. Принципы работы TwitBlock описываются следующим образом: для каждого проверяемого пользователя проверяются некие характеристики, ассоциируемые со спамерской деятельностью, на основании которых выдается вероянтость того, что аккаунт является спамерским, в процентах.

4.5 Выводы

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






































14

5 Исследование и построение решения задачи

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

5.1 Общее описание алгоритма машинного обучения для обнаружения спама

       Формальная постановка задачи обнаружения спама в социальной сети Twitter: Задача: для аккаунта ? ? A, где A – множество аккаунтов, построить функцию

 категоризации ?(?): A ? {Spam, Ham}, то есть аккаунт классифицируется как спамерский, если функция ? принимает значение Spam, и как благонадежный иначе.

      Применение для классификации алгоритма машинного обучения с учителем включает два этапа: обучение и классификация.
Обучение:

1. Сформировать набор аккаунтов {A}, размеченных метками C = {Spam, Ham}.

2. Трансформировать каждый аккаунт в вектор признаков x?R|F|, где F -

множество признаков.

3. Запустить алгоритм обучения, порождающий классификатор ?(x) ? {Spam, Ham}

Классификация:

построенный классификатор ?(x) применяется к признаковому описанию аккаунта ?, таким образом получем предсказание принадлежности его к аккаунтам-распространителям спама.

5.2 Признаки машинного обучения

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


15

базовом методе, в подраздле 5.2.2 даются описания признаков, добавленных в улучшенном методе.

5.2.1 Базовый метод

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

• графовые признаки 1-4 (раздел 4.1.1)

• профильные признаки 1, 2 (раздел 4.1.2)

• признаки на основе взаимодействия 1, 3 (раздел 4.1.3), а также процент твитов пользователя, которые были проретвичены

• твитовые признаки 1-19 (раздел 4.1.4)

      Признаки, учитывающие использование спам-слов в имени аккаунта или твитах не используются, так как в работе [4] при описании этих признаков не указывается ссылка на список используемых спам слов. Ввиду необходимости самостоятельно составлять список спам слов признаки перенесены в раздел дополнительных.
     Также решено не задействовать в качестве признаков графовые характеристики в силу повышеной сложности их вычисления, а также того, что для их вычисления необходимо собрать подграф по размероам сопоставимый со всем графом [34].

5.2.2 Дополнительные признаки


5.2.2.1 Спам-слова

Так как не существует специализированого списка спам-слов для Twitter, был составлен

собственный список. Предполагается, что рассылка спама с использованием микроблоггинга использует те же средства, что и почтовая рассылка несмотря на малую длину сообщения. Задачей пользователя, рассылающего спам-сообщения обычно является заставить жертву перейти по ссылке, следовательно, используются слова-наживки: «100% free», «act now!»; названия известных продуктов: «apple», «iPad», «Nike», а также нецензурная лексика.

Для составления списка взяты слова из нескольких списков для электронной почты1.

1http://www.activewebhosting.com/faq/email-filterlist.html, http://www.mailup.com/spam-words-to-avoid.htm, http://digwp.com/2010/02/stop-spammers-custom-blacklist/,

http://www.leapfrogva.com/the-ultimate-list-of-email-spam-trigger-words/, https://github.com/splorp/wordpress-comment-blacklist/blob/master/blacklist.txt.


16

5.2.2.2 Профильные признаки

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

признак:

1) ? слово из списка: является подстрокой имени пользователя Предположение 1: спамеры часто указывают ссылку на сайт рекламируемого ими товара,

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

2) В профиле указана ссылка на сайт Предположение 2: для спамеров характерно владение многими профилями, в том числе
«про запас» на случай блокировки. Поэтому при создании новых профилей часто генерируются случайные последовательности символо вдля использования в качестве имени аккаунта. В имени аккаунта спамера будет в таком случае иметь место присутствие нехарактерных для слов и, особенно, имен, последовательностей символов.

Вводятся новые бинарные признаки:

3) Присутствие в имени аккаунта N-грам до определенной длины над символами из имен Предположение 3: при создании новых аккаунтов спамеру проще всего указать имя

пользователя, совпадающее с именем аккаунта. Новые признаки:
4) Схожесть имен аккаунта и пользователя (может вычисляться при помощи расстояния Левенштейна [19], коэффициента Жаккара [20] и др.)

      Необходимо также выбрать наилучшие меры схожести для строк. В работе [21] сравниваются различные метрики для строк, метрика Монге-Элкана [22] признается одной из наиболее эффективных для сравнения имен сущностей.
Данная метрика, как и расстояние Левенштейна является функцией редакционного расстояния. Также используется расстояние Левенштейна , нормированное по методу Монге-Элкана:

для строк s и t, разбитых на подстроки s = a1 ...aK, t = b1 ...bL
1  K	L

K i=1  i=1i ,b j )



5.2.2.3 Единицы измерения некоторых признаков

Для возможности учитывать различное количество последних статусов в пользователя?

вводятся признаки процент ретвитов и процент ответов среди статусов. При учитывании




17

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


5.2.2.4 Твитовые признаки

По списку спам-слов полученных в 5.2.2.1 считаются следующие признаки для твитов:

1) Количество спам-слов в сообщении минимальное, максимальное, медиана и среднее

2) Процент твитов, содержащих спам-слова

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

3) Количество заглавных букв в твите минимальное, максимальное, медиана и среднее

4) Процент твитов, содержащих заглавные буквы

5) Количество восклицательных знаков в твите минимальное, максимальное, медиана и среднее

6) Процент твитов, содержащих восклицательные знаки


5.2.2.5 Признаки на основе тематического моделирования

      Для тематического моделирования сообщений пользователей используется модель LDA (Рис. 2).
















Рис. 2 Модель LDA

LDA — генеративная вероятностная модель, в соответствии с которой каждый текст в корпусе моделируется как смесь над набором тем. Каждая тема, в свою очередь, моделируется как смесь над набором вероятностей тем [32]. В качестве документов используются статусы, сконкатенированные для каждого пользователя. В результате построения модели для каждого статуса пользователя всем словам соответствуют метки тем. Темой статуса считается наиболее


18

частая тема составляющих его слов. Таким образом для каждой последовательности статусов пользователя получаем последовательность тем статусов.
      В соответствии с работой, посвященной использованию LDA для выявления спам в сети интернет [33], вычисляются следующие признаки:
1) Количество тем для пользователя

2) Количество смен темы

3) Максимальное количество последовательных статусов на одну тему


5.3 Алгоритмы машинного обучения

      Будут применяться следующие алгоритмы машинного обучения, наиболее часто и успешно используемые в задаче обнаружения спам-сообщений: наивный байесовский классификатор, метод опорных векторов (SVM), J48, случайный лес.
      Наивный байесовский классификатор предсказывает класс объекта, минимизируя вероятность ошибки, в предположении, что признаки, используемые при его описании, попарно независимы [23].
Метод опорных векторов строит в пространстве признаков оптимальную гиперплоскость

– линейную функцию решения с максимальным зазором между векторами различных классов. При построении такой гиперплоскости зазор определяется лишь небольшим объемом обучающей выборки (т.н. Опорными векторами) [24].
      J48 – алгоритм построения дерева решений С4.5 с или без обрезания ветвей. Листья дерева решений классы, узлы – условия, определяющие переход по ветви. [25]
       Случайный лес – классификатор, представляющий собой ансамбль деревьев решений, предсказывающий класс обьекта как ниболее часто предсказываемый лежащими в основе деревьями, строящимися со случайным выбором признаков без обрезания ветвей [26].

5.4 Эксперимент

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









19

5.4.1 Набор данных


5.4.1.1 Существующие наборы данных

Вследствие установленных Twitter правил, ограничивающих распространение статусов,

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

      Авторы [4] предоставляют по запросу данные в виде посчитанных значений признаков, использованных в их работе.
       Также существует список из 632 спамеров [13]. Данный сисок получен на основе спам сообщений, полученных автором, сообщений с метокй @spam других пользователей (один из способов пожаловаться на спам в Twitter) и поиска по

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

5.4.1.2 Создание собственного набора данных

      Обычно используются методы сбора данных через Twiiter API с последующей разметкой данных как спама на основании блокировок пользователей сетью Twitter, а также черных списков URL [6], [7].
      По результатам обзора традиционных методов разметки данных используется комбинированный подход, включающий разметку спамеров как по блокировкам Twitter, так и по наличию в статусах ссылок находящихся в черных списках Google Safebrowsing.

Алгоритм создания набораа данных:

            Для набора данных, полученного при помощи Modis Crawler, содержащего 135 245 пользователей, полученных поиском в ширину. Ограничения: 1000 статусов на пользователя, в наборе данных присутствуют только пользователи, имеющие в сумме не более 10000 фолловеров и друзей
1. Выделено 7996 пользователей, чьи аккаунты оказались заблокированы Twitter через 2 месяца после сбора — определяются по переходу на страницу — https://twitter.com/account/suspended
2. Для всех статусов пользователей выделены как все полные ссылки (см.TwitterAPI https://dev.twitter.com/docs/api/1.1/get/statuses/user_timeline поле «expanded_url»),


20

так и все сокращенные ссылки (при помощи регулярного выражения, применяемого к тексту твита, т.к. не все такие ссылки отражены в поле «url»).

3. Среди всех ссылок выявляются содержащие вредоносный контент:

а) для сокращенных ссылок — по предупреждению от Twitter о возможной опасности посещения сайта (означает, что целевая страница присутствует в базе данных Twitter по вредоносным страницам, происхождение базы данных не уточняется, сообщается, что отсутствие указание на вредоносность сайта на http://www.google.com/safebrowsing/diagnostic еще не является основанием для разблокировки. Возможно, используются сообщения пользователей о вредоносных ссылках, которые те могут оставлять на странице https://support.twitter.com/forms/spam)
б) для полных ссылок — домены проверяются при помощи Google Safebrowsing

API

Все пользователи, .......................