From 31395157b14e12c4eb70a574a5cedb587d61b200 Mon Sep 17 00:00:00 2001 From: Vsevolod Stakhov Date: Thu, 6 Nov 2008 18:29:52 +0300 Subject: [PATCH] * Add description of classifying process --- README-classify.koi8.txt | 93 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 93 insertions(+) create mode 100644 README-classify.koi8.txt diff --git a/README-classify.koi8.txt b/README-classify.koi8.txt new file mode 100644 index 000000000..9f3934c90 --- /dev/null +++ b/README-classify.koi8.txt @@ -0,0 +1,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. +Такая организация позволяет замещать только наименее используемые токены. -- 2.39.5