Методичка. Распознование образов

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

Задания для индивидуальной работы

Реализовать задания 3 – 7 параграфа 1 при помощи метода потенциальных функций, сравнить полученные результаты с результатами, полученными при помощи других методов.

Литература

1.Метод потенциальных функций в теории обучения машин / М.А. Айзерман, Э. М. Бравеман, Л. И. Розоно-

эр. – М.: Наука, 1970. – 384 с.

2. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.:

Фазис, 2006.

3.Дьяконов, A. Г. Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab (практикум на ЭВМ кафедры математических методов прогнозирования). — МАКСПресс, 2010.

— 278 с.

4.Прикладная статистика: Классификации и снижение размерности: Справ. изд./С. А. Айвазян, В. М. Бухшта-

52

бер, И. С. Енюков, Л. Д. Мешалкин; Под ред. С. А. Айвазяна. - М.: Финансы и статистика, 1989. - 607 с.

5.Лепский А.Е., Броневич А.Г. Математические методы распознавания образов: Курс лекций. – Таганрог: Изд-

во ТТИ ЮФУ, 2009. – 155 с.

6.Воронцов К.В. Курс лекций «Математические методы обучения по прецедентам» // http://www.machinelearning.ru/wiki/images/6/6d/Voron- ML-1.pdf

7.Распознавание образов методом потенциальных функций // http://citforum.ru/programming/delphi/recognition_2/

53

9. Метод k-средних

Теоретические основы

Метод k-средних – простой, быстрый и точный метод кластеризации [1, 2, 3, 4]. Заключается в том, чтобы отнести объект к одному из заранее определенных классов (кластеров1), центр тяжести которого, находится ближе всего к данному объекту. Особенностью метода является то, что выделенные в результате расчетов кластеры не будут пересекаться – гарантируется, что каждый классифицированный объект будет отнесен только к одному классу

[1].

В классическом варианте алгоритм k-средних относится к методам обучения без учителя и является итерационным алгоритмом. Варианты такой реализации данного алгоритма на С-подобном языке программирования можно найти в [1], для среды MatLab в [4].

Выделяют следующие основные проблемы алгоритма k-средних:

необходимость заранее знать число кластеров;

чувствительность алгоритма к выбору начальных центров кластеров.

Так как в методе k-средних для определения «центра» класса используется среднее арифметическое, то данный алгоритм будет чувствителен к шумам и выбросам. Поэтому существует вариация метода k-средних – метод k- медиан. Метод k-медиан - тот же центроидный метод, но

1 Для простоты здесь будем считать термины «класс» и «кластер» равнозначными, хотя разница заключается в том, что под «кластером» понимается подмножество объектов разбиваемой совокупности, которое заранее не задано, тогда как если заранее задается число подмножеств, на которое будем разбивать объекты, то говорят про «классы».

54

центр объединенного кластера вычисляется как медиана, которая, как известно из статистики, меньше подвержена влияниям выбросов. В работе [1] можно фрагменты программ на С-подобном языке программирования для подсчета среднего значения и медианы.

Задания для индивидуальной работы

Реализовать задания 3 – 7 параграфа 1 при помощи методов k-средних и k-медиан, сравнить полученные результаты между собой, а также с результатами, полученными при помощи других методов.

Литература

1.Игорь Гайдышев, "Анализ и Обработка Данных: специальный справочник", СПб: Питер, 2001. - 752 с.

2.Прикладная статистика: Классификации и снижение размерности: Справ. изд./С. А. Айвазян, В. М. Бухштабер, И. С. Енюков, Л. Д. Мешалкин; Под ред. С. А. Ай-

вазяна. - М.: Финансы и статистика, 1989. - 607 с.

3. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.:

Фазис, 2006.

4.Дьяконов, A. Г. Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab (практикум на ЭВМ кафедры математических методов прогнозирования). — МАКСПресс, 2010.

— 278 с.

