Как вы тестируете реализацию k-средних?

Отказ от ответственности: я разместил этот вопрос на Stackoverflow, но я подумал, что это лучше подходит для этой платформы.

Как вы тестируете свою собственную реализацию k-средних для многомерных наборов данных?

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

У тебя есть идея получше?

K-средство включает в себя стохастический компонент, поэтому очень маловероятно, что вы получите тот же результат, если у вас точно такая же реализация и вы не используете ту же начальную конфигурацию. Тем не менее, вы можете увидеть, согласуются ли ваши результаты с известными реализациями (не знаю о Matlab, но реализация алгоритма k-средних в R хорошо объяснена, см. Hartigan & Wong, 1979 ).

Что касается сравнения двух серий результатов, то по-прежнему существует проблема с переключением меток, если он должен запускаться несколько раз. Опять же, в пакете e1071 R есть очень удобная функция (; matchClasses()), которая может использоваться для поиска «наилучшего» отображения между двумя категориями в таблице двусторонней классификации. По сути, идея состоит в том, чтобы переставить строки, чтобы максимизировать их согласование со столбцами, или использовать жадный подход и переставлять строки и столбцы, пока сумма по диагонали (необработанное соглашение) не станет максимальной. Коэффициент согласия, как статистика Каппа , также предоставляются.

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

Сопоставление двух наборов результатов легко вычислить, поскольку информация, которую вы получаете в тесте, может быть представлена ​​в виде набора из трех кортежей: первый компонент (многомерная) точка, второй - (произвольная) метка кластера предоставляется вашим алгоритмом, а третий - (произвольная) метка кластера, предоставляемая эталонным алгоритмом. Построить по $k$$k$таблица классификации для пар меток: если результаты совпадают, она будет кратна матрице перестановок. То есть каждая строка и каждый столбец должны иметь ровно одну ненулевую ячейку. Это простая проверка для программирования. Также очень просто отследить небольшие отклонения от этого идеала до отдельных точек данных, чтобы вы могли точно увидеть, как эти два ответа отличаются, если они различаются вообще. Я бы не стал подсчитывать статистические показатели согласия: либо есть совершенное согласие (вплоть до перестановки), либо его нет, и в последнем случае вам необходимо отследить все точки несогласия, чтобы понять, как они возникают. Результаты либо совпадают, либо нет; любое количество разногласий, даже в одной точке, нуждается в проверке.

Возможно, вы захотите использовать несколько видов наборов данных для тестирования: (1) опубликованные наборы данных с опубликованными результатами k-средних; (2) синтетические наборы данных с очевидными сильными кластерами; (3) синтетические наборы данных без очевидной кластеризации. (1) - хорошая дисциплина, которую следует использовать всякий раз, когда вы пишете какую- либо программу по математике или статистике. (2) это легко сделать многими способами, например, путем генерации некоторых случайных точек, которые будут служить центрами кластеров, а затем генерации облаков точек путем случайного смещения центров кластеров на относительно небольшие величины. (3) предоставляет некоторые случайные проверки, которые потенциально могут обнаружить неожиданное поведение; опять же, это хорошая общая дисциплина тестирования.

Кроме того, рассмотрите возможность создания наборов данных, которые подчеркивают алгоритм, лежа на границах между крайними решениями. Это потребует творческого подхода и глубокого понимания вашего алгоритма (который, вероятно, у вас есть!). Одним примером, который я хотел бы проверить в любом событии, были бы наборы векторов вида где v - вектор без нулевых компонентов, и i принимает последовательные целые значения 0 , 1 , 2 , … , n - 1 . Я также хотел бы проверить алгоритм на множествах векторов, которые образуют равносторонние многоугольники. В любой ситуации, случаи , когда п является не$i \mathbb{v}$$\mathbb{v}$$i$$0, 1, 2, \ldots, n-1$$n$кратно , особенно интересны, в том числе , где п есть меньше , чем к . Общим для этих ситуаций является то, что (а) они используют все измерения проблемы, но (б) правильные решения геометрически очевидны, и (в) существует множество правильных решений.$k$$n$$k$

$d \ge 2$$\mathbb{u}$$\mathbb{v}$$2d$$\mathbb{x}$$\mathbb{z}$$\mathbb{x}$$\mathbb{z}$

$\mathbb{y}$$\mathbb{w}$$\mathbb{x}$$\mathbb{y}$$\mathbb{x}$$\mathbb{y}$$d$$n$$\cos(2 \pi k / n) \mathbb{x} + \sin(2 \pi k / n) \mathbb{y}$$k$$0$$n-1$

Одним из очень простых «наивных» подходов было бы использование простых синтетических данных, для которых каждая реализация должна приводить к одним и тем же кластерам.

Пример в Python с import numpy as np:

test_data = np.zeros((40000, 4))
test_data[0:10000, :] = 30.0
test_data[10000:20000, :] = 60.0
test_data[20000:30000, :] = 90.0
test_data[30000:, :] = 120.0

Ибо n_clusters = 4это должно дать вам перестановку[30, 60, 90, 120]

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