Постановка задачи

В качестве примера применения кластеризации рассмотрим принцип действия антиспамового фильтра, назначение которого — принять решение о том, является ли данное письмо несанкционированно рассылаемой рекламной информацией. Действие подобного фильтра может базироваться на разных алгоритмах, но, как правило, состоит из двух процессов: настройки фильтра (которая выполняется либо однократно, либо периодически, но не часто) и принятия решения о том, относится ли спама конкретное письмо к категории (что происходит намного чаще, чем настройка фильтра).

Один из возможных алгоритмов настройки антиспамового фильтра выглядит следующим образом. Берется большое количество писем, о которых точно известно, принадлежат ли они к несанкционированно рассылаемой рекламе. Далее для каждого письма вычисляется частотность встречающихся в нем определенных, заранее заданных слов, словосочетаний или символов. Сведения об этом наборе служат исходными данными для процесса создания кластеров согласно описанному выше алгоритму (этот процесс в некоторых источниках называется model training — тренировка модели). Принятие решения о принадлежности конкретного письма к категории спама осуществляется на основании того, в какой кластер попадет данное письмо. Заметим, что алгоритм действия коммерческих антиспамовых фильтров может быть сложнее — данная статья отнюдь не претендует на детальный разбор принципов их работы.

В качестве примера исходных данных воспользуемся набором сведений о более чем 4 тыс. писем, изученных сотрудниками компании Hewlett-Packard в 1999 году. Этот набор данных, доступный в виде файла в формате CSV по адресу www.ics.uci.edu/~mlearn/MLRepository.html (на указанном сайте находится довольно много интересных баз данных, которые разрешено свободно применять в научных целях), содержит одну таблицу, в которой имеется колонка IsSpam с целочисленными значениями (1 — письмо является спамом, 0 — письмо не является таковым), а также большое количество колонок с частотностью различных английских слов. Для упрощения работы с этим набором данных импортируем его в какую-нибудь СУБД, например в Access или Microsoft SQL Server. Имеет также смысл создать автоматически заполняемое целочисленное ключевое поле, которое потребуется при создании модели Data Mining на основе этих данных (рис. 2).

рис. 2

Итак, можно приступить к созданию кластеров.

Создание кластеров

ля создания кластеров следует запустить инструмент администрирования аналитических служб Microsoft SQL Server Analysis Manager (мы не будем останавливаться на подробностях применения данного инструмента; интересующиеся этим вопросом могут обратиться к циклу статей «Введение в OLAP», опубликованному в нашем журнале в 2001 году, — найти его можно на компакт-диске, прилагаемом к этому номеру журнала). С помощью Analysis Manager следует создать новую многомерную базу данных (назовем ее MyMiningData) и описать в ней доступ к источнику исходных данных (в нашем случае — к базе данных Access; рис. 3).

рис. 3

Далее следует выбрать соответствующую дочернюю ветвь Mining Models, а из ее контекстного меню — пункт New Mining Model. Затем нужно ответить на вопросы мастера построения моделей Data Mining. В частности, необходимо указать следующее: для построения модели используются реляционные данные, применяется алгоритм Microsoft Clustering, данные для анализа расположены в одной таблице (при этом следует выбрать ее имя). Затем в этой таблице нужно выбрать поле, являющееся уникальным идентификатором каждого письма в наборе (case key), а также поля, которые будут использоваться в качестве параметров для построения кластеров. В нашем примере из имеющихся в таблице нескольких десятков полей, соответствующих частоте употребления в письмах разных слов и символов, мы выбрали десять (рис. 4).

рис. 4

Завершить создание модели можно в редакторе Relational Mining Model Editor, указав в свойствах модели число кластеров (пусть оно будет равно пяти). Создание самих кластеров осуществляется с помощью выбора пункта меню Tools ® Process Mining Model (рис. 5).

рис. 5

Ниже мы рассмотрим, что представляют собой полученные кластеры.