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

Большая Энциклопедия Нефти и Газа

Множество пользователей AutoCAD держат свои базы данных отдельно от чертежей и, надо сказать, поступают совершенно правильно, так как в настоящее время можно, например, непосредственно работать с данными, связав строку из таблицы базы данных с объектом чертежа. Такие объекты достаточно разумны, они в состоянии поддерживать постоянную связь с данными, оперативно реагировать на вносимые непосредственно из AutoCAD изменения: будь то цена или номер детали. Внесенные изменения немедленно отразятся на всех других объектах чертежа, связанных с данными. Можно, наконец, пометить все связанные объекты чертежа текстовыми ярлыками, содержимое которых соответствует данным из базы. [2]

Множество пользователей вычислительной сети , выделенных в отдельную группу, которым предоставлена возможность обмениваться сообщениями друг с другом, но исключен обмен сообщениями со всеми другими пользователями. [3]

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

Вычислительный центр, обслуживающий множество пользователей и организаций как в пакетном, так и в интерактивном режимах. [5]

Многопользовательская операционная система обслуживает некоторое множество пользователей , зарегистрированных в соответствующем учетном файле — учетном файле пользователей. Первичной характеристикой пользователя служит его имя. [6]

Анализ выделенных классов позволяет определить множество пользователей РБД , для которых целесообразно проведение работ по типизации структуры баз данных по критерию их информационной общности. [7]

Пусть R гк, к 1 К0 — множество пользователей РБД , которые распределены по географически удаленным узлам вычислительной сети ( ВС); Dk dk, i 15 Ik — множество информационных элементов, описывающих предметную область k — го пользователя. [8]

Главная функция любой СУБД — координация совместной работы множества пользователей с разделяемый информацией. [9]

При разработке типовых систем проектирование осуществляется одним или несколькими разработчиками для множества пользователей в соответствии с их требованиями. В качестве подсистем нижнего уровня ( элементов) рассматриваются заказчики ( пользователи) типовой СОД, которые могут вести по решению центра проектирование и отладку ее определенной части и в дальнейшем осуществляют эксплуатацию системы в целом. [10]

Функциями среды выполнения называются функции, поддерживающие совместное использование аппаратных ресурсов множеством пользователей . Одновременное функционирование нескольких программ обеспечивается главным образом двумя механизмами: механизмом переключения процессора ( процессоров) с программы на программу и механизмом координации использования ресурсов конкурирующими программами пользователей. Соответственно нижний функциональный уровень оцерационной системы включает механизмы диспетчирования и временного запрещения доступа, или замков. [11]

Клждая база ориентирована к а определенный класс применений, н с ней взаимодействует опредс-ленное множество пользователей . Каждый пользователь должен иметь возможность работать только с определенной и известной ему частью базы данных. Логическая и физическая организация базы дачных неизбежно будет меняться в процессе развития БД и оптимизации работы с ним Однако пользователь должен продолжать видеть свое подмножество базы данных таким же, как и до реорганизации, а РГО прогпэммьт ПРН этом не должны изменяться. С другой стороны, изменение прикладных программ, ведущих обработку базы данных, не должно приводить к обязательной реорганизации самой базы. Этот принцип называется независимостью данных от программ. [12]

Каждая созданная база ориентирована на определенный класс применений, и с ней взаимодействует некоторое множество пользователей . Каждый пользователь или коллектив пользователей должен иметь возможность работать только с определенной и известной ему частью базы данных. При развитии базы данных, ее приложений и общей оптимизации работы с ней логическая и физическая ее организации неизбежно будут меняться. Однако пользователь должен продолжать видеть свое подмножество базы таким же, как и до реорганизации, причем нет необходимости менять для этого его программы. В свою очередь, изменение прикладных программ, ведущих обработку базы данных, не должно приводить к обязательной реорганизации самой базы. [13]

На первом этапе предпроектного анализа проводится разбиение пользователей на два класса в соответствии со степенью общности их предметных областей и определяется множество пользователей , для которых целесообразно проектирование РБД. Целесообразность определяется наличием заданной степени общности между предметными областями рассматриваемого множества пользователей. [15]

Защита информации / Лабораторные работы(задание) / Лабораторная_работа_№2

Запустить программы просмотра и редактирования реестра Windows regedit.exe и regedt32.exe (с помощью команды «Выполнить» главного меню). Ознакомиться со структурой реестра, включить в отчет краткие сведения о содержании основных разделов реестра (HKEY_CURRENT_USER и HKEY_LOCAL_MACHINE). Включить в отчет сведения о различиях в функциональных возможностях изученных программ редактирования реестра. Включить в электронную версию отчета копии экранных форм, иллюстрирующих использование редакторов реестра.

Примечание: в операционную систему Windows XP Professional включен один редактор реестра, который можно запустить с помощью любого из указанных выше имен.

Скопировать в произвольную папку на диске рабочей станции файл rt.zip из указанного преподавателем сетевого диска.

Извлечь файлы из скопированного в пункте 2 архива.

Запустить программу restrick.exe, позволяющую ограничить возможности пользователей ОС Windows. Включить в отчет сведения о назначении и основных функциях программы. С помощью редактора реестра найти и отразить в отчете разделы реестра Windows, хранящие информацию о выбранной политике безопасности. Включить в отчет ответ на вопрос, какое ограничение на работу пользователя должно быть обязательно установлено, чтобы обеспечить минимальную эффективность рассмотренных и аналогичных средств. Включить в электронную версию отчета копии экранных форм, используемых при работе с программой restrick.exe. Завершить работу с программой restrick.exe.

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

Открыть (или создать) произвольный документ в текстовом процессоре Word. Изучить порядок использования паролей для защиты документов в Microsoft Word и включить в отчет соответствующие сведения. Включить в электронную версию отчета копии экранных форм, использованных при выполнении данного пункта. Завершить работу с Word.

Открыть (или создать) произвольную таблицу Excel. Изучить порядок использования паролей для защиты документов в табличном процессоре Microsoft Excel и включить в отчет соответствующие сведения. Включить в электронную версию отчета копии экранных форм, использованных при выполнении данного пункта. Завершить работу с Excel.

Скопировать в произвольную папку на локальном жестком диске файл whisper.zip из указанного преподавателем сетевого диска.

Запустить программу Setup для установки программы Whisper 32 (непосредственно из архива, скопированного в пункте 8, без его распаковки).

Запустить программу whisper.exe, предназначенную для создания и ведения базы данных паролей пользователя. Изучить назначение и основные функции программы и включить в отчет соответствующие сведения. Включить в электронную версию отчета копии экранных форм, использованных при выполнении данного пункта. Завершить работу с программой whisper.exe.

Ознакомиться (на примере папок, созданных в папке c:\ Documents and Settings \ Имя пользователя \ Документы и в папке c:\ Documents and Settings \ All Users \ Документы) с порядком разграничения доступа к ресурсам в защищенных версиях операционной системы Windows (с помощью контекстного меню объекта и элементов управления соответствующих диалоговых окон). Если команда «Общий доступ и безопасность» недоступна (при работе в ОС Windows XP Professional), то выключить режим «Использовать простой общий доступ к файлам» на вкладке «Вид» окна свойств папки. Включить в отчет сведения об особенностях управления доступом к папкам и файлам в этих ОС. Включить в электронную версию отчета копии экранных форм, использованных при выполнении данного пункта.

Ознакомиться (с помощью Панели управления Windows и редактора реестра) с порядком разграничения доступа к принтерам и разделам реестра. Включить в электронную версию отчета копии экранных форм, использованных при выполнении данного пункта.

Ознакомиться (с помощью функции Панели управления Администрирование | Управление компьютером) с порядком создания и изменения учетных записей пользователей и групп в защищенных версиях операционной системы Windows. Включить в отчет соответствующие сведения. Включить в электронную версию отчета копии соответствующих экранных форм.

Ознакомиться (с помощью функции Панели управления Администрирование | Локальная политика безопасности | Локальные политики | Назначение прав пользователя) с порядком назначения прав пользователям и группам. Включить в отчет соответствующие сведения. Включить в электронную версию отчета копии соответствующих экранных форм.

