Классификация и кластеризация

Закон Ципфа

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

^ снятие омонимии при обработке натуральных языков;

^ в поисковых системах — для ограничения области поиска в целях повышения точности (вертикальный поиск);

^ автоматическое определение языка, на котором написан текст;

^ анализ тональности (определение эмоциональной окраски текста).

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

Различия в подходах заключаются как в понимании того, что такое термин, так и в способах определения веса термина.

Одним из самых распространенных методов перехода к математической модели документа, является «метод ключевых слов». Ключевое слово — слово в тексте, способное в совокупности с другими ключевыми словами представлять текст. Суть метода в следующем. Для каждого класса текстов создается список характерных для него слов, тогда каждый текст можно представить в виде вектора частот появлении в нём слов из данного списка. Возникает проблема поиска и выделения из текста слов, которые будут для него ключевыми. Огромный объем информации, который подлежит обработке, делают особенно актуальной задачу автоматического выделения ключевых слов. Причем от чистоты этого выделения напрямую зависит точность классификации.

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

В 1949 году Джордж Ципф^[1] сформулировал несколько закономерностей. Данные законы получены не на основе математических выводов, а на основе анализа статистики частоты слов текстах на многих языках, то есть эмпирически.

Если все слова достаточно длинного текста упорядочить по убыванию частоты их использования, то частота п-го слова в таком списке окажется приблизительно обратно пропорциональна его порядковому номеру п (так называемому рангу этого слова). Например, второе по используемости слово встречается примерно в два раза реже, чем первое, третье — в три раза реже, чем первое, и т. д. (рис. 4.1).

Рис. 4.1. Закон Ципфа для русской Википедии

Это утверждение верно в пределах одного языка. Однако и межъязыковые различия невелики. На каком бы языке текст ни был написан, вид кривой Ципфа останется неизменной. Может немного отличаться лишь коэффициент гиперболы (рис. 4.2).

Рис. 4.2. Закон Ципфа для разных языков

Законы Ципфа позволяют находить ключевые слова.

Исследования показывают, что наиболее значимые для текста слова лежат в средней части графика (рис. 4.3). Этот факт имеет простое обоснование. Слова, которые попадаются слишком часто, в основном оказываются предлогами, местоимениями. Редко встречающиеся слова тоже, в большинстве случаев, не имеют решающего смыслового значения.

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

Рис. 4.3. Выбор ключевых слов

Одним из способов, например, является предварительное исключение из исследуемого текста слов, которые изначально не могут являться значимыми и, поэтому, являющиеся «шумом». Такие слова называются нейтральными или стоповыми (стоп-словами). Для русского текста стоповыми словами могли бы являться все предлоги, частицы, личные местоимения.

• [1] Оео^е Клгщяку гарвардский нрофессор-лингвист и филолог 46