Рубрики
Без рубрики

Руководство по кластеризации K-средств с помощью Java

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

Автор оригинала: Darinka Zobenica.

Вступление

K-Means-один из самых простых и популярных алгоритмов кластеризации в науке о данных. Он разделяет данные на основе их близости к одному из K так называемых центроидов -точек данных, которые являются средним значением всех наблюдений в кластере. Наблюдение – это единая запись данных определенного формата.

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

Что такое кластеризация?

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

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

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

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

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

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

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

Значимые кластеры необходимы для изучения биологии, климата, медицины, бизнеса и т.д.

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

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

Алгоритм K-Средних

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

Псевдокод

1. Select K initial centroids
REPEAT:
    2. Form K clusters by assigning each observation to its nearest centroid's cluster
    3. Recompute centroids for each cluster
UNTIL centroids do not change

Алгоритм K-Средних Объяснен

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

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

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

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

Важно отметить, что для расчета среднего значения мы должны иметь дело с количественными данными. Если у нас есть качественные (номинальные или порядковые) данные, мы должны использовать другую вариацию алгоритма (K-Медоид, K-Медиана и т.д.) Или комбинацию различных методов в зависимости от типа атрибута.

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

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

Обычно мы измеряем качество нашей кластеризации, создавая целевую функцию . Для K-средних эта целевая функция часто упоминается SSE (Сумма квадратов ошибок) . Как следует из его названия, SSE-это сумма расстояний каждого наблюдения от его ближайшего центроида . Таким образом, наша цель при кластеризации-минимизировать SSE:

$$ SSE =}^K}^{\текст{размер кластера}} d((центроид)_i, (экземпляр)_j)^2 $$

Выбор Начальных Центроидов

Самый простой способ выбрать начальные центроиды-просто выбрать число K и выбрать K случайные точки. Однако K-средние чрезвычайно чувствительны к первоначальному выбору центроидов и иногда выдают совершенно разные результаты в зависимости от этого. Чтобы найти более оптимальное решение, нам нужно решить две проблемы:

  1. Как выбрать K
  2. Как выбрать K начальные центроиды

Существует несколько способов определения числа K :

  • X-означает кластеризацию – попытка разделения и сохранение наилучших разбиений в соответствии с РАЗМЕРОМ до тех пор, пока не будет достигнут критерий остановки, такой как Информационный критерий Акайке (AIC) или Байесовский информационный критерий (BIC)
  • Метод силуэта – коэффициент силуэта измеряет, насколько каждый элемент похож на свой собственный кластер ( сцепление ) по сравнению с тем, насколько он похож на другие кластеры ( разделение ), максимизация этого коэффициента с помощью генетического алгоритма на нем может дать нам хорошее число для K

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

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

Вот почему мы используем то, что называется методом Локтя . Мы запускаем алгоритм K-средних с различными значениями K и строим их на графике в соответствии с вышеупомянутым соотношением, которое мы получаем в конце для каждого из них. Значение K , которое мы выбираем, – это то, где находится “локоть” кривой, то есть где мы начинаем получать уменьшающуюся отдачу по мере увеличения K :

Как только мы определимся с K , нам нужно выбрать K стартовые центроиды. Оптимальный выбор этого параметра является NP-сложной задачей, поэтому был разработан алгоритм для аппроксимации хорошего решения. Давайте посмотрим на некоторые анимации того, что может произойти, если мы неправильно их выберем:

Один из алгоритмов, который приблизительно решает эту проблему, называется K-Means++. Она состоит из следующих шагов:

  1. Выберите один центроид случайным образом из точек данных в наборе данных с одинаковой вероятностью (все точки с одинаковой вероятностью будут выбраны).
  2. Для каждой точки данных x , которая еще не выбрана, вычислите расстояние D(x) от ее ближайшего центроида.
  3. Выберите одну новую точку данных y случайным образом в качестве нового центроида, используя взвешенную вероятность, где y выбирается с вероятностью квадрата расстояния .( D(y)*D(y) ). Другими словами, чем дальше y находится от ближайшего центроида, тем выше вероятность того, что он будет выбран.
  4. Повторяйте шаги 2 и 3 до тех пор, пока не будут выбраны K центроиды.
  5. Запустите стандартные K-средние с инициализированными центроидами.

Сложность во времени и пространстве

Время , необходимое для K-средних, равно O(I·K·m·n) , где:

  • I – это количество итераций, необходимых для сходимости
  • K – это количество кластеров, которые мы формируем
  • m – это количество атрибутов
  • n – количество наблюдений

Это имеет смысл, потому что для каждой итерации O(I) мы должны пройти все наблюдения O(n) и вычислить их расстояние O(m) от каждого центроида O(K) .

Сложность пространства составляет O(m·(n+K)) , потому что мы сохраняем n точек из нашего набора данных плюс K точек для центроидов, каждая точка имеет m атрибутов.

Реализация K-средств в Java

Из-за отсутствия обычной поддержки наборов данных и интеллектуального анализа данных реализовать K-Means в основной Java непросто. Вы можете найти полный рабочий код здесь , но мы предоставим краткую документацию по вспомогательному классу, набору данных и реализации самого алгоритма:

  • Набор данных классов

    Git Essentials

    Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

    Узнайте больше

    • Запись класса – вложенный класс, содержит HashMap<Строка, Двойная> , в котором хранится одна строка таблицы с ключом, соответствующим имени атрибута, и значением, соответствующим его, ну, значению.
    • Поля:
      • Имена атрибутов – список имен атрибутов
      • записи – список Записей ов
      • минимумы и максимумы – минимумы и максимумы для каждого атрибута, которые будут использоваться для генерации случайного значения между ними.
      • индексы центроидов – список центроидов кластеров.
    • Набор данных(строка csvFileName) вызывает исключение IOException – конструктор, считывает данные из предоставленного файла .csv и инициализирует поля класса с его помощью.
    • HashMap<Строка, дважды> вычислить центроид(int кластер) – вычисляет центроид для данного кластера.
    • LinkedList<Хэш-карта<Строка,Двойная>> пересчитать центроиды(int K) – вычисляет все K центроиды.
    • HashMap<Строка, двойная> случайная из набора данных() – возвращает случайную точку данных из всех доступных точек данных из набора данных (она нужна нам для инициирования первого центроида).
    • общедоступная хэш - карта<Строка,двойная> Вычисляет вес центроида () – вычисляет расстояние всех точек от выбранных в данный момент центроидов и взвешивает их все в соответствии с этим расстоянием, поэтому наиболее вероятным будет выбран самый дальний, а затем выбирает один из них, используя выбор рулетки …)
    • статическое двойное евклидовое расстояние(HashMap<Строка, Двойной> a, HashMap<Строка, Двойной> b) – вычисляет расстояние между двумя точками данных.
    • Double calculateTotal SSE(Список ссылок<Хэш-карта<Строка,Двойные>> центроиды) – вычисляет РАЗМЕР всех кластеров.

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

Теперь давайте продолжим и реализуем K-средства, используя этот класс в качестве помощника:

public class KMeans {

    // Higher precision means earlier termination
    // and higher error
    static final Double PRECISION = 0.0;

