Iweishen

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

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

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

Подходы к классификации текстов

Существует три подхода к задаче классификации текстов.

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

Другой подход заключается в написании правил, по которым можно отнести текст к той или иной категории. Например, одно из таких правил может выглядеть следующим образом: "если текст содержит слова производная и уравнение, то отнести его к категории математика". Специалист, знакомый с предметной областью и обладающий навыком написания регулярных выражений, может составить ряд правил, которые затем автоматически применяются к поступающим документам для их классификации. Этот подход лучше предыдущего, поскольку процесс классификации автоматизируется и, следовательно, количество обрабатываемых документов практически не ограничено. Более того, построение правил вручную может дать лучшую точность классификации, чем при машинном обучении (см. ниже). Однако создание и поддержание правил в актуальном состоянии (например, если для классификации новостей используется имя действующего президента страны, соответствующее правило нужно время от времени изменять) требует постоянных усилий специалиста.

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

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

Имеется множество категорий (классов, меток) ${\mathfrak {C}}=\{c_{1},...,c_{\left|{\mathfrak {C}}\right|}\}$.

Имеется множество документов ${\mathfrak {D}}=\{d_{1},...,d_{\left|{\mathfrak {D}}\right|}\}$.

Неизвестная целевая функция $\Phi \colon {\mathfrak {C}}\times {\mathfrak {D}}\rightarrow \{0,1\}$.

Необходимо построить классификатор $\Phi ^{\prime }$, максимально близкий к $\Phi$.

Имеется некоторая начальная коллекция размеченных документов ${\mathfrak {R}}\subset {\mathfrak {C}}\times {\mathfrak {D}}$, для которых известны значения $\Phi$. Обычно её делят на «обучающую» и «проверочную» части. Первая используется для обучения классификатора, вторая — для независимой проверки качества его работы.

Классификатор может выдавать точный ответ $\Phi ^{\prime }\colon {\mathfrak {C}}\times {\mathfrak {D}}\rightarrow \{0,1\}$ или степень подобия $\Phi ^{\prime }\colon {\mathfrak {C}}\times {\mathfrak {D}}\rightarrow [0,1]$.

Этапы обработки

Индексация документов

Построение некоторой числовой модели текста, например в виде многомерного вектора слов и их веса в документе. Уменьшение размерности модели.

Построение и обучение классификатора

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

Оценка качества классификации

Можно оценивать по критериям полноты, точности, сравнивать классификаторы по специальным тестовым наборам.

Обучающие методы

Наивная байесовская модель

Наивная байесовская модель является вероятностным методом обучения. Вероятность того, что документ d попадёт в класс c записывается как $P(c|d)$. Поскольку цель классификации - найти самый подходящий класс для данного документа, то в наивной байесовской классификации задача состоит в нахождении наиболее вероятного класса c_m

$c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,P(c|d)$

Вычислить значение этой вероятности напрямую невозможно, поскольку для этого нужно, чтобы обучающее множество содержало все (или почти все) возможные комбинации классов и документов. Однако, используя формулу Байеса, можно переписать выражение для $P(c|d)$

$c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,{\frac {P(d|c)P(c)}{P(d)}}={\underset {c\in C}{\operatorname {argmax} }}\,P(d|c)P(c)$

где знаменатель $P(d)$ опущен, так как не зависит от c и, следовательно, не влияет на нахождение максимума; P(c) - вероятность того, что встретится класс c, независимо от рассматриваемого документа; P(d|c) - вероятность встретить документ d среди документов класса c.

Используя обучающее множество, вероятность P(c) можно оценить как

${\hat {P}}(c)={\frac {N_{c}}{N}}$

где $N_{c}$ - количество документов в классе c, N - общее количество документов в обучающем множестве. Здесь использован другой знак для вероятности, поскольку с помощью обучающего множества можно лишь оценить вероятность, но не найти её точное значение.

Чтобы оценить вероятность $P(d|c)=P(t_{1},t_{2},...,t_{n_{d}}|c)$, где $t_{k}$ - терм из документа d, $n_{d}$ - общее количество термов в документе (включая повторения), необходимо ввести упрощающие предположения (1) о условной независимости термов и (2) о независимости позиций термов. Другими словами, мы пренебрегаем, во-первых, тем фактом, что в тексте на естественном языке появление одного слова часто тесно связано с появлением других слов (например, вероятнее, что слово интеграл встретится в одном тексте со словом уравнение, чем со словом бактерия), и, во-вторых, что вероятность встретить одно и то же слово различна для разных позиций в тексте. Именно из-за этих грубых упрощений рассматриваемая модель естественного языка называется наивной (тем не менее она является достаточно эффективной в задаче классификации). Итак, в свете сделанных предположений, используя правило умножения вероятностей независимых событий, можно записать

