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

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «== Свойства и структура алгоритма CLOPE == === Общее описание алгоритма CLOPE === Алгоритм CLOPE реша…»)
 
Строка 14: Строка 14:
 
[[Файл:Clope split.png|border|Гистограммы разбиений]]
 
[[Файл:Clope split.png|border|Гистограммы разбиений]]
  
Лучшим признаётся разбиение, у которого  
+
Лучшим признаётся разбиение, у которого сумма H/W, взвешенная с количеством транзакций в каждом кластере, минимальна.
 
=== Математическое описание алгоритма CLOPE ===
 
=== Математическое описание алгоритма CLOPE ===
 
=== Вычислительное ядро ===
 
=== Вычислительное ядро ===

Версия 09:47, 20 января 2017

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

1.1 Общее описание алгоритма 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. Гистограммы разбиений

Лучшим признаётся разбиение, у которого сумма H/W, взвешенная с количеством транзакций в каждом кластере, минимальна.

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

1.3 Вычислительное ядро

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Информационный граф

1.7 Ресурс параллелизма

1.8 Входные и выходные данные