chapter-23.tex

\chapter{Практика: спам-фильтр}
\label{ch:23}

\thispagestyle{empty}

В~2002 году Пол Грэхем, имея некоторое количество свободного времени пос\-ле продажи
Viaweb Yahoo, написал статью <<A Plan for Spam>>\pclfootnote{Она доступна по адресу
  \url{http://www.paulgraham.com/spam.html} и в книге <<Hackers \& Painters: Big Ideas from
  the Computer Age>> (O'Reilly, 2004).}, которая привела к небольшой революции в технологии
фильтрации спама.  До этой статьи, большинство спам-фильтров были написаны в терминах
рукописных правил: если сообщение имеет в заголовке слово XXX, то, вероятно, оно является
спамом; если в сообщении имеются три или больше слов в строке написанных ЗАГЛАВНЫМИ
БУКВАМИ, то вероятно, что это тоже спам. Грэхем провёл несколько месяцев пытаясь написать
фильтр, который бы использовал такие правила, до того, как осознал, что это фундаментально
неправильная задача.

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

Чтобы не пытаться думать как спамер, Грэхем решил попробовать отделять спам от не спама,
используя статистику, собранную о том, какие слова появляются в обоих типах сообщений.
Фильтр может отслеживать то, как часто отдельные слова появляются и в спаме и в не спаме,
и затем использовать частоты вхождения этих слов в сообщения, чтобы вычислить вероятность
того, к какой группе относится сообщение.  Он назвал этот подход байесовской фильтрацией
(Bayesian filtering) по ассоциации с названием статистического подхода, который он
использовал для вычисления частот слов\pclfootnote{Есть некоторые возражения на тему,
  действительно ли подход, предложенный Грэхемом, является <<байесовским>>.  Однако имя уже
  стало привычным, и оно становится синонимом для названия <<статистический>>, когда речь
  идёт о спам-фильтрах.}.

\section{Сердце спам-фильтра}

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

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

\begin{myverb}
(defpackage :com.gigamonkeys.spam
  (:use :common-lisp :com.gigamonkeys.pathnames))
\end{myverb}

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

\begin{myverb}
(in-package :com.gigamonkeys.spam)
\end{myverb}

Вы можете продолжать использовать это имя пакета или можете заменить
\lstinline{com.gigamonkeys} на домен, который находится под вашим контролем\footnote{Плохой
  практикой является распространение версии этого приложения, используя пакет, имя
  которого начинается с \lstinline{com.gigamonkeys}, поскольку вы не управляете данным
  доменом.}\hspace{\footnotenegspace}.

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

\begin{myverb}
CL-USER> (in-package :com.gigamonkeys.spam)
#<The COM.GIGAMONKEYS.SPAM package>
SPAM> 
\end{myverb}

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

\begin{myverb}
(defun classify (text)
  (classification (score (extract-features text))))
\end{myverb}

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

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

\begin{myverb}
(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)))
\end{myverb}

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

\begin{myverb}
(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.")))
\end{myverb}

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

\begin{myverb}
(defvar *feature-database* (make-hash-table :test #'equal))
\end{myverb}

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

\begin{myverb}
(defun clear-database ()
  (setf *feature-database* (make-hash-table :test #'equal)))
\end{myverb}

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

\begin{myverb}
(defun intern-feature (word)
  (or (gethash word *feature-database*)
      (setf (gethash word *feature-database*)
            (make-instance 'word-feature :word word))))
\end{myverb}

Вы можете выделить из сообщения отдельные слова с помощью регулярных выражений.  Например,
используя библиотеку Common Lisp Portable Perl-Compatible Regular Expression
(\lstinline{CL-PPCRE}), написанную Weitz, вы можете написать \lstinline{extract-words} следующим
образом\footnote{Библиотека \lstinline{CL-PPCRE} включена в исходные тексты для книги,
  доступные с сайта, посвящённого книге.  Или вы можете скачать её с сайта разработчика по
  адресу \url{http://www.weitz.de/cl-ppcre/}.}\hspace{\footnotenegspace}:

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

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

\begin{myverb}
(defun extract-features (text)
  (mapcar #'intern-feature (extract-words text)))
\end{myverb}

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

\begin{myverb}
SPAM> (extract-words "foo bar baz")
("foo" "bar" "baz")
\end{myverb}

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

\begin{myverb}
SPAM> (extract-words "foo bar baz foo bar")
("baz" "foo" "bar")
\end{myverb}

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

\begin{myverb}
SPAM> (extract-features "foo bar baz foo bar")
(#<WORD-FEATURE @ #x71ef28da> #<WORD-FEATURE @ #x71e3809a>
 #<WORD-FEATURE @ #x71ef28aa>)
\end{myverb}

Однако, как вы можете видеть, стандартный метод печати произвольных объектов не особо
информативен.  В~процессе работы над этой программой было бы полезно иметь возможность
печатать объекты \lstinline{word-feature} в более понятном виде.  К счастью, как я упоминал в
главе~\ref{ch:17}, печать объектов реализована в терминах обобщённой функции
\lstinline{PRINT-OBJECT}, так что для изменения способа печати объектов \lstinline{word-feature} вам
нужно определить метод для \lstinline{PRINT-OBJECT}, специализированный для
\lstinline{word-feature}.  Для того чтобы сделать реализацию подобных методов более лёгкой,
Common Lisp предоставляет макрос \lstinline{PRINT-UNREADABLE-OBJECT}\footnote{Основная причина
  использования \lstinline{PRINT-UNREADABLE-OBJECT} заключается в том, что он берёт на себя
  заботу о выдаче ошибки, если кто-то пытается напечатать ваш объект в форме, подходящей
  для последующего считывания, например при использовании директивы \lstinline{~S} функции
  \lstinline{FORMAT}.}\hspace{\footnotenegspace}.

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

\begin{myverb}
(print-unreadable-object (object stream-variable &key type identity)
  body-form*)
\end{myverb}

Аргумент \lstinline{object} является выражением, которое вычисляется в объект, который должен
быть напечатан.  Внутри тела \lstinline{PRINT-UNREADABLE-OBJECT} \lstinline{stream-variable}
связывается с потоком, в который вы можете напечатать все, что вам нужно. Всё, что вы
на\-пе\-ча\-тае\-те в этот поток, будет выведено в \lstinline{PRINT-UNREADABLE-OBJECT} и заключено в
стандартный синтаксис для нечитаемых объектов~---
\lstinline!#<>!\footnote{\lstinline{PRINT-UNREADABLE-OBJECT} также выдаёт ошибку, если он
  используется в то время, когда переменная контроля печати \lstinline{*PRINT-READABLY*} имеет
  истинное значение.  Так что метод \lstinline{PRINT-OBJECT}, состоящий только из
  \lstinline{PRINT-UNREADABLE-OBJECT}, будет корректно реализовывать поведение
  \lstinline{PRINT-OBJECT} с учётом состояния переменной \lstinline{*PRINT-READABLY*}.}\hspace{\footnotenegspace}.

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

\begin{myverb}
(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))))
\end{myverb}

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

\begin{myverb}
  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>)
\end{myverb}

\section{Тренируем фильтр}

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

\begin{myverb}
(defun train (text type)
  (dolist (feature (extract-features text))
    (increment-count feature type))
  (increment-total-count type))
\end{myverb}

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

\begin{myverb}
(defun increment-count (feature type)
  (ecase type
    (ham (incf (ham-count feature)))
    (spam (incf (spam-count feature)))))
\end{myverb}

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

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

\begin{myverb}
(increment-count some-feature 'ham)
\end{myverb}

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

\begin{myverb}
(increment-count some-feature 'spam)
\end{myverb}

\noindent{}то будет выполнено второе выражение, увеличивая счётчик для спама.  Заметьте, что при
вызове \lstinline{increment-count} символы \lstinline{ham} и \lstinline{spam} маскируются, иначе это
приведёт к тому, что они будут считаться именами переменных.  Но они не маскируются, когда
они используются в \lstinline{ECASE}, поскольку \lstinline{ECASE} не вычисляет ключи
сравнения\footnote{С технической точки зрения, ключи сравнения в выражениях \lstinline{CASE}
  или \lstinline{ECASE} рассматриваются как указатели списков, которые могут обозначать списки
  объектов.  Отдельный объект, не являющийся списком, рассматривается как указатель
  списка, состоящий только из одного объекта, в то время как список обозначает сам себя.
  Таким образом, каждое выражение может иметь несколько ключей сравнения; \lstinline{CASE} и
  \lstinline{ECASE} будут выбирать выражения, чей список ключей содержит нужное значение.
  Например, если вы хотите сделать \lstinline{good} синонимом для \lstinline{ham}, а \lstinline{bad}~---
  синонимом для \lstinline{spam}, то вы можете записать \lstinline{increment-count} в следующем
  виде:

\begin{myverb}
(defun increment-count (feature type)
  (ecase type
    ((ham good) (incf (ham-count feature)))
    ((spam bad) (incf (spam-count feature)))))
\end{myverb}
}\hspace{\footnotenegspace}.

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

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

\begin{myverb}
(defvar *total-spams* 0)
(defvar *total-hams* 0)

(defun increment-total-count (type)
  (ecase type
    (ham (incf *total-hams*))
    (spam (incf *total-spams*))))
\end{myverb}

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

\begin{myverb}
(defun clear-database ()
  (setf
   *feature-database* (make-hash-table :test #'equal)
   *total-spams* 0
   *total-hams* 0))
\end{myverb}

\section{Пословная статистика}

Сердцем статистического спам-фильтра являются функции, которые вычисляют статистические
вероятности.  Математические нюансы\pclfootnote{Говоря о математических нюансах,
  закоренелые статистики могут быть оскорблены легкомысленным использованием слова
  <<вероятность>> в данной главе.  Однако, поскольку даже профессора, которые делятся на
  байесианцев и вероятностников, не могут прийти к согласию о значении термина
  вероятность, то я не буду об этом беспокоиться.  Это книга о программировании, а не о
  статистике.} того, как эти вычисления производятся, не являются темой данной книги~---
заинтересованные читатели могут обратиться к нескольким статьям Гэри Робинсона (Gary
Robinson)\pclfootnote{К~статьям Robinson, которые относятся к теме данной главы, можно
  отнести <<A Statistical Approach to the Spam Problem>> (опубликованная в Linux Journal и
  доступная с \url{http://www.linuxjournal.com/article.php?sid=6467}, а также в более
  коротком варианте, в его блоге по адресу
  \url{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>> (доступная по адресу \url{http://garyrob.blogs.com/whychi93.pdf}).
  Другой полезной статьёй может быть <<Handling Redundancy in Email Token Probabilities>>
  (доступна с \url{http://garyrob.blogs.com//handlingtokenredundancy94.pdf}).  Архив
  списка рассылки проекта SpamBayes (\url{http://spambayes.sourceforge.net/}) также
  содержит большое количество полезной информации об алгоритмах и подходах к тестированию
  спам-фильтров.}. Однако я сосредоточусь на том, как это все реализуется.

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

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

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

\begin{myverb}
(defun spam-probability (feature)
  (with-slots (spam-count ham-count) feature
    (/ spam-count (+ spam-count ham-count))))
\end{myverb}

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

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

\begin{myverb}
(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)))))
\end{myverb}

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

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

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

\begin{myverb}
(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))))
\end{myverb}

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

\section{Комбинирование вероятностей}

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

Если бы вероятности отдельных свойств были бы независимы, то можно было бы перемножить их
для получения общей вероятности.  Но, к сожалению, в действительности они зависимы~---
некоторые свойства появляются вместе с другими, а некоторые никогда не появляются с
другими\pclfootnote{Техники, которые комбинируют не независиммые вероятности таким образом,
  как будто они являются независимыми, называются <<наивными байесовскими>>.  Оригинальное
  предложение Грэхема в действительности было наивным байевским классификатором с
  использованием некоторых <<эмпирически выведенных>> констант.}.

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

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

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

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

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

\begin{myverb}
(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))))
\end{myverb}

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

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

\begin{myverb}
(defun untrained-p (feature)
  (with-slots (spam-count ham-count) feature
    (and (zerop spam-count) (zerop ham-count))))
\end{myverb}

Новой функцией является \lstinline{fisher}.  Если предположить, что вы уже имеете функцию
\lstinline{inverse-chi-square}, \lstinline{fisher} является достаточно простой.

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

К сожалению, существует небольшая проблема с этой прямолинейной реализацией.  Хотя
использование \lstinline{REDUCE} является кратким и идиоматичным способом умножения списка
чисел, но в этом конкретном приложении существует опасность, что произведение будет
слишком маленьким, чтобы быть представленным как число с плавающей запятой. В~этом случае
результат окажется нулём.  И если произведение
вероятностей будет равно нулю, то всё будет напрасно, поскольку вызов \lstinline{LOG} для нуля
либо выдаст ошибку, либо, в некоторых реализациях, приведёт к получению специального
значения <<отрицательная бесконечность>>, которое приведёт к тому, что все последующие
вычисления станут бессмысленными.  Это очень нежелательно, поскольку метод Фишера очень
чувствителен к малым значениям (близким к нулю) и при умножении часто возникает
вероятность потери значимых разрядов.

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

\begin{myverb}
(log (reduce #'* probs))
\end{myverb}

\noindent{}напишите вот этот:

\begin{myverb}
(reduce #'+ probs :key #'log)
\end{myverb}

\section{Обратная функция chi-квадрат}

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

\begin{myverb}
(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))
\end{myverb}

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

\section{Тренируем фильтр}

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

\begin{myverb}
SPAM> (clear-database)
\end{myverb}

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

\begin{myverb}
SPAM> (train "Make money fast" 'spam)
\end{myverb}

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

\begin{myverb}
SPAM> (classify "Make money fast")
SPAM
SPAM> (classify "Want to go to the movies?")
UNSURE
\end{myverb}

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

\begin{myverb}
(defun classification (score)
  (values
   (cond
     ((<= score *max-ham-score*) 'ham)
     ((>= score *min-spam-score*) 'spam)
     (t 'unsure))
   score))
\end{myverb}

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

\begin{myverb}
SPAM> (classify "Make money fast")
SPAM
0.863677101854273D0
SPAM> (classify "Want to go to the movies?")
UNSURE
0.5D0
\end{myverb}

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

\begin{myverb}
SPAM> (train "Do you have any money for the movies?" 'ham)
1
SPAM> (classify "Make money fast")
SPAM
0.7685351219857626D0
\end{myverb}

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

\begin{myverb}
SPAM> (classify "Want to go to the movies?")
HAM
0.17482223132078922D0
\end{myverb}

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

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

\section{Тестируем фильтр}

Для тестирования фильтра вам нужны наборы сообщений известных типов.  Вы можете
использовать сообщения из вашего почтового ящика или можете взять один из наборов
сообщений, размещённых в Интернете.  Например, набор сообщений
SpamAssassin\pclfootnote{Несколько наборов спамовых сообщений, включая набор сообщений от
  SpamAssassin, можно найти по адресу
  \url{http://nexp.cs.pdx.edu/~psam/cgi-bin/view/PSAM/CorpusSets}.} содержит несколько
тысяч сообщений, классифицированных вручную на спам, явный не спам и не спам, который
тяжело отличить от спама.  Чтобы сделать пользование тестами более простым, вы можете
определить вспомогательные функции, которые управляются массивом пар имя файла/тип.  Вы
можете определить функцию, которая принимает имя файла и тип и добавляет их в набор
следующим образом:

\begin{myverb}
(defun add-file-to-corpus (filename type corpus)
  (vector-push-extend (list filename type) corpus))
\end{myverb}

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

\begin{myverb}
(defparameter *corpus* (make-array 1000 :adjustable t :fill-pointer 0))
\end{myverb}

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

\begin{myverb}
(defun add-directory-to-corpus (dir type corpus)
  (dolist (filename (list-directory dir))
    (add-file-to-corpus filename type corpus)))
\end{myverb}

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

\begin{myverb}
SPAM> (add-directory-to-corpus "mail/spam/" 'spam *corpus*)
NIL
SPAM> (add-directory-to-corpus "mail/ham/" 'ham *corpus*)
NIL
\end{myverb}

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

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

\begin{myverb}
(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)))
\end{myverb}

Эта функция начинает работу с очистки базы свойств\footnote{Если вы хотите проводить
  тестирование, не затрагивая существующую базу свойств, то вы должны связать
  \lstinline{*feature-database*}, \lstinline{*total-spams*} и \lstinline{*total-hams*}, используя
  \lstinline{LET}, но вы не будете иметь возможности просмотра этих баз после окончания работы
  данной функции, до тех пор, пока вы не будете возвращать эти значения как результат
  работы функции.}\hspace{\footnotenegspace}. Затем она перемешивает набор писем, используя функцию, которую мы
реализуем далее, и определяет, на основе параметра \lstinline{testing-fraction}, сколько
значений мы будем использовать для обучения и сколько мы оставим для тестирования.  Две
вспомогательные функции \lstinline{train-from-corpus} и \lstinline{test-from-corpus} будут
принимать именованные параметры \lstinline{:start} и \lstinline{:end}, что позволит работать над
частью заданного набора сообщений.

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

\begin{myverb}
(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))))
\end{myverb}

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

\begin{myverb}
(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)))))
\end{myverb}


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

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

Простым и эффективным способом реализации \lstinline{shuffle-vector} будет использование
алгоритма Фишера---Ятеса (Fisher---Yates)\pclfootnote{Этот алгоритм назван в честь Фишера,
  который предложил метод, используемый для комбинации вероятностей, и Франка Ятеса, его
  соавтора по книге <<Statistical Tables for Biological, Agricultural and Medical
  Research>> (Oliver \& Boyd, 1938), в которой, согласно высказыванию Кнута, они впервые
  опубликовали описание данного алгоритма.}.  Вы можете начать с реализации функции
  \lstinline{nshuffle-vector}, которая перемешивает вектор, используя то же самое хранилище.
  Имя функции соответствует тому же самому соглашению по именованию деструктивных функций,
  таких как \lstinline{NCONC} и \lstinline{NREVERSE}.  Она выглядит следующим образом:

\begin{myverb}
(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)
\end{myverb}

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

\begin{myverb}
(defun shuffle-vector (vector)
  (nshuffle-vector (copy-seq vector)))
\end{myverb}

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

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

\begin{myverb}
(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))))
\end{myverb}


\section{Анализ результатов}

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

\begin{myverb}
(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))))))
\end{myverb}

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

\begin{myverb}
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
\end{myverb}

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

\begin{myverb}
(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))
\end{myverb}

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

\begin{myverb}
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))
\end{myverb}

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

\begin{myverb}
(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))))))
\end{myverb}

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

\begin{myverb}
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
\end{myverb}

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

\begin{myverb}
(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))
\end{myverb}

\section{Что далее?}

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

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

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

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "pcl-ru"
%%% TeX-open-quote: "<<"
%%% TeX-close-quote: ">>"
%%% End: