Что такое кластер в программировании
Перейти к содержимому

Что такое кластер в программировании

  • автор:

Кластеры. Функции работы с кластерами.

Кроме массивов, в LabVIEW есть кластеры. От массивов они отличаются тем, что кластер — это объединение элементов разных типов (как пучок проводов в телефонном кабеле). Аналогом кластеров в обычных текстовых языках программирования служат структуры. Кластеры удобно использовать для уменьшения количества связей на диаграмме. Или для уменьшения количества терминалов у SubVI. Максимальное количество терминалов, которые можно привязать к элементам передней панели SubVI равно 28. Поэтому, если число индикаторов и регуляторов превышает это значение, то не остается ничего другого, как объединить часть элементов в кластер. Чтобы объединить несколько индикаторов или регуляторов в кластер, нужно выбрать в панели Controls>>All Controls>>Array & Cluster инструмент cluster, поместить его на лицевую панель, и затем внутрь рамки поместить нужные индикаторы/регуляторы.

Так же можно сделать кластерную константу (для этого из палитры Cluster выбрать cluster constant и поместить на блок-схему, потом перетащить внутрь нужные элементы). Если нужна константа с теми же элементами, что и на передней панели — то щелкаем на ней правой кнопкой мыши и выбираем «Create>>Constant». Кстати, это работает не только с кластерами.

Порядковые номера элементов кластера.

Элементы кластера имеют порядковый номер, связанные с их позицией внутри оболочки кластера. Первый объект, помещенный внутрь кластера имеет номер 1, второй — 2 и так далее. При удалении/добавлении элементов происходит автоматическая смена номеров. Порядок элементов определяет то, в какой последовательности будут идти выходы для этих элементов в функциях Bundle и Unbundle. Посмотреть порядок и изменить его можно, щелкнув правой кнопкой мыши по границе кластера, и выбрав в контекстном меню » Reorder Controls In Cluster».

1. Кнопка подтверждения 2. Кнопка отмены 3. Курсор 4. Старое значение порядка 5. Новое значение Для того, чтобы изменить порядковый номер элемента, нужно набрать новый номер в окошке Click to set to text и потом щелкнуть на нужном элементе. Не забудьте сохранить сделанные изменения, нажав на кнопку OK. Помните, что два кластера с одними и теми же элементами, но с разным порядком расположения этих элементов будут считаться разными по структуре, и их нельзя будет связать между собой.

Эти функции находятся в палитре Functions>>All Functions>>Cluster и позволяют создавать кластеры и управлять ими.

Используйте функцию Bundle для того, чтобы объединить отдельные элементы в кластер или чтобы изменить значения отдельных элементов в уже существующем кластере. Изменить количество терминалов у функции можно просто растянув ее, или щелкнуть правой кнопкой мыши и выбрать Add Input. Если вы соедините вход cluster с каким-нибудь кластером, то число входов для элементов должно совпадать с числом элементов в этом кластере. Если вход cluster подключен, то можно подсоединить только те элементы, значение которых вы хотите изменить. Пример: есть кластер, состоящий из трех элементов.

Можно использовать функцию bundle для того, чтобы изменить значение элемента Command, так, как показано на рисунке:

Замена и доступ к элементам кластера.

Используйте функцию Bundle by Name для того, чтобы получить доступ к элементу кластера по его имени (метке). Эта функция работает почти так же, как и функция Bundle, но она ссылается на элементы кластера, используя их имена. Число входов не обязательно должно совпадать с числом элементов в кластере — вы можете обратиться только к тем элементам, которые нужны.

Пример: с помощью функции Bundle by Name изменяем значения элементов Command и Function. Если в процессе работы над программой понадобится добавить в кластер еще один элемент или изменить порядок элеменов, то при использовании функции Bundle by Name менять все будет не нужно, т.к. порядок и состав элементов в кластере не важен, а важны только имена.

Есть две функции для того, чтобы разбить кластер обратно на отдельные элементы — это функции Unbundle и Unbundle by Name. Думаю, по аналогии с функциями образования кластеров все должно быть понятно.

В этом примере исходный кластер «расщепляется» с помощью этих двух функций. С помощью функции Unbundle by Name можно оставить только те элементы, которые нас интересуют в данный момент. При использовании обычной функции Unbundle будут возвращены все существующие элементы кластера.

Кластер серверов

Кластер серверов (Server Cluster) — это определенное количество серверов, объединенных в группу и образующих единый ресурс. Данное решение позволяет существенно увеличить надежность и производительность системы.

Сгруппированные в локальную сеть несколько компьютеров можно назвать аппаратным кластером, однако, суть данного объединения — повышение стабильности и работоспособности системы за счет единого программного обеспечения под управлением модуля (Cluster Manager).

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

  • 1 Управлять произвольным количеством аппаратных средств с помощью одного программного модуля;
  • 2 Добавлять и усовершенствовать программные и аппаратные ресурсы, без остановки системы и масштабных архитектурных преобразований;
  • 3 Обеспечивать бесперебойную работу системы, при выходе из строя одного или нескольких серверов;
  • 4 Синхронизировать данные между серверами — единицами кластера;
  • 5 Эффективно распределять клиентские запросы по серверам;
  • 6 Использовать общую базу данных кластера.

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

При проектировании систем с участием серверного кластера необходимо учитывать возможности клиентского программного обеспечения по идентификации кластера и совместной работе с командным модулем (Cluster Manager). В противном случае вероятна ситуация, при которой попытка программы-клиента с помощью модуля получить доступ к данным ресурса через другие сервера может получить отказ (конкретные механизмы в данном случае зависят от возможностей и настроек кластера и клиентского оборудования).

Принято считать, что кластеры серверов делятся на две модели:

  • 1 Использование единого массива хранения информации, что дает возможность более быстрого переподключения при сбое. Однако в случае с объемной базой данных и большим количеством аппаратных единиц в системе, возможно падение производительности;
  • 2 Модель, при которой серверы независимы, как и их периферия. В случае отказа перераспределение происходит между серверами. Здесь ситуация обратная — трафик в системе более свободен, однако, усложняется и ограничивается пользование общей базой данных.

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

PARALLEL.RU — Информационно-аналитический центр по параллельным вычислениям

Для начинающих пользователей вычислительных кластеров

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

Что такое вычислительный кластер?

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

Подробнее о том, как устроен и работает вычислительный кластер можно почитать в книге А.Лациса «Как построить и использовать суперкомпьютер».

Как запускаются программы на кластере?

Для каждого кластера имеется выделенный компьютер — головная машина (front-end). На этой машине установлено программное обеспечение, которое управляет запуском программ на кластере. Собственно вычислительные процессы пользователей запускаются на вычислительных узлах, причем они распределяются так, что на каждый процессор приходится не более одного вычислительного процесса. Запускать вычислительные процессы на головной машине кластера нельзя.

Пользователи имеют терминальный доступ на головную машину кластера, а входить на узлы кластера для них нет необходимости. Запуск программ на кластере осуществляется в т.н. «пакетном» режиме — это значит, что пользователь не имеет непосредственного, «интерактивного» взаимодействия с программой, программа не может ожидать ввода данных с клавиатуры и выводить непосредственно на экран. Более того, программа пользователя может работать тогда, когда пользователь не подключен к кластеру.

Какая установлена операционная система?

Вычислительный кластер, как правило, работает под управлением одной из разновидностей ОС Unix — многопользовательской многозадачной сетевой операционной системы. В частности, в НИВЦ МГУ кластеры работают под управлением ОС Linux — свободно распространяемого варианта Unix. Unix имеет ряд отличий от Windows, которая обычно работает на персональных компьютерах, в частности эти отличие касаются интерфейса с пользователем, работы с процессами и файловой системы.

Более подробно об особенностях и командах ОС UNIX можно почитать здесь:

  • Инсталляция Linux и первые шаги (книга Matt Welsh, перевод на русский язык А.Соловьева).
  • Учебник по Unix для начинающих.
  • Энциклопедия Linux.
  • Операционная система UNIX (информационно-аналитические материалы на сервере CIT-Forum).
Как хранятся данные пользователей?

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

Какие используются компиляторы?

Никаких специализированных параллельных компиляторов для кластеров не существует. Используются обычные оптимизирующие компиляторы с языков Си и Фортран — GNU, Intel или другие, умеющие создавать исполняемые программы ОС Linux. Как правило, для компиляции параллельных MPI-программ используются специальные скрипты (mpicc, mpif77, mpif90 и др.), которые являются надстройками над имеющимися компиляторами и позволяют подключать необходимые библиотеки.

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

Существует несколько способов задействовать вычислительные мощности кластера.

1. Запускать множество однопроцессорных задач. Это может быть разумным вариантом, если нужно провести множество независимых вычислительных экспериментов с разными входными данными, причем срок проведения каждого отдельного расчета не имеет значения, а все данные размещаются в объеме памяти, доступном одному процессу.

2. Запускать готовые параллельные программы. Для некоторых задач доступны бесплатные или коммерческие параллельные программы, которые при необходимости Вы можете использовать на кластере. Как правило, для этого достаточно, чтобы программа была доступна в исходных текстах, реализована с использованием интерфейса MPI на языках С/C++ или Фортран. Примеры свободно распространяемых параллельных программ, реализованных с помощью MPI: GAMESS-US (квантовая химия), POVRay-MPI (трассировка лучей).

3. Вызывать в своих программах параллельные библиотеки. Также для некоторых областей, таких как линейная алгебра, доступны библиотеки, которые позволяют решать широкий круг стандартных подзадач с использованием возможностей параллельной обработки. Если обращение к таким подзадачам составляет большую часть вычислительных операций программы, то использование такой параллельной библиотеки позволит получить параллельную программу практически без написания собственного параллельного кода. Примером такой библиотеки является SCALAPACK. Русскоязычное руководство по использованию этой библиотеки и примеры можно найти на сервере по численному анализу НИВЦ МГУ. Также доступна параллельная библиотека FFTW для вычисления быстрых преобразований Фурье (БПФ). Информацию о других параллельных библиотеках и программах, реализованных с помощью MPI, можно найти по адресу http://www-unix.mcs.anl.gov/mpi/libraries.html.

4. Создавать собственные параллельные программы. Это наиболее трудоемкий, но и наиболее универсальный способ. Существует два основных варианта. 1) Вставлять параллельные конструкции в имеющиеся параллельные программы. 2) Создавать «с нуля» параллельную программу.

Как работают параллельные программы на кластере?

Параллельные программы на вычислительном кластере работают в модели передачи сообщений (message passing). Это значит, что программа состоит из множества процессов, каждый из которых работает на своем процессоре и имеет свое адресное пространство. Причем непосредственный доступ к памяти другого процесса невозможен, а обмен данными между процессами происходит с помощью операций приема и посылки сообщений. То есть процесс, который должен получить данные, вызывает операцию Receive (принять сообщение), и указывает, от какого именно процесса он должен получить данные, а процесс, который должен передать данные другому, вызывает операцию Send (послать сообщение) и указывает, какому именно процессу нужно передать эти данные. Эта модель реализована с помощью стандартного интерфейса MPI. Существует несколько реализаций MPI, в том числе бесплатные и коммерческие, переносимые и ориентированные на конкретную коммуникационную сеть.

Как правило, MPI-программы построены по модели SPMD (одна программа — много данных), то есть для всех процессов имеется только один код программы, а различные процессы хранят различные данные и выполняют свои действия в зависимости от порядкового номера процесса.

Более подробно об MPI можно почитать здесь:

  • Курс Вл.В.Воеводина «Параллельная обработка данных». Лекция 5. Технологии параллельного программирования. Message Passing Interface.
  • Вычислительный практикум по технологии MPI (А.С.Антонов).
  • А.С.Антонов «Параллельное программирование с использованием технологии MPI».
  • MPI: The Complete Reference (на англ.яз.).
  • Глава 8: Message Passing Interface в книге Яна Фостера «Designing and Building Parallel Programs» (на англ.яз.).
Где можно посмотреть примеры параллельных программ?

Схематичные примеры MPI-программ можно посмотреть здесь:

  • Курс Вл.В.Воеводина «Параллельная обработка данных». Приложение к лекции 5.
  • Примеры из пособия А.С.Антонова «Параллельное программирование с использованием технологии MPI».

Примеры простейших работающих MPI-программ доступны в составе пакета MPICH, свободно распространяемой реализации MPI. Для пользователей НИВЦ МГУ простейшие примеры MPI-программ на Си и Фортране доступны в директории /home/examples/mpi. Примеры использования конструкций MPI в программах на языке Си можно посмотреть в тестах производительности для параллельных компьютеров. Примеры программ на Фортране с комментариями можно посмотреть в англоязычном документе «MPI User’s Guide in Fortran» (формат Word).

Можно ли отлаживать параллельные программы на персональном компьютере?

