Разработка метода повышения быстродействия непараметрических классификаторов библиографических текстовых документов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Бородкин, Артем Александрович
- Специальность ВАК РФ05.13.01
- Количество страниц 162
Оглавление диссертации кандидат технических наук Бородкин, Артем Александрович
Введение
ГЛАВА 1. ПРОЦЕСС И МЕТОДЫ ОБРАБОТКИ ДОКУМЕНТАЛЬНОЙ ИНФОРМАЦИИ
1.1. Основные термины и определения
1.2. Этапы процесса обработки и анализа текстовой информации
1.3. Сбор данных и формирование выборок
1.4. Начальная и содержательная обработка текстовых документов
1.5. Разведочный анализ текстовых данных
1.6. Способы оценки точности классификации
1.7. Непараметрические методы классификации
1.7.1. Метод ближайшего соседа
1.7.2. Метод ^-ближайших соседей
1.7.3. Взвешенный метод Ышижайших соседей
1.7.4. Метод потенциальных функций
1.8. Способы устранения общих недостатков непараметрических методов
1.9. Целевой показатель редукции
Выводы
ГЛАВА 2. РАЗРАБОТКА МЕТОДА РЕДУКЦИИ ОБУЧАЮЩЕЙ ВЫБОРКИ
2.1. Редуцированные методы
2.1.1. Метод нахождения прототипов
2.1.2. Инкрементные и декрементные методы редукции
2.2. Сопоставление методов редукции
2.3. Критерии определения "внутренних" документов
2.4. Алгоритм выбора радиуса гиперсферы
2.5. Модифицированный метод прототипов для объединения "внутренних" документов
2.6. Метод редукции обучающих выборок
2.7. Оценка вычислительной сложности и быстродействия непараметрических методов, использующих редуцированные выборки
2.8. Формирование выборок для исследований и экспериментальная настройка параметров процедуры редукции исходя из требований заданного ЦП
2 8.1. Формирование обучающих, тестовых и экзаменационных выборок
2.8.2. Настройка параметров метода редукции
Выводы
ГЛАВА 3. РАЗРАБОТКА И ПРИМЕНЕНИЕ МЕТОДИКИ ВЫБОРА ПРОЦЕДУР (И ПАРАМЕТРОВ) ОБРАБОТКИ И АНАЛИЗА ТЕКСТОВЫХ
ДАННЫХ НА ОСНОВЕ НЕПАРАМЕТРИЧЕСКИХ КРИТЕРИЕВ
3.1. Применение непараметрических критериев в задачах обработки и анализа текстовых документов
3.2. Основные непараметрические критерии для анализа связанных
выборок
3.2.1. Критерий Фридмана
3.2.2. Критерий Вилкоксона
3.3. Методика выбора процедур (и параметров) обработки и анализа текстовых данных на основе непараметрических критериев
3.4. Проведение исследований процедур обработки и анализа текстовых данных и применение разработанной методики на основе непараметрических критериев
3.4.1. Результаты исследований на англоязычных библиографических выборках
3.4.2. Результаты исследований на русскоязычных библиографических выборках
Выводы
ГЛАВА 4. РАЗРАБОТКА ПРОГРАММНЫХ СРЕДСТВ ДЛЯ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ И АНАЛИЗА
БИБЛИОГРАФИЧЕСКИХ ТЕКСТОВЫХ ДОКУМЕНТОВ
4.1 Сравнительный анализ известных разработок Text Mining
4.2 Структура и функциональные возможности учебно-исследовательского программного комплекса (УИПК)
4.3. Разработка комплекса лабораторных работ по курсу «Интеллектуальные информационные системы» с использованием УИПК
4.4. Применение УИПК для решения прикладных задач
Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
Приложение 1 Лабораторные работы
Приложение 2 Настройка параметров для выборок из русскоязычной
цифровой библиотеки eLibrary
Приложение 3 Акты о внедрении
Рекомендованный список диссертаций по специальности «Системный анализ, управление и обработка информации (по отраслям)», 05.13.01 шифр ВАК
Систематизация, разработка методов и коллективов решающих правил классификации библиографических текстовых документов2009 год, доктор технических наук Толчеев, Владимир Олегович
Разработка и исследование метода классификации библиографической текстовой информации2005 год, кандидат технических наук Некрасов, Иван Валериевич
Метод классификации библиографической информации на основе комбинированных профилей классов с учетом структуры документов2017 год, кандидат наук Мохов, Андрей Сергеевич
Разработка и исследование методов построения атрибутного тематического классификатора документов2009 год, кандидат технических наук Ха Ти Чунг
Многоуровневые непараметрические системы распознавания образов на основе декомпозиции обучающей выборки по ее размерности2009 год, кандидат технических наук Капустин, Антон Николаевич
Введение диссертации (часть автореферата) на тему «Разработка метода повышения быстродействия непараметрических классификаторов библиографических текстовых документов»
Введение
В последние два десятилетия существенно увеличились объемы накопленных текстовых документов и возросли потребности практики в эффективных программно-алгоритмических и методических средствах их анализа (процедуры Text Mining). Автоматизированное разнесение текстовой информации по заданным классам (задача классификации) является одним из наиболее востребованных на практике направлений Text Mining и позволяет упорядочивать большие документальные массивы, снижая информационную нагрузку на пользователя [1,2,3].
Наиболее быстро возрастают объемы научно-технической информации, которые практически удваиваются в течение 2-3 лет [1]. При обработке и анализе научно-технических документов чаще всего решается задача классификации. Она, в частности, возникает при отслеживании публикаций в научных журналах, выпускаемых ведущими мировыми издательствами. Выявление из больших документальных массивов значимых статей, которые представляют практический интерес для пользователей (инженеров, преподавателей, научных сотрудников), является актуальной задачей. Такие статьи содержат важные сведения для повышения эффективности НИОКР, разработки новых учебных курсов, подготовки диссертаций и монографий и т.п. Автоматизированное упорядочивание массивов научной информации по классам позволяет существенно сократить затраты на рутинные процедуры обработки данных и, в конечном итоге, способствует увеличению результативности проводимых исследований.
Чаще всего в крупных хранилищах текстовых данных в свободном (бесплатном) доступе имеются документы, представленные в виде библиографических описаний. Библиографические описания состоят из названия, аннотации, ключевых слов, фамилий авторов и другой вспомогательной информации. Доступ к полнотекстовым версиям обычно реализуется на коммерческой основе. В связи с этим целесообразно проводить автоматизированный мониторинг и классификацию научных
статей, ежемесячно публикуемых в ведущих профессиональных изданиях, по их библиографическим описаниям. После изучения и оценки результатов классификации имеет смысл приобрести у издателя только те полнотекстовые версии, которые необходимы для успешного проведения собственных исследований. В данной диссертации рассматриваются вопросы обработки и анализа библиографической текстовой информации.
Для автоматизированной классификации текстовой информации необходимо выбрать метод классификации (классификатор) и настроить его параметры. Классификатор, как правило, настраивается с помощью достаточно большого массива текстовой информации, в котором экспертами каждому документу присвоена метка класса (такой массив называется обучающей выборкой).
Анализ российских и зарубежных публикаций в области Data and Text Mining показывает, что основные усилия разработчиков сконцентрированы на построении классификаторов, обладающих высокой точностью [1,3,4,5]. Под оценкой точности в данной работе понимается отношение правильно классифицированных документов к общему числу классифицируемых документов. Для увеличения точности используются различные подходы: синтез коллективов решающих правил, организация ресурсозатратного обучения для высокоточной настройки параметров методов, увеличение размера и количества обучающих выборок, тщательное выявление информативных признаков (терминов) [6,7,8,9,10].
В современных условиях стремительного увеличения массивов накопленной информации ужесточаются требования к методам классификации по быстродействию. Эти требования особо важно учитывать при обработке и анализе текстовых данных, имеющих высокую размерность (большое число терминов, описывающих документ). Под быстродействием классификатора в данной работе понимается время, затрачиваемое на отнесение документа к одному из классов. Быстродействие измеряется или
как количество вычислительных операций или как процессорное время, необходимое для классификации.
На современном этапе высокое быстродействие является обязательным условием применения классификаторов для решения таких задач как обработка коротких новостных сообщений в информационных агентствах, анализ вопросов, поступающих в ходе on-line конференций, автоматизированное разнесение документов по классам в больших цифровых библиотеках, реализация эффективного документооборота в крупных компаниях. Кроме того, при разработке программно-алгоритмических средств Text Mining для решения широкого круга прикладных проблем требуется учитывать режим «перегрузки» системы обработки текстовых данных, когда интенсивность обрабатываемого документального потока достигает пиковых значений.
Следует отметить, что разработка как высокоточных, так и быстродействующих процедур классификации приводит к существенному росту затрат (вычислительных операций) на этапе обучения [10]. Именно на основе многоаспектной обработки большого числа обучающих выборок удается извлечь эвристики, позволяющие увеличить точность (или быстродействие). Высокие затраты при обучении в дальнейшем оправдываются за счет многократного использования настроенного классификатора. В частности, продолжительность автоматизированного отслеживания и классификации научных статей по заданным специалистом тематикам обычно составляет 2-3 года, в течение которых осуществляется соответствующая НИОКР, подготавливается диссертация, монография и т.п.
К сожалению, увеличение точности классификации обычно приводит к снижению быстродействия из-за усложнения решающего правила, используемого в методе классификации, а увеличение быстродействия сопровождается падением точности из-за упрощения работы классификатора. В настоящее время существует лишь небольшое число методов классификации, для которых могут быть разработаны специальные
процедуры, позволяющие повысить быстродействие практически без потерь в точности. Прежде всего, к таким классификаторам относятся непараметрические методы (метод ближайшего соседа и его модификации, метод потенциальных функций) [13,14,15,16].
Непараметрические методы (НМ) обеспечивают достаточно высокую точность, однако затрачивают значительное время на классификацию новых наблюдений. В специализированной литературе предлагаются различные модификации НМ с целью увеличения быстродействия. Эти модификации можно разделить на две большие группы: методы ускоренного поиска ближайшего соседа, в которых на этапе обучения проводится упорядочивание обучающей выборки для более быстрого нахождения ближайшего соседа (ближайших соседей) и методы редукции (сокращения) размеров обучающих выборок [10,17,18,19,20,21].
Как представляется, вопросам разработки методов редукции в литературе по Data and Text Mining уделяется значительно меньше внимания, чем методам ускоренного поиска ближайшего соседа. При этом в специализированных публикациях обычно рассматриваются методы редукции выборок, содержащих фактографическую информацию. В результате их применения удается добиться сокращения размера фактографических выборок более чем на 30 процентов.
В настоящее время практически отсутствуют работы, в которых проводится разработка и исследование аналогичных процедур для анализа документальной информации. Вместе с тем при классификации больших массивов неструктурированных текстовых данных, обладающих высокой размерностью, особо важно использовать процедуры, «ускоряющие» непараметрические классификаторы и практически не изменяющие их точности.
Несмотря на несомненный прогресс вычислительной техники и повышение производительности компьютеров, решить проблему быстродействия исключительно на «техническом» уровне не представляется
возможным из-за чрезвычайно высоких темпов роста объема обрабатываемой информации. Многие организации ориентируется на проведение гибридной обработки данных. В режиме пакетной обработки offline автономно от пользователя проводится формирование выборок (по заданным тематикам) и предварительная обработка документальной информации, которая включает ресурсоемкие процедуры с большим числом вычислительных операций. Затем с участием пользователя в режиме реального времени on-line проводится анализ данных: обучение, переобучение и дообучение классификаторов, анализ влияния различных факторов на точность классификации, сопоставление различных решающих правил и выбор наилучшего метода для решения конкретной задачи. Причем зачастую многие исследования повторяются неоднократно и направлены на проверку различных гипотез исследователя и, в конечном итоге, удовлетворения его информационных потребностей. Именно на этапе анализа происходят основные временные затраты пользователя и использование режима on-line позволяет существенно повысить эффективность его научно-исследовательской деятельности. Таким образом, разработка процедуры редукции обучающих выборок, ускоряющей непараметрические методы на «алгоритмическом» уровне вне зависимости от используемой техники, должна обеспечить экономию времени пользователя на стадии анализа документальной информации и оценки получаемых результатов.
Принимая во внимание вышесказанное, сформулируем цель диссертационного исследования.
Цель работы: увеличение быстродействия непараметрических классификаторов библиографической текстовой информации без существенного снижения их точности на основе разработки метода редукции обучающей выборки.
Для достижения указанной цели необходимо:
1. Сформулировать целевой показатель редукции, учитывающий требования по точности и быстродействию.
2. Провести комплексный сравнительный анализ известных методов редукции.
3. С позиций сформулированного целевого показателя разработать метод редукции обучающих выборок, позволяющий увеличить быстродействие непараметрических методов классификации без существенных потерь в точности.
4. Исследовать предложенный метод редукции на различных выборках, состоящих из библиографических текстовых документов.
5. Разработать и применить комплексную методику выбора процедур (и параметров) обработки и анализа текстовых данных на основе статистических непараметрических критериев.
6. На основе предложенных и известных методов разработать программный комплекс для обработки и анализа массивов библиографических документов.
Методы исследования. Полученные в диссертации результаты основываются на применении методов теории вероятностей, математической статистики, линейной алгебры, теории множеств, вычислительной геометрии, теории алгоритмов.
Научная новизна.
1. Обоснован и исследован критерий выявления "внутренних" документов, основанный на новой формуле линейного взвешивания ^-ближайших соседей.
2. Разработан новый метод редукции, основывающийся на критерии выявления "внутренних" документов, алгоритме выбора радиуса окрестности для каждого класса, модифицированном методе прототипов для объединения "внутренних" документов. Даны рекомендации по выбору настраиваемых параметров разработанного метода, приведены оценки вычислительной сложности.
3. В результате исследований на различных выборках было установлено, что разработанный метод редукции удовлетворяет сформулированному целевому критерию и в среднем на 19 процентов увеличивает быстродействие и практически не изменяет ошибку классификации метода А:-ближайших соседей.
4. С помощью разработанной методики, использующей статистические непараметрические критерии, обоснован выбор использованных в работе процедур предварительной обработки текстовых документов, определены значения настраиваемых параметров методов классификации и редукции.
Практическая ценность результатов.
Разработан учебно-исследовательский программный комплекс (УИПК), позволяющий проводить эффективную предварительную обработку и классификацию библиографической текстовой информации. В УИПК наряду с алгоритмами известных методов редукции включены алгоритмы, предложенные и исследованные лично автором. Показано, что применение на практике нового метода редукции позволяет увеличить быстродействие непараметрических методов без существенного увеличения ошибки классификации.
Разработанное программное обеспечение легко адаптируется к различным предметным областям и требованиям пользователя, при необходимости оно может дополняться новыми модулями. УИПК предназначен для широкого круга исследователей, не имеющих специальных знаний в области программирования и теории классификации.
В работе показано, что функциональные возможности комплекса позволяют решать не только учебные, но и прикладные научно-исследовательские задачи, проводить разработку и апробацию новых методов классификации, редукции, предварительной обработки данных.
Реализация результатов.
Программные модули УИПК были использованы при реализации проекта по созданию информационно-аналитической системы Института проблем химической физики РАН (ИПХФ РАН). Эффективность практического применения разработанного программно-алгоритмического обеспечения подтверждается актом об использовании результатов диссертационной работы в ИПХФ РАН.
УИПК внедрен в учебный процесс кафедры управления и информатики МЭИ, на его базе проводится 3 лабораторные работы по курсу «Интеллектуальные информационные системы». УИПК зарегистрирован в МЭИ в качестве программного средства учебного назначения. Применение разработанного программного комплекса в учебном процессе подтверждено актом о внедрении.
Апробация работы. Материалы диссертации докладывались на четырех международных конференциях "Информационные средства и технологии" (2007, 2008, 2009, 2010 гг. Москва, МЭИ), на одной Научной сессии МИФИ (2008 г. Москва, МИФИ), на двух научно-технических семинарах "Современные технологии в задачах управления, автоматики и обработки информации" (2007, 2011 гг. Алушта, МАИ).
Публикации
По теме диссертации опубликовано 10 работ, в том числе 2 статьи в журналах из Перечня ВАК.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, содержащего 129 наименований, 3-х приложений. Основной текст диссертации излагается на 150 машинописных страницах и содержит 34 рисунка и 17 таблиц.
Похожие диссертационные работы по специальности «Системный анализ, управление и обработка информации (по отраслям)», 05.13.01 шифр ВАК
Структурно-параметрический синтез нейросетевых систем обработки информации2003 год, доктор технических наук Милов, Владимир Ростиславович
Модели и методы автоматической классификации текстовых документов2003 год, кандидат технических наук Шабанов, Владислав Игоревич
Исследование приемного тракта системы связи командного типа2004 год, кандидат технических наук Клименко, Владимир Викторович
Многоуровневая непараметрическая система обработки информации1999 год, доктор технических наук Ченцов, Сергей Васильевич
Исследование и разработка методов формирования решающих правил при классификации фрагментов на полутоновых изображениях2011 год, кандидат технических наук Поцыкайло, Александр Анатольевич
Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Бородкин, Артем Александрович
Выводы
1. Проведен комплексный сравнительный анализ существующих программных средств обработки и анализа текстовых документов, обоснована необходимость проведения собственной разработки.
2. Разработан, апробирован и внедрен в учебный процесс учебно-исследовательский программный комплекс. Наряду с известными алгоритмами обработки и анализа в УИПК включены процедуры, разработанные автором. Созданный программный комплекс может быть адаптирован к различным предметным областям и требованиям пользователей, при необходимости он может дополняться новыми модулями.
3. Показаны возможности УИПК для решения исследовательских задач, включая обучение индивидуальных классификаторов, формирование коллективов решающих правил, проведение редукции массивов библиографической текстовой информации.
ЗАКЛЮЧЕНИЕ
Основным итогом диссертационной работы является разработка и исследование метода редукции, удовлетворяющего введенному целевому показателю и увеличивающего быстродействие непараметрических методов без существенного увеличения ошибки классификации.
Полученные теоретико-прикладные результаты прошли всестороннюю проверку в составе разработанного учебно-исследовательского программного комплекса для обработки и анализа библиографической текстовой информации. Итоги исследований подробно изложены в выводах по каждой главе диссертации, поэтому ниже формулируются лишь наиболее важные результаты работы.
1. Для решения поставленных в диссертации задач предложен целевой показатель, который предусматривает сокращение размера обучающей выборки более чем на 10 процентов при условии допустимого увеличения ошибки классификации менее чем на 3 процента.
2. Детализирован процесс обработки и анализа текстовой информации с учетом решаемых в диссертации задач. Обоснована целесообразность включения дополнительных «подэтапов», необходимых для проведения редукции текстовых выборок.
3. Рассмотрены известные непараметрические методы (НМ) классификации, проанализированы их преимущества и недостатки. Показаны способы устранения недостатков НМ. Проведен обзор и сравнительный анализ известных редуцированных методов и выявлены процедуры, наиболее эффективные с точки зрения сформулированного целевого показателя.
4. Разработано две новые формулы линейного взвешивания ^-ближайших соседей, применение которых не требует экспериментальной настройки дополнительных параметров и позволяет при расчете весов наиболее полно учитывать структуру выборки.
5. На основе разработанной автором формулы линейного взвешивания предложен новый критерий выявления "внутренних" документов. С точки зрения целевого показателя обосновано применение этого критерия для проведения редукции обучающих выборок.
6. Разработан новый метод редукции, основывающийся на критерии выявления "внутренних" документов, алгоритме выбора радиуса окрестности для каждого класса и модифицированном методе прототипов для объединения "внутренних" документов. Даны рекомендации по выбору настраиваемых параметров разработанного метода, приведены оценки вычислительной сложности.
7. Показано, что разработанный метод редукции удовлетворяет сформулированному целевому показателю и при практически неизменной ошибке классификации в среднем на 19 процентов сокращает размер англоязычных и русскоязычных обучающих выборок (соответственно также в среднем на 19 процентов увеличивает быстродействие метода ^-ближайших соседей). Разработанный метод обладает устойчивостью по отношению к небольшим изменениям структуры выборок (размера выборки и количества документов в классах).
8. Разработана и обоснована методика использования статистических непараметрических критериев для выбора наиболее подходящих процедур обработки и анализа текстовых данных. Предложенная методика применена на практике для выбора алгоритмов предварительной обработки текстовых данных, параметров методов редукции и классификации.
9. Разработан, апробирован и внедрен в учебный процесс учебно-исследовательский программный комплекс. Наряду с известными алгоритмами обработки и анализа в УИПК включены процедуры, разработанные автором. Данный программный комплекс может быть адаптирован к различным предметным областям и требованиям пользователей, при необходимости он может дополняться новыми модулями.
10. Продемонстрированы возможности УИПК по проведению комплексных исследований методов обработки текстовой информации и решению важных прикладных задач за счет применения эффективных процедур обучения индивидуальных классификаторов, редукции текстовых массивов, формирования коллективов решающих правил.
Список литературы диссертационного исследования кандидат технических наук Бородкин, Артем Александрович, 2012 год
ЛИТЕРАТУРА
1. Барсегян А.А., Куприянов М.С., Холод И.И., Тесс М.Д., Елизаров С.И. Анализ данных и процессов. С-Пб.: БХВ-Петербург, 2009. - 512 с.
2. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. М.: Нолидж. 2000. - 352 с.
3. Sebastiani F. Machine Learning in Automated Text Categorization. ACM Computing Survey. 34 (1), 2002. pp. 1-47.
4. Demsar J. Statistical Comparisons of Classifiers over Multiple Data Sets. Journal of Machine Learning Research, 7, 2006, pp. 1-30.
5. Schutze H., Hull D.A., Pedersen J.O. A comparison of Classifiers and Document Representation for the Routing Problem. Proceedings of the 19th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 1996, pp. 229-237.
6. Растригин JI.A., Эренштейн P.X. Метод коллективного распознавания. М. Энергоиздат, 1981. - 79 с.
7. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Института математики. 1999. - 270 с.
8. Scott S., Matwin S. Feature Engineering for Text Classification. In Proceedings 16th International Conference on Machine Learning, 1999, pp.379-388.
9. Yang Y., Pedersen J.O. A Comparative Study on Feature Selection in Text Categorization. Proceedings of the 14th International Conference on Machine Learning ICML-97, 1997, pp.412-420.
Ю.Толчеев B.O. Систематизация, разработка методов и коллективов решающих правил классификации библиографических текстовых документов. Диссертация на соискание ученой степени доктора технических наук. Специальность 05.13.01, МЭИ, 2009, 335 с. 1 l.Masand В., Linoff G., Waltz D. Classifying news stories using memory based reasoning. Proceedings of the 15th Annual International ACM SIGIR
Conference on Research and Development in Information Retrieval. 1992, pp.59-65.
12.Солтон Дж. Динамические библиотечно-информационные системы. М.: Мир. 1979.-557 с.
13.Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир. 1976. -511 с.
14.Патрик Э. Основы теории распознавания образов. М.: Советское радио, 1980.-408 с.
15.Фукунаги К. Введение в статическую теорию распознавания образов. М.: Наука. 1979. - 367 с.
16.Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970.- 384с.
17.Farago A., binder Т., Lugosi G. Fast Nearest Neighbor Search in Dissimilarity Spaces. IEEE Transactions on Pattern Analysis and Machine Intelligence. 15, 1993, pp. 957-962.
i&Fridman J.H., Baskett F., Shustek L.J. An Algorithm for Finding Nearest Neighbor. IEEE Transactions on Computers. Vol. C-24, 1975, pp. 1000-1006.
iP.Aggarwal C. On the Use of Human-Computer Interaction for Projected Nearest Neighbor Search. Data Mining and Knowledge Discovery. V.13, July, 2006, pp.89-117.
20. Wilson D.R., Martinez T.R. Reduction Techniques for Instance-based Learning Algorithms. Machine Learning, 38, 2000, pp. 257-286.
21.Толчеев B.O. Разработка и исследование новых модификаций метода ближайшего соседа. Приложение к журналу «Информационные технологии», №3, 2005, с. 1-32.
22.Chang C-L. Finding Prototypes for Nearest Neighbor Classifiers. IEEE Transactions on Computers. Vol. C-23, November 1974, pp. 1179-1184.
23.Толчеев B.O. Современные методы обработки и анализа текстовой информации. Учебное пособие. Изд-во МЭИ, 2006. - 76с.
24.Тьюки Дж. Анализ результатов наблюдений. Разведочный анализ. М.: Мир, 1981 -688 с.
25.Орлов А.И. Прикладная статистика. М.¡Экзамен, 2006. - 671 с.
26.Кокс Д., Снелл Э. Прикладная статистика. Принципы и примеры. М.: Мир, 1984-200с.
27.Эфрон Б. Нетрадиционные методы многомерного статистического анализа. М.: Финансы и статистика. 1988. - 367 с.
28.Вапник В.Н., Червоненкис А .Я. Теория распознавания образов. М.: Наука. 1974.-415с.
29.Сэлтон Г. Автоматическая обработка, хранение и поиск информации. М: Советское радио, 1973. - 560 с.
30.Salton G., Buckley С., Allan J. Automatic structuring of text files. Electronic Publishing, Volume 5, Number 1, 1992, pp. 1-17.
31.Hull D. Stemming Algoritms: A Case Study for Detailed Evaluation. Journal of the American Society for Information Science, 47, 1996, pp. 70-84.
32.Hampel F.R. Robust Estimation: A Considered Partial Survey. Z. Wahrsch. Verw. Geb., 27, pp.87-104.
33. Clark D. Using Consensus Ensembles to Identify Suspect Data. KES, 2004, pp. 483-490.
34. Ершов A.A. Стабильные методы оценки параметров. Автоматика и телемеханика, №8,1978, с.66-100.
35.Кпогг Е., Ng R. Algorithms for Mining Distance-based Outliers in Large Data Sets. Proc. 24th Int. Conf. on Very Large Databases, 1998, pp.392-403.
36.Breuning M., Kriegel H., Ng R., Sander J. LOF: Identifying Density Based Local Outliers. Proc. SIGMOD, 2000, pp.93-104.
37 .Прикладная статистика. Классификация и снижение размерности. Под ред. С.А. Айвазяна. М.: Финансы и статистика. 1989. - 607 с.
38.Limas М., Mere J., Ascacibar F., Gonzalez E. Outlier Detection and Data Cleaning in Multivariate Non-Normal Samples: The PAELLA Algorithm. Data Mining and Knowledge Discovery. V.9, №2 2004, pp. 171-187.
39.0tey M., Ghoting A., Parthasarathy S. Fast Distributed Outlier Detection in Mixed-Attribute Data Sets. Data Mining and Knowledge Discovery. V.12, №23 2006, pp. 203-228.
40.Hodge V., Austin J. A Survey of Outlier Detection Methodologies. Artificial Intelligence Review.22, 2004, pp.85-126.
41 .Jiang M., Tseng S., Su C. Two Phase Clustering Process for Outliers Detection. Pattern Recognition Letters, 22, 2001, pp. 691-700.
42.Cover T.M., Hart P.E. Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory. Vol. IT-13, January 1967, pp. 21-27.
43.Воронцов K.B. Лекции no статистическим (байесовским) алгоритмам классификации (http://www.ccas.ru/voron/download/Bayes.pdf).
АА.Нейронные сети. STATISTIC A Neural Networks. М.: Телеком. 2001.-182 с.
45.Некрасов И.В., Толчеев В.О. Модифицированный метод ближайшего соседа с использованием опорных точек для классификации текстовых документов. Вестник МЭИ, №1, 2004, стр. 76-81.
46.Dudani S.A. The Distance-Weighted k-Nearest-Neighbor Rule. IEEE Transactions on Systems, Man and Cybernetics. Vol. SMC-6, April 1976, pp. 325-327.
47.Толчеев B.O. Взвешенные и редуцированные методы ближайшего соседа. Вестник МЭИ, №5, 2005, с. 84-90.
48.Болотов А.А., Фролов А.Б. Классификация и распознавание в дискретных системах. Изд-во МЭИ, 1997. - 99 с.
49.Дорофеюк А.А. Алгоритмы автоматической классификации. Автоматика и телемеханика. № 12 1971, с. 78-113.
50.Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.
51.Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989.-476 с.
52.Zhang J. Selecting Typical Instances in Instance-Based Learning. Proceedings of 9th International Conference on Machine Learning, 1992, pp. 470-479.
53.Бородкин А.А., Толчеев В.О. Об оценке точностных и временных характеристик методов классификации библиографических текстовых документов. Научная сессия МИФИ 2008. Том 11. М. МИФИ, 2008, стр. 152-153.
54.Бородкин А.А., Толчеев В.О. Исследование влияния структуры выборки и процедур предварительной обработки на точность классификации текстовой информации. Международная конференция "Информационные средства и технологии". Том 2. МЭИ. Изд-во Станкин, 2007, с. 33-34.
55.Hart Р.Е. The Condensed Nearest Neighbor Rule. IEEE Transactions on Information Theory, 14, 1968, pp. 515-516.
56. Wilson D.L. Asymptotic Properties of Nearest Neighbor Rules Using Edited Data. IEEE Transactions on Systems, Man, and Cybernetics, 2, 1972, pp. 408421.
57.Tomek I. An Experiment with the Edited Nearest Neighbor Rule. IEEE Transactions on Systems, Man and Cybernetics. Vol. 6 № 6, June 1976, pp. 448-452.
58.Ritter G.L., Woodruff H.B., Lowry S.R., Isenhour T.L. An Algorithm for a Selective Nearest Neighbor Decision Rule. IEEE Transactions on Information Theory. Vol. IT-21, № 6, November 1975, pp. 665-669.
59.Wilson D.R., Martinez T.R. Heterogeneous Radial Basis Functions. Proceedings of the International Conference on Neural Networks, 1996, pp. 1263-1267.
60.Aha D. Tolerating Noisy, Irrelevant and Novel Attributes in Instance-Based Learning Algorithms. International Journal of Man-Machine Studies, 36, 1992, pp. 267-287.
61.Aha D., Kibler D., Albert M. Instance-based Learning Algorithms. Machine Learning, 6,1991, pp. 37-66.
62.Lin H., Motoda H. On Issues of Instance Selection. Data Mining and Knowledge Discovery, 6,2002, p. 115-130.
63.Bezdek J.C., Reichherzer T.R., Lim G.S., Attikiouzel Y. Multipleprototype Classifier Design. IEEEE Transaction on Systems, Man and Cybernetics. Part C. 28(1), 1998, p.67-79.
64.Kim S-W., Oommen B.J. A Brief Taxonomy and Ranking of Creative Prototype Reduction Scheme. Pattern Anal. Application Journal. 6(3), 2003, pp. 232-244.
65.Kim S-W., Oommen B.J. A Enhancing Prototype Reduction Scheme with Recursion: A Method Applicable for Large Data Sets. IEEEE Transaction on Systems, Man and Cybernetics. Part B. 34(3), 2004, p.1384-1397.
66.Bezdek J.C., Kucheva L.I. Nearest Prototype Classifier Designs. An Experimental Study. International Journal of Intelligent Systems. 16, 2001, p.1445-1473.
67.Eick C.F., Zeidat N., Vilalta R. Using Representative-Based Clustering for Nearest Neighbor Dataset Editing. 4th IEEEE International Conference on Data Mining. Brighton, 2004, 375-378.
68.Hamamoto Y., Uchimura S., Tomita S. A Bootstrap Technique for Nearest Neighbor Classifier Design. IEEE Transactions on Pattern Anal. And Machine Intelligence. Vol. 19(1), 1997, pp. 73-79.
69.Kucheva L.I., Bezdek J.C., Nearest Prototype Classification: Clustering, Genetic Algorithms or Random Search? IEEEE Transaction on Systems, Man and Cybernetics. Part C. 28(1), 1998, p. 160-164.
70.Li G., Japkowicz N., Stocki T.J., Unger R.K. Instance Selection by Border Sampling in Multi-class Domain. Advanced Data Mining, 2009, p. 209-221.
71.Li G., Japkowicz N., Stocki T.J., Unger R.K. Full Border Identification for Reduction of Training Sets. 21st Canadian Artificial Intelligence Conference. Winsor, 2008, p. 203-215.
72.Guichong Li Border Sampling Techniques in Machine Learning. Doctor Thesis. University of Ottawa, 2009, 182p.
73.Tax D., Duin R. Support Vector Data Description. Pattern Recognition Letters, 20, 1999, pp. 1191-1199.
74. Cao L., Lee H., Chong W. Modified Support Vector Novelty Detector Using Training Data with Outliers. Pattern Recognition Letters, 24, 2003, pp. 24792487.
75.Domingos P. Rule Induction and Instance-Based Learning: A Unified Approach. Proceedings of 14th International Joint Conference on Artificial Intelligence, 1995, pp. 1226-1232.
76.Domingos P. Unifying Instance-Based and Rule-Induction. Machine Learning, 24, 1996, pp.141-168.
77.Cameron-Jones R.M. Instance Selection by Encoding Length Heuristic with
tVi
Random Mutation Hill Climbing. Proceedings of 8 Australian Joint Conference on Artificial Intelligence, 1995, pp. 99-106.
78.Бородкин A.A., Комплексная процедура редукции выборок текстовых документов // Международный форум информатизации МФИ-2010. Труды XVIII международной научно-технической конференции «Информационные средства и технологии». Т.З. - М.:МЭИ, 2010 - с. 251254
79.Бородкин А.А., Толчеев В.О. Методы удаления нерелевантных документов из обучающих выборок. Международный форум информатизации МФИ-2009. Труды XVII международной научно-технической конференции «Информационные средства и технологии». Т.З. - М.:МЭИ, 2009 - с. 169-173
80.Веуег К., Goldstein J., Ramakrishnan R., Shaft U. When Is Nearest Neighbor Meaningful. Proceedings International Conference Database Theory, 1999, pp. 217-235.
81 .Berchtold S., Bohm C., Keim D., Kriegel H-P. A Cost Model for Nearest Neighbor Search in High-dimensional Data Space. Proceedings of ACM Annual Symposium Principles of Database Systems, 1997, pp.78-86.
82. Бородкин A.A., Толчеев В.О. Разработка комплексной процедуры редукции для увеличения быстродействия непараметрических методов
классификации текстовых документов. Заводская лаборатория. Диагностика материалов. №11, с.64-69.
83.Бородкин А.А., Толчеев В.О., Часовский А.В., Исследование зависимости точности классификации от структуры выборки!! Современные технологии в задачах управления, автоматики и обработки информации: труды XVI Международного научно-технического семинара. Сентябрь 2007 г., Алушта. - Тула: Изд-во ТулГУ, 2007 - с. 244-245
84.Herrera F., Herrera-Viedma Е. Aggregation Operators for Linguistic Weighted Information. IEEE Transactions on Systems, Man and Cybernetics, 27, 1997, pp. 646-656.
85.Dasarathy B.V., Sheela B. Visiting Nearest Neighbors. A survey of Nearest Neigbor Classification Techniques. Proceedings of the International Conference on Cybernetics and Society, 1977, pp. 630-635.
86.Браверман Э.М., Мучник И.Б. Структурные методы обработки эмпирических данных. М.: Наука, 1983. - 464 с.
87.Романов В.П. Интеллектуальные информационные системы в экономике. М.: Экзамен, 2003. - 494 с.
88.Кендалл М. Стьюарт А. Статистические выводы и связи. М.: Наука, 1973.-899 с.
89.Холлендер М., Вульф Д. Непараметрические методы статистики. М.: Финансы и статистика, 1983 - 518 с.
90.Лепский А.Е., Броневич А.Г. Математические методы распознавания образов. Курс лекций. Таганрог. Изд-во ТТИ ЮФУ, 2009- 152 с.
91. Дубров A.M., Мхитарян B.C., Трошин Л.И. Многомерные статистические методы. -М.: Финансы и статистика, 2000. - 351 с.
92.Прикладная статистика. Основы моделирования и первичная обработка данных. Под ред. С.А. Айвазяна.-М.: Финансы и статистика, 1983. - 471 с.
93.Шурыгин A.M. Прикладная статистика: робастность, оценивание, прогноз. М.: Финансы и статистика, 2000.
94.Орлов А.И. Эконометрика. М.: Изд-во Экзамен, 2004 - 576 с.
95.3агоруйко Н.Г., Елкина В.Н., Лбов Г.С. Алгоритмы обнаружения эмпирических закономерностей. Новосибирск: Наука, 1985. - 110 с.
96. Орлов А.И. О развитии математических методов теории классификации. Заводская лаборатория. Диагностика материалов. №7, 2009, с. 51-63.
97.Дюран Б., Оделл П. Кластерный анализ. - М.: Статистика, 1977. - 128 с.
98.Реброва М.П. Автоматическая классификация в системах обработки информации: поиск документов. М.: Радио и связь, 1983. - 97 с.
99.Терехина А.Ю. Анализ данных методами многомерного шкалирования. -М. Наука, 1986.- 168 с.
100. Agrawal R., Gehrke J., Gunopulos D., Raghavan P. Automatic Subspace of High Dimensional Data for Data Mining Applications. Proc. ACM SIGMOD Int. Conf. on Management of Date, 1998, pp.94-105.
101. Hinneburg A, Keim D.A. An Efficient Approach to Clustering in Large Multimedia Databases with Noise. Proc. 4nd Int. Conf. on Knowledge Discovery and Data Mining, 1998, pp.58-65.
102. Ester M., Kriegel H.-P., Sander J., Xu X. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining, 1996, pp.226-231.
103. Berchtold S., Bohm C., Keim D., Kriegel H-P. A Cost Model for Nearest Neighbor Search in High-dimensional Data Space. Proceedings of ACM Annual Symposium Principles of Database Systems, 1997, pp.78-86.
104. Beyer K., Goldstein J., Ramakrishnan R., Shaft U. When Is Nearest Neighbor Meaningful. Proceedings International Conference Database Theory, 1999, pp. 217-235.
105. Wettschereck D., Aha D., Mohri T. A Review and Comparative Evaluation of Feature Weighting Methods for a Class of Lazy Learning Algorithms. Artificial Intelligence Review, 11,1997, pp.273-314.
106. Verbaeten S., Van Assche A. Ensemble Methods for Noise Elimination in Classification Problems. Technical Report. Belgium, University of Leuven, Department of Computer Science, 2003.
107. Толчеев В.О. Синтез коллективов решающих правил для проведения классификации текстовых документов. Информационные технологии, №10, 2007, с.-32-38.
108. Kuncheva L.I., Whitaker C.J. Measures of Diversity in Classifiers Ensembles and Their Relationship with the Ensemble Accuracy. Machine Learning, 51, 2003, pp. 181-207.
109. Воронцов K.B., Колосков A.O. Профили компактности и выявление опорных объектов в метрических алгоритмах классификации. Искусственный интеллект. 2006. С.30-33.
110. Dietterich T.G. Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms. Neural Computation, 10, 1998, pp. 18951924.
111. Абусев P.А., Лумельский Я.П. Статистическая групповая классификация. Учебное пособие. Пермь, 1987. - 92 с.
112. Shaffer J.P. Multiple Hypothesis Testing. Annual Review of Psychology, 46, 1995,561-584.
113. Schmidt F.L. Statistical Significance Testing and Cumulative Knowledge in Psychology. Psychological Methods. 1, 1996, pp. 115-129.
114. Новиков Д.А. Статистические методы в педагогических исследованиях. М.: МЗ-Пресс, 2004 - 66с.
115. Будрейка Н.Н. Непараметрические методы исследования в психологии. Психологическая наук и образование. №1, 2007, сс. 40-47.
116. Хеттманспергер Т. Статистические выводы, основанные на рангах. М.: Финансы и статистика, 1987 - 334 с.
117. Тюрин Ю.Н., Макаров А.А. Статистический анализ данных на компьютере. - М.: Инфра-М, 1998. - 528 с.
118. Орлов А.И. Какие гипотезы можно проверять с помощью двухвыборочного критерия Вилкоксона. Заводская лаборатория. Диагностика материалов. №1, 1999, с. 51-56.
119. Орлов А.И. О проверке однородности двух независимых выборок. Заводская лаборатория. Диагностика материалов. №1, 2003, с.55-60.
120. Орлов А.И. Заметки по теории классификации. Социология: методология, методы, математические модели. №2, 1991, с.28-50.
121. Бородкин A.A., Толчеев В.О. Структура и функциональные возможности учебно-исследовательского программного комплекса. Международный форум информатизации МФИ-2008. Труды XVI международной научно-технической конференции «Информационные средства и технологии». Т.З. - М.:МЭИ, 2008 - с. 85-87
122. Бородкин A.A. Толчеев В.О., Применение метода потенциальной функции для классификации библиографических текстовых документов // Научная сессия МИФИ-2008. Сборник научных трудов. Т.П. Технологии разработки программных систем. Информационные технологии. - М.: МИФИ, 2008-с. 150-151
123. Бородкин A.A., Толчеев В.О. Разработка учебно-исследовательского программного комплекса для обработки и анализа библиографических текстовых документов. Вестник МЭИ №1 2010 г. М: МЭИ, 2010 - с. 96102
124. Бородкин A.A., Дербенев Н.В., Толчеев В.О., Программно-алгоритмические средства обработки и анализа библиографической текстовой информации. Современные технологии в задачах управления, автоматики и обработки информации: тезисы докладов XX Международного научно-технического семинара (г. Алушта, 18-24 сентября 2011 г.) - Пенза: Изд-во ПТУ, 2011 - с. 267-268
125. Nene S.A., Nayar S.K. А Simple Algorithm for Nearest Neighbor Search in High Dimensions. Technical Report. Department of Computer Science of Columbia University. New York, 1995, pp. 1-36.
126. Воронцов K.B. Обзор современных исследований по проблеме качества обучения алгоритмов. Таврический вестник информатики и математики. 2004.(,www.ccas.ru/frc/papers/voron04twim.pdf).
127. Плешко В.В. Поиск с учетом словоформ русского языка (http:// baks.gaz.ru/oradoc/ora/oral 5 5 .htm)
128. Толпегин П.В. Информационные технологии анализа русских естественно-языковых текстов. Часть 1. Изд-во Вычислительного центра им. Дородницына РАН, 2006. - 20 с.
129. Губин М.В., Морозов А.Б. Влияние морфологического анализа на качество информационного поиска (http://rcdl.ru/doc/2006/paper_67_v2.pdf).
Приложение 1 Лабораторные работы
Лабораторная работа №1
Формирование выборок и проведение предварительной обработки библиографических текстовых данных
Цель: сформировать обучающие и экзаменационные выборки из библиографических текстовых документов и применить методы предварительной обработки текстовых данных к полученным выборкам.
1. Изучить структуру библиографических документов и возможности модуля автоматизированного извлечения информации (Сервис—^Загрузка данных)
2. В соответствии с темой дипломной работы (направлением научных исследований) выбрать предметную область для поиска информации (задачей поиска является отбор документов, которые могут быть использованы при подготовке дипломного проекта). Сформировать 15 запросов на основе имеющейся априорной информации о предметной области (при необходимости использовать рубрикатор базы данных (БД) Compendex).
3. По составленным запросам с помощью модуля автоматизированного извлечения информации загрузить и сохранить на локальный диск библиографические документы в файлы с соответствующими названиями (например, Neural networks.txt, Control theory.txt, ...). Источник данных для загрузки определяется преподавателем из следующего списка:
а) библиографическая БД Compendex:;
б) цифровой библиотека (ЦБ) Researchlndex;
в) ЦБ ACM
Используя набор классов (в виде файлов, созданных самостоятельно или взятых из директории Articles), сформировать не менее 3-х выборок (Сервис—»Формирование выборок).
Обучающие и экзаменационные выборки формируются методом случайного отбора без возвращения и имеют равномерное распределение документов по классам (Ng -размер класса в обучающей
выборке, Ng е [100,150], ng - размер класса в экзаменационной выборке, g = l,...,G, количество классов (7 = 7). Соотношение между размером обучающей и экзаменационной выборок задается формулой N(T=l0n„. Проанализировать размер документов, которые оказались
о о
отобранными и заменить наиболее короткие документы. Сформированные выборки далее обозначаются, как «группа выборок М1».
4. Провести предварительную обработку сформированных в п.З выборок:
- Построить словари, проанализировать их размеры и частоты встречаемости терминов (Обработка и анализ данных^Построение словаря).
- для достижения минимума ошибки определить значение (интервал изменения) порога отсечения терминов по частоте встречаемости (использовать метод центроидов (МЦ), метод k-ближайшего соседа (к-БС, k=25) и наивный байесовский метод (НБМ)), сделать вывод о согласованности результатов, полученных для каждого из методов; Указание: данный пункт выполняется для евклидовой метрики, tfc-взвешивания, при удалении стоп-слов и включенном стемминге.
- выбрать размер словаря (количество информативных терминов) М, наиболее приемлемое для всех методов;
- проанализировать влияние стемминга (процедуры выявления основ слов) на точность классификации вышеуказанными методами.
Точность измеряется по экзаменационным выборкам и оценивается средним значением по группе выборок и размахом (значениями максимальной и минимальной ошибок).
5. Исследовать влияние способа взвешивания терминов на точность классификации (использовать МЦ и метод k-БС). Для проведения сравнительного анализа использовать tf-, tf-idf-, tfc-, ltc~, atc-взвешивания и размер словаря, определенный в п.4. Выбрать метод взвешивания наиболее приемлемый для МЦ и к-БС.
Указание: В п. 4 п. 5 необходимо построить графики зависимости ошибки классификации от значений порога отсечение. Для этого нужно переключиться в исследовательский режим работы программы (Режим-^Исследовательский), задать и сохранить необходимые значения параметров предварительной обработки данных, выполнить обучение и классификацию (Обработка и анализ данных—»Обучение и классификация), сохранить полученные результаты в текстовый файл, построить графики в Excel
Лабораторная работа №2
Обучение и исследование методов классификации библиографических
текстовых документов
Цель: Исследование влияния основных факторов на точность классификации, проведение обучения классификаторов и настройка их параметров.
1. Рассчитать показатель компактности для обучающих массивов из «группы выборок №1». С помощью метода центроидов (МЦ), метода к-ближайших соседа (к-БС) и наивного байесовского метода (НБМ) оценить зависимость между точностью классификации и компактностью выборок.
2. Из источника данных, использованного для составления «группы выборок №1», сформировать выборки различного размера Ng =100,150,200,250,300,350; (число классов G = 7,Ng = I0ng, Ng и
п „- количество документов в классе соответственно для обучающей и
о
экзаменационной выборок, документы распределены по классам равномерно). Исследовать влияние размера выборки на точность классификации МЦ, к -БС, НБМ. Выбрать размер выборки для количества классов равного 7 (G=l), исходя из критерия точность-быстродействие.
3. Из источника данных, использованного для составления «группы выборок №1», сформировать выборки с различным числом классов G = 3,5,7,9,11,13; размер выборок определен в п.2. Исследовать влияние числа классов на точность классификации МЦ, к-БС, НБМ.
4. Из источника данных, использованного для составления «группы выборок №1», сформировать выборки, в которых документы распределены по классам неравномерно (N\ = N4 = 70; N2 = N5 =100; N3 =N6 = 110; N7 = 140). Исследовать влияние неравномерного
распределения документов по классам на точность классификации МЦ, к -БС,НБМ.
5. Для «группы выборок №1». провести исследование влияния метрик расстояния на точность классификации с помощью МЦ, к-БС.
6. Провести настройку параметров не менее трех методов классификации из общего списка (по выбору преподавателя) и выявить значения параметров, обеспечивающие наилучшую точность.
Список методов:
- метод к-ближайших соседей (параметр к);
- модифицированный метод ближайшего соседа (параметр к, количество
опорных точек S);
- обобщенный метод ближайшего соседа (параметр к, количество опорных
точек S, коэффициент взвешивания р);
- метод потенциальных функций (вид функции, параметры а и Р);
- метод %г ~ профилей (параметр (порог) Т);
- метод Ml- профилей (параметр (порог) Т, параметр п).
7. Оценить точность методов, их быстродействие (процессорное (CPU) время в секундах) и затраты на настройку параметров. Обобщить результаты сравнительного анализа методов по критерию точность-быстродействие-затраты в сводной таблице.
Лабораторная работа №3
Синтез коллективов решающих правил для классификации библиографических текстовых документов
Цель: для увеличения точности классификации библиографических текстовых документов синтезировать коллективы решающих правил.
1. Изучить принципы построения коллективов решающих правил (.КРП).
2. Используя «группу выборок №1» для методов классификации, исследовавшихся в п.6 лабораторной работы №2, а также МЦ и НЕМ рассчитать показатель их «разнородности» по формуле ¡^-статистики.
3. На базе критерия точность-разнородность отобрать три наиболее подходящих метода для их включения в неоднородный коллектив решающих правил (КРП), действующий на основе простого голосования. Оценить точность и быстродействие КРП-1 (т = 3, т - количество членов комитета). Сформировать КРП-2, состоящий из всех исследуемых методов (т = 5). Проанализировать влияние количества членов комитета и степени их разнородности на ошибку и быстродействие. Оценить устойчивость результатов. Сравнить результаты с теоретическими, полученными для независимых равноточных классификаторов. Применить операцию «отказ от классификации» к элементам выборок, оценить результирующую точность.
4. Сформировать однородный комитет (КРП-3), состоящий или из семейства методов ближайшего соседа (метода к-БС, ММБС, ОМБС) или семейства профильных методов (МЦ, метод профилей, метод М/-профилей). Оценить ошибку и быстродействие КРП-3. Провести сравнительный анализ трех синтезированных комитетов, сделать вывод о целесообразности формирования однородных КРП.
5. Провести сопоставление точности КРП и точности индивидуального классификатора, например метода к-БС.
Приложение 2 Настройка параметров для выборок из русскоязычной цифровой библиотеки еЫЬгагу
Исследование №1
Цель исследования', выявить зависимость ошибки классификации от размера словаря (числа терминов) при обучении на группе выборок VI, V2, V3 Зафиксированные параметры, используются МЦ и МБС с евклидовой метрикой и //с-взвешиванием, без стемминга.
Зависимость средней по выборкам ошибки классификации от размерности матрицы документ-термин:
Результат исследования: рекомендуемый диапазон изменения размера словаря М е [166;300].
В работе для дальнейших исследований зафиксировано М = 166.
Исследование №2
Цель исследования: определение параметра к в методе к -БС
Зафиксированные параметры: евклидова метрика и //с-взвешивание, без стемминга.
Рис. Зависимость средней ошибки от количества ближайших соседей Результат исследования', рекомендуемый диапазон изменения к - к е [9;29]; В работе использовалось к = 9.
В отличие от обработки англоязычных выборок для русскоязычных документов не использовался стемминг. Это связано с тем, что из-за сильной морфологической изменяемости слов русского языка и сложного словообразования алгоритмы стемминга допускают достаточно много неточностей и менее эффективны при проведении классификации, чем при анализе англоязычных текстов [127,128,129]. В отсутствии стемминга ожидаемо увеличился размер словаря терминов (для русскоязычных выборок М= 166, для англоязычных выборок М= 125).
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.