Понятие транзакций и проблема их кластеризации - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата
Термин "транзакция" относится к подмножеству предметов из общей совокупности с переменным числом предметов (мощностью подмножества). Транзакциями являются записи в таблице, содержащие категориальные атрибуты и имеющие различную длину, в отличие от категориальных БД, где длина всех записей одинакова. В связи с этим транзакционные БД считаются менее упорядоченными, по сравнению с категориальными БД, что усложняет их кластеризацию. Похожие транзакции должны иметь общие предметы при определенном уровне поддержки частоты их встречаемости, не ниже заданного, называемого минимальной поддержкой. Этого трудно добиться на разреженных транзакционных данных с низкой встречаемостью одинаковых наборов предметов. Примером таких транзакций являются множества терминов в статьях или документах, когда близкие по смыслу текстовые источники содержат мало точно совпадающих терминов (ключевых слов), т. е. трудно выделить общую тему. Классическими примерами транзакций являются корзина покупок в магазине, профиль интересов клиента, множество симптомов пациента, множество характеристик образа и тому подобное.
Транзакционная или операционная база данных (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%. Следовательно, эти типичные боевики можно использовать, чтобы характеризовать интересы этого кластера людей, в противоположность кластеру людей, интересующихся мелодрамами. Дело в том, что для большого числа боевиков и большого кластера людей, которые любят боевики, маловероятно, что каждый человек предпочитает те же боевики, что и другой человек в этом кластере. В связи с низкой парной похожестью внутри кластера необходимы другие критерии оценки похожести предметов в кластере, способные сгруппировать любителей боевиков и мелодрам в разные кластеры.
Похожие статьи
-
Понятие Data Mining Средства Data Mining включают в себя очень широкий класс различных технологий и инструментов. Средства Data Mining на рынке...
-
В наше время все большее количество компаний, стремясь к повышению эффективности и прибыльности бизнеса пользуются цифровыми (автоматизированными)...
-
Кластеризация (или кластерный анализ) -- это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться...
-
При работе над проектом разрабатывались два основных компонента системы: база данных (далее - БД) и интерфейс клиентского приложения. Затем необходимо...
-
Вычислительная сложность алгоритмов Алгоритм кластеризации Вычислительная сложность Иерархический O(n2) K-средних O(nkl), где k - число кластеров, l -...
-
Общее описание программного обеспечения, реализующего разработанный алгоритм Основной идеей дипломного проекта, является реализация алгоритма...
-
Преимущества, которые дает тестировщику автоматизация тестирования: - Исключен "человеческий фактор". Существует некоторая гарантия того, что не один...
-
Поскольку клиентская часть представляет собой приложение на базе операционной системы Android, то для ее разработки был выбран рекомендуемый...
-
Обоснование выбора средств разработки проекта Для реализации корпоративной информационной системы "Бюджетное планирование и отчетность" в исследуемой...
-
В настоящее время биометрия входит в состав наиболее распространенных технологий и средств защиты информации. Отпечатки пальцев являются самой широко...
-
При запуске программы с входными параметрами {"-makexls" "filename. xls" "температурная_точка" "отклонение" "элемент"} происходит извлечение результатов...
-
Назначение и функции программной системы Разработанная база данных "Библиотека" предназначена для использования в учреждениях библиотек. Основной...
-
Выбор программ и алгоритмы реализации базы данных - База данных "Кинотеатр"
Microsoft Office Access - мощное приложение Windows. При этом производительность СУБД органично сочетаются со всеми удобствами и преимуществами Windows....
-
Модели транзакций - Банки и базы данных. Системы управления базами данных
Под транзакциями понимаются действия, производимые над базой данных и переводящие ее из одного согласованного состояния в другое согласованное состояние....
-
Тестируемый программный продукт является высокопроизводительным приложением, которое предоставляет возможность создания и настройки сетей беспроводного...
-
Компания MERA Networks - является одним из крупнейших мировых поставщиков услуг в сфере информационно-коммуникационных технологий. MERA предлагает...
-
Автоматизированное тестирование программного обеспечения - это процесс проверки программного обеспечения, который включает в себя такие шаги как запуск,...
-
В то время как цель проекта заключалась в оценке эффективности автоматизации тестирования функционала ядра, работа стала своего рода подведением итогов...
-
Для того, чтобы вынести решение об оправданности или неоправданности внедрения автоматизированного тестирования вместо ручного, необходимо...
-
В течении года от команды разработчиков пришло 6 пакетов, содержащих изменения в ядре программы. Для каждого пакета составлялось в среднем от 1-ого до...
-
Выбор программного обеспечения для внедрения KPI целиком и полностью упирается в потребности конкретной компании. Благодаря все большей и большей...
-
Стек технологий При выборе стека технологий основное внимание уделялось следующим факторам, в порядке убывания значимости: § Кроссплатформенность; §...
-
В процессе разработки программного средства было создано 12 таблиц. Для их создания использовалось графическое средство SqlYong и кодирование на языке...
-
Разработка структур БД Информационная структура БД (Рисунок 2.1) Рисунок 2.1 - Структура БД. Разработка интерфейса для работы с БД В проект в первую...
-
2.1 Описание структуры базы данных Реляционная схема базы данных для ЦЗН представлена следующими таблицами: "ПО" - содержит список единиц программного...
-
Постановка задачи на разработку программного обеспечения Для того чтобы предлагаемая схема была интегрирована в САПР, который не имеет функции интеграции...
-
Цель Работы - изучить основные способы работы с пользовательским типом данных "класс", его объектами, методами и способы доступа к ним. - Теоретические...
-
Выбор средств реализации информационной системы Названные в параграфе 1.4. настоящей работы задачи могут быть решены тремя типами средств автоматизации:...
-
ER - диаграмма базы данных была представлена на рис. 2. Рис.2. ER-диаграмма базы данных. Таблица admin - содержит два столбца login и password которые...
-
Гражданский кодекс Российской Федерации в части четвертой регулирует вопросы охраны результатов интеллектуальной деятельности и средств индивидуализации....
-
Постановление Правительства Российской Федерации №1119 "Об утверждении требований к защите персональных данных при их обработке в информационных системах...
-
Первым шагом при начале работе над учебным проектом является определение ролей участников данного проекта. Данный этап является одним из наиболее важных,...
-
Данная глава посвящена решению таких задач, как выявление теоретических основ тестирования, классификация и описание видов тестирования, анализ и...
-
Для того, чтобы строить диаграммы в соответствии с рисунком 2.7, необходимо реализовать алгоритм соединения двух объектов линией. Для отображения линии...
-
Считывание сложноструктурированных данных При разработке программного обеспечения был выбрано построковое считывание данных, ввиду использования...
-
Функциональные требования: - Поиск и обработка информации в текстовых файлах при появлении файлов в соответствующей директории по запросу администратора...
-
Версионность базы данных - Программное обеспечение для пропускной системы на основе технологии NFC
С ростом приложения существует проблема обновления схемы базы данных с сохранением внесенных данных. Если информация в базе данных не может быть легко...
-
Для написания АИС использовались следующие языки программирования, программные средства и библиотеки: - Язык программирования PHP 5.4; -...
-
Программный интерфейс для базы данных я разрабатывал в объектно-ориентрованной среде Delphi, с помощью Embarcadero RAD Studio. Конструктор форм Delphi в...
-
Предлагаемая библиотека хранит все данные в отдельных таблицах, таким образом он не обязан использовать ту же СУБД, что и основное приложение. В качестве...
Понятие транзакций и проблема их кластеризации - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата