Обобщенный алгоритм кластеризации - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата
Коллекция транзакций хранится в файле на диске. Алгоритм читает каждую транзакцию t последовательно и присоединяет t к существующему кластеру, или создает t как новый кластер, тот который минимизирует стоимость для текущей кластеризации. Идентификатор кластера каждой транзакции записывается обратно в файл. Это называется фазой размещения. В фазе усовершенствования алгоритм читает каждую транзакцию t (в том же порядке как в фазе размещения), перемещает t в существующий не одиночный кластер (возможно, оставляет там, где она есть), чтобы минимизировать Cost(C). После каждого перемещения идентификатор кластера у транзакции обновляется, и любой пустой кластер немедленно уничтожается. Если ни одна транзакция не перемещается при проходе по всем транзакциям, фаза усовершенствования оканчивается. В противном случае начинается новый проход. Существенно, что при добавлении каждой транзакции минимизируется глобальный критерий стоимости Cost(C). Ключевым шагом является нахождение адреса кластера для размещения или перемещения транзакции. Этот вопрос обсуждается ниже.
Парадигма следования фазы усовершенствования за фазой размещения заимствована из алгоритмов k-средних и k-мод. Однако в предлагаемом алгоритме имеются важные отличия. Во-первых, не требуется предварительно определять число k кластеров. Вместо этого кластеры создаются и уничтожаются динамически на основе критерия стоимости. Во-вторых, адрес кластера транзакции определяется не по расстоянию до ближайшего кластера или до его моды/центроида, а путем расчета стоимости Cost(C), являющейся не локальным, а глобальным критерием качества.
/* Фаза размещения транзакций */
- 1. while not end of the file do 2. read the next transaction < t, -- >; 3. allocation t to an existing or new cluster Ci to minimize Cost(C); 4. write ;
/* Фаза улучшения кластеризации */
- 5. repeat 6. not_moved = true; 7. while not end of the file do 8. read the next transaction < t, ci > ; 9. move t to an existing non-singleton cluster Cj to minimize Cost(C); 10. if Ci ? Cj then 11. write < t, cj >; 12. not_moved = false; 13. eliminate any empty cluster; 14. until not_moved;
Рис. 5 Обобщенный алгоритм кластеризации
Похожие статьи
-
Термин "транзакция" относится к подмножеству предметов из общей совокупности с переменным числом предметов (мощностью подмножества). Транзакциями...
-
Кластеризация (или кластерный анализ) -- это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться...
-
Вычислительная сложность алгоритмов Алгоритм кластеризации Вычислительная сложность Иерархический O(n2) K-средних O(nkl), где k - число кластеров, l -...
-
Понятие Data Mining Средства Data Mining включают в себя очень широкий класс различных технологий и инструментов. Средства Data Mining на рынке...
-
Подход, основанный на "больших" предметах и функциональный критерий кластеризации Поддержка предмета в кластере Ci есть относительное число транзакций в...
-
В наше время все большее количество компаний, стремясь к повышению эффективности и прибыльности бизнеса пользуются цифровыми (автоматизированными)...
-
Выбор программного обеспечения для внедрения KPI целиком и полностью упирается в потребности конкретной компании. Благодаря все большей и большей...
-
Преимущества, которые дает тестировщику автоматизация тестирования: - Исключен "человеческий фактор". Существует некоторая гарантия того, что не один...
-
Общее описание программного обеспечения, реализующего разработанный алгоритм Основной идеей дипломного проекта, является реализация алгоритма...
-
В настоящее время биометрия входит в состав наиболее распространенных технологий и средств защиты информации. Отпечатки пальцев являются самой широко...
-
Расчет затрат, связанных с организацией рабочих мест для исполнителей проекта, проводится на основе требований СНИПа (санитарные нормы и правила) и...
-
Автоматизированное тестирование программного обеспечения - это процесс проверки программного обеспечения, который включает в себя такие шаги как запуск,...
-
В то время как цель проекта заключалась в оценке эффективности автоматизации тестирования функционала ядра, работа стала своего рода подведением итогов...
-
Для того, чтобы вынести решение об оправданности или неоправданности внедрения автоматизированного тестирования вместо ручного, необходимо...
-
В течении года от команды разработчиков пришло 6 пакетов, содержащих изменения в ядре программы. Для каждого пакета составлялось в среднем от 1-ого до...
-
Для того чтобы выполнить автоматическое тестирование с использованием Cucumber, прежде всего необходимо иметь представление о структуре инструмента и...
-
Тестируемый программный продукт является высокопроизводительным приложением, которое предоставляет возможность создания и настройки сетей беспроводного...
-
Компания MERA Networks - является одним из крупнейших мировых поставщиков услуг в сфере информационно-коммуникационных технологий. MERA предлагает...
-
Поскольку клиентская часть представляет собой приложение на базе операционной системы Android, то для ее разработки был выбран рекомендуемый...
-
Для оценки возможности выполнения проекта имеющимся в распоряжении разработчика штатным составом исполнителей, нужно рассчитать их среднее количество,...
-
Приложение, которое необходимо разработать, должно производить геометрическую реконструкцию сцены и вычисление цвета вершин модели. Для геометрической...
-
При работе над проектом разрабатывались два основных компонента системы: база данных (далее - БД) и интерфейс клиентского приложения. Затем необходимо...
-
При запуске программы с входными параметрами {"-makexls" "filename. xls" "температурная_точка" "отклонение" "элемент"} происходит извлечение результатов...
-
Разработаем алгоритм одного из основных методов, используемого в данной программе. Private void pictureBox1_MouseDown(objects sender, MouseEventArgs e)...
-
Для вычисления цвета могут быть использованы различные подходы. Вычисление цвета может проводиться одновременно с геометрической реконструкцией,...
-
При перезагрузке Raspbery счетчик counter сбрасывается и файлы начинают перезаписываться. Для того, чтобы обойти данную проблему воспользуемся переносом...
-
Версионность базы данных - Программное обеспечение для пропускной системы на основе технологии NFC
С ростом приложения существует проблема обновления схемы базы данных с сохранением внесенных данных. Если информация в базе данных не может быть легко...
-
Работа программы представлена на рисунке 2.3 Рис. 2.3 Кодирование и тестирование программы Программа кодировалась на языке Си++, используя библотеку Qt5x...
-
Постановка задачи на разработку программного обеспечения Для того чтобы предлагаемая схема была интегрирована в САПР, который не имеет функции интеграции...
-
Считывание сложноструктурированных данных При разработке программного обеспечения был выбрано построковое считывание данных, ввиду использования...
-
Для реализации поставленной задачи методом конечных элементов будут использованы следующие программные обеспечения (ПО): - MATLAB - ПО и одноименный язык...
-
Выбор средств реализации информационной системы Названные в параграфе 1.4. настоящей работы задачи могут быть решены тремя типами средств автоматизации:...
-
Для осуществления первой задачи данной работы был проведен проведение подробный анализ семи наиболее распространенных технологий работы с Большими...
-
Для того, чтобы строить диаграммы в соответствии с рисунком 2.7, необходимо реализовать алгоритм соединения двух объектов линией. Для отображения линии...
-
После обмена данными с АЦП происходит преобразование считанных данных в одно целое число, характеризующее уровень сигнала на входе АЦП. Т. к. АЦП имеет...
-
Цель Работы - изучить основные способы работы с пользовательским типом данных "класс", его объектами, методами и способы доступа к ним. - Теоретические...
-
Цель Работы - научиться использовать операции динамического выделения и освобождения памяти на примере работы с одномерными и двумерными массивами, а...
-
2.1 Описание структуры базы данных Реляционная схема базы данных для ЦЗН представлена следующими таблицами: "ПО" - содержит список единиц программного...
-
1. НА 7 ПК ИСПОЛЬЗУЕТСЯ microsoft Windows xp sp2. 2. на 1 используется Altlinux 5 3. Программы офисного назначения: A) Microsoft Office Excel 2003 B)...
-
После преобразования аналогового сигнала в цифровую форму с помощью АЦП возникает необходимость в программной обработке полученного цифрового сигнала....
Обобщенный алгоритм кластеризации - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата