Почему K означает кластеризацию?
Кластеризация K среднего используется для классификации наборов данных в K кластеров/категорий на основе точек данных/признаков. Попробуем разобраться на реальном примере. Задумывались ли вы, как YouTube заполняет для вас список видео, когда вы открываете приложение, или HotStar заполняет ваш список веб-сериалов, когда вы открываете приложение? Все они используют рекомендательные системы, чтобы рекомендовать контент на основе категоризации. Они классифицируют зрителей с помощью алгоритмов машинного обучения по различным категориям, и на основе этой категории вы получаете рекомендации. Если вы когда-либо смотрели спортивные и научно-фантастические фильмы, ваш список будет заполнен рекомендациями о спортивных и научно-фантастических фильмах. Эта категоризация определяется не только историей, есть и другие параметры, такие как демографические данные, язык контента и т. д. Возвращаясь к теме Кластеризация K Mean помогает нам выполнять категоризацию на основе точек данных/функций. Это один из алгоритмов, которые можно использовать для категорий. Он может иметь различные приложения, начиная от классификации документов, категоризации клиентов для электронной коммерции и платформ потоковой передачи песен / видео.
Иллюстрация
Как алгоритм работает внутри?
Мы предоставляем набор входных данных и желаемое количество кластеров для классификации. Основная цель здесь — сгруппировать все наборы данных в k кластеров. Наборы данных в одном кластере будут иметь схожие функции. Давайте попробуем визуализировать на приведенном выше примере, что изначально объекты в форме звезды и круга являются частью одного и того же кластера или визуально трудно разделить на разные наборы. После применения кластера K Mean форма круга была сгруппирована в одну группу, а объекты в форме звезды были сгруппированы в другой набор. В этом суть алгоритма группировки объектов с похожими характеристиками, такими как круглые формы, сгруппированные вместе. Здесь значение K равно 2. K Mean Cluster вращается вокруг принципа евклидова расстояния.
Евклидово расстояние
Он помогает рассчитать расстояние между двумя точками. Давайте попробуем понять это на примере, предположим, что у нас есть две точки (A, B) в двумерной плоскости x-y. Мы хотим рассматривать точки A и B как центральные точки и классифицировать 10 других точек на основе евклидова расстояния от A, B. Точки, которые ближе к A с использованием формулы евклидова расстояния, будут частью группы/категории A, а точки, которые ближе к B, основанный на евклидовом расстоянии, будет частью группы/категории B.
Математический вывод с использованием теоремы Пифагора
Как работает алгоритм?
Шаг 1
Определите количество категорий/кластеров. Другими словами, определите значение К.
Шаг 2
Инициализируйте центроид начального кластера со случайными значениями из набора данных.
Шаг 3
Рассчитайте евклидово расстояние каждой точки данных от центра тяжести кластеров. Назначьте точку данных кластеру, который ближе к ней.
Евклидово расстояние Евклидово расстояние — Википедия
Шаг 4
Измените центроидное значение кластеров, взяв среднее значение всех точек данных, входящих в этот кластер.
Шаг 5
Продолжайте повторять шаги 3 и 4 до тех пор, пока изменение центроида кластера не станет минимальным, или перетасовка точек данных между кластерами не станет незначительной, или мы не достигнем предопределенного количества итераций.
Код Пояснение
Код был написан на ядре java без использования каких-либо фреймворков. Цель здесь состоит в том, чтобы иметь базовую реализацию примера в java. Модели искусственного интеллекта основаны на математике и не зависят от языка. Код можно выполнить, используя приведенный ниже пример. Класс принимает три аргумента: список точек данных, количество кластеров и числовые характеристики.
public static void main(String[] args) {
// Data set
List<Double[]> dataSet = new ArrayList<>();
Double[] data1 = { .23d, .34d, .67d };
Double[] data2 = { .23d, .84d, .47d };
Double[] data3 = { .21d, .64d, .97d };
Double[] data4 = { .13d, .84d, .899d };
dataSet.add(data4);
dataSet.add(data3);
dataSet.add(data2);
dataSet.add(data1);
KMeanClustering clustering = new KMeanClustering(dataSet, 2, 3);
HashMap<String, Double[]> clusterCentroidValues = clustering.buildCluster();
clusterCentroidValues.forEach((k, val) -> {
System.out.println(" ClusterId/CategoryId: " + k + " Centriod values: " + Arrays.toString(val));
});
// Test with new point
Double[] data5 = { .131d, .841d, .89d };
String category = clustering.predictCategory(data5);
System.out.println(category);
}
Пример рабочего кода Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Random;
public class KMeanClustering {
private List<Double[]> featuresData;
private HashMap<String, List<Double[]>> clusters;
private HashMap<String, Double[]> clusterCentroidValues;
private int numberOfClusters;
private int numberOfFeatures;
private int numberEpochs = 1000;
public KMeanClustering(List<Double[]> featuresData, int numberOfClusters, int numberOfFeatures) {
this.featuresData = featuresData;
this.numberOfClusters = numberOfClusters;
this.numberOfFeatures = numberOfFeatures;
this.initializeModel();
}
public HashMap<String, Double[]> buildCluster() {
initialClustersCreation();
return refiningKClusters();
}
public int getRandomNumberUsingNextInt(int min, int max) {
Random random = new Random();
return random.nextInt(max - min) + min;
}
/*
* This method creates k clusters and initialize their value to initial random
* values
*
*/
private void initializeModel() {
clusters = new HashMap<>();
clusterCentroidValues = new HashMap<>();
for (int i = 0; i < numberOfClusters; i++) {
List<Double[]> list = new ArrayList<>();
int randomIndex = getRandomNumberUsingNextInt(0, featuresData.size());
Double[] initialValues = featuresData.get(randomIndex);
String clusterId = "" + i;
clusterCentroidValues.put(clusterId, initialValues);
System.out.println(" Initial centroid value for Cluster: " + clusterId + " Values : "
+ Arrays.toString(initialValues));
clusters.put(clusterId, list);
}
}
/*
* This method classify data points into cluster for first time .After this
* method execution will have datapoints classified/divided into initial k
* clusters.
*/
public void initialClustersCreation() {
coreClassifyingLogic(featuresData);
}
/*
* This is core processing logic in which we keep iterating over data set and
* keep classifying them based on euclidean distance from centroid of cluster.
* The centroid of cluster also keeps getting changed based on mean datapoints
* in that cluster. This is important step to keep cluerer improving. The
* process stops when we reach number of epochs defined . The stopping logic can
* be driven by number epochs , centroid values not changing substancially ,
* data points not moving across cluster . For simiplicity sake epoch has been
* used.
*/
private HashMap<String, Double[]> refiningKClusters() {
while (keepOnClassifying()) {
for (String key : clusters.keySet()) {
List<Double[]> tempfeaturesData = clusters.get(key);
// This is move cluster value based on mean of the data points in the cluster to
// improve clustering further
// TODO this could be easily done in core processing method for code reuse
// perspective
Double[] clusterValues = clusterCentroidValues.get(key);
Double[] newCentriodValues = new Double[clusterValues.length];
Arrays.fill(newCentriodValues, 0.0d);
for (int i = 0; i < tempfeaturesData.size(); i++) {
Double[] data = tempfeaturesData.get(i);
for (int j = 0; j < newCentriodValues.length; j++) {
newCentriodValues[j] = newCentriodValues[j] + data[j];
}
}
// TODO this can be easily done in previous loop from code optimization
// perspective
for (int i = 0; i < newCentriodValues.length; i++) {
newCentriodValues[i] = newCentriodValues[i] / tempfeaturesData.size();
}
System.out.println(" Old centroid value for Cluster: " + key + " Old Value : "
+ Arrays.toString(clusterValues) + " New Values: " + Arrays.toString(newCentriodValues)
+ " Previous Number of datapoints in this cluster: " + tempfeaturesData.size());
// Reassign new mean values to centroids based on mean calculation done above.
clusterCentroidValues.put(key, newCentriodValues);
// This is method does reassignment of Cluster based on eulucdean distance
coreClassifyingLogic(tempfeaturesData, key);
}
}
return clusterCentroidValues;
}
/*
*
*/
private boolean keepOnClassifying() {
if (numberEpochs <= 0) {
return false;
}
numberEpochs = numberEpochs - 1;
// TODO Add logic to consider other parameter lik clsutercentroid value not
// changes and cluser data point not shuffling between clusters
return true;
}
/*
*
*/
private void coreClassifyingLogic(List<Double[]> tempfeaturesData) {
for (int i = 0; i < tempfeaturesData.size(); i++) {
Double euclideanDistance = Double.MAX_VALUE;
String destinationCluster = "";
Double[] data = tempfeaturesData.get(i);
for (String clusterKey : clusterCentroidValues.keySet()) {
Double[] clusterCentroids = clusterCentroidValues.get(clusterKey);
Double sumSquareDistance = 0.00d;
for (int k = 0; k < data.length; k++) {
Double tempDistance = (clusterCentroids[k] - data[k]);
Double squareDistance = Math.pow(tempDistance, 2);
sumSquareDistance = sumSquareDistance + squareDistance;
}
Double clusterSpecificDistance = Math.sqrt(sumSquareDistance);
if (clusterSpecificDistance.compareTo(euclideanDistance) < 0) {
euclideanDistance = clusterSpecificDistance;
destinationCluster = clusterKey;
}
}
List<Double[]> classifiedData = clusters.get(destinationCluster);
if (classifiedData == null) {
classifiedData = new ArrayList<>();
}
classifiedData.add(data);
}
}
/*
*
*/
private void coreClassifyingLogic(List<Double[]> tempfeaturesData, String previousKey) {
List<Integer> indexToBeRemoved = new ArrayList<>();
for (int i = 0; i < tempfeaturesData.size(); i++) {
Double euclideanDistance = Double.MAX_VALUE;
String destinationCluster = "";
Double[] data = tempfeaturesData.get(i);
for (String clusterKey : clusterCentroidValues.keySet()) {
Double[] clusterCentroids = clusterCentroidValues.get(clusterKey);
Double sumSquareDistance = 0.00d;
for (int k = 0; k < data.length; k++) {
Double tempDistance = (clusterCentroids[k] - data[k]);
Double squareDistance = Math.pow(tempDistance, 2);
sumSquareDistance = sumSquareDistance + squareDistance;
}
Double clusterSpecificDistance = Math.sqrt(sumSquareDistance);
if (clusterSpecificDistance.compareTo(euclideanDistance) < 0) {
euclideanDistance = clusterSpecificDistance;
destinationCluster = clusterKey;
}
}
if (!destinationCluster.equalsIgnoreCase(previousKey)) {
List<Double[]> classifiedData = clusters.get(destinationCluster);
if (classifiedData == null) {
classifiedData = new ArrayList<>();
}
classifiedData.add(data);
// Cannot remove index in same iteration because of concurrent modification
// exception
indexToBeRemoved.add(i);
}
}
for (int i = 0; i < indexToBeRemoved.size(); i++) {
tempfeaturesData.remove(i);
}
}
public String predictCategory(Double[] data) {
Double euclideanDistance = Double.MAX_VALUE;
String destinationCluster = "";
for (String clusterKey : clusterCentroidValues.keySet()) {
Double[] clusterCentroids = clusterCentroidValues.get(clusterKey);
Double sumSquareDistance = 0.00d;
for (int k = 0; k < data.length; k++) {
Double tempDistance = (clusterCentroids[k] - data[k]);
Double squareDistance = Math.pow(tempDistance, 2);
sumSquareDistance = sumSquareDistance + squareDistance;
}
Double clusterSpecificDistance = Math.sqrt(sumSquareDistance);
if (clusterSpecificDistance.compareTo(euclideanDistance) < 0) {
euclideanDistance = clusterSpecificDistance;
destinationCluster = clusterKey;
}
}
return destinationCluster;
}
public static void main(String[] args) {
// Data set
List<Double[]> dataSet = new ArrayList<>();
Double[] data1 = { .23d, .34d, .67d };
Double[] data2 = { .23d, .84d, .47d };
Double[] data3 = { .21d, .64d, .97d };
Double[] data4 = { .13d, .84d, .899d };
dataSet.add(data4);
dataSet.add(data3);
dataSet.add(data2);
dataSet.add(data1);
KMeanClustering clustering = new KMeanClustering(dataSet, 2, 3);
HashMap<String, Double[]> clusterCentroidValues = clustering.buildCluster();
clusterCentroidValues.forEach((k, val) -> {
System.out.println(" ClusterId/CategoryId: " + k + " Centriod values: " + Arrays.toString(val));
});
// Test with new point
Double[] data5 = { .131d, .841d, .89d };
String category = clustering.predictCategory(data5);
System.out.println(category);
}
}
Пожалуйста, обратитесь к комментариям метода и встроенным комментариям для более подробной информации.
Открытые вопросы
Как выбрать количество кластеров в первой точке?
Что такое К среднее ++?
