Понятие транзакций и проблема их кластеризации - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата

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

Транзакционная или операционная база данных (Transaction database) представляет собой двумерную таблицу, которая состоит из номера транзакции (TID) и перечня покупок, приобретенных во время этой транзакции.

TID - уникальный идентификатор, определяющий каждую сделку или транзакцию.

Пример транзакционной базы данных, состоящей из покупательских транзакций, приведен ниже в таблице. В таблице первая колонка (TID) определяет номер транзакции, во второй колонке таблицы приведены товары, приобретенные во время определенной транзакции.

TID

Приобретенные покупки

100

Хлеб, молоко, печенье

200

Молоко, сметана

300

Молоко, хлеб, сметана, печенье

400

Колбаса, сметана

500

Хлеб, молоко, печенье, сметана

Благодаря последним разработкам в области поиска информации, Web технологий и Data Mining, кластеризация транзакций играет важную роль и привлекает внимание во многих приложениях и областях, в которых ускоряет поиск ближайшего соседа. Например, кластеризация используется как важнейший метод во многих web приложениях; транзакционная кластеризация применяется в целевом маркетинге/рекламе, при обнаружении причин заболеваний, при поиске информации, основанном на содержании образа, при получении рекомендаций соединений для web пользователей, организации папок и закладок, создании информационных иерархий подобных Yahoo! и Infoseek и т. д.

Для кластеризации транзакций оказываются не эффективными подходы, основанные на парной похожести транзакций (k-means, k-modes) и используемых при этом локальных критериях оценки похожести. Проблема заключается в том, что транзакционные данные являются разреженными, каждая транзакция содержит небольшое количество предметов из общей совокупности и малое число общих предметов с другими транзакциями.

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

Пример 1. Рассмотрим кластер из пяти транзакций

T1 = {a, e, h, k}, t2 = {a, c, f}, t3 = {a, b, c}, t4 = {b, c, i, j}, t5 = {b, e, g}.

Каждая транзакция представляет собой множество любимых боевиков пяти личностей. Из всех возможных 10 пар транзакций только две пары (t2, t3) и (t3, t4) имеют два общих боевика. Все другие пары имеют не более чем 1 общий боевик. Следовательно, парное подобие в этом кластере слабое. Однако можно заметить, что a, b, c являются типичными боевиками, так как два из них присутствуют в 3-х из пяти транзакций, т. е. вероятность любителей боевиков составляет 60%. Следовательно, эти типичные боевики можно использовать, чтобы характеризовать интересы этого кластера людей, в противоположность кластеру людей, интересующихся мелодрамами. Дело в том, что для большого числа боевиков и большого кластера людей, которые любят боевики, маловероятно, что каждый человек предпочитает те же боевики, что и другой человек в этом кластере. В связи с низкой парной похожестью внутри кластера необходимы другие критерии оценки похожести предметов в кластере, способные сгруппировать любителей боевиков и мелодрам в разные кластеры.

Похожие статьи




Понятие транзакций и проблема их кластеризации - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата

Предыдущая | Следующая