Разработка MPI-программ и проверка функциональности возможна на обычном ПК. Можно запускать несколько MPI-процессов на однопроцессорном компьютере и таким образом проверять работоспособность программы. Желательно, чтобы это был ПК с ОС Linux, где можно установить пакет MPICH. Это возможно и на компьютере с Windows, но более затруднительно.

Насколько трудоемко программировать вычислительные алгоритмы c помощью MPI и есть ли альтернативы?

Набор функций интерфейса MPI иногда называют «параллельным ассемблером», т.к. это система программирования относительно низкого уровня. Для начинающего пользователя-вычислителя может быть достаточно трудоемкой работой запрограммировать сложный параллельный алгоритм с помощью MPI и отладить MPI-программу. Существуют и более высокоуровневые системы программирования, в частности российские разработки — DVM и НОРМА, которые позволяют пользователю записать задачу в понятных для него терминах, а на выходе создают код с использованием MPI, и поэтому могут быть использованы практически на любом вычислительном кластере.

Как ускорить проведение вычислений на кластере?

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

1. Подбор опций оптимизации компилятора. Подробнее об опциях компиляторов можно почитать здесь:

  • Компиляторы Intel C++ и Fortran (русскоязычная страница на нашем сайте).
  • GCC online documentation.

2. Использование оптимизированных библиотек. Если некоторые стандартные действия, такие как умножение матриц, занимают значительную долю времени работы программы, то имеет смысл использовать готовые оптимизированные процедуры, выполняющие эти действия, а не программировать их самостоятельно. Для выполнения операций линейной алгебры над матричными и векторными величинами была разработана библиотека BLAS («базовые процедуры линейной алгебры»). Интерфейс вызова этих процедур стал уже фактически стандартом и сейчас существуют несколько хорошо оптимизированных и адаптированных к процессорным архитектурам реализаций этой библиотеки. Одной из таких реализаций является свободно распространяемая библиотека ATLAS, которая при установке настраивается с учетом особенностей процессора. Компания Интел предлагает библиотеку MKL — оптимизированную реализацию BLAS для процессоров Intel и SMP-компьютеров на их основе. Тут статья про подбор опций MKL.

Подробнее о библиотеках линейной алгебры (BLAS) можно почитать здесь:

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

4. Более оптимальное использование кэш-памяти. В случае возможности изменять последовательность действий программы, нужно модифицировать программу так, чтобы действия над одними и те же или подряд расположенными данными данными выполнялись также подряд, а не «в разнобой». В некоторых случаях может быть целесообразно изменить порядок циклов во вложенных циклических конструкциях. В некоторых случаях возможно на «базовом» уровне организовать вычисления над такими блоками, которые полностью попадают в кэш-память.

5. Более оптимальная работа с временными файлами. Например, если программа создает временные файлы в текущем каталоге, то более разумно будет перейти на использование локальных дисков на узлах. Если на узле работают два процесса и каждый из них создает временные файлы, и при этом на узле доступны два локальных диска, то нужно, чтобы эти два процесса создавали файлы на разных дисках.

6. Использование наиболее подходящих типов данных. Например, в некоторых случаях вместо 64-разрядных чисел с плавающей точкой двойной точности (double) может быть целесообразным использовать 32-разрядные числа одинарной точности (float) или даже целые числа (int).

Более подробно о тонкой оптимизации программ можно почитать в руководстве по оптимизации для процессоров Intel и в других материалах по этой теме на веб-сайте Intel.

Как оценить и улучшить качество распараллеливания?

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

Важным показателем, который говорит о том, эффективно ли в программе реализован параллелизм, является загрузка вычислительных узлов, на которых работает программа. Если загрузка на всех или на части узлов далека от 100% — значит, программа неэффективно использует вычислительные ресурсы, т.е. создает большие накладные расходы на обмены данными или неравномерно распределяет вычисления между процессами. Пользователи НИВЦ МГУ могут посмотреть загрузку через веб-интерфейс для просмотра состояния узлов.

В некоторых случаях для того, чтобы понять, в чем причина низкой производительности программы и какие именно места в программе необходимо модифицировать, чтобы добиться увеличения производительности, имеет смысл использовать специальные средства анализа производительности — профилировщики и трассировщики. На кластере Ant установлена система для отладки MPI-программ deb-MPI. Краткую информацию по системе можно найти по адресу http://parallel.ru/cluster/deb-MPI-UG.html .—>

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

Кластеризация

