Участник:Андрей Туманов/Алгоритм кластеризации категориальных данных CLOPE

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

1.2 Математическое описание алгоритма

Пусть имеется база транзакций $D$, состоящая из множества транзакций $\{t_1,t_2,...,t_n\}$. Каждая транзакция есть набор объектов $\{i_1,...,i_m\}$. Множество кластеров $\{C_1,...,C_k\}$ есть разбиение множества $\{t_1,...,t_n\}$, такое, что $C_1 \cup \dots \cup C_k=\{t_1,...,t_n\}$ и $C_i \ne \empty$ и $C_i \cap C_j = \empty$, для $i \ge 1, k \ge j$. Каждый элемент $C_i$ называется кластером, а $n, m, k$ – количество транзакций, количество объектов в базе транзакций и число кластеров соответственно.

Каждый кластер $C$ имеет следующие характеристики:

$D(C)$ – множество уникальных объектов;

$Occ(i,C)$ – количество вхождений (частота) объекта $i$ в кластер $C$;

$S(C)= \sum_{i \in D(C)} Occ(i,C)= \sum_{t_i \in C} \mid t_i \mid ,$

$W(C)= \mid D(C) \mid ,H(C)=S(C)/W(C)$

Функция стоимости:

$Profit(C) = \frac{\sum^{k}_{i=1} G(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid } = \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 }$

$\mid C_i \mid$количество объектов в $i$-ом кластере, $k$ – количество кластеров, $r$ – коэффициент отталкивания $(0 \lt r \le 1)$

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

Постановка задачи кластеризации алгоритмом CLOPE выглядит следующим образом:

для заданных $D$ и $r$ найти разбиение $C$ такое, что: $Profit(C) \longrightarrow max$.

3 Литература

[1]