Рубрики

K означает кластеризацию — Введение

Нам предоставляется набор данных элементов с определенными характеристиками и значениями для этих элементов (например, вектор). Задача состоит в том, чтобы классифицировать эти элементы по группам. Для этого мы будем использовать алгоритм kMeans; алгоритм обучения без присмотра.

обзор

(Это поможет, если вы будете думать о предметах как о точках в n-мерном пространстве). Алгоритм разделит элементы на k групп сходства. Чтобы вычислить это сходство, мы будем использовать евклидово расстояние в качестве измерения.

Алгоритм работает следующим образом:

  1. Сначала мы инициализируем k точек, называемых средними, случайным образом.
  2. Мы классифицируем каждый элемент в соответствии с его ближайшим средним значением и обновляем его координаты, которые являются средними значениями элементов, классифицированных в этом значении.
  3. Мы повторяем процесс для заданного числа итераций, и в конце у нас есть наши кластеры.

Упомянутые выше «точки» называются средними, потому что они содержат средние значения элементов, классифицированных в нем. Для инициализации этих средств у нас есть много вариантов. Интуитивно понятный метод заключается в инициализации средств случайных элементов в наборе данных. Другой метод заключается в инициализации средних значений при случайных значениях между границами набора данных (если для объекта элементы имеют значения в [0,3], мы инициализируем средние значения со значениями в [0,3]).

Вышеприведенный алгоритм в псевдокоде:

Initialize k means with random values

For a given number of iterations:
    Iterate through items:
        Find the mean closest to the item
        Assign item to mean
        Update mean

Читать данные

Мы получаем ввод в виде текстового файла («data.txt»). Каждая строка представляет элемент и содержит числовые значения (по одному для каждой функции), разделенные запятыми. Вы можете найти образец данных здесь.

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

def ReadData(fileName):

  

    # Прочитать файл, разбив по строкам

    f = open(fileName, 'r');

    lines = f.read().splitlines();

    f.close();

  

    items = [];

  

    for i in range(1, len(lines)):

        line = lines[i].split(',');

        itemFeatures = [];

  

        for j in range(len(line)-1):

            v = float(line[j]); # Преобразовать значение объекта в плавающее

            itemFeatures.append(v); # Добавить значение функции в dict

  

        items.append(itemFeatures);

  

    shuffle(items);

  

    return items;

Инициализировать средства

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

def FindColMinMax(items):

    n = len(items[0]);

    minima = [sys.maxint for i in range(n)];

    maxima = [-sys.maxint -1 for i in range(n)];

      

    for item in items:

        for f in range(len(item)):

            if (item[f] < minima[f]):

                minima[f] = item[f];

              

            if (item[f] > maxima[f]):

                maxima[f] = item[f];

  

return minima,maxima;

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

def InitializeMeans(items, k, cMin, cMax):

  

    # Initialize означает случайные числа между

    # мин и макс каждой колонки / функции

    f = len(items[0]); # количество функций

    means = [[0 for i in range(f)] for j in range(k)];

      

    for mean in means:

        for i in range(len(mean)):

  

            # Установить значение в случайное число с плавающей точкой

            # (добавление + -1, чтобы избежать широкого размещения среднего)

            mean[i] = uniform(cMin[i]+1, cMax[i]-1);

  

    return means;

Евклидово расстояние

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

def EuclideanDistance(x, y):

    S = 0; # Сумма квадратов разностей элементов

    for i in range(len(x)):

        S += math.pow(x[i]-y[i], 2);

  

    return math.sqrt(S); # Квадратный корень суммы

Обновление Средства

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

m = (m*(n-1)+x)/n

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

def UpdateMean(n,mean,item):

    for i in range(len(mean)):

        m = mean[i];

        m = (m*(n-1)+item[i])/float(n);

        mean[i] = round(m, 3);

      

    return mean;

Классифицировать предметы

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

def Classify(means,item):

  

    # Классифицировать элемент по среднему значению с минимальным расстоянием

    minimum = sys.maxint;

    index = -1;

  

    for i in range(len(means)):

  

        # Найти расстояние от элемента до среднего

        dis = EuclideanDistance(item, means[i]);

  

        if (dis < minimum):

            minimum = dis;

            index = i;

      

    return index;

Найти средства

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

Приведенная ниже функция принимает в качестве входных данных (количество желаемых кластеров), элементы и количество максимальных итераций и возвращает средние значения и кластеры. Классификация элемента хранится в массиве, а количество элементов в кластере — в.

def CalculateMeans(k,items,maxIterations=100000):

  

    # Найти минимумы и максимумы для столбцов

    cMin, cMax = FindColMinMax(items);

      

    # Инициализировать средства в случайных точках

    means = InitializeMeans(items,k,cMin,cMax);

      

    # Инициализировать кластеры, массив для хранения

    # количество предметов в классе

    clusterSizes= [0 for i in range(len(means))];

  

    # Массив для хранения кластера, в котором находится элемент

    belongsTo = [0 for i in range(len(items))];

  

    # Рассчитать средства

    for e in range(maxIterations):

  

        # Если не происходит изменение кластера, остановите

        noChange = True;

        for i in range(len(items)):

  

            item = items[i];

  

            # Классифицировать элемент в кластер и обновить

            # соответствующие средства.

            index = Classify(means,item);

  

            clusterSizes[index] += 1;

            cSize = clusterSizes[index];

            means[index] = UpdateMean(cSize,means[index],item);

  

            # Элемент изменен кластером

            if(index != belongsTo[i]):

                noChange = False;

  

            belongsTo[i] = index;

  

        # Ничего не изменилось, вернуть

        if (noChange):

            break;

  

    return means;

Найти кластеры

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

def FindClusters(means,items):

    clusters = [[] for i in range(len(means))]; # Начальные кластеры

      

    for item in items:

  

        # Классифицировать элемент в кластер

        index = Classify(means,item);

  

        # Добавить элемент в кластер

        clusters[index].append(item);

  

    return clusters;

Другими популярными мерами подобия являются:

1. Косинусное расстояние: определяет косинус угла между точечными векторами двух точек в n-мерном пространстве

2. Манхэттенское расстояние: вычисляется сумма абсолютных разностей между координатами двух точек данных.

3. Расстояние Минковского: оно также известно как обобщенная метрика расстояния. Может использоваться как для порядковых, так и для количественных переменных.

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

Эта статья предоставлена Антонисом Марониколакисом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

K означает кластеризацию — Введение

0.00 (0%) 0 votes