    /* K-Means++ implementation, initializes K centroids from data */
    static LinkedList> kmeanspp(DataSet data, int K) {
        LinkedList> centroids = new LinkedList<>();

        centroids.add(data.randomFromDataSet());

        for(int i=1; i> centroids = kmeanspp(data, K);

        // Initialize Sum of Squared Errors to max, we'll lower it at each iteration
        Double SSE = Double.MAX_VALUE;

        while (true) {

            // Assign observations to centroids
            var records = data.getRecords();

            // For each record
            for(var record : records){
                Double minDist = Double.MAX_VALUE;
                // Find the centroid at a minimum distance from it and add the record to its cluster
                for(int i = 0; i < centroids.size(); i++){
                    Double dist = DataSet.euclideanDistance(centroids.get(i), record.getRecord());
                    if(dist < minDist){
                        minDist = dist;
                        record.setClusterNo(i);
                    }
                }
            }

            // Recompute centroids according to new cluster assignments
            centroids = data.recomputeCentroids(K);

            // Exit condition, SSE changed less than PRECISION parameter
            Double newSSE = data.calculateTotalSSE(centroids);
            if(SSE-newSSE <= PRECISION){
                break;
            }
            SSE = newSSE;
        }
    }

    public static void main(String[] args) {
        try {
            // Read data
            DataSet data = new DataSet("files/sample.csv");

            // Remove prior classification attr if it exists (input any irrelevant attributes)
            data.removeAttr("Class");

            // Cluster
            kmeans(data, 2);

            // Output into a csv
            data.createCsvOutput("files/sampleClustered.csv");

        } catch (IOException e){
            e.printStackTrace();
        }
    }
}

Файл sample.csv содержит:

A,B
1,3
2,4
1,2
3,4
1,2
2,2
2,1
10,12
14,11
12,14
16,13
1,1
4,4
10,11
15,13
13,12
4,1
4,3
4,5

Выполнение этого кода приводит к созданию нового файла пример кластеризованного файла.csv , который содержит:

A,B,ClusterId
1.0,3.0,1
2.0,4.0,1
1.0,2.0,1
3.0,4.0,1
1.0,2.0,1
2.0,2.0,1
2.0,1.0,1
10.0,12.0,0
14.0,11.0,0
12.0,14.0,0
16.0,13.0,0
1.0,1.0,1
4.0,4.0,1
10.0,11.0,0
15.0,13.0,0
13.0,12.0,0
4.0,1.0,1
4.0,3.0,1
4.0,5.0,1

У нас есть два кластера, 0 и 1 вот. И в зависимости от характеристик каждого из них алгоритм сгруппировал их в один из них.

Возможные проблемы с K-средними

У K-средних есть как общие проблемы, стереотипные для алгоритмов кластеризации, так и проблемы, характерные только для K-средних. Давайте рассмотрим некоторые из наиболее распространенных из них и то, как с ними обращаться.

Обработка Пустых Кластеров

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

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

  2. В качестве альтернативы мы могли бы найти кластер с наибольшим SSE и выбрать из него центроид. Это позволило бы эффективно разделить этот кластер и уменьшить общий размер больше, чем выбор какой-либо случайной точки.

Выбросы

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

Они могут вызвать дополнительные осложнения с SSE, так как они могут вызвать неоптимальные кластеризации только для того, чтобы центроид был ближе к выбросам. Обычно рекомендуется устранить выбросы перед использованием K-средств, чтобы избежать этой проблемы.

Однако важно отметить, что в зависимости от приложения, для которого вы используете алгоритм, сохранение выбросов может иметь решающее значение. Например, при сжатии данных вы должны кластеризировать каждую точку , включая выбросы. В общем, нас могут заинтересовать выбросы для некоторых целей (очень выгодные клиенты, исключительно здоровые особи, взаимосвязь между размером крыла и скоростью спаривания у Drosophila malerkotliana …).

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

Локальные Минимумы и Сокращение SSE С последующей обработкой

Как это часто бывает с этими алгоритмами, K-средние не гарантируют оптимальности. Это может привести к локальному минимуму – результат, который можно было бы улучшить с помощью некоторой настройки.

Мы можем снизить общую SSE, умело разделив существующие кластеры или добавив новый центроид. Если мы разделяем кластер, хорошо выбрать кластер с наибольшим РАЗМЕРОМ, который часто также будет иметь наибольшее количество точек. Если мы добавим новый центроид, часто бывает полезно выбрать точку, наиболее удаленную от всех существующих центроидов.

Если мы хотим впоследствии уменьшить количество кластеров (например, чтобы в результате мы сохранили точно K кластеров), мы также можем использовать два разных метода. Мы можем либо:

  1. Объедините два кластера (обычно самые маленькие или те, у которых самый низкий SSE)
  2. Разнесите кластер, удалив его центроид и переназначив его участников в другие кластеры.

Поиск Несуществующих Кластеров

K-Средства найдут K кластеров независимо от исходных данных . Если есть 3 кластера и вы установили K в 5 , он найдет 5 кластеров. Если есть нет кластеров вообще, он все равно найдет 5 кластеров:

Нет никакого способа предотвратить это в самом К-средстве. Вместо этого следует сначала проверить статистику Хопкинса , чтобы увидеть, есть ли какие-либо кластеры в самих данных. Статистика Хопкинса работает путем сравнения набора данных со случайно сгенерированным однородным набором точек.

Допустим, у нас есть наш набор данных X, и в нем есть n точек данных. Мы отбираем m из них для анализа.

Затем мы случайным образом генерируем другой набор данных, Y, который следует равномерному распределению. У также есть m точки данных.

Расстояние между некоторым членом X и его ближайшим соседом мы назовем w .

Расстояние между некоторым членом Y и его ближайшим соседом в X мы назовем u .

Затем статистика Хопкинса выглядит следующим образом:

$$ H =}^m}^m u_i}^m w_i} $$

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

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

Если это неслучайно, расстояния внутри набора будут значительно меньше и будут незначительно влиять на знаменатель, приближая результат к 1.

Типы базовых кластеров, которые он может распознавать

K-среднее очень хорошо распознает шаровые скопления одинаковой плотности и одинакового размера.

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

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

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

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

Второй очень очевидный тип набора данных, с которым у K-Means будут проблемы, – это набор данных, полный кластеров с несогласованными размерами . Если у вас есть большой широкий кластер и рядом с ним крошечный кластер, крошечный кластер часто будет полностью поглощен большим.

Это связано с тем, что он не сильно влияет на свой РАЗМЕР, потому что он просто немного увеличивает свой диаметр. Если мы каким-то образом получим два центроида в этих двух кластерах, большой кластер, скорее всего, будет разделен на две части, а не обнаружит реально существующие кластеры.

Это опять же потому, что РАЗМЕР большого широкого кластера и крошечного будет больше, чем РАЗМЕР большого кластера, уменьшенного вдвое. Опять же, как и в предыдущих разделах, мы рекомендуем визуализацию и/или сравнение результатов с помощью различных методов (т. е. иерархической кластеризации), чтобы определить, вызывает ли это проблемы.

И третья упомянутая проблема-это кластеры различной плотности . Плотные точки будут оказывать в среднем большее влияние, чем те, которые не так плотно упакованы, и они будут ближе к своей центроиде, чем те, которые не так плотно упакованы. Менее плотные кластеры будут иметь больший РАЗМЕР, будут разбиты на части и поглощены окружающими плотными кластерами.

Вот иллюстрация проблемы кластеров с различными размерами и плотностью:

Вариации K-средних

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

  • K-Режимы – Центроид-это элемент, созданный путем выбора наиболее частого появления в кластере для каждого атрибута.
  • K-Медоиды – похоже на среднее значение, но оно ограничено тем, что является фактическим членом набора данных, а не просто возможным значением.
  • K-Медиана – вместо среднего значения мы используем медиану или “средний элемент” для каждого атрибута, чтобы создать наш центроид.
  • Кластеризация с максимизацией ожиданий (EM) с использованием моделей смеси Гаусса (GMM) –обнаруживает эллиптические формы с помощью как среднего , так и стандартного отклонения для определения принадлежности к кластеру.

Вывод

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