1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
Особенности классификации и статистического анализа
===================================================
В rspamd используется алгоритм ортогональных разреженных биграмм (OSB),
который основан на следующем принципе:
н -----------------------------------
а -----------------------------------
б -----------------------------------
о | w1 | w2 | w3 | w4 | w5 |
р | | | | | | --> выходные токены
ы -----------------------------------
/ Текущий набор хешей и весов
/
Входные токены
То есть, процесс преобразования можно представить следующим образом:
для каждого набора весов (w1..w5) составляется набор хешей. Первоначальный
шаг выглядит так: берем 5 токенов, помещаем их в текущий набор, умножаем на
веса, складываем, получаем выходной токен. Далее применяем последовательно для каждого
набора весов. То есть, из одного набора хешей мы получаем число выходных токенов,
равное числу наборов весов. Далее мы в w1 помещаем новый хеш и сдвигаем w1..w4 на
1 вправо. С набором хешей w1',w1..w4 проделываем аналогичные операции. И так до
тех пор, пока входные токены не закончатся. Выходных токенов больше, чем входных,
в число раз, равное числу наборов весов.
Сейчас в rspamd для формирования наборов весов используется алгоритм ортогональных
разреженных биграмм. Число наборов в данном алгоритме равно N=W-1, где W - длина
набора хешей (окно). Наборы весов формируются следующим образом (для W=5):
{ 1, 7, 0, 0, 0 },
{ 3, 0, 13, 0, 0 },
{ 5, 0, 0, 29, 0 },
{ 11, 0, 0, 0, 51 },
После этого мы должны вычислить принадлежность потока выходных токенов к некоторому
классу. Для этого используется алгоритм Winnow.
Here's a quick synopsys of the algorithm:
Идея алгоритма очень проста:
1) Каждый возможный входной токен имеет вес 1.0 (то есть, нас интересуют только те
токены, которые не равны 1.0)
2) Для обучения проделываем следующие шаги:
- генерируем набор токенов путем OSB алгоритма
- удаляем все дупликаты
- если данный входной набор принадлежит классу (например, спам или неспам), то умножаем вес
каждого встреченного токена на т.н. Promotion Constant, которая равна 1,23
- если данный входной набор не принадлежит классу, то умножаем каждый найденный токен на
Demotion Constant в данном классе, которая равна 0,83
- абсолютно неважно, сколько раз встречался данный токен во входном потоке, мы его умножаем
на promotion или demotion только один раз
3) Для классификации потока мы поступаем следующим образом:
- генерируем набор токенов путем OSB алгоритма
- удаляем все дупликаты
- суммируем веса всех токенов, найденных в каждом из файлов данных статистики (при этом те токены,
которые мы не нашли, имеют вес 1)
- затем мы делим полученную сумму на число токенов и смотрим, какой из классов (файлов данных) набрал
больше очков и делаем заключение о принадлежности входного текста к классу
Файлы данных статистики представляют собой следующие структуры:
{
Header,
{ feature_block1..feature_blockN }
}
Заголовок файла очень прост:
struct {
char magic[3] = { 'r', 's', 'd' };
u_char version[2] = { '1', '0' };
uint64_t create_time;
}
Каждый feature_block состоит из 4-х полей:
struct {
uint32_t hash1;
uint32_t hash2;
uint32_t value; /* На самом деле это float */
uint32_t last_access;
}
Итого 16 байт на каждый feature. 0-е значения показывают свободную ячейку.
Значение hash1 используется в качестве индекса:
idx = hash1 % filesize;
Где filesize - размер в количестве feature_block'ов. При этом данный токен
должен помещаться в заданную ячейку или ячейку за ним. При этом образуется
цепочка токенов:
idx
\
| занят | занят | занят | свободен |
\-----^ \-----^ \-----^
При этом, длина такой цепочки должна быть лимитирована некоторым разумным числом,
например 128. Тогда максимальное время доступа будет не более 128-и итераций.
Если мы не нашли за 128 итераций свободную ячейку, то мы можем поместить новый токен
на место того, который меньше всего использовался (min (last_access)). При этом
при доступе к ячейке необходимо обновлять last_access: last_access = now - creation_time.
Такая организация позволяет замещать только наименее используемые токены.
|
