Реализация алгоритма K-средних кластеризации изображений

алгоритм

0. Кластеризация изображений

0.1 Что такое кластеризация изображений?

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

Когда объект кластеризации представляет собой изображение, это называется кластеризацией изображения.

Более подробное введение см. в ссылке [1] в конце текста.

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

0.2 Классификация алгоритмов кластеризации

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

По масштабу кластеризации методы кластеризации можно разделить на следующие три типа:

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

Следующая часть в основном знакомитK-meansметод кластеризации.

1. Алгоритм кластеризации K-средних

K-meansАлгоритм представляет собой алгоритм кластеризации на основе расстояния, также известный какK均值илиK平均, также часто называемый Ллойдом (Lloyd)алгоритм. Он итеративно делит каждую точку в наборе данных на ближайший к ней кластер, а расстояние относится к расстоянию от точки данных до центра кластера.

1.1 Основные принципы K-средних

K-meansИдея алгоритма очень проста: для заданного набора выборок в соответствии с расстоянием между выборками выборки делятся наKкластеры. Соединяйте данные в кластеры как можно теснее, а расстояние между кластерами делайте как можно большим.

Kmeansшаг:

  1. случайная инициализацияkкоординаты центра скопления
  2. Подсчитайте все объекты в наборе данных, чтобыkрасстояния от центров кластеров и разделить точки данных на ближайшие кластеры
  3. Для каждого кластера пересчитайте центроид кластера, который является средним значением координат узлов в текущем кластере.
  4. Повторяйте шаги 2 и 3 до сходимости

Условия расторжения:

  • больше никаких перераспределений
  • Достигнуто максимальное количество итераций
  • Все классовые центры перемещаются меньше определенного значения

K-meansпроблема

  1. Жадные алгоритмы: часто застревают в локальных оптимумах

    • Количество учебных центровKвыбор
    • выбор начальной точки

  2. Чувствителен к шуму или выбросам

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

  3. Влияние формы точки выборки на кластеризацию

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

1.2 Параметры в K-средних

1. Значение К

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

Метод выбора:

  1. elbow methodрисуяKи диаграмму взаимосвязи функции потерь, выберите точку перегибаKценность. То есть попробуйте с несколькими значениями и выберите поворотный момент, когда индекс кластеризации оптимален или улучшен.
  2. Выбор опыта. Определить несколько на основе человеческого опытаK, несколько случайных центров инициализации выбирают наиболее подходящий эмпирически.

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

elbow methodТакже известный как «метод локтя», он использует тенденцию изменения суммы квадратов ошибок (SSE) в качестве метода выбора.Kпоказатель стоимости.

SSE = \Sigma_{i=1}^{k} \Sigma_{p\in C_i}|p-m_i|^2

в,C_iпервыйiкластеры,pдаC_iточки выборки в ,m_iдаC_iцентр массы,SSE— ошибка кластеризации всех выборок, указывающая на качество эффекта кластеризации.

Как показано на рисунке ниже, когдаKКогда значение равно 2~7, соответствующий результат кластеризации, когдаK=5когда эффект наилучший.

2. Начальный центр кластера (центроид)

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

Общий метод выбора начального центроида:

  • случайный выбор
  • Kmeans++Способ
    • Центр первого класса -> выбран случайным образом
    • ПомнитеD(x)для точки данныхxрасстояние до ближайшего центра скопления
    • Выберите следующий центр кластера с вероятностью, пропорциональнойD(x)^2
    • И так далее, пока неKКусок.

3. Метрики расстояния

расстояниеK-meansИндекс для измерения сходства точек выборки в кластере.

K-meansНаиболее часто используемые методы измерения расстояния:

  • Евклидово расстояние
  • косинусное сходство
  • Манхэттенское расстояние

2. sklearn, реализованный K-means

Pythonсерединаsklearnпредоставлена ​​библиотекаK-meansМетод реализации кластеризации можно вызвать напрямую.

Для кластеризации изображений нам нужно извлечь функции, представляющие содержимое изображения.x_i,x_iдаdвектор пространственных признаков. имеютNизображение, вектор признаков которого выражается какX=(x_1, x_2, x_3,....x_n), размерность(n, d).

Пример:

from sklearn.cluster import KMeans
import numpy as np

# X表示一组图像的特征向量
X = np.array([[1, 2], [1, 4], [1, 0],
           [4, 2], [4, 4], [4, 0]])
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
kmeans.labels_
# array([0, 0, 0, 1, 1, 1], dtype=int32)
kmeans.predict([[0, 0], [4, 4]])
# array([0, 1], dtype=int32)
kmeans.cluster_centers_
# array([[ 1.,  2.],
#        [ 4.,  2.]])