5.Форсайт Д.А., Понс Ж. Компьютерное зрение. Современный подход. : Пер. с англ. – М.: Издательский дом

«Вильямс», 2004. – 928 с.

55

6.Ландэ Д. В., Снарский А. А., Безсуднов И. В. Интернетика: Навигация в сложных сетях: модели и алгорит-

мы. — M.: Либроком (Editorial URSS), 2009. — 264 с.

7.Лепский А.Е., Броневич А.Г. Математические методы распознавания образов: Курс лекций. – Таганрог: Изд-

во ТТИ ЮФУ, 2009. – 155 с.

8.Искусственный интеллект: современный подход / Стюарт Рассел, Питер Норвиг, 2-е изд..: Пер. с англ. – М. : Издательский дом "Вильяме", 2006. – 1408 с.

56

Приложение 1: Возможные признаки текстовой информации

1.Средняя длина слова: сумма длин всех слов в буквах, деленная на количество слов.

2.Среднее количество слов в предложении: общее количество слов, деленное на количество предложений.

3.Среднее количество определенной части речи1 (глагол, существительное и т.д.) в предложении: общее количество слов выбранной части речи, деленных на количество предложений в тексте.

4.Степень (процент) сжатия архиватором (7zip, rar и т.п.).

5.Среднее количество иностранных слов в предложении: общее количество иностранных слов, деленное на количество предложений в тексте.

6.Количество предложений начинающихся с определенной части речи (например, предлога).

7.Среднее количество особых форм глагола (причастий или деепричастий) в предложении: общее количество особых форм глагола, деленных на количество слов в тексте.

8.Среднее количество цитат в тексте: общее количество цитат у данного автора, деленных на количество слов в тексте.

9.Среднее количество определенных символов (букв, цифр, знаков препинания и т.д.) в тексте: общее количество выбранных символов у данного автора, деленных на количество слов в тексте.

10.Доля гласных или согласных букв в тексте.

1 Можно воспользоваться программой морфологического анализа текстов на русском языке Mystem компании Yandex: http://company.yandex.ru/technologies/mystem/.

57

Дополнительный список литературы и источников

1.Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning. — Springer, 2001. — 533 p.

2.http://mlearn.ics.uci.edu/MLRepository.html – библиотека баз и генераторов данных, предназначенных для экспериментального анализа алгоритмов машинного обучения.

3.Интеллектуальные информационные системы: Учебник / А. В. Андрейчиков, О. Н. Андрейчикова. М.: Финансы и статистика, 2006. – 424 с.

4.Компьютерное моделирование лингвистических объектов : монография / И.Е.Воронина. – Воронеж : Изда- тельско-полиграфический центр Воронежского государственного университета, 2007. – 177 с.

5.С. А. Айвазян, В.С. Мхитарян. Прикладная статистика и основы эконометрики. - М.: Издательское объедине-

ние «Юнити», 1998. - 1022 с.

6.Миркин, Б. Г. Методы кластер-анализа для поддержки принятия решений: обзор : препринт WP7/2011/03 [Текст] / Б. Г. Миркин ; Национальный исследовательский университет «Высшая школа экономики». – М. : Изд. дом Национального исследовательского университета «Высшая школа экономики», 2011. – 88 с.

7.Christopher M. Bishop. Pattern recognition and machine learning. - Springer, 2006. – 738 с.

58

Учебное издание

Вероятностные методы анализа неструктурированной текстовой информации

Сидоров Юрий Владимирович Смирнов Николай Васильевич

59

Редактор Л. П. Соколова

Компьютерная верстка и дизайн – Н. В. Смирнов

60

Подписано в печать 25.09.2009 Формат 60 84116 . Бумага офсетная.

Офсетная печать. Уч.-изд. л. 8,3. Тираж 500 экз. Изд. № 204.

Государственное образовательное учреждение высшего профессионального образования

ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Отпечатано в типографии Издательства ПетрГУ 185910, г. Петрозаводск, пр. Ленина, 33

61