#algorithm #k-means
#алгоритм #k-средние
Вопрос:
Все алгоритмы k-средних так или иначе пытаются найти k точек, чтобы, если вы сопоставите любую точку из исходного набора данных с ближайшей точкой из этих k точек, вы бы минимизировали сумму квадратов расстояний до этих точек.
Проблема с этой функцией затрат:
Представьте следующий 1-мерный случай (т. Е. Числа вместо векторов) с k = 2. Давайте назовем основные точки истинности A и B такими, что A = -1 и B = 1. И давайте назовем точки оптимальным алгоритмом k-средних, который вернул бы C и D таким образом, чтобы C и D соответствовали A и B соответственно. Теперь предположим, что у нас есть большой набор данных, который был создан из точек вокруг A и B с некоторым нормальным распределением. Предполагая, что дисперсия достаточно велика, мы ожидаем, что процент точек из A будет положительным, а процент точек из B будет отрицательным, из-за этого эти точки будут сопоставлены с неправильными точками, и это сделало бы C и D ближе друг к другу, чем A и B, и, как следствие,дисперсия увеличивает C и D, оба приближаются к 0.
Решение этой проблемы?
Эта проблема кажется мне настолько фундаментальной, что я был уверен, что смогу найти что-то об этом, однако, когда я искал, я ничего не мог найти по этой проблеме. Итак, мой вопрос в том, есть ли какой-либо документ / алгоритм, который решает эту проблему и пытается ее решить? Даже для особых случаев, когда предполагается нормальное распределение данных или какие-либо другие предположения о распределении данных? Мне просто странно, что я нигде не нашел упоминания об этой проблеме, что когда-либо.
Ответ №1:
Эта проблема является универсальным явлением, связанным с так называемой ошибкой байесовской классификации, которая является наименьшей ошибкой, которую вы можете достичь, когда распределения классов перекрываются. (На практике классификаторы достигают худшего, чем эта теоретическая оценка.)
Это явно означает, что в случае перекрытий невозможно избежать процента неправильной классификации, каким бы ни был метод. Есть большие кошки и маленькие тигры.
На самом деле, это очень распространенная, если не повсеместная ситуация. Единственный способ улучшить его — использовать дополнительные функции для классификации, т. Е. Увеличить размерность пространства данных. Например, указание цвета в дополнение к размеру.
Комментарии:
1. Неужели нет никакого способа исправить это без добавления измерений? Разве нельзя попытаться найти 2 точки так, чтобы при условии, что дисперсия будет иметь ожидаемое k-среднее значение, подобное тому, что мы получили? Итак, мы могли бы взять k-средние, а затем применить какой-либо алгоритм, который попытался бы это исправить? Алгоритм должен в основном брать близкие точки из k-средних и на основе дисперсии пытаться отдалить их друг от друга.
2. Если классы перекрываются, вы не можете избежать ошибки классификации.
3. Но что, если меня не волнует классификация, а только расположение центров масс (k-средних). Мы можем оценить дисперсию каждого кластера и на основе этого найти k-точки так, чтобы, если мы будем рандомизировать точки вокруг них с одинаковой дисперсией и вычислять k-средние, мы получили бы те же k-средние, которые мы получили из данных. Я не думал о каком-либо способе сделать это, который не потребует огромного количества времени, но я сомневаюсь, что нет никакого способа.
4. @TomerWolberg: извините, я не понимаю, что вы пытаетесь сделать.
5. @TomerWolberg: рассматривали ли вы подход гауссовой смеси, возможно, подходящий для вашего случая?
Ответ №2:
В большинстве контекстов алгоритм k-средних определяется как задача оптимизации, которая минимизирует внутрикластерную дисперсию каждого кластера.
В случае бесконечной дисперсии данных проблема, с которой вы сталкиваетесь, — это проблема неединственности решения алгоритма k-средних. Поскольку истинная дисперсия обоих базовых распределений приближается к бесконечности, набор оптимальных решений для постановки задачи k-средних бесконечен. То есть любой набор средних возвращает точно такое же качество подгонки (теоретически.) На практике алгоритм k-средних просто переберет (конечный) шум в ваших данных и выберет произвольную пару средних.
Проще говоря, определение проблемы k-средних не подходит в описываемом вами случае бесконечной дисперсии. Обратите внимание, что в случае бесконечной дисперсии у вас гораздо большие проблемы, чем k-средние, не дающие полезного решения. Другие фундаментальные свойства (такие как Центральная предельная теорема) больше не гарантируются.
В случае конечной, но большой дисперсии мы ожидаем, что проблема k-средних будет плохо обусловлена. Чтобы понять, почему, рассмотрим Центральную предельную теорему (CLT) в контексте k-средних.
CLT утверждает, что средние, вычисленные во время k-средних, сходятся к распределению нормали со средним, равным истинному среднему (для данных), и дисперсией, равной sigma^2 / sqrt(n) , где sigma^2 — дисперсия ваших данных и n — количество выборок. По мере sigma^2 приближения к бесконечности n необходимо приближаться к бесконечности (квадратично), чтобы иметь разумные шансы точно оценить истинное среднее значение.
Проще говоря, решение вашей проблемы состоит в том, чтобы выполнить соответствующий предварительный анализ ваших данных, чтобы определить, насколько высока ваша дисперсия, и достаточно ли у вас количества выборок для ожидаемой дисперсии. Если нет, вернитесь и соберите больше данных или примените другую технику.