2.1 Класс KMeans

class sklearn.cluster.KMeans(n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=1, algorithm='auto')

параметр:

параметр значение
n_clsuters int, необязательно, по умолчанию8. Количество кластерных центров, то есть количество кластеров
init {‘k-means++’, 'random'или ndarray}, метод инициализации центроидов, по умолчанию'k-means++',‘random’Случайным образом выберите начальные центроиды из обучающих данных.Если вы передаете ndarray, это должно выглядеть так(n_clusters, n_features)и дайте начальный центроид
n_init int,дефолт10, инициализировать количество раз для запуска алгоритма с разными центроидами, а окончательное решение является оптимальным результатом, выбранным в смысле инерции
max_iter int,дефолт300, выполнить один разK-meansМаксимальное количество итераций алгоритма
tol floatтип, по умолчанию0.0001
precompute_distances {auto, True, False} Предварительное вычисление значений расстояния (быстрее, но занимает больше памяти), предварительный расчет не требуется при выполнении результатов кластеризации несколько раз на наборе данных.
verbose intтип, по умолчанию0, печатать ли промежуточный процесс, 0 не печатать
random_state intтип,RandomStateэкземпляр илиNone, необязательно, по умолчаниюNone. еслиint,random_stateявляется начальным числом, используемым генератором случайных чисел, еслиRandomStateпример,random_stateявляется генератором случайных чисел, если онNone, генератор случайных чиселnp.randomизRandomStateПример
n_jobs intТип, объем используемой вычислительной мощности при параллельном вычислении каждого n_init. если-1, все процессоры используются полностью, если указано как1, параллельный код не используется, что удобно для отладки. Если значение меньше -1, используйте(n_cpus + 1 + n_jobs). заn_jobs = -2, использоватьn_cpus-1.
algorithm по желанию值'auto', 'full','elkan'. «полный» — это традиционный алгоритм K-средних, «elkan» — это алгоритм K-средних elkan, значение по умолчанию «auto» будет решать, как выбрать «full» и «elkan» в зависимости от того, являются ли значения данных разреженными. . В общем, выберите «elkan» для плотных данных и «full» в противном случае.

Основные свойства:

Атрибуты значение
cluster_centers_ vector [n_clsuters, n_features], координаты центра каждого кластера
Labels_ категориальная метка для каждых данных, начиная с 0
inertia_ floatТип, сумма расстояний от каждой точки данных до центра тяжести ее кластера, используемая для оценки того, подходит ли количество кластеров.

2.2 Метод класса KMeans

1. fit()

Сгруппируйте набор данных после того, как Kmeans определит категорию.

определение:

def fit(self, X, y=None)
    random_state = check_random_state(self.random_state)
    X = self._check_fit_data(X)

    self.cluster_centers_, self.labels_, self.inertia_, self.n_iter_ = \
        k_means(
            X, n_clusters=self.n_clusters, init=self.init,
            n_init=self.n_init, max_iter=self.max_iter, verbose=self.verbose,
            precompute_distances=self.precompute_distances,
            tol=self.tol, random_state=random_state, copy_x=self.copy_x,
            n_jobs=self.n_jobs, algorithm=self.algorithm,
            return_n_iter=True)
    return self

Внутренний вызовk_meansФункция выполняет кластеризацию и возвращаетself.

перечислитьk_means()функция, которая возвращаетself.cluster_centers_,self.labels_, self.inertia_, self.n_iter_.

  • self.cluster_centers_: центр кластера, форма(k, n_features)
  • self.labels_:int, значение индекса кластера, форма(n_samples,)
  • self.inertia_: значение искажения кластеризации (сумма квадратов всех наблюдаемых расстояний в обучающей выборке)
  • self.n_iter_: количество итераций, соответствующее наилучшему результату, только еслиreturn_n_iterустановить какTrueвернуться, когда.

2. predict()

Определить категорию по результатам кластеризации

def predict(self, X)
  • X:{array, sparse matrix}, форма[n_samples, n_features]возвращаемое значение:
  • labels:array, форма[n_samples,]. Каждый пример принадлежит индексу класса кластера.

3. fit_predict

def fit_predict(self, X, y=None)
    return self.fit(X).labels_

возвращаемое значение:

  • labels:array, форма[n_samples,]. Значение индекса класса кластера, к которому принадлежит каждый пример.

Вычислите кластеризацию и предскажите индекс кластера для каждой выборки.

