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

Концептуальная кластеризация — это парадигма машинного обучения для классификации без учителя , которая была определена Рышардом С. Михальски в 1980 году (Фишер 1987, Михальски 1980) и развивалась в основном в 1980-х годах. Он отличается от обычной кластеризации данных тем, что генерирует описание концепции для каждого сгенерированного класса. Большинство методов концептуальной кластеризации способны генерировать иерархические структуры категорий; см. в разделе «Категоризация» дополнительную информацию об иерархии . Концептуальная кластеризация тесно связана с анализом формальных концепций , обучением дерева решений и обучением смешанной модели .

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

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

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

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

КЛАСТЕР/2 (Михальский и Степп, 1983)
ПАУТИНКА (Фишер, 1987)
СИР (Колоднер, 1983)
ГАЛУА (Карпинето и Романо, 1993),
ЗКФ (Талавера и Бехар, 2001)
ИНК (Хадзикадич и Юн, 1989)
ИТЕРАЦИЯ (Бисвас, Вайнберг и Фишер 1998),
ЛАБИРИНТ (Томпсон и Лэнгли, 1989)
ПОДЧИНИТЬ (Джоньер, Кук и Холдер, 2001).
UNIMEM (Лебовиц, 1987)
ВИТТ (Хэнсон и Бауэр, 1989),

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

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

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

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

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

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

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

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

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

Язык COBWEB

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

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

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

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

Ссылки

Бисвас, Г.; Вайнберг, Дж.Б.; Фишер, Дуглас Х. (1998). «Итерация: концептуальный алгоритм кластеризации для интеллектуального анализа данных». Транзакции IEEE в системах, человеке и кибернетике. Часть C: Приложения и обзоры . 28 (2): 100–111. дои : 10.1109/5326.669556 .

Карпинето, К.; Романо, Г. (2014) [1993]. «Галуа: теоретико-порядковый подход к концептуальной кластеризации» . Материалы 10-й Международной конференции по машинному обучению, Амхерст . стр. 33–40. ISBN 978-1-4832-9862-7 .

Фишер, Дуглас Х. (1987). «Получение знаний посредством поэтапной концептуальной кластеризации» (PDF) . Машинное обучение . 2 (2): 139–172. дои : 10.1007/BF00114265 .

Фишер, Дуглас Х. (1996). «Итеративная оптимизация и упрощение иерархических кластеризаций». Журнал исследований искусственного интеллекта . 4 : 147–178. arXiv : cs/9604103 . Бибкод : 1996cs........4103F . дои : 10.1613/jair.276 . S2CID 9841360 .

Фишер, Дуглас Х.; Лэнгли, Патрик В. (1986). «Концептуальная кластеризация и ее связь с числовой таксономией» . В Гейле, Вашингтон (ред.). Искусственный интеллект и статистика . Ридинг, Массачусетс: Аддисон-Уэсли. стр. 77–116. ISBN 978-0-201-11569-7 . OCLC 12973461 .

Фишер, Дуглас Х.; Паццани, Майкл Дж. (2014) [1991]. «Вычислительные модели концептуального обучения» . В Фишере, DH; Паццани, MJ; Лэнгли, П. (ред.). Формирование концепции: знания и опыт обучения без учителя . Сан-Матео, Калифорния: Морган Кауфманн. стр. 3–43. дои : 10.1016/B978-1-4832-0773-5.50007-9 . ISBN 978-1-4832-2116-8 .

Дженнари, Джон Х.; Лэнгли, Патрик В.; Фишер, Дуглас Х. (1989). «Модели поэтапного формирования понятий» . Искусственный интеллект . 40 (1–3): 11–61. дои : 10.1016/0004-3702(89)90046-5 .

Хэнсон, С.Дж.; Бауэр, М. (1989). «Концептуальная кластеризация, категоризация и полиморфия» . Машинное обучение . 3 (4): 343–372. дои : 10.1007/BF00116838 .

Джоньер, И.; Кук, диджей; Холдер, Л.Б. (2001). «Иерархическая концептуальная кластеризация на основе графов». Журнал исследований машинного обучения . 2 : 19–43. дои : 10.1162/153244302760185234 .

Лебовиц, М. (1987). «Эксперименты с поэтапным формированием понятий» . Машинное обучение . 2 (2): 103–138. дои : 10.1007/BF00114264 .

Михальский, Р.С. (1980). «Получение знаний посредством концептуальной кластеризации: теоретическая основа и алгоритм разделения данных на соединительные концепции» (PDF) . Международный журнал политического анализа и информационных систем . 4 : 219–244.

Михальский, Р.С.; Степп, RE (1983). «Обучение на наблюдениях: концептуальная кластеризация» (PDF) . В Михальском, РС; Карбонелл, Дж.Г.; Митчелл, ТМ (ред.). Машинное обучение: подход искусственного интеллекта . Пало-Альто, Калифорния: Тайога. стр. 331–363. ISBN 978-0-935382-05-1 . OCLC 455234543 .

Степп, Р.Э.; Михальский, Р.С. (1986). «Концептуальная кластеризация: изобретение целенаправленной классификации структурированных объектов» (PDF) . В Михальском, РС; Карбонелл, Дж.Г.; Митчелл, ТМ (ред.). Машинное обучение: подход искусственного интеллекта . Лос-Альтос, Калифорния: Морган Кауфманн. стр. 471–498. ISBN 0-934613-00-1 .

Талавера, Л.; Бежар, Дж. (2001). «Концептуальная кластеризация на основе общности с вероятностными концепциями». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 23 (2): 196–206. дои : 10.1109/34.908969 .

Внешние ссылки