Задача классификации предполагает что

Задача классификации (Classification problem)

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

Пусть X — множество описаний объектов, Y — конечное множество номеров (имен, меток) классов. Существует неизвестная целевая зависимость — отображение y ∗ : X → Y , значения которой известны только на объектах конечной обучающей выборки X m = ( x 1 , y 1 ) , … , ( x m , y m ) . Требуется построить алгоритм a : X → Y , способный классифицировать произвольный объект x ∈ X .

В математической статистике задачи классификации называются также задачами дискриминантного анализа.

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

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

К числу распространенных методов решения задачи классификации относятся:

нейронные сети;
логистическая и пробит-регрессия;
деревья решений;
метод ближайшего соседа;
машины опорных векторов;
дискриминантный анализ.

Задача классификации применяется во многих областях:

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

Классификация

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

Классифицировать объект — значит, указать номер (или наименование класса), к которому относится данный объект.

Классификация объекта — номер или наименование класса, выдаваемый алгоритмом классификации в результате его применения к данному конкретному объекту.

В математической статистике задачи классификации называются также задачами дискриминантного анализа.

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

Типология задач классификации

Типы входных данных

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

Классификацию сигналов и изображений называют также распознаванием образов.

Типы классов

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

Классификация: формальная постановка

Пусть — множество описаний объектов, — конечное множество номеров (имён, меток) классов. Существует неизвестная целевая зависимость — отображение , значения которой известны только на объектах конечной обучающей выборки . Требуется построить алгоритм , способный классифицировать произвольный объект .

Вероятностная постановка задачи

Более общей считается вероятностная постановка задачи. Предполагается, что множество пар «объект, класс» является вероятностным пространством с неизвестной вероятностной мерой . Имеется конечная обучающая выборка наблюдений , сгенерированная согласно вероятностной мере . Требуется построить алгоритм , способный классифицировать произвольный объект .

Признаковое пространство

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

В зависимости от множества признаки делятся на следующие типы:

бинарный признак: ;
номинальный признак: — конечное множество;
порядковый признак: — конечное упорядоченное множество;
количественный признак: — множество действительных чисел.

Часто встречаются прикладные задачи с разнотипными признаками, для их решения подходят далеко не все методы.

Примеры прикладных задач

Задачи медицинской диагностики

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

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

Ценность такого рода систем в том, что они способны мгновенно анализировать и обобщать огромное количество прецедентов — возможность, недоступная специалисту-врачу.

Предсказание месторождений полезных ископаемых

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

Оценивание кредитоспособности заёмщиков

Эта задача решается банками при выдаче кредитов. Потребность в автоматизации процедуры выдачи кредитов впервые возникла в период бума кредитных карт 60-70-х годов в США и других развитых странах. Объектами в данном случае являются физические или юридические лица, претендующие на получение кредита. В случае физических лиц признаковое описание состоит из анкеты, которую заполняет сам заёмщик, и, возможно, дополнительной информации, которую банк собирает о нём из собственных источников. Примеры бинарных признаков: пол, наличие телефона. Номинальные признаки — место проживания, профессия, работодатель. Порядковые признаки — образование, занимаемая должность. Количественные признаки — сумма кредита, возраст, стаж работы, доход семьи, размер задолженностей в других банках. Обучающая выборка составляется из заёмщиков с известной кредитной историей. В простейшем случае принятие решений сводится к классификации заёмщиков на два класса: «хороших» и «плохих». Кредиты выдаются только заёмщикам первого класса. В более сложном случае оценивается суммарное число баллов (score) заёмщика, набранных по совокупности информативных признаков. Чем выше оценка, тем более надёжным считается заёмщик. Отсюда и название — кредитный скоринг. На стадии обучения производится синтез и отбор информативных признаков и определяется, сколько баллов назначать за каждый признак, чтобы риск принимаемых решений был минимален. Следующая задача — решить, на каких условиях выдавать кредит: определить процентную ставку, срок погашения, и прочие параметры кредитного договора. Эта задача также может быть решения методами обучения по прецедентам.

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

Оптическое распознавание символов

Распознавание речи

Обнаружение спама

Классификация документов

Методы решения

Байесовский классификатор:
- квадратичный классификатор;
- линейный дискриминант Фишера;
- наивный байесовский классификатор;
- метод парзеновского окна;
- разделение смеси вероятностных распределений (EM-алгоритм);
- метод потенциальных функций или метод радиальных базисных функций;
- метод ближайших соседей.
- Нейронная сеть:
  - персептрон;
  - многослойный персептрон;
  - гибридная сеть встречного распространения;
  - Линейный разделитель:
    - линейный дискриминант Фишера;
    - наивный байесовский классификатор;
    - однослойный персептрон;
    - логистическая регрессия;
    - машина опорных векторов.
    - Индукция правил:
      - решающее дерево;
      - решающий список;
      - решающий лес;
      - тестовый алгоритм;
      - алгоритм вычисления оценок.
      - Алгоритмическая композиция:
        
        взвешенное голосование;
        
        бустинг;
        
        бэггинг;
        
        метод комитетов;
        
        смесь экспертов.
        
        Сокращение размерности:
        
        селекция признаков;
        
        метод главных компонент;
        
        метод независимых компонент;
        
        многомерное шкалирование.
        
        Выбор модели:
        
        минимизация эмпирического риска;
        
        структурная минимизация риска;
        
        минимум длины описания;
        
        скользящий контроль;
        
        извлечение признаков
        
        самоорганизация моделей;
        
        случайный поиск с адаптацией;
        
        генетический алгоритм.
        
        Курсы лекций
        
        Воронцов К.В.Математические методы обучения по прецедентам. МФТИ (2004), ВМиК МГУ (2007).
        
        Лифшиц Ю. Автоматическая классификация текстов (Слайды) — лекция №6 из курса «Алгоритмы для Интернета».
        
        Мерков А. Б. Основные методы, применяемые для распознавания рукописного текста (2005).
        
        Мерков А. Б. О статистическом обучении (2006).
        
        Местецкий Л. М. Математические методы распознавания образов. ВМиК МГУ, кафедра ММП (2002).
        
        Jaakkola T.Machine Learning. MIT (2004). — на английском языке.
        
        Литература
        
        Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
        
        Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
        
        Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.
        
        Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9.
        
        Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. ISBN 966-00-0341-2.
        
        Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.
        
        Mitchell T. Machine Learning. — McGraw-Hill Science/Engineering/Math, 1997. ISBN 0-07-042807-7.
        
        Задача классификации и рубрикации текстов Текст научной статьи по специальности «Компьютерные и информационные науки»
        
        Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Агеев В.Н.
        
        К вопросу о поиске документов «По аналогии»
        О задании меры сходства для кластеризации текстовых документов
        
        Автоматизированная система обработки динамических коллекций разноязычных текстовых документов по морскому и речному делу
        
        Разработка и апробация системы поиска дубликатов в текстах проектной документации
        Разработка учебно-методического взаимодействия учебно-методического комплекса с Internet
        i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
        i Надоели баннеры? Вы всегда можете отключить рекламу.
        
        Текст научной работы на тему «Задача классификации и рубрикации текстов»
        
        классификации и рубрикации текстов
        
        д.т.н., профессор кафедры АПП
        
        Классификация текстовых документов заключается в отнесении документа к одному из заранее известных классов. Часто классификацию применительно к текстовым документам называют категоризацией или рубрикацией. Очевидно, что данные названия происходят от задачи систематизации документов по каталогам, категориям и рубрикам. При этом структура каталогов может быть как одноуровневой, так и многоуровневой (иерархической).
        
        Формально задачу классификации текстовых документов описывают набором множеств. Множество документов представляется в виде:
        
        Категории документов представляются множеством:
        
        Иерархию категорий можно представить в виде множества пар, отражающих отношение вложенности между рубриками:
        
        (категория ср вложена в категорию с).
        
        В задаче классификации требуется на основе этих данных построить процедуру, которая заключается в нахождении наиболее вероятной категории из множества Сдля исследуемого документа dt.
        
        Большинство методов классификации текстов так или иначе основаны на предположении, что документы, относящиеся к одной категории, содержат одинаковые признаки (слова или словосочетания), и наличие или отсутствие таких признаков в документе говорит о его принадлежности или непринадлежности к той или иной теме.
        
        Таким образом, для каждой категории должно быть множество признаков:
        
        Такое множество признаков часто называют словарем, т. к. оно состоит из лексем, которые включают слова и/или словосочетания, характеризующие категорию.
        
        Подобно категориям каждый документ также имеет признаки, по которым его можно отнести с некоторой степенью вероятности к одной или нескольким категориям:
        
        Множество признаков всех документов должно совпадать с множеством признаков категорий:
        
        Необходимо заметить, что данные наборы признаков являются отличительной чертой классификации документов от классификации объектов в Data Mining, которые характеризуются набором атрибутов.
        
        Решение об отнесении документа dt к категории с принимается на основании пересечения:
        
        Задача методов классификации состоит в том, чтобы наилучшим образом выбрать такие признаки и сформулировать правила, на основе которых будет приниматься решение об отнесении документа к рубрике.
        
        Существует два противоположных подхода к формированию множества F.C) и построению правил:
        
        1) машинное обучение — предполагается наличие обучающей выборки документов, по которому строится множество FC);
        
        2) экспертный метод — предполагает, что выделение признаков (FC)) и составление правил производится экспертами.
        
        В случае машинного обучения анализируется статистика лингвистических шаблонов (таких как лексическая близость, повторяемость слов и т. п.) из документов обучающей выборки. В нее должны входить документы, относящиеся к каждой рубрике, чтобы создать набор признаков (статистическую сигнатуру) для каждой рубрики, который впоследствии будет использоваться для классификации новых документов. Достоинством данного подхода является отсутствие необходимости в словарях, которые сложно построить для больших предметных областей. Однако чтобы избежать неправильной классификации, требуется обеспечить хорошее представительство документов для каждой рубрики.
        
        Во втором случае формирование словаря (множества F(C) может быть выполнено на основе набора терминов предметной области и отношений между ними (основные термины, синонимы и родственные термины). Классификация может затем определить рубрику документа в соответствии с частотой, с которой появляются выделенные в тексте термины (ключевые понятия).
        
        Возможна и комбинация двух описанных подходов, когда выделение признаков и составление правил выполняются автоматически на основе обучающей выборки, и в то же время правила строятся в таком виде, чтобы эксперту была понятна логика автоматической рубрикации, и у него была возможность вручную корректировать эти правила.
        
        Для классификации текстовых документов успешно используются многие методы и алгоритмы классификации. Байесовский подход предполагает вычисление вероятностей принадлежности текстового документа к каждой рубрике. Решение о принадлежности принимается по максимальной вероятности:
        
        p(y= сr\E) = p[xi =cp\y = cr)xp(x2 =cd\y = cr)x. х
        
        Зависимая переменная / указывает на принадлежность документа к категории. Событие ^заключается в наличии в текстовом документе признаков, характеризующих категорию с. При этом независимой переменной xg является признак fg — наличие слова из словаря Fc) для категории c в текстовом документе d:
        
        [1, если fg eF(d¡), где f’g eF(cr);
        
        Xg ~ |o, если fg *F(d¡), где fg eF(cr).
        
        Аналогичную трактовку получают зависимая и независимая переменные и в других методах классификации при использовании их для текстовых документов.
        
        Для классификации текстовых документов были разработаны и другие методы и разрабатываются новые. Примером такого метода является классификация, основанная на полнотекстовом поиске. С помощью этого метода на основе обучающей выборки формируются запросы к полнотекстовой поисковой машине, соответствующие каждой из рубрик. Затем эти запросы выполняются для исследуемого документа, и выбирается та рубрика, запросы которой в наибольшей степени соответствуют исследуемому документу. Особенностью метода является то, что результат машинного обучения представляет собой набор запросов к поисковой системе и легко интерпретируется.
        
        Таким образом, возникает задача нахождения по данному множеству документов класса схожих по содержанию документов (поиск «по аналогии»). Процесс разбиения множества документов электронной базы па классы, при котором элементы, объединяемые в один класс, имеют большее сходство, нежели элементы, принадлежащие разным классам, называется кластеризацией.
        
        В качестве информационного запроса предполагается задание непустого множества документов, а в качестве результата выполнения запроса выдаются документы, каждый из которых в определенном смысле близок к одному из документов, входящих в заданное множество. В качестве информационного запроса предполагается задание непустого множества документов, а в качестве результата выполнения запроса выдаются документы, каждый из которых в определенном смысле близок к одному из документов, входящих в заданное множество. При этом надо иметь в виду, что при интеграции нескольких баз данных можно столкнуться с наличием в объединенном множестве дубликатов одного и того же документа, которые для удобства пользователя следует исключать из окончательных результатов поиска.
        
        Для оценки отношения сходства между парами документов рекомендуется использовать множества их ключевых слов (понимаемых в данном случае как входящие в текст документа термины, относящиеся по смыслу к данной предметной области). Однако на сходство документов научной тематики могут также влиять и другие факторы, например, наличие у документов общего автора (или, тем более, нескольких авторов).
        
        Однако ситуация, когда требуется поиск документов «по аналогии», возникает не только применительно к научным публикациям. Например, в настоящее время в Интернете существуют несколько десятков новостных информационных порталов, основной принцип работы которых заключается в аккумулировании новостной информации, публикуемой на сайтах информационных агентств, и объединении сообщений, освещающих ход развития того или иного события, в так называемые сюжеты (такое объединение обычно реализуется посредством публикации в конце сообщения гиперссылок на другие сообщения, относящиеся к этому же сюжету). Огромные объемы поступающей информации требуют автоматизации процесса выявления сообщений сходной тематики, причем, как и в задаче поиска научных публикаций, здесь также возникает проблема удаления избыточной информации. Однако в данном случае дело осложняется тем, что в отличие от предыдущей задачи, при формировании новостных сюжетов требуется удалять не только полные, но и нечеткие дубликаты, возникающие, например, вследствие того, что разные информационные агентства независимо друг от друга сообщили одну и ту же новость (естественно, несколько разными словами).
        
        Рассмотрим процедуру поиска объектов «по аналогии». Пусть мы уже выделили основные свойства, присущие данному типу объектов, и задали подходящие шкалы, описывающие множества возможных значений каждого из свойств (если рассматриваемые объекты -документы, то в качестве шкал для определения меры сходства используются атрибуты библиографического описания документов).
        
        Для номинальных шкал мера сходства определяется следующим образом: если значения свойств объектов совпадают, то мера близости по этой шкале равна 1, иначе 0. При этом необходимо учитывать, что значения свойств объектов для номинальной шкалы могут быть составными (например, документ может иметь сразу нескольких авторов). В таком случае ц. = п/п0У где п0 = тах<пя^), пя^2)>, n¡0(dJ)) -общее количество элементов, составляющих значение /-го атрибута документа d, п;1 — количество совпадающих элементов.
        
        После того, как подсчитана мера сходства по каждой из шкал, можно приступить к вычислению меры сходства ц(dv d2) между объектами, входящими в заданное множество, и объектами, среди которых мы ищем аналогичные заданным. Для этого обычно используется одна из стандартных формул вычисления расстояний с весовыми коэффициентами, которые обеспечивают, чтобы вычисленное значение меры не превосходило 1. Весовые коэффициенты (они, разумеется, неотрицательны) в простейшем случае равны между собой, однако путем задания весовых коэффициентов, отличных друг от друга, мы можем указать априорную относительную важность шкал. Более того, значения весовых коэффициентов могут определяться и предполагаемой апостериорной достоверностью данных соответствующей шкалы, то есть в определенных случаях один из коэффициентов может быть увеличен с пропорциональным уменьшением остальных. Например, полное (или даже «почти полное») совпадение значений атрибута «авторы» документа d и документа d2 более весомо в случае, когда количество значений этого атрибута в документе d достаточно велико (по сравнению со случаем, когда документ d имеет всего одного автора). Использование для вычисления меры сходства между объектами и d2 стандартной евклидовой метрики
        
        где = 1, оказывается не всегда удобным из-за заметного влияния
        
        отдельных больших значений ц.. Этот недостаток менее заметен при использовании расстояния Хемминга
        
        Напротив, если понимание сходства для конкретной задачи подразумевает отсутствие больших различий по любой отдельно взятой шкале, то целесообразно использовать расстояние Чебышева
        
        |ашЦ, d2) = max |a,|a,(d1, d2 )|, где max|a,| < 1.
        
        В этих формулах выражение |,(d|, d2) означает |,(y(d|), y(d2)), где у — функция меры сходства [4].
        
        Для непосредственной процедуры нахождения объектов, аналогичных объектам из заданного множества, необходимо задать пороговое значение меры сходства re (0, 1). Если заданное множество D*
        
        состоит из одного объекта d*, то при |/(d,,dy)
        
        объект d аналогичен заданному, в противном случае считается, что аналогия отсутствует. Ситуация осложняется, если множество D* содержит более одного объекта. Тогда критерием аналогичности объекта d элементам множества D* служит неравенство |/(D,,d/)
        
        l/(D*,dJ) — расстояние от объекта d до множества D* (обычно под этим подразумевается минимум расстояний от объекта d до элементов множества — D*, хотя иногда в качестве |/(D,,dj) целесообразно рассматривать расстояние от объекта d до определенного тем или иным способом «центра» множества D*). Независимо от количества элементов в множестве D*, возможно задание «градаций аналогичности», определяемых посредством набора чисел , /= 1, . n, где rk< r при k< l Если rk< (D*, d) < rk+ 1, а r,< (D*, d2) < r+ 1 при k< l, то считается, что объект d более схож с элементами множества D*, чем объект d2. Введение градаций аналогичности используется, например, для установления приоритета просмотра документов, найденных в процессе информационного поиска.
        
        Несколько иной подход к нахождению аналогичных объектов связан с кластеризацией объектов объединенного множества, включающего в себя как элементы множества D*, так и объекты, относительно которых необходимо установить наличие или отсутствие аналогии с элементами множества D* (напомним, что кластеризацией называется разбиение множества объектов на классы, при котором элементы, объединяемые в один класс, имеют большее (в определенном смысле) сходство, нежели элементы, принадлежащие разным классам). При этом объектами, аналогичными элементам множества D*, признаются объекты, принадлежащие классам, содержащим определенное количество элементов D* (это количество может быть задано как абсолютная величина или как доля элементов D* в данном классе).
        
        В методах, применяемых для решения задачи кластеризации текстовых документов, можно выделить два основных подхода: «синтаксический» и «лексический».
        
        Суть «синтаксического» подхода состоит в представлении документа в виде множества всевозможных последовательностей фиксированной длины к, состоящих из соседних слов (такие последовательности называются «шинглами»). Нетрудно видеть, что такие шинглы суть значения соответствующей номинальной шкалы. Два документа считаются похожими, если множества их шинглов существенно пересекаются.
        
        В рамках «лексического» подхода строится словарь (то есть список различных слов) L коллекции документов, из которого исключены слова, встречающиеся в коллекции слишком редко и слишком часто (как правило, содержание документа наиболее адекватно отражают слова со средним значением частоты встречаемости). Далее для каждого документа формируется множество входящих в него различных слов и и определяется пересечение Р этого списка с построенным словарем А На основании близости таких списков можно судить о сходстве документов.
        
        Основная проблема кластеризации документов заключается в таком разнесении документов по группам, при котором элементы каждой группы были бы настолько сходны друг с другом, чтобы в некоторых случаях можно было пренебречь их индивидуальными особенностями. В частности, производить поиск в систематизированном файле гораздо легче, чем в несистематизированном, ибо группы документов, профили которых не имеют сходства с поисковым предписанием, не включаются в углубленный процесс поиска. При кластеризации документов важно прийти к разумному компромиссу относительно размера кластеров, избегая как формирования большого числа очень мелких кластеров (что снижает эффективность кластеризации как выделения множеств сходных документов), так и небольшого количества очень крупных классов (что может вызвать уменьшение точности поиска).
        
        Принято различать две задачи кластеризации: формирование кластеров на основе сведений (свойств и характеристик) о классифицируемых объектах и отнесение объектов к сформированным кластерам (или кластерам, находящимся в процессе формирования). Собственно формирование классов выполняется обычно на основе сопоставления векторов документов, причем класс определяется как множество всех объектов, имеющих достаточно высокие значения коэффициента подобия. Составление характеристик класса эквивалентно построению профиля; отнесение объектов к классам зависит от степени подобия между идентификаторами объектов и профилями классов.
        
        В качестве потенциально пригодных для решения поставленной задачи были проанализированы два классических метода кла-
        
        стеризации документов: кластеризация путем нахождения клик в полной матрице подобия документов [1] и кластеризация по методу Роккио [2].
        
        Процесс нахождения клик основан на построении полной матрицы подобия, посредством которой каждой паре документов (dv d2) ставится в соответствие коэффициент подобия S(dv d2). Обычно выбирается пороговое значение Т, и матрица подобия приводится к бинарному виду путем замены единицей всех коэффициентов подобия таких, что S(dv d2) > Т, и нулем — всех остальных. Далее искомые классы определяются как клики, которые могут быть получены из бинарного ряда подобия.
        
        В алгоритме Роккио построение матрицы подобия заменяется проверкой плотности пространства некоторых документов. В качестве возможных центров кластеров выступают только те документы, которые по результатам вычислений оказались расположенными в плотных зонах пространства. Кластеризуемый документ относят к тому классу, подобие с центроидом которого оказалось наиболее высоким.
        
        Сравнение классических алгоритмов показало, что метод определения кластеров на множестве клик, полученных из матрицы подобия, показал себя малопригодным для решения поставленной задачи, так как имеет тенденцию к образованию большого количества очень мелких групп: по 1-2 документа. Это объясняется тем, что вероятность подобия друг другу всех элементов в более крупных группах объектов чрезвычайно низка.
        
        1. СолтонДж. Динамические библиотечно-информационные системы / Дж. Солтон. — М. : Мир, 1979.
        
        2. Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест ; пер. с англ. — М. : МЦНМО, 2001.
        
        Похожие публикации:
        
        Hseq как расшифровать
        
        Как делать электронные конспекты
        
        Как посчитать статистику
        
        На чем написан телеграм