Ознакомиться (с помощью функции Панели управления Администрирование | Локальная политика безопасности | Политики учетных записей | Политика паролей) с порядком определения параметров безопасности для парольной аутентификации. Включить в отчет соответствующие сведения. Включить в электронную версию отчета копии соответствующих экранных форм.

Ознакомиться (с помощью функции Панели управления Администрирование | Локальная политика безопасности | Политики учетных записей | Политика блокировки учетных записей) с порядком определения параметров безопасности для политики блокировки учетных записей. Включить в отчет соответствующие сведения. Включить в электронную версию отчета копии соответствующих экранных форм.

Включить в отчет ответы на контрольные вопросы, номера которых выбираются в соответствии с номером варианта.

Включить в отчет титульный лист и сохранить файл с электронной версией отчета в произвольной папке на локальном жестком диске.

После проверки отчета преподавателем удалить файл с электронной версией отчета и файл программы Restrick, удалить программу Whisper 32 с помощью Панели управления Windows, удалить файлы архивов rt.zip и whisper.zip.

Завершить работу с ОС Windows.

Контрольные вопросы

Какой из изученных в лабораторной работе редакторов реестра предоставляет функции по разграничению доступа к разделам реестра и как использовать эти функции?

Полномочия какого из пользователей ограничиваются с помощью программы restrick.exe?

В чем разница между функциями программы restrick.exe «Restrict “Run program” window» и «Restrict “Run” command»?

Как с помощью программы restrick.exe ограничить доступ пользователей к дисковым устройствам?

Как ограничить доступ пользователей к функциям Панели управления с помощью программы restrick.exe?

Доступ к каким функциям Панели управления может быть ограничен с помощью программы restrick.exe?

В чем недостаточность средств ограничения прав пользователей, предоставляемых программой restrick.exe?

Как может быть заблокирована рабочая станция на период временного отсутствия пользователя? Укажите несколько вариантов.

Какой из способов блокирования рабочей станции на период временного отсутствия пользователя является наиболее безопасным и почему?

Как устанавливается защита от чтения документов Microsoft Word и таблиц Microsoft Excel?

Как реализована (в чем выражается) защита документов Microsoft Office от чтения с помощью паролей?

Насколько надежна защита документов Microsoft Office от чтения с помощью паролей?

Как устанавливается защита от изменения документов Microsoft Word и таблиц Microsoft Excel?

Как реализована (в чем выражается) защита документов Microsoft Office от изменения с помощью паролей?

Насколько надежна защита документов Microsoft Office от изменения с помощью паролей?

Как создать новую базу данных паролей с помощью программы whisper.exe и защитить ее от несанкционированного доступа?

Как реализована (в чем выражается) защита базы данных паролей программы whisper.exe?

Как добавить новый пароль в базу данных программы whisper.exe?

Какая информация указывается при добавлении новой записи в базу данных программы whisper.exe?

Для чего в программе whisper.exe предназначена функция Generate?

Для чего предназначены элементы управления в окне автоматической генерации паролей программы whisper.exe?

Как скрыть отображаемые на экране пароли из базы данных программы whisper.exe, но при этом сохранить возможность их переноса в требуемую программу?

Какие права доступа к личным и разделяемым файлам и папкам устанавливаются операционной системой по умолчанию?

Кто может управлять разрешениями на доступ к ресурсу?

Какая информация содержится в дескрипторе безопасности объекта?

Какая модель разграничения доступа к объектам реализована в защищенных версиях операционной системы Windows?

В чем основные недостатки модели разграничения доступа к объектам, реализованной в защищенных версиях операционной системы Windows?

Какие специфические права доступа могут быть определены для принтера?

Какие специфические права доступа могут быть определены для раздела реестра?

Какие разрешения на доступ к принтеру установлены в системе и почему?

Какие установлены разрешения на доступ к разделу реестра HKEY_LOCAL_MACHINE и почему?

Какие установлены разрешения на доступ к разделам реестра HKEY_CURRENT_USER и HKEY_CURRENT_USER \ Software \ Microsoft \ Windows \ CurrentVersion \ Policies и почему?

Кто управляет разрешениями на доступ к принтерам и почему?

Кто управляет разрешениями на доступ к разделам реестра и почему?

Какие из объектов могут наследовать разрешения на доступ к ним и от кого?

Для чего предназначены параметры создаваемой учетной записи пользователя?

В чем разница между отключением и блокировкой учетной записи?

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

Как назначаются права пользователям и группам в защищенных версиях операционной системы Windows?

Какие требования по сложности могут предъявляться к паролям в операционной системе Windows?

Для чего предназначены параметры парольной аутентификации, связанные с установкой минимального срока действия и неповторяемости паролей?

Какие параметры могут быть установлены для политики блокировки учетных записей?

Для чего предназначены параметры политики блокировки учетных записей?

В чем слабость парольной аутентификации?

Как может быть повышена надежность аутентификации с помощью паролей?

Какой может быть реакция системы на попытку подбора паролей?

Кому может быть разрешен доступ по чтению ко всей базе учетных записей пользователей и почему?

Кому может быть разрешен доступ по записи к базе учетных записей пользователей и почему?

Введение

Цель работы: Освоение методов оптимизации кольцевой топологии и топологии типа общая шина-звезда.

1. Согласно варианту задания, используя описанный метод, определить оптимальную топологию сети типа общая шина-звезда, с 4 концентраторами.

2. Согласно варианту задания, используя описанный метод, определить оптимальную кольцевую топологию сети.

Координаты рабочих станций заданы в таблице:

Разбиение множества рабочих станций на 4 группы

Разбиваем множество рабочих станций сначала на 2 группы, затем для каждой пары узлов решаем, входит ли узел в данную группу, по критерию наибольшей близости к «центру тяжести» группы. Координаты «центра тяжести» ищем на каждом шаге как среднее арифметическое координат точек, вошедших в данную группу.

После разбиения на группы и начального расположения концентраторов в «центрах тяжести» групп получим:

Здесь начальное положение концентраторов обозначено цветными фигурами:

Обозначения рабочих станций:

— номер рабочей станции (в соответствии с таблицей-заданием).

Существует альтернатива объединить в группу 4,5 и 7 рабочие станции и подключить их к первому концентратору (q₁). Это снизит нагрузку на четвертый концентратор q₄ (к нему будут подключены 2 рабочие станции вместо 3-х), но увеличит протяженность каналов связи, длину которых мы должны минимизировать в данной задаче.

Ищем оптимальное положение I концентратора.

I X₀ = 1/3 (10+15+15) = 13.3 Y₀ = 1/3 (5+10+15) = 10

F = (x-10) + (y-5) + (x-15) + (y-10) + (x-15) + (y-15) + (x-20) + (y-10) F (13.3;

10) = (13.3-10) + (10-5) + (13.3-15) + (10-10) + (13.3-15) + (10-15) = 4.9

2. 10) = (14-10) + (10-5) + (14-15) + (10-10) + (14-15) + (10-15) = 2

4. 10) = (16-10) + (10-5) + (16-15) + (10-10) + (16-15) + (10-15) = 8

6. 9) = (15-10) + (9-5) + (15-15) + (9-10) + (15-15) + (9-15) = 3

8. 11) = (15-10) + (11-5) + (15-15) + (11-10) + (15-15) + (11-15) = 8

Ищем оптимальное положение II концентратора.

II X₀ = 1/4 (25+30+40+40) = 33.75 Y₀ = 1/4 (10+15+15+20) = 15

F = (x-25) + (y-15) + (x-30) + (y-10) + (x-40) + (y-15) + (x-40) + (y-20) F (33.75; 15) = (33.75-25) + (15-15) + (33.75-30) + (15-10) + (33.75-40) + (15-15) + (33.75-40) + (15-20) = 0

Ищем оптимальное положение III концентратора.

III X₀ = 1/3 (20+25+30) = 25 Y₀ = 1/3 (25+30+30) = 28.3

F = (x-20) + (y-30) + (x-25) + (y-30) + (x-30) + (y-25) F (25; 28.3) = (25-20) + (28.3-30) + (25-25) + (28.3-30) + (25-30) + (28.3-25) = — 0.1

