Участник:Ilya365365/Алгоритм кластеризации категориальных данных

Свойства и структура алгоритма CLOPE

Общее описание алгоритма CLOPE

Алгоритм CLOPE решает задачу кластеризации категориальных данных. Здесь и далее под категориальными данными понимаются качественные характеристики объектов, измеренные в шкале наименований, то есть при сравнении категориальных данных указывается только, одинаковы или нет объекты относительно данного признака.

Алгоритм CLOPE работает с транзакциями. Под термином транзакция понимается произвольный набор объектов, например, список ключевых слов статьи, товары, купленные в супермаркете, множество симптомов пациента, характерные фрагменты изображения и так далее. Задача кластеризации транзакционных данных состоит в получении такого разбиения всего множества транзакций, чтобы похожие транзакции оказались в одном кластере, а отличающиеся друг от друга – в разных кластерах.

В основе алгоритма кластеризации CLOPE лежит идея максимизации глобальной функции стоимости, которая повышает близость транзакций в кластерах при помощи увеличения параметра кластерной гистограммы.Для примера рассмотрим выборку из пяти списков покупок: {(apple, banana), (apple, banana, cake), (apple, cake, dish), (dish, egg), (dish, egg, fish)}, или сокращённо {ab, abc, acd, de, def}. Каждый список - транзакция. Каждый купленный предмет является объектом. Представим себе, что мы хотим сравнить между собой следующие два разбиения на кластеры:

1: {{ab, abc, acd}, {de, def}}

2: {{ab, abc}, {acd, de, def}}.

Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину W (количество уникальных объектов кластера) и высоту H (отношение общего числа объектов и ширины). Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4.

Лучшим признаётся разбиение, при котором достигается минимум функции [math]\displaystyle{ Profit(C)=\frac{\sum^{k}_{i=1} H(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} }[/math]  =  [math]\displaystyle{ \frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} }[/math] Здесь [math]\displaystyle{ r }[/math] - коэффициент отталкивания, [math]\displaystyle{ k }[/math] - количество кластеров, [math]\displaystyle{ S(C_i) }[/math] - число объектов в кластере [math]\displaystyle{ C_i }[/math], [math]\displaystyle{ \mid C_i \mid }[/math] - число транзакций в кластере [math]\displaystyle{ C_i }[/math], [math]\displaystyle{ H(C_i) }[/math] и [math]\displaystyle{ W(c_i) }[/math] - высота и ширина [math]\displaystyle{ C_i }[/math] соответственно.