Кластеризация (англ. cluster analysis) — задача группировки множества объектов на подмножества (кластеры) таким образом, чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.

Задача кластеризации относится к классу задач обучения без учителя.

Постановка задачи кластеризации

Пусть [math]X[/math] — множество объектов, [math]Y[/math] — множество идентификаторов (меток) кластеров. На множестве [math]X[/math] задана функция расстояния между объектами [math]\rho(x,x’)[/math] . Дана конечная обучающая выборка объектов [math]X^m = \ < x_1, \dots, x_m \>\subset X[/math] . Необходимо разбить выборку на подмножества (кластеры), то есть каждому объекту [math]x_i \in X^m[/math] сопоставить метку [math]y_i \in Y[/math] , таким образом чтобы объекты внутри каждого кластера были близки относительно метрики [math]\rho[/math] , а объекты из разных кластеров значительно различались.

Определение:
Алгоритм кластеризации — функция [math]a\colon X\to Y[/math] , которая любому объекту [math]x\in X[/math] ставит в соответствие идентификатор кластера [math]y\in Y[/math] .

Множество [math]Y[/math] в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем, что метки объектов из обучающей выборки [math]y_i[/math] изначально не заданы, и даже может быть неизвестно само множество [math]Y[/math] .

Решение задачи кластеризации объективно неоднозначно по ряду причин:

  • Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию «по построению», однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области;
  • Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр [1] ;
  • Результат кластеризации существенно зависит от метрики. Однако существует ряд рекомендаций по выбору метрик для определенных классов задач. [2] .

Число кластеров фактически является гиперпараметром для алгоритмов кластеризации. Подробнее про другие гиперпараметры и их настройку можно прочитать в статье [3] .

Теорема невозможности Клейнберга

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

Определение:
Алгоритм кластеризации [math]a[/math] является масштабно инвариантным (англ. scale-invariant), если для любой функции расстояния [math]\rho[/math] и любой константы [math]\alpha \gt 0[/math] результаты кластеризации с использованием расстояний [math]\rho[/math] и [math]\alpha\cdot\rho[/math] совпадают.

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

Определение:
Полнота (англ. Richness). Множество результатов кластеризации алгоритма [math]a[/math] в зависимости от изменения функции расстояния [math]\rho[/math] должно совпадать со множеством всех возможных разбиений множества объектов [math]X[/math] .

Вторая аксиома утверждает, что алгоритм кластеризации должен уметь кластеризовать обучающую выборку на любое фиксированное разбиение для какой-то функции расстояния [math]\rho[/math] .

Определение:
Алгоритм кластеризации является согласованным (англ. consistent), если результат кластеризации не изменяется после допустимого преобразования функции расстояния.

Третья аксиома требует сохранения кластеров при уменьшении внутрикластерного расстояния и увеличении межкластерного расстояния.

Примеры преобразований с сохранением кластеров
Cluster 0.png Clusters scale inv.png Cluster consist.png
Исходное расположение объектов и их кластеризация Пример масштабной инвариантности. Уменьшен масштаб по оси ординат в два раза. Пример допустимого преобразования. Каждый объект в два раза приближен к центроиду своего класса. Внутриклассовое расстояние уменьшилось, межклассовое увеличилось.

Исходя из этих аксиом Клейнберг сформулировал и доказал теорему:

Для множества объектов, состоящего из двух и более элементов, не существует алгоритма кластеризации, который был бы одновременно масштабно-инвариантным, согласованным и полным.

Несмотря на эту теорему Клейнберг показал [4] , что иерархическая кластеризация по методу одиночной связи с различными критериями останова удовлетворяет любым двум из трех аксиом.

Типология задач кластеризации

Типы входных данных

  • Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками (англ. features). Признаки могут быть как числовыми, так и категориальными;
  • Матрица расстояний между объектами. Каждый объект описывается расстоянием до всех объектов из обучающей выборки.

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

Цели кластеризации

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