эквивалентно вызовуfit(X)метод, вызовpredict(X)функция.

Примечание. В этой функции возвращается свойство self.fit(X).labels_.

4. transform

def transform(self, X)

Преобразуйте X в пространство кластерных расстояний

возвращаемое значение:

  • X_new:array, форма[n_samples, k]

5. fit_transform

def fit_transform(self, X, y=None)

выполнять операции кластеризации иXТрансформируйтесь в дальнее пространство.

эквивалентно вызовуfit(X)метод, вызовtransform(X)функцию, но более эффективную.

Важно, метод Kmeans в sklearn не может указывать метод метрики расстояния, и по умолчанию используется евклидово расстояние.

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

От:Кластерный анализ — какая метрика расстояния используется kmeans sklearn? - IT House - Сообщество разработчиков программного обеспечения для обмена технологиями

3. Scipy, реализованный K-means

scipyТакже реализовано в библиотекеK-meansалгоритм.

Индекс центра или кластерный индекс также известен как"код", таблица отображения кода в центр называется"кодовая книга".

3.1 функция kmeans

использоватьkmeansфункция для кластеризации, которая требует двух шагов для достижения

  1. использоватьkmeansгенерация функцийcodebookи значение искажения
  2. использоватьvqфункция будетcodebookНазначьте каждому наблюдению и получите расстояние от каждого наблюдения до ближайшей центральной точки.

Пример:

import scipy
from scipy.cluster.vq import kmeans, vq, whiten
import numpy as np

#生成待聚类的数据点,这里生成了20个点,每个点4维:
points=scipy.randn(20,4) 

data=whiten(points) # 将原始数据做归一化处理
#返回聚类中心的映射表和损失
codebook, variance = kmeans(data, 4) 
# 使用vq函数根据聚类中心对所有数据进行分类，vq的输出所有数据的label和距离
code, distance = vq(data, codebook)

# 结果
>>> codebook # (4,4)
array([[-1.227829  , -0.41256122, -0.1342359 , -0.98257834],
       [ 1.01190005, -0.34999089, -0.13180372,  0.06394479],
       [ 0.01156929, -0.39212056,  1.86893218, -0.34921357],
       [ 0.21946277,  1.36809613,  0.87196001,  0.9213216 ]])
>>>variance
1.221658211170926

>>> code
array([2, 0, 0, 2, 0, 2, 1, 3, 1, 1, 3, 0, 1, 0, 1, 1, 3, 2, 3, 2],
      dtype=int32)
>>>distance
array([1.32927696, 0.99594691, 1.38351644, 1.22323281, 1.12605626,
       2.04444249, 0.55554746, 2.06947197, 1.44928466, 1.09481098,
       1.60957745, 1.07210177, 1.3848659 , 0.6393925 , 0.69392457,
       1.06200234, 1.09091552, 0.87726365, 0.76938663, 1.96214695])

определение функции kmeans:

def kmeans(obs, k_or_guess, iter=20, thresh=1e-5, check_finite=True)

параметр:

  • obs:ndarray,MxNМассив, каждая строка которого представляет вектор наблюдения. Характеристики должны быть введеныwhitenобработка функций
  • k_or_guess:intилиndarray, количество сгенерированных центральных точек, каждой центральной точке присваиваетсяcode, который также является генерируемым центроидомcode_bookИндекс строки в матрице для выбора начальных k-центров путем случайного выбора наблюдений из матрицы наблюдений. Вы также можете пройти вkxNМассив s для указания начальных k центральных точек.
  • iter:int, необязательное значение.Количество раз для запуска алгоритма k-средних, который возвращает вариант с наименьшим искажениемcode book, еслиk_or_guessМассив параметров задает начальный центроид, этот параметр будет проигнорирован,Этот параметр не представляет количество итераций алгоритма k-средних..
  • thresh:float, необязательное значение. Если изменение искажения с момента последней итерации k-средних меньше или равно пороговому значению, алгоритм k-средних завершается.
  • check_finite:bool, необязательное значение, значение по умолчанию:True. Проверять, содержит ли входная матрица только конечные числа. Отключение может повысить производительность, но может вызвать проблемы (сбой, завершение), если входные данные содержат бесконечность или NaN.

возвращение:

  • codebook:ndarray, измерение, состоящее из k центроидов(k,N)массив
  • distortion:floatтип, расстояние между наблюдаемым значением и сгенерированной центральной точкойСреднее евклидово расстояние (неквадратное). Обратите внимание, что вK-meansСтандартное определение искажения в алгоритме — это сумма квадратов расстояний.

