В.А. Кошелева Алгоритм обучения без учителя на основе кластерного анализа. III международная научная конференция студентов, аспирантов и молодых ученых «Компьютерный мониторинг и информационные технологии». 24 мая 2007г.В области машинного обучения широко применяются методы кластерного анализа. Например, в области медицины кластеризация заболеваний, лечения заболеваний или симптомов заболеваний даёт возможность широко использовать таксономию. В области психиатрии правильная диагностика кластеров симптомов, таких как паранойя, шизофрения и т.д., является решающей для успешной терапии. Известны широкие применения кластерного анализа в маркетинговых исследованиях, археологии. Таким образом, в тех случаях, когда необходимо классифицировать большое количество информации для формирования знаний о предметной области, кластерный анализ оказывается весьма полезным и эффективным. [2] Для решения задачи кластеризации (clustering problem) требуются набор неклассифицированных объектов и средства измерения их подобия. Целью кластеризации является организация объектов в классы, удовлетворяющие некоторому стандарту качества, например, на основе максимального сходства объектов каждого класса. [1] Одним из первых подходов решения задач кластеризации является числовая таксономия (numeric taxonomy). Численные методы основываются на представлении объектов с помощью свойств, каждое из которых может принимать некоторое числовое значение. При наличии корректной метрики подобия каждый объект (вектор из n значений признаков) рассматривают как точку в n-мерном пространстве. Используя метрику подобия, алгоритмы кластеризации этой группы строят классы по принципу «снизу вверх». В рамках этого подхода, также называемого стратегией накопительной кластеризации (agglomerative clustering), категории формируются следующим образом: 1) среди всех пар объектов выбирается пара с максимальной степенью подобия, которая и становится кластером; 2) определяются свойства кластера как некоторые функции свойств элементов (например, среднее значение), и компоненты объектов заменяются этими значениями признаков; 3) процесс повторяется до тех пор, пока все объекты не будут отнесены к одному кластеру. Результатом работы такого алгоритма является бинарное дерево, листья которого соответствуют экземплярам, а внутренние узлы – кластерам более общего вида. Данный алгоритм обучения без учителя оценивает плотность по методу максимального правдоподобия. Это означает построение такого распределения, которому с наибольшей вероятностью подчиняются входные объекты. Примером такой кластеризации является система COBWEB [3]. Не претендуя на лучшую модель человеческого познания, эта система учитывает категории базового уровня и степень принадлежности элемента соответствующей категории. Кроме того, в программе COBWEB реализован инкрементальный алгоритм обучения, не требующий представления всех обучающих примеров до начала обучения. Во многих приложениях обучаемая система получает данные, зависящие от времени. В этом случае она должна строить полезные определения понятий на основе исходных данных и обновлять эти описания с появлением новой информации. В системе COBWEB также решена проблема определения корректного числа кластеров. Подход, когда количество кластеров определяется пользователем нельзя назвать гибким. В системе COBWEB для определения количества кластеров, глубины иерархии и принадлежности категории новых экземпляров используется глобальная метрика качества. В системе COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Также в системе реализован метод поиска экстремума в пространстве возможных кластеров с использованием критерия полезности категорий для оценки и выбора возможных способов категоризации. Этот алгоритм достаточно эффективен и выполняет кластеризацию на разумное число кластеров. Поскольку в нем используется вероятностное представление принадлежности, получаемые категории являются гибкими и робастными. Кроме того, в нем проявляется эффект категорий базового уровня, поддерживается прототипирование и учитывается степень принадлежности. Он основан не на классической логике, а, подобно методам теории нечетких множеств, учитывает «неопределенность» категоризации как необходимый компонент обучения и рассуждений в гибкой и интеллектуальной манере. Программа COBWEB является недоступной, и дальнейшая работа будет направлена на реализацию алгоритмов кластеризации для извлечения знаний в прикладных областях. |