Адаптация алгоритма k-means clustering для Big Data анализа | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 1 июня, печатный экземпляр отправим 5 июня.

Опубликовать статью в журнале

Авторы: ,

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №48 (234) ноябрь 2018 г.

Дата публикации: 29.11.2018

Статья просмотрена: 50 раз

Библиографическое описание:

Горбачев Д. И., Гончаров Е. Ю. Адаптация алгоритма k-means clustering для Big Data анализа // Молодой ученый. — 2018. — №48. — С. 15-17. — URL https://moluch.ru/archive/234/54268/ (дата обращения: 20.05.2019).



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

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

Адаптация k-means clustering для Big Data

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

  1. Все свойства можно не учитывать для построения результатов кластеризации
  2. Полученная структура кластера будет соответствовать проводимому анализу Big Data

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

Алгоритм:

Представим в виде диапазона значений размером М. Из данного диапазона возьмем диапазон m элементов из M. Этот диапазон берется на основе подходящих значений для анализа. Сортируем их в порядке убывания начиная с наиболее подходящего . Первое значение является первичным, остальные измерения являются вторичными. Количество кластеров k предварительно определено.

Шаг 1: Изменение каждого значения вычисляется , , где это максимальное значение i-го измерения, это минимальное значение i-го измерения.

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

Шаг 3: Центроид каждого кластера вычисляется как среднее значение всех кластеров.

Шаг 4: Для каждого вторичного значения подходящего под условие повторяем следующее:

Шаг 4.1: Поиск резко отклоняющихся значений для каждого кластера на основе условия: для каждого значения если то значение является резко отклоняющимся в j точке.

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

Преимущества предложенного алгоритма над классическим k-meansclustering для BigData анализа.

  1. Количество итерации предопределено. Число итераций в классическом неопределенно.
  2. Форма кластера многогранна — k-means clustering способно идентифицировать только выпуклые формы. Предлагаемый алгоритм дает многогранные кластеры, которые могут ассимилировать как выпуклые, так и нерегулярные кластеры.

Это позволяет снизить временные затраты за счет фиксированного количества итераций. Использовалась Manhattan distance concept в модифицированной форме, которая также уменьшает время выполнения. Для большинства наборов данных точность, достигаемая предложенным алгоритмом, выше, чем у классического алгоритма. Но есть и недостатки: обработка происходит плохо пока данные разных категорий не преобразованы в эквивалентные цифровые данные. Изучение кластеризации Big Data с точки зрения категорий может быть возможным расширением данного алгоритма. Также можно применить концепции машинного обучения для определения приоритета атрибутов вместо запроса от пользователя.

Литература:

  1. K-means clustering algorithm // Data Clustering Algorithms. URL: https://sites.google.com/site/dataclusteringalgorithms/k-means-clustering-algorithm (дата обращения: 26.11.2018).
  2. Manhattan distance concept // Manhattan distance. URL: https://xlinux.nist.gov/dads/HTML/manhattanDistance.html
Основные термины (генерируются автоматически): кластер, предлагаемый алгоритм, алгоритм, данные, предложенный алгоритм, число итераций, шаг.


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

Алгоритм разделяет данные на k кластеров Si...

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

Применение методов кластеризации для обработки новостного...

Кратко рассматриваются различные типы алгоритмов кластеризации в зависимости от модели представления коллекции объектов: статические, инкрементальные и

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

Метод k средних при решении задачи распознавания диктора по...

Алгоритм k-средних разбивает исходное множество на k кластеров, где k — предварительно заданное число. Для этого сначала значения средних инициализируются некоторыми векторами из исходного множества. Затем на каждой итерации алгоритма происходит распределение...

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

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

Предложенный алгоритм основывается на задании векторов используемых ресурсов

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

Оценка рисков информационной безопасности с помощью метода...

Раздел 3 предлагает оценку рисков информационной безопасности на основе взаимной

Данные были классифицированы по К-means алгоритму с оптимальными взаимными

Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.

Анализ эффективности алгоритмов сортировки и вcтроенных...

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

Метод определения весов параметров из набора входящих...

Количество итераций равно количеству атрибутов j в наборе на входе .

Количество итераций для каждого набора равно сумме чисел сочетаний без повторений из j-1

Для каждого кластера определяются эталонные значения параметров как усредненные данные по...

О способе унификации программно-алгоритмической модели...

На первом шаге алгоритма создается множество решений, называемое популяцией.

На каждой итерации алгоритма направление и длина вектора скорости каждой из частиц в классическом алгоритме изменяются в соответствие со сведениями о найденных оптимумах [5]

Обзор некоторых алгоритмов нестрогого сопоставления записей...

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

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

Алгоритм разделяет данные на k кластеров Si...

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

Применение методов кластеризации для обработки новостного...

Кратко рассматриваются различные типы алгоритмов кластеризации в зависимости от модели представления коллекции объектов: статические, инкрементальные и

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

Метод k средних при решении задачи распознавания диктора по...

Алгоритм k-средних разбивает исходное множество на k кластеров, где k — предварительно заданное число. Для этого сначала значения средних инициализируются некоторыми векторами из исходного множества. Затем на каждой итерации алгоритма происходит распределение...

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

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

Предложенный алгоритм основывается на задании векторов используемых ресурсов

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

Оценка рисков информационной безопасности с помощью метода...

Раздел 3 предлагает оценку рисков информационной безопасности на основе взаимной

Данные были классифицированы по К-means алгоритму с оптимальными взаимными

Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.

Анализ эффективности алгоритмов сортировки и вcтроенных...

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

Метод определения весов параметров из набора входящих...

Количество итераций равно количеству атрибутов j в наборе на входе .

Количество итераций для каждого набора равно сумме чисел сочетаний без повторений из j-1

Для каждого кластера определяются эталонные значения параметров как усредненные данные по...

О способе унификации программно-алгоритмической модели...

На первом шаге алгоритма создается множество решений, называемое популяцией.

На каждой итерации алгоритма направление и длина вектора скорости каждой из частиц в классическом алгоритме изменяются в соответствие со сведениями о найденных оптимумах [5]

Обзор некоторых алгоритмов нестрогого сопоставления записей...

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

Задать вопрос