Набор данных, который сегодня кажется объемным, почти наверняка станет небольшим в ближайшем будущем. Массивные наборы данных не всегда сложны, а небольшие наборы данных всегда просты, что подчеркивает, что сложность набора данных является важным фактором при определении того, является ли они большими. Для качественного анализа входящего потока данных необходимо использовать алгоритмы.
Кластеризация — это разделение данных на группы похожих объектов. Каждая группа, называемая кластером, состоит из объектов, которые аналогичны друг другу и отличающиеся от объектов других групп.
Адаптация k-means clustering для Big Data
При кластеризации больших данных основной целью считается, что если данные располагаются в матрице, то строки представляют значение информации, а столбцы представляют свойства каждого значения, тогда матрица может не иметь определенных значений во многих местах. Если данные организовать так, что свойства интересующего значения могут получить приоритет над другими элементами, то:
- Все свойства можно не учитывать для построения результатов кластеризации
- Полученная структура кластера будет соответствовать проводимому анализу 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 анализа.
- Количество итерации предопределено. Число итераций в классическом неопределенно.
- Форма кластера многогранна — k-means clustering способно идентифицировать только выпуклые формы. Предлагаемый алгоритм дает многогранные кластеры, которые могут ассимилировать как выпуклые, так и нерегулярные кластеры.
Это позволяет снизить временные затраты за счет фиксированного количества итераций. Использовалась Manhattan distance concept в модифицированной форме, которая также уменьшает время выполнения. Для большинства наборов данных точность, достигаемая предложенным алгоритмом, выше, чем у классического алгоритма. Но есть и недостатки: обработка происходит плохо пока данные разных категорий не преобразованы в эквивалентные цифровые данные. Изучение кластеризации Big Data с точки зрения категорий может быть возможным расширением данного алгоритма. Также можно применить концепции машинного обучения для определения приоритета атрибутов вместо запроса от пользователя.
Литература:
- K-means clustering algorithm // Data Clustering Algorithms. URL: https://sites.google.com/site/dataclusteringalgorithms/k-means-clustering-algorithm (дата обращения: 26.11.2018).
- Manhattan distance concept // Manhattan distance. URL: https://xlinux.nist.gov/dads/HTML/manhattanDistance.html