Уведомление: 1. В функции kmeans параметр iter используется для указания количества запусков алгоритма K-средних, а не количества итераций. Условие завершения алгоритма можно указать только через параметр thresh. 2. Метрика расстояния использует среднее евклидово расстояние (неквадратное).

определение функции vq:

def vq(obs, code_book, check_finite=True)

будетcode bookкаждый изcodeотнесены к наблюдениям. существуетMXNКаждый вектор наблюдения в массиве сcode bookсравните центроиды вcode.

obsФункции в должны иметь единичную дисперсию, которую можно получить, передав их вwhitenфункцию для реализации.code bookможно использоватьK-meansалгоритм или другой алгоритм кодирования для создания.

параметр:

  • obs:MxNМассив, каждая строка представляет наблюдение. Особенности должны пройтиwhitenобработка функций.
  • code_book:ndarray. Обычно генерируется с использованием алгоритма k-средних, каждая строка представляет отдельныйcode, столбцы представляютcodeсобственные значения.
  • check_finite:bool, необязательное значение, по умолчаниюTrue. Проверять, содержит ли входной массив только конечные значения. Отключение может повысить производительность, но может вызвать проблемы (сбой, завершение), если входные данные содержат бесконечность или NaN.

возвращаемое значение:

  • code: ndarray, массив длины M, содержащий данные для каждого наблюденияcode book.
  • dist: ndarray,(M,)Значение искажения каждого наблюдения до ближайшего кода.

3.2 функция kmeans2

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

scipy.cluster.vq.kmeans2(data, k, iter=10, thresh=1e-05, minit='random', missing='warn', check_finite=True)

параметр:

  • data:ndarray,(M,N)Массив наблюдений M с размерностями N.
  • k:int or ndarray, количество кластеров. еслиminitпараметрmatrix, или если даноndarray, который интерпретируется как начальная кластеризация.
  • iter:int, необязательное значение,k-meansалгоритм работаетколичество итераций, обратите внимание, что сkmeansфункциональныйiterПараметры имеют разные значения.
  • thresh:float, необязательное значение, не используется
  • minit:str, необязательное значение, метод инициализации. по желаниюrandom, points,++иmatrix.
    • random: генерировать k центроидов из гауссова, среднее значение и дисперсия оцениваются по данным
    • points: случайным образом выберите k наблюдений (строк) из данных в качестве начальных центров
    • ++:в соответствии сkmeans++метод выбрать k наблюдений
    • matrix: интерпретирует параметр k как массив (k,M) начальных центроидов
  • missing:str, необязательное значение, метод, используемый для решения пустого кластера, доступные методы:warnиraise.
    • warn: дать предупреждение и продолжить
    • raise: поднятыйClusterErrorи завершить алгоритм
  • check_finite:bool, необязательно, проверять, что входная матрица содержит только конечные числа, по умолчаниюTrue

возвращаемое значение:

  • centroid:ndarray: массив (k, N), представляющийk-meansцентральная точка последней итерации метода
  • label:ndarray, значение кода или индекса для каждого наблюдения. label[i] — код или индекс центроида, к которому ближе всего i-е наблюдение

Пример

import scipy
from scipy.cluster.vq import kmeans2, whiten
import numpy as np

#生成待聚类的数据点,这里生成了20个点,每个点4维:
points=scipy.randn(20,4) 

data=whiten(points) # 将原始数据做归一化处理
centroid, label = kmeans2(data, 5)

# 结果
>>> centroid
array([[ 0.52132816,  0.97577703, -0.30863464, -1.30546523],
       [-0.27344139, -0.81129939, -0.59560322,  0.47788319],
       [ 1.99658961, -0.10701021,  1.09921144,  0.51397034],
       [-0.37598454,  1.72180727, -0.18127439,  0.58114466],
       [ 0.25895367, -0.01881385,  1.25681737,  0.03119893]])
>>> label
array([1, 0, 3, 0, 1, 1, 2, 4, 0, 1, 1, 0, 4, 4, 0, 3, 1, 4, 3, 2],
      dtype=int32)

4. Ссылки

[1]Предварительное исследование различных алгоритмов кластеризации - Zheng Han Andrew.Hann - Blog Park

[2]Метод извлечения признаков: Kmeans кластеризации — Блог Jack_Kuo — Блог CSDN

[3]sklearn.cluster.KMeans — документация scikit-learn 0.17

[4]Кластеризация K-средних и векторное квантование (scipy.cluster.vq) — Справочное руководство по SciPy v1.3.1

Категории