1. F (25; 28.4) = (25-20) + (28.4-30) + (25-25) + (28.4-30) + (25-30) + (28.4-25) = 0.2

2. F (25.1; 28.3) = (25.1-20) + (28.3-30) + (25.1-25) + (28.3-30) + (25.1-30) + (28.3-25) = 0.2

С учетом полученного оптимального расположения концентраторов схема топологии сети изменится следующим образом:

Обзор алгоритмов кластеризации данных

В своей дипломной работе я проводил обзор и сравнительный анализ алгоритмов кластеризации данных. Подумал, что уже собранный и проработанный материал может оказаться кому-то интересен и полезен.
О том, что такое кластеризация, рассказал sashaeve в статье «Кластеризация: алгоритмы k-means и c-means». Я частично повторю слова Александра, частично дополню. Также в конце этой статьи интересующиеся могут почитать материалы по ссылкам в списке литературы.

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

Понятие кластеризации

Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны. Главное отличие кластеризации от классификации состоит в том, что перечень групп четко не задан и определяется в процессе работы алгоритма.

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

Меры расстояний

Итак, как же определять «похожесть» объектов? Для начала нужно составить вектор характеристик для каждого объекта — как правило, это набор числовых значений, например, рост-вес человека. Однако существуют также алгоритмы, работающие с качественными (т.н. категорийными) характеристиками.

После того, как мы определили вектор характеристик, можно провести нормализацию, чтобы все компоненты давали одинаковый вклад при расчете «расстояния». В процессе нормализации все значения приводятся к некоторому диапазону, например, [-1, -1] или [0, 1].

Евклидово расстояние
Наиболее распространенная функция расстояния. Представляет собой геометрическим расстоянием в многомерном пространстве:
Квадрат евклидова расстояния
Применяется для придания большего веса более отдаленным друг от друга объектам. Это расстояние вычисляется следующим образом:
Расстояние городских кварталов (манхэттенское расстояние)
Это расстояние является средним разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако для этой меры влияние отдельных больших разностей (выбросов) уменьшается (т.к. они не возводятся в квадрат). Формула для расчета манхэттенского расстояния:
Расстояние Чебышева
Это расстояние может оказаться полезным, когда нужно определить два объекта как «различные», если они различаются по какой-либо одной координате. Расстояние Чебышева вычисляется по формуле:
Степенное расстояние
Применяется в случае, когда необходимо увеличить или уменьшить вес, относящийся к размерности, для которой соответствующие объекты сильно отличаются. Степенное расстояние вычисляется по следующей формуле:
,
где r и p – параметры, определяемые пользователем. Параметр p ответственен за постепенное взвешивание разностей по отдельным координатам, параметр r ответственен за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра – r и p — равны двум, то это расстояние совпадает с расстоянием Евклида.

Классификация алгоритмов

Иерархические и плоские.
Иерархические алгоритмы (также называемые алгоритмами таксономии) строят не одно разбиение выборки на непересекающиеся кластеры, а систему вложенных разбиений. Т.о. на выходе мы получаем дерево кластеров, корнем которого является вся выборка, а листьями — наиболее мелкие кластера.
Плоские алгоритмы строят одно разбиение объектов на кластеры.
Четкие и нечеткие.
Четкие (или непересекающиеся) алгоритмы каждому объекту выборки ставят в соответствие номер кластера, т.е. каждый объект принадлежит только одному кластеру. Нечеткие (или пересекающиеся) алгоритмы каждому объекту ставят в соответствие набор вещественных значений, показывающих степень отношения объекта к кластерам. Т.е. каждый объект относится к каждому кластеру с некоторой вероятностью.

Объединение кластеров

Одиночная связь (расстояния ближайшего соседа)
В этом методе расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Результирующие кластеры имеют тенденцию объединяться в цепочки.
Полная связь (расстояние наиболее удаленных соседей)
В этом методе расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. наиболее удаленными соседями). Этот метод обычно работает очень хорошо, когда объекты происходят из отдельных групп. Если же кластеры имеют удлиненную форму или их естественный тип является «цепочечным», то этот метод непригоден.
Невзвешенное попарное среднее
В этом методе расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них. Метод эффективен, когда объекты формируют различные группы, однако он работает одинаково хорошо и в случаях протяженных («цепочечного» типа) кластеров.
Взвешенное попарное среднее
Метод идентичен методу невзвешенного попарного среднего, за исключением того, что при вычислениях размер соответствующих кластеров (т.е. число объектов, содержащихся в них) используется в качестве весового коэффициента. Поэтому данный метод должен быть использован, когда предполагаются неравные размеры кластеров.
Невзвешенный центроидный метод
В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.
Взвешенный центроидный метод (медиана)
Этот метод идентичен предыдущему, за исключением того, что при вычислениях используются веса для учета разницы между размерами кластеров. Поэтому, если имеются или подозреваются значительные отличия в размерах кластеров, этот метод оказывается предпочтительнее предыдущего.

Обзор алгоритмов

Алгоритмы иерархической кластеризации

Среди алгоритмов иерархической кластеризации выделяются два основных типа: восходящие и нисходящие алгоритмы. Нисходящие алгоритмы работают по принципу «сверху-вниз»: в начале все объекты помещаются в один кластер, который затем разбивается на все более мелкие кластеры. Более распространены восходящие алгоритмы, которые в начале работы помещают каждый объект в отдельный кластер, а затем объединяют кластеры во все более крупные, пока все объекты выборки не будут содержаться в одном кластере. Таким образом строится система вложенных разбиений. Результаты таких алгоритмов обычно представляют в виде дерева – дендрограммы. Классический пример такого дерева – классификация животных и растений.

Для вычисления расстояний между кластерами чаще все пользуются двумя расстояниями: одиночной связью или полной связью (см. обзор мер расстояний между кластерами).

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

Алгоритмы квадратичной ошибки

Задачу кластеризации можно рассматривать как построение оптимального разбиения объектов на группы. При этом оптимальность может быть определена как требование минимизации среднеквадратической ошибки разбиения:

где c_j — «центр масс» кластера j (точка со средними значениями характеристик для данного кластера).

Случайно выбрать k точек, являющихся начальными «центрами масс» кластеров.
Отнести каждый объект к кластеру с ближайшим «центром масс».
Пересчитать «центры масс» кластеров согласно их текущему составу.
Если критерий остановки алгоритма не удовлетворен, вернуться к п. 2.

К недостаткам данного алгоритма можно отнести необходимость задавать количество кластеров для разбиения.

Нечеткие алгоритмы

Выбрать начальное нечеткое разбиение n объектов на k кластеров путем выбора матрицы принадлежности U размера n x k.
Используя матрицу U, найти значение критерия нечеткой ошибки:
,
где c_k — «центр масс» нечеткого кластера k:
.
Перегруппировать объекты с целью уменьшения этого значения критерия нечеткой ошибки.
Возвращаться в п. 2 до тех пор, пока изменения матрицы U не станут незначительными.

Алгоритмы, основанные на теории графов

Суть таких алгоритмов заключается в том, что выборка объектов представляется в виде графа G=(V, E), вершинам которого соответствуют объекты, а ребра имеют вес, равный «расстоянию» между объектами. Достоинством графовых алгоритмов кластеризации являются наглядность, относительная простота реализации и возможность вносения различных усовершенствований, основанные на геометрических соображениях. Основными алгоритмам являются алгоритм выделения связных компонент, алгоритм построения минимального покрывающего (остовного) дерева и алгоритм послойной кластеризации.

Алгоритм выделения связных компонент

В алгоритме выделения связных компонент задается входной параметр R и в графе удаляются все ребра, для которых «расстояния» больше R. Соединенными остаются только наиболее близкие пары объектов. Смысл алгоритма заключается в том, чтобы подобрать такое значение R, лежащее в диапазон всех «расстояний», при котором граф «развалится» на несколько связных компонент. Полученные компоненты и есть кластеры.

Для подбора параметра R обычно строится гистограмма распределений попарных расстояний. В задачах с хорошо выраженной кластерной структурой данных на гистограмме будет два пика – один соответствует внутрикластерным расстояниям, второй – межкластерным расстояния. Параметр R подбирается из зоны минимума между этими пиками. При этом управлять количеством кластеров при помощи порога расстояния довольно затруднительно.

Алгоритм минимального покрывающего дерева

Алгоритм минимального покрывающего дерева сначала строит на графе минимальное покрывающее дерево, а затем последовательно удаляет ребра с наибольшим весом. На рисунке изображено минимальное покрывающее дерево, полученное для девяти объектов.

Путём удаления связи, помеченной CD, с длиной равной 6 единицам (ребро с максимальным расстоянием), получаем два кластера: и . Второй кластер в дальнейшем может быть разделён ещё на два кластера путём удаления ребра EF, которое имеет длину, равную 4,5 единицам.

Послойная кластеризация

Алгоритм послойной кластеризации основан на выделении связных компонент графа на некотором уровне расстояний между объектами (вершинами). Уровень расстояния задается порогом расстояния c. Например, если расстояние между объектами , то .

Алгоритм послойной кластеризации формирует последовательность подграфов графа G, которые отражают иерархические связи между кластерами:

где G t = (V, E t ) — граф на уровне с t ,
,
с t – t-ый порог расстояния,
m – количество уровней иерархии,
G 0 = (V, o), o – пустое множество ребер графа, получаемое при t 0 = 1,
G m = G, то есть граф объектов без ограничений на расстояние (длину ребер графа), поскольку t m = 1.

Посредством изменения порогов расстояния <с 0 , …, с m >, где 0 = с 0 < с 1 < …< с m = 1, возможно контролировать глубину иерархии получаемых кластеров. Таким образом, алгоритм послойной кластеризации способен создавать как плоское разбиение данных, так и иерархическое.

Сравнение алгоритмов

Вычислительная сложность алгоритмов

Алгоритм кластеризации	Вычислительная сложность
Иерархический	O(n 2 )
k-средних	O(nkl), где k – число кластеров, l – число итераций
c-средних	O(nkl), где k – число кластеров, l – число итераций
Выделение связных компонент	зависит от алгоритма
Минимальное покрывающее дерево	O(n 2 log n)
Послойная кластеризация	O(max(n, m)), где m < n(n-1)/2

Сравнительная таблица алгоритмов

Алгоритм кластеризации	Форма кластеров	Входные данные	Результаты
Иерархический	Произвольная	Число кластеров или порог расстояния для усечения иерархии	Бинарное дерево кластеров
k-средних	Гиперсфера	Число кластеров	Центры кластеров
c-средних	Гиперсфера	Число кластеров, степень нечеткости	Центры кластеров, матрица принадлежности
Выделение связных компонент	Произвольная	Порог расстояния R	Древовидная структура кластеров
Минимальное покрывающее дерево	Произвольная	Число кластеров или порог расстояния для удаления ребер	Древовидная структура кластеров
Послойная кластеризация	Произвольная	Последовательность порогов расстояния	Древовидная структура кластеров с разными уровнями иерархии

Немного о применении

В своей работе мне нужно было из иерархических структур (деревьев) выделять отдельные области. Т.е. по сути необходимо было разрезать исходное дерево на несколько более мелких деревьев. Поскольку ориентированное дерево – это частный случай графа, то естественным образом подходят алгоритмы, основанными на теории графов.

В отличие от полносвязного графа, в ориентированном дереве не все вершины соединены ребрами, при этом общее количество ребер равно n–1, где n – число вершин. Т.е. применительно к узлам дерева, работа алгоритма выделения связных компонент упростится, поскольку удаление любого количества ребер «развалит» дерево на связные компоненты (отдельные деревья). Алгоритм минимального покрывающего дерева в данном случае будет совпадать с алгоритмом выделения связных компонент – путем удаления самых длинных ребер исходное дерево разбивается на несколько деревьев. При этом очевидно, что фаза построения самого минимального покрывающего дерева пропускается.

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

Отдельно хочу сказать, что для достижения наилучшего результата необходимо экспериментировать с выбором мер расстояний, а иногда даже менять алгоритм. Никакого единого решения не существует.