Методы кластеризации

  • Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике;
  • Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности:
    • EM-алгоритм;

    Сравнение алгоритмов кластеризации из пакета scikit-learn [5]

    Меры качества кластеризации

    Для оценки качества кластеризации задачу можно переформулировать в терминах задачи дискретной оптимизации. Необходимо так сопоставить объектам из множества [math]X[/math] метки кластеров, чтобы значение выбранного функционала качества приняло наилучшее значение. В качестве примера, стремятся достичь минимума среднего внутрикластерного расстояния [math]F_0 = \dfrac<\sum_<[y_i=y_j]\cdot\rho(x_i, x_j)>><\sum_[y_i=y_j]>[/math] или максимума среднего межкластерного расстояния [math]F_1 = \dfrac<\sum_<[y_i\neq y_j]\cdot\rho(x_i, x_j)>><\sum_[y_i\neq y_j]>[/math] .

    Подробнее про меры качества можно прочитать в статье оценка качества в задаче кластеризации.

    Применение

    Биология и биоинформатика

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

    Медицина

    • Используется в позитронно-эмиссионной томографии для автоматического выделения различных типов тканей на трехмерном изображении;
    • Применяется для выявления шаблонов устойчивости к антибиотикам; для классификации антибиотиков по типу антибактериальной активности.

    Маркетинг

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

    Интернет

    • Выделение групп людей на основе графа связей в социальных сетях;
    • Повышение релевантности ответов на поисковые запросы путем группировки веб-сайтов по смысловым значениям поискового запроса.

    Компьютерные науки

    • Кластеризация используется в сегментации изображений для определения границ и распознавания объектов;
    • Кластерный анализ применяется для определения образовавшихся популяционных ниш в ходе работы эволюционных алгоритмов для улучшения параметров эволюции;
    • Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере;
    • Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.

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

    Метод K-средних (Алгоритм Ллойда)

    Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем объекты снова разбиваются на кластеры в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения внутрикластерного расстояния.

    Алгоритм минимизирует сумму квадратов внутрикластерных расстояний: [math] \sum_^ ||x_i — \mu_||^2 \: \to \: \min_< \, \<\mu_a\>>, \: \: ||x_i — \mu_a||^2 = \sum_^ (f_j(x_i) — \mu_)^2[/math]

    На вход алгоритму подаётся выборка [math]X^m = \< x_1, \dots, x_m \>[/math] и количество кластеров [math]K = |Y|[/math] .

    На выходе получаем центры кластеров [math]\mu_a[/math] для кластеров [math]a \in Y[/math] .

    [math]\mu_a := init(X^m)[/math] # Инициализируем произвольно начальное приближение для центров кластеров [math]a \in Y[/math]. (Можно наиболее удалённые друг от друга объекты выборки) [math]A := [ -1 \: | \: for \: x_i \in X^m ][/math] # Инициализируем массив отображений из объектов выборки в их кластеры [math]changed := True[/math] [math]while[/math] [math]changed[/math]: # Повторяем пока [math]A_i[/math] изменяются [math]changed := False[/math] [math]for[/math] [math]x_i \in X^m[/math]: # Относим каждый [math]x_i[/math] к ближайшему центру [math]A_ := A_i[/math] [math]A_i := arg \min_ ||x_i - \mu_a||[/math] [math]if[/math] [math]A_i \neq A_[/math]: [math]changed := True[/math] [math]for[/math] [math]a \in Y[/math]: # Вычисляем новые положения центров [math]\mu_a := \frac^[A_i = a] x_i>^[A_i = a]>[/math] [math]return[/math] [math]\mu_a, \: A[/math] # Возвращаем центры кластеров и распределение по ним объектов выборки 

    DBSCAN

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

    На вход алгоритму подаётся набор точек, параметры [math]\epsilon[/math] (радиус окружности) и [math]m[/math] (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида: основные точки, прямо достижимые, достижимые и шумовые.

    • Точка является основной, если в окружности с центром в этой точке и радиусом [math]\epsilon[/math] находится как минимум [math]m[/math] точек.
    • Точка [math]a[/math] является прямо достижимой из основной точки [math]b[/math] , если [math]a[/math] находится на расстоянии, не большем [math][/math] от точки [math]b[/math] .
    • Точка [math]a[/math] является достижимой из [math]b[/math] , если существует путь [math]p_1, \dots, p_n[/math] с [math]p_1 = a[/math] и [math]p_n = b[/math] , где каждая точка [math]p_[/math] прямо достижима из точки [math]p_i[/math] .
    • Все остальные точки, которые не достижимы из основных точек, считаются шумовыми.

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

    Алгоритм начинается с произвольной точки из набора, которая еще не просматривалась. Для точки ищется [math][/math] -окрестность. Если она не содержит как минимум [math]m[/math] точек, то помечается как шумовая, иначе образуется кластер [math]K[/math] , который включает все точки из окрестности. Если точка из окрестности уже является частью другого кластера [math]C_j[/math] , то все точки данного кластера добавляются в кластер [math]K[/math] . Затем выбирается и обрабатывается новая, не посещённая ранее точка, что ведёт к обнаружению следующего кластера или шума.

    На выходе получаем разбиение на кластеры и шумовые объекты. Каждый из полученных кластеров [math]C_j[/math] является непустым множеством точек и удовлетворяет двум условиям:

    • Любые две точки в кластере попарно связаны (то есть найдется такая точка в кластере, из которой достижимы обе этих точки).
    • Если точка достижима из какой-либо точки кластера, то она принадлежит кластеру.

    Пусть для каждого [math]x \in X^m[/math] имеем посчитанной его [math]\epsilon[/math] -окрестность [math]U_(x) = \[/math] .

    [math]U := X^m[/math] # Непомеченные объекты [math]A := [ -1 \: | \: for \: x_i \in X^m ][/math] # Инициализируем массив отображений из объектов выборки в их кластеры [math]a := 0[/math] # Количество кластеров [math]while[/math] [math]U \neq \varnothing[/math]: # Пока в выборке есть непомеченные объекты [math]x := rand(U)[/math] # Берём случайную непомеченную точку [math]if[/math] [math]|U_(x) \lt m|[/math]: [math]mark[x][/math] [math]:=[/math] "[math]noise[/math]" # Пометим [math]x[/math] как, возможно, шумовой [math]else[/math]: [math]K := U_(x)[/math] [math]a := a + 1[/math] # Создадим новый кластер K [math]for[/math] [math]x' \in K[/math]: [math]if[/math] [math]x' \in U[/math] || [math]mark[x'][/math] [math]==[/math] "[math]noise[/math]": # Если [math]x'[/math] не помечен или помечен как шумовой [math]if[/math] [math]|U_(x')| \geq m[/math]: [math]mark[x'] :=[/math] "[math]interior[/math]" # Пометим [math]x'[/math] как внутренний кластера [math]K[/math] [math]K := K \cup U_(x')[/math] # Добавим вместе с [math]x'[/math] всю его окрестность [math]else[/math]: [math]mark[x'] :=[/math] "[math]frontier[/math]" # Пометим [math]x'[/math] как граничный кластера [math]K[/math] [math]for[/math] [math]x_i \in K[/math]: [math]A_i := a[/math] [math]U := U \setminus K[/math] [math]return[/math] [math]a, \: A, \: mark[/math] # Возвращаем количество кластеров, распределение по кластерам и метки объектов (внутренние, граничные или шумовые) 

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

    Пример кода

    Пример на языке R

    Основная статья: Примеры кода на R

    Для реализации алгоритма k-средних используется пакет ClusterR . В нем реализовано 2 функции: KMeans_arma() и KMeans_rcpp() . В примере далее рассмотрена реализация с использованием функции KMeans_arma() .

    # importing package and its' dependencies library(ClusterR) # reading data data "data.csv") # evaluating model model clusters = 2, n_iter = 10, seed_mode = "random_subset", verbose = T, CENTROIDS = NULL) # predicting results predictions 

    См. также

    • Оценка качества в задаче кластеризации
    • EM-алгоритм
    • Иерархическая кластеризация
    • [math]\mathrm[/math] -средних [на 28.01.18 не создан]

    Примечания

    1. ↑scikit-learn — Clustering
    2. ↑ Cornwell, B. (2015). Linkage Criteria for Agglomerative Hierarchical Clustering. Social Sequence Analysis, 270–274
    3. ↑ Shalamov Viacheslav, Valeria Efimova, Sergey Muravyov, and Andrey Filchenkov. "Reinforcement-based Method for Simultaneous Clustering Algorithm Selection and its Hyperparameters Optimization." Procedia Computer Science 136 (2018): 144-153.
    4. ↑Kleinberg J. An Impossibility Theorem for Clustering
    5. ↑scikit-learn — Comparing different clustering algorithms on toy datasets

    Источники информации

    • Википедия — Кластерный анализ
    • Wikipedia — Cluster analysis
    • MachineLearning — Кластеризация
    • К.В.Воронцов Лекции по алгоритмам кластеризации и многомерного шкалирования
    • Kleinberg J. An Impossibility Theorem for Clustering
    • Машинное обучение
    • Кластеризация

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *