Применение в задаче классификации SMS сообщений оптимизированного наивного байесовского классификатора

С момента появления технологии СМС сообщений прошло более 15 лет, и как всякая технология были этапы интенсивного роста, стабильной эксплуатации и медленного угасания (наблюдается в настоящее время [1,2]). Однако, несмотря на снижение популярности технологии СМС, в настоящее время, это единственная технология, способная доставлять текстовые сообщения поверх GSM трафика в отсутствии активного Интернет соединения, становясь, таким образом, гарантированным способом доставки (в случае активного статуса абонента в сети). Благодаря данной отличительной черте, СМС остается активным каналом распространения заведомо неинтересной, а порой и зловредной, информации для конечного потребителя, классифицируемой далее как спам. Также, несмотря на снижение СМС трафика, количество спама в нем продолжает расти [3]. Таким образом, задача внедрения существующих и разработка новых методов классификации сообщений является актуальной.

В настоящее время существует большое количество решений основанных как на неадаптивных, так и адаптивных алгоритмах. Среди подобных решений можно выделить: искусственные нейронные сети, искусственные иммунные алгоритмы, деревья решений, методы ближайших соседей ( k-NN алгоритмы), регрессионные модели, вероятностные подходы и т.д. Также, большое внимание уделяется разработке новых алгоритмов, с использованием последних достижений в области машинного обучения и DataMining ’а.

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

комплексах и аппаратах пользователей, при классификации СМС сообщений является их определение в один из двух классов: класс спам ( S ) сообщений и сообщений, не относящихся к спаму ( nS ) [4]. Техника классификации зачастую основана на обнаружении ранее внесенных ключевых слов в некоторый «черный список». Например для ОС Android применяется технология Spam SMS blocker или SMS spam runner в ОС Symbian . Функционирование системы классификации основано на конечном числе ключевых слов в спам словаре и зачастую не удовлетворяют своими характеристиками при процессе классификации сообщений для конечного пользователя.

Однако, несмотря на постоянные разработки и совершенствование текущих алгоритмов, наивный байесовский классификатор (НБК) является одним из наиболее популярных алгоритмов [5] по причине простоты реализации и минимальных как человеческих, так и финансовых затрат при внедрении в информационные системы (ИС) компаний-провайдеров или на устройствах конечных потребителей (пользователей).

Простота и формализация подхода в НБК, при которой все слова в СМС сообщении не зависят друг от друга, делает его менее эффективным в случае, если бы учитывался и порядок слов. Поэтому его оптимизация, учитывающая данный аспект есть актуальная задача. Для этого предлагается использование основанного на НБК алгоритма, рассматривающего СМС не только как набор слов, но и как набор некоторых объектов (группы слов). Предполагается, что данный подход позволит повысить общую точность процесса классификации за счет расчета количества не только каждого слова, но и количества групп слов входящих в одно сообщение.

МЕХАНИЗМ РАСЧЕТА ВЕРОЯТНОСТИ

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

Рассмотрим примитивное СМС сообщение X , состоящее из конечного набора слов X 1 ,...,X n : X = ( X ! ,..., Xn^ .

Обозначим за Y класс (в нашем случае это классы S и nS ), к которому данное сообщение может быть отнесено. Тогда для любых двух слов X₁ и X₂ из сообщения x вероятность отнесения к классу Y равно:

p ( X | Y ) = p ( X 1 , X ₂| Y ) =

= p (X J X 2 , Y ) p ( X 2 I Y ) =     (1)

= p ( X 1 | Y ) p ( X 2 | Y )

Экстраполируя на конечное число слов X₁ ,..., X_n , получим соотношение:

n p (X!,..., X„|Y) = П p (X\Y) .   (2)

i = 1

С другой стороны, вероятность того что Y примет l -ое возможное значение для сообщения, состоящего из X₁ ,..., X_n слов, в соответствии с теоремой Байеса равна:

p ( Y = y_z | X 1 ,..., X n ) =

_ p^(Y = У / ) p ^{( X} p™> ^X n | ^Y = У / ) w 4                                                      . ⁽³⁾

ПОСТРОЕНИЕ ОБУЧАЮЩЕЙ ТАБЛИЦЫ

Для наглядности описания процесса построения обучающей таблицы для СМС сообщений, рассмотрим конкретный пример. Пусть дано пять СМС сообщений: два сообщения X 1 = Р X 1 ^ , Х ₂ = Г X 1 _ X 2 1 относящиеся к классу nS и три ^Х 3 = Г ^X 3 1 , ^Х 4 = Г ^X 2 _ X 3 1 , ^X 5 = Г X 2 _ X 3 , X 2 _ ^X 3 ^! 1 к классу S . Тогда таблица векторов для выборки будет иметь вид (табл. 1):

В данном случае, из СМС сообщений были извлечены слова XX 1 , X ₂, X ₃ ^ , которые являются характеристическими признаками при дальнейшей классификации СМС сообщений. Извлечение слов подразумевает отсутствие учета знаков препинания. Тогда общее кол-во слов входящих в тот или иной класс (табл. 2):

В случае появления в системе нового сообщения x , процесс выделения признаков (слов) будет состоять из следующих этапов:

• 1.    Из сообщения удаляются все знаки препинания и выделяются только слова;

• 2.    Слова не встречающиеся в исходной векторной таблице исключаются;

• 3.    Подсчитывается общее количество оставшихся слов.

В нашем представленном примере, вероятность того, что новое СМС сообщение x будет отнесено к классу nS равно:

p ( nS | X i , X 2 , X 3 ) =

• =    p ( nS ) p ( X 1 1 nS ) p ( X ₂1 nS ) p ( X ₃1 nS ) . ⁽⁵⁾

А вероятность того что сообщение x будет отнесено к классу S равно:

p ( S | X 1 , X 2 , X 3 ) = p ( S ) p ( X 1 1 S ) p ( X 2 1 S ) p ( X 3 1 S ) .(6)

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

ОПТИМИЗАЦИЯ НБК

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

Построение обучающей таблицы

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

Таблица 1. Векторная таблица сообщений

Сообщение	Класс	Количество слов
		X 1	X 2	X 3
—* x 1	nS	1	0	0
—— x 2	nS	1	1	0
x 3	S	0	0	1
—— x 4	S	0	1	1
x 5	S	0	2	2

Таблица 2. Количество вхождений слов в определенные классы

Слова	Класс nS	Класс S
X 1	2	0
X 2	1	3
X 3	0	4
Итого	3	7

Процесс построения ассоциаций

Для наглядности процесса построения ассоциаций рассмотрим конкретный пример. Пусть дано 9 СМС сообщений из классов nS и S: 5 из класса S и 4 – nS соответственно.

S : x i = Г X 1 , X 2 , X 5 1 , ^x 2 = Г X 2 , X 3 1 ,

• ^X 3 = Г X 1 , X 3 1 , ^X 4 = Г X 1 , X 2 1 ,

X 5 = Г X 1 , X 2 , X 3 1

nS : x 6 = Г ^X 2 , ^X 4 1 , ^X 7 = Г ^X 1 , ^X 2 , ^X 4 1 ,

^X 8 = Г ^X 2 , ^X 3 1 , ^X 9 = Г ^X 1 , ^X 2 , ^X 3 , ^X 5 1

Максимальная длина анализируемых ассоциаций не может быть больше минимальной длины сообщений. В нашем случае, минимальная длина равна 2 (сообщения л : ₂ , X ₃ , X ₄ , X ₆ , X ₈ ). Таким образом, множество слов, характеризующих сообщения, входящие в класс S состоит из элементов Г X 11 Г X 21 Г X 31 Г X 51 Г X 1 , X 21 Г X 1 , X 31 Г X 2 , X 3 1 ^, тогда как множество nS состоит из элементов Г X 1 1Г X 2 1Г X 3 1Г X 4 1, Г X 5 1Г X 1 , X 2 1, Г X 2 , X 3 1, Г X 2 , X 4 1 .

Составим таблицу векторов для классов nS и S. Для этого из каждой определенной последова- тельности для своего соответствующего класса, определим количество вхождений в соответствующее сообщение. Тогда, таблица векторов для класса S будет иметь следующий вид (табл. 3).

Таблица векторов для класса nS имеет следующий вид (табл. 4).

Далее сформируем таблицу вхождения слов в определенный класс (табл. 5).

Таким образом:

Общее число слов в словаре | X | = 9;

Вероятность определения слова в класс nS p(nS) = 4/9;

Вероятность определения слова в класс S p(S) = 5/9;

Общее число слов класса nS | nS | = 19;

Общее число слов класса S | S | = 17.

Рассмотрим конкретный пример, возьмем тестовое СМС сообщение вида X = (X 1, X 1, X2,X2,X3). Тогда, в рамках построенной модели вероятность того, что сообщение будет отнесено к классу nS равно: p (nS, X1, X1, X 2, X 2, X3) = p (nS) X p (X11 nS )2 X x p(X21 nS)2 x p(X31 nS) x p(X1, X21 nS) x x p(X1, X31 nS) x p (X2, X31 nS)

Таблица 3. Таблица векторов класса S

Сообщение	Признаки (слова и их последовательности)
	X 1	X 2	X 3	X 5	X 1 ,X 2	X 1 ,X 3	X 2 ,X 3
—— x 1	1	1	0	1	1	0	0
Х 2	0	1	1	0	0	0	1
х 3	1	0	1	0	0	1	0
^— x 4	1	1	0	0	0	1	0
Х 5	1	1	1	0	1	1	1

Таблица 4. Таблица векторов класса nS

Сообщение	Признаки (слова и их последовательности)
	X 1	X2	X 3	X 4	X5	X1,X2	X2,X3	X2,X4
x 6	0	1	0	1	0	0	0	1
x 7	1	1	0	1	0	1	0	1
X 8	0	1	1	0	0	0	1	0
X 9	1	1	1	0	1	1	1	0

Таблица 5. Вхождение слов в определенный класс

Признаки КлассnS КлассS Признаки КлассnS КлассS X1 4 2 X1,X2 2 2 X2 3 4 X1,X3 3 0 X3 4 2 X2,X3 2 2 X4 0 2 X2,X4 0 2 Итого: Класс nS :19, Класс S: 17 p (nS, X,, X,, X 2, X 2, X3) =

С другой стороны, вероятность того, что сообщение будет отнесено к классу S равно:

p ( S , X 1 , X 1 , X 2 , X 2 , X 3 ) = p ( S ) X p ( X 1 1 S )² X

X p ( X 2 | S )² X p ( X 3 | S ) X p ( X 1 , X 2 | S ) X

X p ( X 1 , X з | S ) X p ( X 2 , X з | S )

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

4 + 15

p ⁽ X^JnS ) = 19 +T X i⁼ 28' p ⁽ X 2^{И )} =

= ^{3 T} 1 = — , p ( X | nS ) = 4 ^T 1 = — ,

19 t | X | 28     ³        19 t | X | 28

4  ( 5 V ( 4 )2  ( 5 ) ( 3 V  ( 4 )

= x| I x| I x| IxI I x| IxI

9  128J 128J  128J 128J  128J1

= 9 x 10 ^{- 9}

p ( S , X , , X , , X 2 , X 2 , X 3 ) =

_ 5 f 3 Y f 5 Y f 3 ) f 3 Y f 1 ) f 3 = 9 426 J Д 26 J ^X^ 26 Ja 26 J A 26M26

= 1.8 x 10 ^{- 9}

Исходя из проведенных вычислений, можно сказать, что тестовое сообщение Jr = ^ X 1 , X 1 , X ₂, X ₂, X ₃ ^ с большей вероятностью будет отнесено к классу nS , нежели S .

p ( X , , X 21 nS ) = YA = A p ( X , , X 3 1 nS ) =

3 T1     4                      2 T13

=         =   , p (X,, X3|nS) =         =

19 t | X | 28      ^{2 3}        19 t | X | 28

p ( X | S ) = ^{2 T 1} = — , p ( X ₂1 S ) = ^{4 T 1} =

¹        17 t | X | 26      ²        17 t | X |

=   , p (X, | S) == —

26     ³       17 t | X | 26

p ( X , , X 2 | S ) = ,7^ = ^ p ( X , , X3V.S ) =

0 T1      1                       2 T13

=-------=—, p (X,, X. | nS) == —,

17 t | X | 26     ^{2 3}        17 t | X | 26

Исходя из этого значение

СРАВНЕНИЕ НБК

И ОПТИМИЗИРОВАННОГО АЛГОРИТМА НА ПРАКТИКЕ

Для практической реализации предложенной идеи бралась база данных SMS Spam Collection v.1 [7], состоящая из 5574 СМС из nS и S классов.

Обучение было построено следующим образом, брались первые 600 строк из представленной БД и на базе них строилась векторная таблица, далее бралось 100 сообщений и проводилось тестирование полученного алгоритма. Далее брались следующие 600 строк, и к ним следующие 100 для тренировки. Процесс был повторен 5 раз. Результаты работы представлены в табл. 6.

Таким образом, для выбранной коллекции СМС сообщений эффективность оптимизированного алгоритма на 1.68% выше, нежели чем у НБК.

Таблица 6. Сводная таблица результатов работы алгоритма

№ тестовой выборки	Оптимизированный алгоритм	НБК(%)	Разница(%)
1	97.5	96.0	+1.5
2	98.2	96.3	+1.9
3	96.1	95.5	+0.6
4	99.0	97.2	+2.8
5	98.4	96.8	+1.6
Итого (среднее):	97.84	96.36	+1.68

ЗАКЛЮЧЕНИЕ

При рассмотрении СМС сообщений не только с точки зрения отдельных слов но и их ассоциаций, точность предложенного оптимизирован-  3.

ного алгоритма выше, нежели чем у НБК. Таким образом, более полный анализ структуры СМС сообщений позволяет не только повысить каче- 4. ство классификации, но и открывает большие перспективы с точки зрения разработки новых

алгоритмов и оптимизации существующих.