Вступление

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

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

• Вступление
• Что такое кластеризация?
• Алгоритм K-средних
  • Псевдокод
  • Объяснение
  • Выбор начальных центроидов
  • Сложность времени и пространства
  • Выполнение
• Проблемы
  • Обработка пустых кластеров
  • Выбросы
  • Локальные минимумы и сокращение SSE с постобработкой
  • Поиск несуществующих кластеров
  • Типы базовых кластеров, которые он может распознать
• Вариации
• Заключение

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

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

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

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

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

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

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

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

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

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

Прототип - это репрезентативная точка данных, и это может быть одно из наблюдений или просто возможное значение для наблюдения. В случае 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 

{.ezlazyload}

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

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

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

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

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

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

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

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

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

$$
SSE = \ sum \ limits_ {i = 1} ^ K \ sum \ limits_ {j = 1} ^ {\ text {размер кластера}} d ((centroid) _i, (instance) _j) ^ 2
$

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

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

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

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

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

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

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

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

{.ezlazyload}

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

{.ezlazyload}

{.ezlazyload}

{.ezlazyload}

Один из алгоритмов, который приблизительно решает эту проблему, называется 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 в Core Java непросто. Вы можете найти полный рабочий код здесь , но мы предоставим короткую документацию вспомогательного класса, DataSet и реализации самого алгоритма:

• Набор данных Class DataSet
  • Class Record - вложенный класс, содержащий HashMap<String, Double> котором хранится одна строка таблицы с ключом, соответствующим имени атрибута, и значением, соответствующим его, ну, значению.
  • Поля:
    • attrNames - список имен атрибутов
    • records - список Record s
    • minimums и maximums - минимумы и максимумы для каждого атрибута, которые будут использоваться для генерации случайного значения между ними.
    • indicesOfCentroids - список центроидов кластера.
  • DataSet(String csvFileName) throws IOException - конструктор, считывает данные из предоставленного .csv и инициализирует ими поля класса.
  • HashMap<String, Double> calculateCentroid(int clusterNo) - пересчитывает центроид для данного кластера.
  • LinkedList<HashMap<String,Double>> recomputeCentroids(int K) - пересчитывает все K центроидов.
  • HashMap<String, Double> randomFromDataSet() - возвращает случайную точку данных из всех доступных точек данных из набора данных (она нужна нам для инициации первого центроида).
  • public HashMap<String,Double> calculateWeighedCentroid() - вычисляет расстояние между всеми точками от выбранных в данный момент центроидов и взвешивает их все в соответствии с этим расстоянием, так что наиболее вероятно будет выбрана наиболее удаленная, а затем выбирает одну из них выбор рулетки ...)
  • static Double euclideanDistance(HashMap<String, Double> a, HashMap<String, Double> b) - вычисляет расстояние между двумя точками данных.
  • Double calculateTotalSSE(LinkedList<HashMap<String,Double>> centroids) - вычисляет SSE всех кластеров.

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

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

 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<HashMap<String, Double>> kmeanspp(DataSet data, int K) { 
 LinkedList<HashMap<String,Double>> centroids = new LinkedList<>(); 
 
 centroids.add(data.randomFromDataSet()); 
 
 for(int i=1; i<K; i++){ 
 centroids.add(data.calculateWeighedCentroid()); 
 } 
 
 return centroids; 
 } 
 
 /* K-Means itself, it takes a dataset and a number K and adds class numbers 
 * to records in the dataset */ 
 static void kmeans(DataSet data, int K){ 
 // Select K initial centroids 
 LinkedList<HashMap<String,Double>> 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 

Запуск этого кода приводит к созданию нового файла sampleClustered.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 и выбрать из него центроид. Выполнение этого эффективно разделит этот кластер и уменьшит общее SSE больше, чем выбор какой-то случайной точки.

Выбросы

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

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

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

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

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

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

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

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

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

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

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

{.ezlazyload}

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

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

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

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

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

Тогда статистика Хопкина выглядит так:

$$
H = \ frac {\ sum \ limits_ {i = 1} ^ m u_i} {\ sum \ limits_ {i = 1} ^ m u_i + \ sum \ limits_ {i = 1} ^ m w_i}
$

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

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

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

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

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

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

{.ezlazyload}

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

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

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

{.ezlazyload}

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

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

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

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

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

{.ezlazyload}

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

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

• K-режимы - центроид - это элемент, созданный путем выбора наиболее частого появления в кластере для каждого атрибута.
• K-Medoids - похоже на среднее значение, но ограничивается тем, чтобы быть фактическим членом набора данных, а не просто возможным значением.
• K-Median - вместо среднего мы используем медиану или «средний элемент» для каждого атрибута, чтобы создать наш центроид.
• Кластеризация ожиданий - максимизация (EM) с использованием моделей гауссовой смеси (GMM) - обнаруживает эллиптические формы, используя как среднее значение, так и стандартное отклонение для определения принадлежности к кластеру.

Заключение

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