Регистрация | Войти
Lisp — программируемый язык программирования
Предыдущая Оглавление Следующая

23. Практика: спам-фильтр

В 2002-м году Paul Graham, имея некоторое количество свободного времени после продажи Viaweb Yahoo, написал статью "A Plan for Spam"1)), которая привела к небольшой революции в технологии фильтрации спама. До статьи Graham, большинство спам-фильтров были написаны в терминах рукописных правил: если сообщение имеет в заголовке слово XXX, то вероятно оно является спамом; Если в сообщении имеется три или больше слов в строке написанных ЗАГЛАВНЫМИ БУКВАМИ, то вероятно, что это тоже спам. Graham провел несколько месяцев пытаясь написать фильтр, который бы использовал такие правила, до того, как осознал что это фундаментально неправильная задача.

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

Чтобы не пытаться думать как спамер, Graham решил попробовать отделять спам от не-спама, используя статистику, собранную о том, какие слова появляются в обоих типах сообщений. Фильтр может отслеживать то, как часто отдельные слова появляются и в спаме и в не-спаме, и затем использовать частоты вхождения этих слов в сообщения, чтобы вычислить вероятность того, к какой группе относится сообщение. Он назвал этот подход Байесовской фильтрацией (Bayesian filtering) по ассоциации с названием статистического подхода, который он использовал для вычисления частот слов.2)

Сердце спам-фильтра

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

Это приложение будет достаточно большим, так что было бы удобным определение нового пакета для того, чтобы избежать конфликта имен. Например, в исходном коде, который вы можете загрузить с сайта данной книги, я использую имя пакета COM.GIGAMONKEYS.SPAM, определяя пакет, который использует и стандартный пакет COMMON-LISP и пакет COM.GIGAMONKEYS.PATHNAMES из главы 15. Определение выглядит следующим образом:

(defpackage :com.gigamonkeys.spam
  (:use :common-lisp :com.gigamonkeys.pathnames)
)

Любой файл, содержащий код для данного приложения должен начинаться со строки:

(in-package :com.gigamonkeys.spam)

Вы можете продолжать использовать это имя пакета, или можете заменить com.gigamonkeys на домен, который находится под вашим контролем.3)

Вы можете также ввести данное выражение в REPL чтобы переключиться на этот пакет и протестировать функции, которые вы пишете. В SLIME это приведет к смене строки приглашения с CL-USER> на SPAM>, вот так:

CL-USER> (in-package :com.gigamonkeys.spam)
#<The COM.GIGAMONKEYS.SPAM package>
SPAM>

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

(defun classify (text)
  (classification (score (extract-features text)))
)

Читая этот код, начиная с самых вложенных функций, первым шагом в классификации сообщения будет извлечение свойств (features), которые затем будут переданы функции score. В функции score вы вычислите значение, которое может быть преобразовано в одну из классификаций (спам, не-спам или неопределенное) функцией classification. Из этих трех функций, функция classification является самой простой. Вы можете предположить, что score будет возвращать значение около 1 если сообщение является спамом, около 0, если оно не является спамом, и около .5, если система не может корректно классифицировать его.

Так что вы можете реализовать classification следующим образом:

(defparameter *max-ham-score* .4)
(defparameter *min-spam-score* .6)