$P(d|c)=P(t_{1},t_{2},...,t_{n_{d}}|c)=P(t_{1}|c)P(t_{2}|c)...P(t_{n_{d}}|c)=\prod _{k=1}^{n_{d}}P(t_{k}|c)$

Оценка вероятнотей $P(t|c)$ с помощью обучающего множества будет

${\hat {P}}(t|c)={\frac {T_{ct}}{T_{c}}}$

где $T_{ct}$ - количество вхождений терма t во всех документах класса c (и на любых позициях - здесь существенно используется второе упрощающее предположение, иначе пришлось бы вычислить эти вероятности для каждой позиции в документе, что невозможно сделать достаточно точно из-за разреженности обучающих данных - трудно ожидать, чтобы каждый терм встретился в каждой позиции достаточное количество раз); $T_{c}$ - общее количество термов в документах класса c. При подсчёте учитываются все повторные вхождения.

После того, как классификатор "обучен", то есть найдены величины ${\hat {P}}(c)$ и ${\hat {P}}(t|c)$, можно отыскать класс документа

$c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,{\hat {P}}(d|c){\hat {P}}(c)={\underset {c\in C}{\operatorname {argmax} }}{\hat {P}}(c)\prod _{k=1}^{n_{d}}{\hat {P}}(t_{k}|c)$

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

$c_{m}={\underset {c\in C}{\operatorname {argmax} }}[\log {\hat {P}}(c)+\sum _{k=1}^{n_{d}}\log {\hat {P}}(t_{k}|c)]$

Эта формула имеет простую интерпретацию. Шансы классифицировать документ часто встречающимся классом выше, и слагаемое $\log {\hat {P}}(c)$ вносит в общую сумму соответствующий вклад. Величины же $\log {\hat {P}}(t|c)$ тем больше, чем важнее терм t для идентификации класса c, и, соответственно, тем весомее их вклад в общую сумму.

Применение

• фильтрация спама
• составление интернет-каталогов
• подбор контекстной рекламы
• в системах документооборота
• автоматическое реферирование (составление аннотаций)
• снятие неоднозначности при автоматическом переводе текстов
• ограничение области поиска в поисковых системах
• определение кодировки и языка текста

Литература

• Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze An Introduction to Information Retrieval Draft. Online edition. Cambridge University Press. - 2009. - 544 p.

См. также

• Наивный байесовский классификатор
• Кластеризация
• Кластеризация документов
• Семантическое зеркало

Ссылки

• Лекция № 6 по классификации текстов курса «Современные задачи теоретической информатики» (постановка задачи, построение и обучение классификатора, оценка качества).
• F. Sebastiani. Machine Learning in Automated Text Categorization (PDF). (англ.)
• "Text mining. Классификация текста". Пример классификации документов с использованием программных алгоритмов STATISTICA

Technology

Tank uses a black and white Motorola television for its display. The control panel consists of four military-style joysticks, two per player, with a fire button mounted on top of the right joystick of each pair.

Inserting coins immediately starts the game, placing the players in the upper right and lower left corners of the maze respectively. The first 50 or so cabinets produced have a protruding wooden coin box area between the two speaker grills.

Tank was the first game to use IC-based ROM to store graphical data. Although Gran Trak 10, released in July 1974, was the first arcade game to use solid state ROM data, Gran-Trak's ROM used an earlier diode-based ROM technology.

The custom game cabinet was designed by Peter L. Takaichi and patented October 20, 1975 (US Patent # D243,624).

Gameplay

Players move their tanks through a maze on screen, avoiding mines and shooting each other. The players are represented by one black and one white tank sprite, and mines are denoted by an "X". Points are scored by shooting the opponent or when a player runs over a mine; the player with the highest score at the end of the time limit wins the game.

The tanks are controlled by two joysticks in a dual configuration. Pushing both joysticks will move the player's tank forward, and pulling them both back causes the tank to stop. Moving the right joystick forward while pulling the left joystick back will cause the tank to turn right, while reversing the motion will cause the tank to turn left.

Ports

• The Atari 2600 game Combat, released in 1977, included several variations of Tank.

Clones

• The Coleco Telstar Combat!, released in 1977, played four variations of Kee Games' Tank using a General Instruments AY-3-8700 Tank chip.

Legacy

• Tank II in 1974.
• The full color and Motorola 6800 microprocessor based Tank 8 in 1976.
• The 6502 microprocessor based Ultra Tank in 1978.
• Battlezone was released in 1980, using the same control mechanism. Designed by Ed Rotberg, the game play was moved to 3D first person format displayed by vector graphics. The player also now competed against computer controlled opponents.

External links

• Armchair Arcade commentary
• Entries at Killer List of Videogames: Tank, Tank II, Tank 8, Ultra Tank
• PCB and Artwork images from Andy's Arcade