Концептуальная кластеризация - Conceptual clustering

Концептуальная кластеризация это машинное обучение парадигма для неконтролируемая классификация развивалась в основном в 1980-е годы. Он отличается от обычного кластеризация данных путем создания описание концепции для каждого сгенерированного класса. Большинство концептуальных методов кластеризации способны генерировать иерархические структуры категорий; видеть Категоризация для получения дополнительной информации об иерархии. Концептуальная кластеризация тесно связана с формальный анализ концепции, обучение по дереву решений, и модель смеси учусь.

Концептуальная кластеризация против кластеризации данных

Концептуальная кластеризация, очевидно, тесно связана с кластеризацией данных; однако в концептуальной кластеризации формирование кластера определяется не только внутренней структурой данных, но и Язык описания который доступен учащемуся. Таким образом, учащийся может не получить статистически сильную группировку данных, если преобладающий язык описания концепций не способен описать эту конкретную регулярность. В большинстве реализаций язык описания был ограничен функцией соединение, хотя в COBWEB (см. "COBWEB "ниже), язык функции вероятностный.

Список опубликованных алгоритмов

Для концептуальной кластеризации предложено изрядное количество алгоритмов. Ниже приведены некоторые примеры:

КЛАСТЕР / 2 (Михальский и Степп, 1983)
COBWEB (Фишер, 1987 г.)
КИРУС (Колоднер, 1983)
ГАЛУА (Карпинето и Романо 1993),
GCF (Талавера и Бехар, 2001)
INC (Хадзикадич и Юн 1989)
ITERATE (Бисвас, Вайнберг и Фишер, 1998 г.),
ЛАБИРИНТ (Томпсон и Лэнгли, 1989)
ПОДПИСКА (Jonyer, Cook & Holder 2001).
UNIMEM (Лебовиц, 1987)
WITT (Hanson & Bauer 1989),

Более общие обсуждения и обзоры концептуальной кластеризации можно найти в следующих публикациях:

Михальский (1980)
Дженнари, Лэнгли и Фишер (1989)
Фишер и Паццани (1991)
Фишер и Лэнгли (1986)
Степп и Михальски (1986)

Пример: базовый концептуальный алгоритм кластеризации

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

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

Структура данных COBWEB представляет собой иерархию (дерево), в которой каждый узел представляет заданный концепция. Каждое понятие представляет собой набор (фактически, мультимножество или мешок) объектов, каждый объект представлен в виде списка свойств с двоичным значением. Данные, связанные с каждым узлом дерева (т. Е. Концепцией), представляют собой целые числа свойств для объектов в этой концепции. Например, (см. Рисунок), пусть концепция ${displaystyle C_ {1}}$ содержат следующие четыре объекта (разрешены повторяющиеся объекты).

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

[1 0 1]
[0 1 1]
[0 1 0]
[0 1 1]

Эти три свойства могут быть, например, [is_male, has_wings, is_nocturnal]. Тогда то, что хранится в этом концептуальном узле, - это количество свойств. [1 3 3], что указывает на то, что 1 из объектов в концепции - мужчина, 3 объекта имеют крылья и 3 объекта ведут ночной образ жизни. Концепция описание - условная вероятность (правдоподобие) свойств в узле. Таким образом, учитывая, что объект является членом категории (концепта) ${displaystyle C_ {1}}$ , вероятность того, что это мужчина, ${displaystyle 1/4 = 0,25}$ . Точно так же вероятность того, что у объекта есть крылья, и вероятность того, что объект ведет ночной образ жизни или и то, и другое, равна ${displaystyle 3/4 = 0,75}$ . Поэтому описание концепции может быть просто дано как [.25 .75 .75], что соответствует ${displaystyle C_ {1}}$ -условная вероятность признака, т. е. ${displaystyle p (x | C_ {1}) = (0,25,0,75,0,75)}$ .

На рисунке справа показано дерево понятий с пятью понятиями. ${displaystyle C_ {0}}$ - это корневой концепт, который содержит все десять объектов в наборе данных. Концепции ${displaystyle C_ {1}}$ и ${displaystyle C_ {2}}$ дети ${displaystyle C_ {0}}$ , первый из которых содержит четыре объекта, а второй - шесть объектов. Концепция ${displaystyle C_ {2}}$ также является родителем концепций ${displaystyle C_ {3}}$ , ${displaystyle C_ {4}}$ , и ${displaystyle C_ {5}}$ , которые содержат три, два и один объект соответственно. Обратите внимание, что каждый родительский узел (относительное понятие вышестоящего уровня) содержит все объекты, содержащиеся в его дочерних узлах (относительные подчиненные понятия). В описании COBWEB Фишером (1987) он указывает, что в узлах хранятся только общие подсчеты атрибутов (не условные вероятности и не списки объектов). Любые вероятности вычисляются по подсчетам атрибутов по мере необходимости.

Язык COBWEB

Язык описания COBWEB является «языком» только в широком смысле, потому что, будучи полностью вероятностным, он способен описать любую концепцию. Однако, если на диапазоны вероятностей, которые могут представлять концепции, накладываются ограничения, получается более сильный язык. Например, мы могли бы разрешить только концепции, в которых хотя бы одна вероятность отличается от 0,5 более чем на ${displaystyle alpha}$ . При этом ограничении с ${displaystyle alpha = 0,3}$ , такое понятие как [.6 .5 .7] не может быть сконструирован учащимся; однако такая концепция, как [.6 .5 .9] будут доступны, потому что хотя бы одна вероятность отличается от 0,5 более чем на ${displaystyle alpha}$ . Таким образом, при таких ограничениях мы получаем нечто вроде традиционного концептуального языка. В предельном случае, когда ${displaystyle alpha = 0,5}$ для каждого признака, и, следовательно, каждая вероятность в концепции должна быть 0 или 1, результатом является основа языка признаков на соединении; то есть каждое понятие, которое может быть представлено, затем может быть описано как совокупность признаков (и их отрицаний), а понятия, которые нельзя описать таким образом, не могут быть представлены.

Критерий оценки

В описании COBWEB Фишером (1987) мерой, которую он использует для оценки качества иерархии, является критерий Глюка и Кортера (1985). категория полезность (CU) мера, которую он заново выводит в своей статье. Мотивация для меры очень похожа на "получение информации "мера, введенная Куинланом для изучения дерева решений. Ранее было показано, что CU для классификации на основе признаков такая же, как и взаимная информация между характеристическими переменными и переменной класса (Gluck & Corter, 1985; Corter & Gluck, 1992), и поскольку эта мера гораздо более известна, мы исходим из взаимной информации как меры категории «добро».

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