(defun classification (score)
  (cond
    ((<= score *max-ham-score*) 'ham)
    ((>= score *min-spam-score*) 'spam)
    (t 'unsure)
)
)

Функция extract-features также достаточно проста, хотя она требует большего количества кода для реализации. В настоящее время, свойствами, которые вы будете извлекать из сообщения, будут слова из текста сообщения. Для каждого слова вам необходимо отслеживать количество вхождений в сообщения, указанные как спам и не-спам. Удобным способом хранения всех этих данных вместе со словом, является определение класса word-feature с тремя слотами.

(defclass word-feature ()
  ((word       
    :initarg :word
    :accessor word
    :initform (error "Must supply :word")
    :documentation "The word this feature represents."
)

   (spam-count
    :initarg :spam-count
    :accessor spam-count
    :initform 0
    :documentation "Number of spams we have seen this feature in."
)

   (ham-count
    :initarg :ham-count
    :accessor ham-count
    :initform 0
    :documentation "Number of hams we have seen this feature in."
)
)
)

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

(defvar *feature-database* (make-hash-table :test #'equal))

Вы должны использовать DEFVAR вместо DEFPARAMETER, поскольку вы не хотите, чтобы *feature-database* была очищена, если в ходе работы вы заново загрузите файл, содержащий определение этой переменной – она может содержать данные, которые вы не хотите потерять. Конечно, это означает, что если вы хотите очистить накопленные данные, то вы не можете просто заново вычислить выражение DEFVAR. Так что вы должны определить функцию clear-database.

(defun clear-database ()
  (setf *feature-database* (make-hash-table :test #'equal))
)

Для нахождения свойств, присутствующих в заданном сообщении, код должен будет выделить отдельные слова, и затем найти соответствующий объект word-feature в таблице *feature-database*. Если *feature-database* не содержит такого свойства, то вам необходимо создать новый объект word-feature чтобы хранить данные о новом слове. Вы можете поместить эту логику в отдельную функцию, intern-feature, которая получает слово и возвращает соответствующее свойство, создавая его, если это необходимо.

(defun intern-feature (word)
  (or (gethash word *feature-database*)
      (setf (gethash word *feature-database*)
            (make-instance 'word-feature :word word)
)
)
)

Вы можете выделить из сообщения отдельные слова с помощью регулярных выражений. Например, используя библиотеку Common Lisp Portable Perl-Compatible Regular Expression (CL-PPCRE), написанную Weitz, вы можете написать extract-words следующим образом:4)

(defun extract-words (text)
  (delete-duplicates
   (cl-ppcre:all-matches-as-strings "[a-zA-Z]{3,}" text)
   :test #'string=
)
)

Теперь все что вам остается реализовать в extract-features – это совместить вместе extract-words и intern-feature. Поскольку extract-words возвращает список строк и вы хотите получить список, в котором каждая строка преобразована в соответствующий объект word-feature, то тут самое время применить MAPCAR.

(defun extract-features (text)
  (mapcar #'intern-feature (extract-words text))
)

Вы можете проверить эти функции в интерпретаторе, например вот так:

SPAM> (extract-words "foo bar baz")
("foo" "bar" "baz")

И вы можете убедиться, что DELETE-DUPLICATES работает правильно:

SPAM> (extract-words "foo bar baz foo bar")
("baz" "foo" "bar")

Вы также можете проверить работу extract-features.

SPAM> (extract-features "foo bar baz foo bar")
(#<WORD-FEATURE @ #x71ef28da> #<WORD-FEATURE @ #x71e3809a>
#<WORD-FEATURE @ #x71ef28aa>)

Однакоб как вы можете видеть, стандартный метод печати произвольных объектов не особо информативен. В процессе работы над этой программой, было бы полезно иметь возможность печатать объекты word-feature в более понятном виде. К счастью, как я упоминал в главе 17, печать объектов реализована в терминах обобщенной функции PRINT-OBJECT, так что для изменения способа печати объектов word-feature вам нужно определить метод для PRINT-OBJECT, специализированный для word-feature. Для того, чтобы сделать реализацию таких методов более легкой, Common Lisp предоставляет макрос PRINT-UNREADABLE-OBJECT.5)

Использование PRINT-UNREADABLE-OBJECT выглядит следующим образом:

(print-unreadable-object (object stream-variable &key type identity)
  body-form*
)

Аргумент object является выражением, которое вычисляется в объект, который должен быть напечатан. Внутри тела PRINT-UNREADABLE-OBJECT, stream-variable связывается с потоком, в который вы можете напечатать все, что вам нужно. Все что вы напечатаете в этот поток, будет выведено в PRINT-UNREADABLE-OBJECT и заключено в стандартный синтаксис для не читаемых объектов – #<>.6)

PRINT-UNREADABLE-OBJECT также позволяет вам включать в вывод тип объекта и признак уникальности (FIXME identity) путем указания именованных параметров type и identity. Если они имеют не-NIL значение, то вывод будет начинаться с имени класса и заканчиваться признаком уникальности (FIXME identity) объекта, точно также, как это делается стандартным методом PRINT-OBJECT для объектов, унаследованных от STANDARD-OBJECT. Для word-feature, вы вероятно захотите определить метод PRINT-OBJECT, который будет включать в вывод тип, но не включать признак уникальности(FIXME identity), а также значения слотов word, ham-count и spam-count. Такой метод может выглядеть вот так:

(defmethod print-object ((object word-feature) stream)
  (print-unreadable-object (object stream :type t)
    (with-slots (word ham-count spam-count) object
      (format stream "~s :hams ~d :spams ~d" word ham-count spam-count)
)
)
)

Теперь вы можете протестировать работу extract-features в интерпретаторе и увидите какие свойства были выделены из сообщения.

SPAM> (extract-features "foo bar baz foo bar")
(#<WORD-FEATURE "baz" :hams 0 :spams 0>
#<WORD-FEATURE "foo" :hams 0 :spams 0>
#<WORD-FEATURE "bar" :hams 0 :spams 0>)

Тренируем фильтр

Теперь, когда у вас имеется способ отслеживания отдельных свойств, вы почти готовы для реализации функции score. Но сначала вам нужно написать код, который вы будете использовать для тренировки фильтра, так что score будет иметь хоть какие-то данные для использования. Вы можете определить функцию train, которая получает некоторый текст и символ, определяющий к какому типу относится это сообщений (спам или не спам), и которая для всех свойств, присутствующих в заданном тесте, увеличивает либо счетчик для спама, либо счетчик не спама, а также глобальный счетчик обработанных сообщений. Снова, вы можете использовать подход разработки "сверху вниз" (top-down) и реализовать эту функцию в терминах других, еще не существующих функций.

(defun train (text type)
  (dolist (feature (extract-features text))
    (increment-count feature type)
)

  (increment-total-count type)
)

Вы уже написали extract-features, так что следующим шагом будет реализация increment-count, которая получает объект word-feature и тип сообщения, и увеличивает соответствующий слот данного свойства. Поскольку нет причин думать, что логика увеличения этих счетчиков будет применяться для различных видов объектов, то вы можете написать ее как обычную функцию.7) Поскольку вы определили и ham-count и spam-count с опциями :accessor, то для увеличения соответствующего слота вы можете использовать вместе INCF и функции доступа, созданные при вычислении DEFCLASS.

(defun increment-count (feature type)
  (ecase type
    (ham (incf (ham-count feature)))
    (spam (incf (spam-count feature)))
)
)

Конструкция ECASE является вариантом конструкции CASE, которые обе похожи на конструкцию case в языках, произошедших от Algol (переименованный в switch в C и его производных). Обе эти конструкции вычисляют свой первый аргумент и затем находят выражение, чей первый элемент (ключ) имеет то же самое значение в соответствии с логикой сравнения EQL. В нашем случае это означает, что вычисляется переменная type, возвращая значение, переданное как второй аргумент функции increment-count.

Ключи поиска не вычисляются. Другими словами, значение переменной type будет сравниваться с непосредственными объектами (literal objects), считанными процедурой чтения Lisp как часть выражения ECASE. В этой функции, это означает что ключи являются символами ham и spam, а не значениями переменных с именами ham и spam. Так что, если increment-count будет вызвана вот так:

(increment-count some-feature 'ham)

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

(increment-count some-feature 'spam)

то будет выполнено второе выражение, увеличивая счетчик для спама. Заметьте, что при вызове increment-count символы ham и spam маскируются, иначе это приведет к тому, что они будут считаться именами переменных. Но они не маскируются, когда они используются в ECASE, поскольку ECASE не вычисляет ключи сравнения.8)

Буква E в ECASE обозначает "исчерпывающий" (FIXME "exhaustive") или "ошибка ("error"), обозначая, что ECASE должен выдать ошибку, если сравниваемое значение не совпадает ни с одним, из перечисленных ключей. Обычное выражение CASE возвращает NIL, если не было найдено совпадений.

Для реализации increment-total-count, вам нужно решить, где вы будете хранить счетчики; в настоящий момент, достаточно использовать две глобальные переменные: *total-spams* и *total-hams*.

(defvar *total-spams* 0)
(defvar *total-hams* 0)

(defun increment-total-count (type)
  (ecase type
    (ham (incf *total-hams*))
    (spam (incf *total-spams*))
)
)

Вы должны использовать DEFVAR для определения этих двух переменных по той же причине, что и для переменной *feature-database* – они будут хранить данные, которые вы не хотите потерять лишь потому, что вы в процессе разработки заново считали исходный код. Но вы можете захотеть, чтобы эти переменные также сбрасывались при очистке *feature-database*, так что вы должны добавить несколько строк в функцию clear-database, как это показано здесь:

(defun clear-database ()
  (setf
   *feature-database* (make-hash-table :test #'equal)
   *total-spams* 0
   *total-hams* 0
)
)

Пословная статистика

Сердцем статистического спам-фильтра являются функции, которые вычисляют статистические вероятности. Математические нюансы9) того, как эти вычисления производятся не являются темой данной книги – заинтересованные читатели могут обратиться к нескольким статьям Gary Robinson.10) Однако я сосредоточусь на том, как это все реализуется.

Начальной точкой для статистических вычислений является набор измеренных значений – частоты сохраненные в переменных *feature-database*, *total-spams* и *total-hams*. Предполагая, что набор сообщений, на которых происходила тренировка, является статистически репрезентативным, мы можем рассматривать полученные частоты как вероятности появления соответствующих свойств в спаме и не спаме.

Основная идея классификации сообщения заключается в выделении всех свойств, вычисления вероятностей для отдельных свойств, и затем объединения всех вычисленных вероятностей в значение для всего сообщения. Сообщения, с большим количеством "спамовых" свойств и малым количеством "не спамовых" будут иметь значения около 1, а сообщения, с большим количеством "не спамовых" свойств и малым количеством "спамовых", получат значение около 0.

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

(defun spam-probability (feature)
  (with-slots (spam-count ham-count) feature
    (/ spam-count (+ spam-count ham-count))
)
)

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

Но вы более заинтересованы в вероятности, что данное свойство будет появляться в спамовых сообщениях, независимо от общей вероятности получения спама или не спама. Таким образом, вам нужно разделить число вхождений в спам на количество спамовых сообщений, на которых происходила тренировка, и то же самое сделать для число вхождений в не спамовые сообщения. Для того, чтобы избежать получения ошибок division-by-zero (деление на ноль), если либо *total-spams*, либо *total-hams* равно нулю, вам необходимо считать соответствующие частоты равными нулю. (Если общее число спамовых или не спамовых сообщений равно нулю, то соответствующие счетчики в свойствах, также должны быть равны нулю, так что вы можете рассматривать полученную частоту равной нулю).

(defun spam-probability (feature)
  (with-slots (spam-count ham-count) feature
    (let ((spam-frequency (/ spam-count (max 1 *total-spams*)))
          (ham-frequency (/ ham-count (max 1 *total-hams*)))
)

      (/ spam-frequency (+ spam-frequency ham-frequency))
)
)
)

Эта версия страдает от другой проблемы – она не обращает внимания на число проанализированных сообщений. Предположим, что вы производили обучение на 2000 сообщений, половина спама и половина не спама. Теперь рассмотрим два свойства, которые входят только в сообщения со спамом. Одно из них входит во все 1000 спамовых сообщений, а второе - только в одно из них. В соответствии с текущей реализацией spam-probability, появление любого из свойств в сообщении, сообщает, что оно является спамом с вероятностью 1.

Однако, все равно возможно, что свойство, которое встречается только в одном, даже спамовом сообщении, в действительности является нейтральным свойством – оно достаточно редко встречается в спаме и не спаме, всего в одном сообщении из 2000. Если вы проведете обучение на следующих двух тысячах сообщений, может быть, что оно встретитсяся еще раз, теперь – в не спаме, и станет нейтральным, с вероятностью вхождения в спам, равной .5.

Так что, наверное, вам хочется вычислять вероятность, которая учитывает количество случаев, когда встречается каждое свойство (number of data points). В своих статьях Robinson предложил функцию, основанную на Байесовском понимании включения наблюдаемых данных в априорные знания или предположения. Проще говоря, вы вычисляете новую вероятность начиная с предполагаемой априорной вероятности и веса, данного этой вероятности, а затем добавляя новую информацию. Функция предложенная Robinson'ом выглядит вот так:

(defun bayesian-spam-probability (feature &optional
                                  (assumed-probability 1/2)
                                  (weight 1)
)

  (let ((basic-probability (spam-probability feature))
        (data-points (+ (spam-count feature) (ham-count feature)))
)

    (/ (+ (* weight assumed-probability)
          (* data-points basic-probability)
)

       (+ weight data-points)
)
)
)

Robinson предложил значения 1/2 для assumed-probability и 1 для weight. Используя эти значения, свойство, которое один раз встретилось в спаме, и ни разу в не спаме, будет иметь значение bayesian-spam-probability равное 0.75, а свойство, которое встречается 10 раз в спаме, и ни разу в не спаме, будет иметь значение bayesian-spam-probability приблизительно равное 0.955, а то, которое входит в 1000 спамовых сообщений, и ни разу в не спам, будет иметь вероятность приблизительно равную 0.9995.

Комбинирование вероятностей

Теперь, когда вы можете вычислить bayesian-spam-probability для каждого из свойств в сообщении, последним шагом будет реализация функции score для комбинирования отдельных вероятностей в одно значение в диапазоне между 0 и 1.

Если бы вероятности отдельных свойств были бы независимы, то можно было бы перемножить их для получения общей вероятности. Но к сожалению в действительности они зависимы – некоторые свойства появляются вместе с другими, а некоторые никогда не появляются с другими.11)

Robinson предложил использовать метод комбинации вероятности, предложенный статистиком R. A. Fisher (Фишер). Не вдаваясь в детали того, как этот метод работает, он выглядит следующим образом: сначала вы комбинируете вероятности путем их умножения. Это дает вам число, близкое к нулю если в вашей выборке много свойств с низкими вероятностями. Потом вы берете логарифм данного числа и умножаете его на -2. Фишер в 1950 показал, что если отдельные вероятности были независимыми, и соответствовали равномерному распределению между 0 и 1, то результирующее значение будет соответствовать chi-квадрат распределению. Это значение и удвоенное число вероятностей может быть передано в обратную функцию chi-квадрат, которая вернет вероятность, которая отражает вероятность получения значения, которое больше значения, полученного комбинированием того же числа произвольно выбранных вероятностей. Когда обратная функция chi-квадрат возвращает маленькую вероятность, это означает что использовалось неправильно число малых значений (либо большое число значений с относительно малой вероятностью, либо несколько очень малых значений) в отдельных вероятностях.

Для использования этой вероятности для определения является ли сообщения спамом или нет, вы должны начать с нулевой гипотезы (null hypothesis), предполагаемого предположения, несостоятельность которого вы надеетесь доказать. Нулевая гипотеза заключается в том, что классифицируемое сообщение в действительности является произвольным набором свойств. Если это так, то отдельные вероятности (вероятности того, что каждое свойство может появиться в спаме) также будут произвольными. Так что, произвольная выборка свойств обычно будет содержать некоторые свойства с большой вероятностью появления в спаме, а другие свойства будут иметь низкую вероятность появления в спаме. Если вы скомбинируете эти произвольно выбранные вероятности в соответствии с методом Фишера, то вы должны получить усредненное значение, для которого обратная функция chi-квадрат сообщит вероятность успеха. Но если обратная функция chi-квадрат возвращает низкую вероятность, то это означает, что к сожалению, вероятности, которые вошли в объединенное значение, были выбраны не произвольным образом; использовалось слишком много значений с низкой вероятностью чтобы это было случайным. Так что вы можете избавиться от нулевой гипотезы и вместо этого использовать альтернативную гипотезу, что свойства были взяты из противоположного примера – с несколькими свойствами с высокой вероятностью, и большим числом с низкой вероятностью. Другими словами, это должно быть не спамовое сообщение.

Однако, метод Фишера не является симметричным, поскольку обратная функция chi-квадрат возвращает вероятность, что заданное число вероятность, выбранных произвольным образом, может быть скомбинировано таким образом, чтобы значение было больше чем полученное путем объединения настоящих вероятностей. Эта асимметрия работает на вас, поскольку когда вы отвергаете нулевую гипотезу, вы знаете что существует более правильная гипотеза. Когда вы комбинируете отдельные вероятности с помощью метода Фишера, и вам говорят, что существует высокая вероятность, что нулевая гипотеза является неправильной (что сообщение не является произвольным набором слов), то это означает, что сообщение, вероятно, является не спамом. Возвращенное число не является вероятностью, что сообщение не является спамом, но, по крайней мере, является хорошим признаком этого. И наоборот, комбинация отдельных вероятностей не спамовых свойств по Фишеру, дает вам признак того, что сообщение обладает свойствами спама.

Для получения окончательного результата вам необходимо объединить эти два значения в одно число, которое даст вам рейтинг "спам-не спам" в диапазоне от 0 до 1. Метод, рекомендованный Робинсоном, заключается в добавлении к числу 1/2 половины разницы между значениями вероятности отнесения к спаму и не спаму, или, другими словами, среднее значение вероятности отнесения к спаму и единицы минус вероятность отнесения к не спаму. Это приводит нужному эффекту, так что если два значения согласованы (высокая вероятность спама и низкая не спама, или наоборот), то вы получите четкий индикатор близкий по значению к 0 или 1. Но когда оба значения высоки или низки, то вы получите окончательное значение приблизительно равное 1/2, что будет рассматриваться как "неопределенное".

Функция score, которая реализует эту схему выглядит следующим образом:

(defun score (features)
  (let ((spam-probs ()) (ham-probs ()) (number-of-probs 0))
    (dolist (feature features)
      (unless (untrained-p feature)
        (let ((spam-prob (float (bayesian-spam-probability feature) 0.0d0)))
          (push spam-prob spam-probs)
          (push (- 1.0d0 spam-prob) ham-probs)
          (incf number-of-probs)
)
)
)

    (let ((h (- 1 (fisher spam-probs number-of-probs)))
          (s (- 1 (fisher ham-probs number-of-probs)))
)

      (/ (+ (- 1 h) s) 2.0d0)
)
)
)

Вы берете список свойств и выполняете цикл, строя два списка вероятностей – один список вероятностей, что сообщение, содержащее каждое из свойств, является спамом, и другой список, что сообщение не является спамом. Для оптимизации, вы также можете подсчитать количество вероятностей и передать это число функции fisher, чтобы избежать подсчета в самой функции fisher. Число, возвращенное функцией fisher будет маленьким, если отдельные вероятности содержат слишком много малых вероятностей чтобы рассматриваться как произвольный текст. Так что, малое число Фишера для "спамовых" вероятностей означает, что там содержится много не-спамовых свойств; вычитая число Фишера из 1, вы получаете вероятность того, что сообщение не является спамом. Соответственно, вычитая число Фишера для "не-спамовых" вероятностей из 1, дает вам вероятность того, что сообщение является спамом. Комбинируя эти два числа вы получаете общую вероятность принадлежности к спаму в диапазоне между 0 и 1.

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

(defun untrained-p (feature)
  (with-slots (spam-count ham-count) feature
    (and (zerop spam-count) (zerop ham-count))
)
)

Новой функцией является fisher. Предполагая, что вы уже имеете функцию inverse-chi-square, то fisher является достаточно простой.

(defun fisher (probs number-of-probs)
  "The Fisher computation described by Robinson."
  (inverse-chi-square
   (* -2 (log (reduce #'* probs)))
   (* 2 number-of-probs)
)
)

К сожалению, существует небольшая проблема с этой прямолинейной реализацией. Хотя использование REDUCE является кратким и идиоматичным способом умножения списка чисел, но в этом конкретном приложении существует опасность, что произведение будет слишком маленьким чтобы быть представленным как число с плавающей запятой. В этом случае, результат будет (FIXME underflow to zero) преобразован в ноль. И если произведение вероятностей будет равен нулю, то все будет напрасно, поскольку вызов LOG для нуля либо выдаст ошибку, либо, в некоторых реализациях, приведет к получению специального значения "отрицательная бесконечность", которое приведет к тому, что все последующие вычисления станут бессмысленными. Это очень нежелательно, поскольку метод Фишера очень чувствителен к малым значениям (близким к нулю), и при умножении часто возникает вероятность (FIXME underflow) переполнения снизу.

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

(log (reduce #'* probs))

напишите вот этот:

(reduce #'+ probs :key #'log)

Обратная функция Chi-квадрат

Реализации функции inverse-chi-square приведенная в данном разделе, является практически прямым переводом на Lisp версии функции написанной Робинсоном на Python. Точное математическое значение этой функции не рассматривается в этой книге, но вы можете получить примерное знание о том, что она делает, путем размышления о том, как значения, которые вы передаете функции fisher будут влиять на результат: большее количество малых значений, переданных fisher, приведет к меньшему значению произведения вероятностей. Логарифм от малого числа приведет к получению отрицательного числа с большим абсолютным значением, которое после умножения на -2 станет еще большим положительным числом. Таким образом, чем больше будет вероятностей с малым значением переданно fisher, тем большее значение будет передано inverse-chi-square. Конечно, число используемых вероятностей также влияет на значение переданное inverse-chi-square. Поскольку вероятности, по определению имеют значение меньшее или равное 1, то большее количество вероятностей входящих в произведение будет приводить к меньшему значению вероятности, и, соответственно, к большему числу, переданному функции inverse-chi-square. Так что функция inverse-chi-square должна возвращать низкую вероятность в тех случаях, когда число Фишера является ненормально большим для числа вероятностей, которые входят в него. Следующая функция делает следующее:

(defun inverse-chi-square (value degrees-of-freedom)
  (assert (evenp degrees-of-freedom))
  (min
   (loop with m = (/ value 2)
      for i below (/ degrees-of-freedom 2)
      for prob = (exp (- m)) then (* prob (/ m i))
      summing prob
)

   1.0
)
)

Возвращаясь к главе 10, вспоминаем, что функция EXP возводит число e (основание натурального алгоритма) в заданную степень. Таким образом, чем больше используемое значение, тем меньше будет начальное значение prob. Но это начальное значение затем будет выравнено вверх, для каждой из степеней свободы, пока m больше чем число степеней свободы. Поскольку значение возвращаемое функцией inverse-chi-square рассматривается как другая вероятность, то важно ограничить значение возвращаемое MIN, поскольку ошибки округления при умножении и возведении в степень могут привести к тому, что LOOP вернет сумму которая больше 1.

Тренируем фильтр

Поскольку вы написали classify и train таким образом, чтобы они принимали аргумент-строку, то вы можете работать с ними интерактивно. Если вы еще это не сделали, то вы должны переключиться на пакет, в рамках которого вы писали код, путем вычисления формы IN-PACKAGE в строке ввода, или используя сокращенную форму, реализованную в SLIME – change-package. Для использования этой возможности SLIME, наберите запятую, и затем наберите имя в строке ввода. Нажатие Tab при наборе имени пакета приведет к автоматическому дополнению имени, основываясь на именах пакетов, которые знает Lisp. Теперь вы можете выполнить любую функцию, которая является частью спам-фильтра. Сначала вы должны убедиться, что база данных свойств пуста.

SPAM> (clear-database)

Теперь вы можете тренировать фильтр с помощью конкретного текста.

SPAM> (train "Make money fast" 'spam)

И посмотреть что думает по этому поводу функция классификации.

SPAM> (classify "Make money fast")
SPAM
SPAM> (classify "Want to go to the movies?")
UNSURE

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

(defun classification (score)
  (values
   (cond
     ((<= score *max-ham-score*) 'ham)
     ((>= score *min-spam-score*) 'spam)
     (t 'unsure)
)

   score
)
)

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

SPAM> (classify "Make money fast")
SPAM
0.863677101854273D0
SPAM> (classify "Want to go to the movies?")
UNSURE
0.5D0

И теперь вы сможете увидеть что произойдет, если потренируете фильтр с некоторым количеством не-спамового текста.

SPAM> (train "Do you have any money for the movies?" 'ham)
1
SPAM> (classify "Make money fast")
SPAM
0.7685351219857626D0

Этот текст все равно считается спамом, но с меньшей оценкой, поскольку слово money входил в не-спамовый текст.

SPAM> (classify "Want to go to the movies?")
HAM
0.17482223132078922D0

А сейчас этот текст правильно распознается как не-спам, из-за наличия в нем слова movies, которое сейчас считается не-спамовым свойством.

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

Тестируем фильтр

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

(defun add-file-to-corpus (filename type corpus)
  (vector-push-extend (list filename type) corpus)
)

Значение corpus (набор) должно быть изменяемым вектором с указателем заполнения. Например, вы можете создать новый набор следующим образом:

(defparameter *corpus* (make-array 1000 :adjustable t :fill-pointer 0))

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

(defun add-directory-to-corpus (dir type corpus)
  (dolist (filename (list-directory dir))
    (add-file-to-corpus filename type corpus)
)
)

Например, предположим, что у вас есть каталог mail, содержащий два подкаталога, spam и ham, каждый содержащий сообщения соответствующего типа (спам и не-спам); вы можете добавить все файлы из этих двух каталогов к набору, хранящемуся в *corpus*, используя следующие команды:

SPAM> (add-directory-to-corpus "mail/spam/" 'spam *corpus*)
NIL
SPAM> (add-directory-to-corpus "mail/ham/" 'ham *corpus*)
NIL

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

Основная функция тестирования будет выглядеть следующим образом:

(defun test-classifier (corpus testing-fraction)
  (clear-database)
  (let* ((shuffled (shuffle-vector corpus))
         (size (length corpus))
         (train-on (floor (* size (- 1 testing-fraction))))
)

    (train-from-corpus shuffled :start 0 :end train-on)
    (test-from-corpus shuffled :start train-on)
)
)

Эта функция начинает работу с очистки базы свойств.13) Затем она перемешивает набор писем используя функцию, которую мы реализуем далее, и определяет, на основе параметра testing-fraction, сколько значений мы будем использовать для обучения и сколько мы оставим для тестирования. Две вспомогательные функции: train-from-corpus и test-from-corpus будут принимать именованные параметры :start и :end, что позволит работать над частью заданного набора сообщений.

Функция train-from-corpus достаточно проста – это цикл по соответствующей части набора сообщений с использованием DESTRUCTURING-BIND для выделения имени файла и типа из списка, находящегося в каждом элементе, и затем передача данных параметров для обучения. Поскольку некоторые почтовые сообщения, особенно такие, которые имеют вложения, имеют достаточно большой размер, то вы должны ограничить количество знаков, которое будет выделяться из сообщения. Функция будет получать текст с помощью функции start-of-file, которую мы реализуем далее, которая будет принимать в качестве параметров имя файла и максимальное количество возвращаемых знаков. train-from-corpus выглядит примерно так:

(defparameter *max-chars* (* 10 1024))

(defun train-from-corpus (corpus &key (start 0) end)
  (loop for idx from start below (or end (length corpus)) do
        (destructuring-bind (file type) (aref corpus idx)
          (train (start-of-file file *max-chars*) type)
)
)
)

Функция test-from-corpus выглядит аналогично, за тем исключением, что вы захотите возвращать список, содержащий результаты каждой из операции классификации, так что вы в последующем сможете проанализировать эти результаты. Так что вы должны захватывать и определенный тип сообщения, и вычисленное значение, возвращенные функцией classify, и собирать эти данные в список состоящий из имени файла, известного типа, типа, возвращенного функцией classify и вычисленного значения. Чтобы сделать результаты более понятными для человека, вы можете включить в список именованные параметры, описывающие соответствующие значения.

(defun test-from-corpus (corpus &key (start 0) end)
  (loop for idx from start below (or end (length corpus)) collect
        (destructuring-bind (file type) (aref corpus idx)
          (multiple-value-bind (classification score)
              (classify (start-of-file file *max-chars*))
            (list
             :file file
             :type type
             :classification classification
             :score score
)
)
)
)
)

Набор вспомогательных функций

Для окончания реализации функции test-classifier, вам необходимо написать две вспомогательных функции, которые напрямую не относятся к фильтрации спама – shuffle-vector и start-of-file.

Простым и эффективным способом реализации shuffle-vector будет использование алгоритма Фишера-Ятеса (Fisher-Yates).14) Вы можете начать с реализации функции nshuffle-vector, которая перемешивает вектор, используя то же самое хранилище. Имя функции соответствует тому же самому соглашению по именованию деструктивных функций, таких как NCONC и NREVERSE. Она выглядит следующим образом:

(defun nshuffle-vector (vector)
  (loop for idx downfrom (1- (length vector)) to 1
        for other = (random (1+ idx))
        do (unless (= idx other)
             (rotatef (aref vector idx) (aref vector other))
)
)

  vector
)

Недеструктивная версия просто делает копию оригинального вектора, и передает его в деструктивную версию.

(defun shuffle-vector (vector)
  (nshuffle-vector (copy-seq vector))
)

Другая вспомогательная функция – start-of-file, также достаточно проста. Наиболее эффективным способом считывания содержимого файла в память, будет создание массива соответствующего размера и использования функции READ-SEQUENCE для его заполнения. Так что вы можете создать массив знаков с размером, равным размеру файла, или максимальному количеству считываемых знаков, в зависимости от того, какое из значений будет меньше. К сожалению, как я упоминал в главе 14, функция FILE-LENGTH не особенно хорошо работает для текстовых потоков, поскольку количество знаков в файле может зависеть от используемой кодировки знаков и конкретного текста. В наихудшем случае, единственным способом точного определения количества знаков в файле, является считывание всего файла. Таким образом, неясно что вернет FILE-LENGTH для текстового потока; в большинстве реализаций FILE-LENGTH всегда возвращает число байт в файле, которое может быть больше, чем число знаков, которое может быть прочитано из файла.

Однако, READ-SEQUENCE возвращает количество прочитанных знаков. Так что вы можете попробовать считать количество знаков, определенное с помощью FILE-LENGTH, и вернуть подстроку, если количество считанных знаков было меньше.

(defun start-of-file (file max-chars)
  (with-open-file (in file)
    (let* ((length (min (file-length in) max-chars))
           (text (make-string length))
           (read (read-sequence text in))
)

      (if (< read length)
        (subseq text 0 read)
        text
)
)
)
)

Анализ результатов

Теперь вы готовы к написанию кода для анализа результатов, сгенерированных test-classifier. Мы должны вспомнить, что test-classifier возвращает список, возвращенный test-from-corpus, в котором каждый элемент является списком свойств (plist), описывающим результаты классификации одного файла. Этот список содержит имя файла, известный тип, результат классификации и вычисленное значение, возвращенное функцией classify. Первой частью нашего аналитического кода, который вы должны написать, является функция, которая будет возвращать признак того, была ли классфикация правильной, или нет (пропущенный спам или не спам, и т.п.). Вы можете использовать DESTRUCTURING-BIND для получения элементов :type и :classification списка результатов (используя опцию &allow-other-keys для того, чтобы DESTRUCTURING-BIND игнорировал другие пары имя-знаение), а затем используя вложенные выражения ECASE для преобразования отдельных сочетаний в конкретный символ.

(defun result-type (result)
  (destructuring-bind (&key type classification &allow-other-keys) result
    (ecase type
      (ham
       (ecase classification
         (ham 'correct)
         (spam 'false-positive)
         (unsure 'missed-ham)
)
)

      (spam
       (ecase classification
         (ham 'false-negative)
         (spam 'correct)
         (unsure 'missed-spam)
)
)
)
)
)

Вы можете проверить эту функцию в интерпретаторе.

SPAM> (result-type '(:FILE #p"foo" :type ham :classification ham :score 0))
CORRECT
SPAM> (result-type '(:FILE #p"foo" :type spam :classification spam :score 0))
CORRECT
SPAM> (result-type '(:FILE #p"foo" :type ham :classification spam :score 0))
FALSE-POSITIVE
SPAM> (result-type '(:FILE #p"foo" :type spam :classification ham :score 0))
FALSE-NEGATIVE
SPAM> (result-type '(:FILE #p"foo" :type ham :classification unsure :score 0))
MISSED-HAM
SPAM> (result-type '(:FILE #p"foo" :type spam :classification unsure :score 0))
MISSED-SPAM

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

(defun false-positive-p (result)
  (eql (result-type result) 'false-positive)
)


(defun false-negative-p (result)
  (eql (result-type result) 'false-negative)
)


(defun missed-ham-p (result)
  (eql (result-type result) 'missed-ham)
)


(defun missed-spam-p (result)
  (eql (result-type result) 'missed-spam)
)


(defun correct-p (result)
  (eql (result-type result) 'correct)
)

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

SPAM> (count-if #'false-positive-p *results*)
6
SPAM> (remove-if-not #'false-positive-p *results*)
((:FILE #p"ham/5349" :TYPE HAM :CLASSIFICATION SPAM :SCORE 0.9999983107355541d0)
(:FILE #p"ham/2746" :TYPE HAM :CLASSIFICATION SPAM :SCORE 0.6286468956619795d0)
(:FILE #p"ham/3427" :TYPE HAM :CLASSIFICATION SPAM :SCORE 0.9833753501352983d0)
(:FILE #p"ham/7785" :TYPE HAM :CLASSIFICATION SPAM :SCORE 0.9542788587998488d0)
(:FILE #p"ham/1728" :TYPE HAM :CLASSIFICATION SPAM :SCORE 0.684339162891261d0)
(:FILE #p"ham/10581" :TYPE HAM :CLASSIFICATION SPAM :SCORE 0.9999924537959615d0))

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

(defun analyze-results (results)
  (let* ((keys '(total correct false-positive
                 false-negative missed-ham missed-spam
)
)

         (counts (loop for x in keys collect (cons x 0)))
)

    (dolist (item results)
      (incf (cdr (assoc 'total counts)))
      (incf (cdr (assoc (result-type item) counts)))
)

    (loop with total = (cdr (assoc 'total counts))
          for (label . count) in counts
          do (format t "~&~@(~a~):~20t~5d~,5t: ~6,2f%~%"
                     label count (* 100 (/ count total))
)
)
)
)

Эта функция выдаст следующий результат, если ей передать список результатов, созданный с помощью test-classifier:

SPAM> (analyze-results *results*)
Total: 3761 : 100.00%
Correct: 3689 : 98.09%
False-positive: 4 : 0.11%
False-negative: 9 : 0.24%
Missed-ham: 19 : 0.51%
Missed-spam: 40 : 1.06%
NIL

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

(defun explain-classification (file)
  (let* ((text (start-of-file file *max-chars*))
         (features (extract-features text))
         (score (score features))
         (classification (classification score))
)

    (show-summary file text classification score)
    (dolist (feature (sorted-interesting features))
      (show-feature feature)
)
)
)


(defun show-summary (file text classification score)
  (format t "~&~a" file)
  (format t "~2%~a~2%" text)
  (format t "Classified as ~a with score of ~,5f~%" classification score)
)


(defun show-feature (feature)
  (with-slots (word ham-count spam-count) feature
    (format
     t "~&~2t~a~30thams: ~5d; spams: ~5d;~,10tprob: ~,f~%"
     word ham-count spam-count (bayesian-spam-probability feature)
)
)
)


(defun sorted-interesting (features)
  (sort (remove-if #'untrained-p features) #'< :key #'bayesian-spam-probability)
)

Что далее?

Конечно, вы могли бы сделать больше реализуя эту задачу. Для превращения написанного кода в полноценное приложение для фильтрации спама, вам понадобилось бы найти способ интеграции его в вашу почтовую систему. Один из способов, который можно было применить для того, чтобы можно было использовать любой почтовый клиенте, является написание кода, который бы позволял выполнять данное приложение как прокси для POP3 – протокола, который большинство клиентов используют для скачивания почты с почтовых серверов. Такая прокси могла бы забирать почту с настоящего POP3-сервера, и раздавать ее вашим почтовым клиентам после того, как сообщения либо будут помечены как спам с помощью дополнительных заголовков, так что фильтры ваших почтовых клиентов смогут распознать такие сообщения, либо будут отложены в сторону. Конечно, вам необходим способ для общения с фильтром на тему неправильной классификации сообщений – поскольку вы установите приложение как сервер, то вы также должны будете предоставить Web-интерфейс для работы с ним. Я буду обсуждать вопросы построения Web-интерфейсов в главе 26, и мы создадим его, для другого приложения, в главе 29.

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

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

1)Она доступна по адресу http://www.paulgraham.com/spam.html и в книге "Hackers & Painters: Big Ideas from the Computer Age" (O'Reilly, 2004
2)Есть некоторые возражения на тему, действительно ли подход, предложенный Graham, является "Байесовским". Однако имя уже стало привычным и оно становится синонимом для названия "ститистический", когда речь идет о спам-фильтрах.
3)Плохой практикой является распространение версии этого приложения, используя пакет, имя которого начинается с com.gigamonkeys, поскольку вы не управляете данным доменом.
4)Библиотека CL-PPCRE включена в исходные тексты для книги, доступные с сайта, посвященного книге. Или вы можете скачать ее с сайта разработчика по адресу http://www.weitz.de/cl-ppcre/.
5)Основная причина использования PRINT-UNREADABLE-OBJECT заключается в том, что он берет на себя заботу о выдаче ошибки, если кто-то пытается напечатать ваш объект в форме, подходящей для последующего считывания, например при использовании директивы ~S функции FORMAT.
6)PRINT-UNREADABLE-OBJECT также выдает ошибку, если он используется в то время, когда переменная контроля печати *PRINT-READABLY* имеет истинное значение. Так что метод PRINT-OBJECT состоящий только из PRINT-UNREADABLE-OBJECT будет корректно реализовывать поведение PRINT-OBJECT с учетом состояния переменной *PRINT-READABLY*.
7)Если вы позже решите, что вам нужны разные версии increment-feature для разных классов, то вы можете переопределить increment-count как обобщенную функцию, а текущую реализацию объявить методом, специализированным для word-feature.
8)С технической точки зрения, ключи сравнения в выражениях CASE или ECASE рассматриваются как указатели списков, которые могут обозначать списки объектов. Отдельный объект, не являющийся списком, рассматривается как указатель списка, состоящий только из одного объекта, в то время, как список обозначает сам себя. Таким образом, каждое выражение может иметь несколько ключей сравнения; CASE и ECASE будут выбирать выражения, чей список ключей содержит нужное значение. Например, если вы хотите сделать good синонимом для ham, а bad – синонимом для spam, то вы можете записать increment-count в следующем виде:
(defun increment-count (feature type)
  (ecase type
    ((ham good) (incf (ham-count feature)))
    ((spam bad) (incf (spam-count feature)))
)
)

9)Говоря о математических нюансах, закоренелые статистики могут быть оскорблены легкомысленным использованием слова "вероятность" в данной главе. Однако, поскольку даже профессора (FIXME pros), которые делятся на байезианцев и вероятностников, не могут прийти к согласию о значении термина вероятность, то я не буду об этом беспокоиться. Это книга о программировании, а не о статистике.
10)К статьям Robinson, которые относятся к теме данной главы, можно отнести "A Statistical Approach to the Spam Problem" (опубликованная в Linux Journal и доступная с http://www.linuxjournal.com/article.php?sid=6467, а также в более коротком варианте, в его блоге по адресу http://radio.weblogs.com/0101454/stories/2002/09/16/spamDetection.html) и "Why Chi? Motivations for the Use of Fisher's Inverse Chi-Square Procedure in Spam Classification" (доступная по адресу http://garyrob.blogs.com/whychi93.pdf). Другой полезной статьей может быть "Handling Redundancy in Email Token Probabilities" (доступна с http://garyrob.blogs.com//handlingtokenredundancy94.pdf). Архив списка рассылки проекта SpamBayes (http://spambayes.sourceforge.net/) также содержит большое количество полезной информации об алгоритмах и подходах к тестированию спам-фильтров.
11)Техники, которые комбинируют не-независиммые вероятности таким образом, как будто они являются независимыми, называются "наивными Байесовскими". Оригинальное предложение Graham в действительности было наивным Байевским классификатором, с использованием некоторых "эмпирически выведенных" констант.
12)Несколько наборов спамовых сообщений, включая набор сообщений от SpamAssassin можно найти по адресу http://nexp.cs.pdx.edu/~psam/cgi-bin/view/PSAM/CorpusSets.
13)Если вы хотите проводить тестирование не затрагивая существующую базу свойств, то вы должны связать *feature-database*, *total-spams* и *total-hams* используя LET, но вы не будете иметь возможности просмотра этих баз после окончания работы данной функции, до тех пор, пока вы не будете возвращать эти значения как результат работы функции.
14)Этот алгоритм назван в честь Фишера, который предложил метод, используемый для комбинации вероятностей, и Франка Ятеса, его соавтора по книге "Statistical Tables for Biological, Agricultural and Medical Research" (Oliver & Boyd, 1938) в которой, согласно высказыванию Кнута, они впервые опубликовали описание данного алгоритма.
Предыдущая Оглавление Следующая
@2009-2013 lisper.ru