123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293 |
- Особенности классификации и статистического анализа
- ===================================================
-
- В 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.
- Такая организация позволяет замещать только наименее используемые токены.
|