В.А. Кошелева, О.И. Федяев Классификация знаний на основе метода кластерного анализа. III международная научно-техническая конференция молодых учёных и студентов. 11-13 декабря 2007г.



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

Кластерный анализ предназначен для разбиения множества объектов на заданное или неизвестное число кластеров на основании некоторого математического критерия качества классификации (cluster (англ.) – гроздь, пучок, скопление, группа элементов, характеризуемых некоторым свойством) [2]. Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования:

1) внутри групп объекты должны быть тесно связаны между собой;
2) объекты разных групп должны быть далеки друг от друга;
3) при прочих равных условиях распределения объектов по группам должны быть равномерными.
Требования пунктов 1 и 2 выражают стандартную концепцию компактности классов разбиения, требование пункта 3 состоит в том, чтобы критерий не навязывал объединения отдельных групп объектов.[2]

Примером кластеризации является система COBWEB [3]. Не претендуя на лучшую модель человеческого познания, эта система учитывает категории базового уровня и степень принадлежности элемента соответствующей категории. Кроме того, в программе COBWEB реализован инкрементальный алгоритм обучения, не требующий представления всех обучающих примеров до начала обучения. Во многих приложениях обучаемая система получает данные, зависящие от времени. В этом случае она должна строить полезные определения понятий на основе исходных данных и обновлять эти описания с появлением новой информации. В системе COBWEB также решена проблема определения корректного числа кластеров. Подход, когда количество кластеров определяется пользователем нельзя назвать гибким. В системе COBWEB для определения количества кластеров, глубины иерархии и принадлежности категории новых экземпляров используется глобальная метрика качества. В системе COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения.

При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility). Критерий полезности категории был определён при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

Значения суммируются по всем категориям , всем свойствам и всем значениям свойств . Значение называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство принимает значение , относится к категории . Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесённых к одной категории, имеют одинаковые значения. Величина называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории свойство принимает значение . Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение – это весовой коэффициент, усиливающий влияние наиболее распространённых свойств. Благодаря совместному учёту этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

В системе COBWEB реализован метод поиска экстремума в пространстве возможных кластеров с использованием критерия полезности категорий для оценки и выбора возможных способов категоризации. Сначала вводится единственная категория, свойства которой совпадают со свойствами первого экземпляра. Для каждого последующего экземпляра алгоритм начинает свою работу с корневой категории и движется далее по дереву. На каждом уровне выполняется оценка эффективности категоризации на основе критерия полезности. При этом оцениваются результаты следующих операций:
1) отнесение экземпляра к наилучшей из существующих категорий;
2) добавление новой категории, содержащей единственный экземпляр;
3) слияние двух существующих категорий в одну новую с добавлением в неё этого экземпляра;
4) разбиение существующей категории на две и отнесение экземпляра к лучшей из вновь созданных категорий.

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

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

Литература


  1. Джордж Ф. Люггер. Искусственный интеллект. Стратегии и методы решения сложных проблем Издательство «Вильямс» - Москва, Санкт-Петербург, Киев, 2003.
  2. Гаврилова Т.А. и др. Базы знаний интеллектуальных систем М, 2000
  3. Fisher D.H. Knowledge acquisition via incremental conceptual clustering. Machine Learning