Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 19
1. Причем тут Байес? В c-means понятно, но тут же именно k-means?
2. Оверинжинирнг такой оверинжиниринг. Используйте лямбды хотя бы.
Приложу свою «учебную» реализацию — github.com/retran/pattern-recognition-examples/blob/master/clusterization/kmeans.rb
2. Оверинжинирнг такой оверинжиниринг. Используйте лямбды хотя бы.
Приложу свою «учебную» реализацию — github.com/retran/pattern-recognition-examples/blob/master/clusterization/kmeans.rb
разница в понятиях hard assignment и soft assignment, а вообще оба алгоритма являются частным случаем байесовой кластеризации
например в курсе probabalistic graphical models был такой вопрос:
Hard Assignment EM: Now suppose that we fix each class-conditional distribution to have the same diagonal matrix D as its covariance matrix, where D is not the identity matrix. If we use hard-assignment EM to estimate the class-dependent mean vectors, which of the following can we say about the resulting algorithm?
Правильный ответ такой:
It is an instance of k-means, but using a different distance metric rather than standard Euclidean distance.
И объяснение:
You will always assign vertices to their closest cluster centroid, just as in k-means. But here the definition of «closest» is skewed by the covariance matrix so that it does not equally depend on each dimension and is thus not a Euclidean distance.
за ссылку спасибо, гляну сейчас -) оверинжениринг тут от того что я пытаюсь абстрагировать реализации конкретных алгоритмов кластеризации от их представления, что бы в процессе датамайнинга можно было бы использовать различные алгоритмы, не переделывая код
например в курсе probabalistic graphical models был такой вопрос:
Hard Assignment EM: Now suppose that we fix each class-conditional distribution to have the same diagonal matrix D as its covariance matrix, where D is not the identity matrix. If we use hard-assignment EM to estimate the class-dependent mean vectors, which of the following can we say about the resulting algorithm?
Правильный ответ такой:
It is an instance of k-means, but using a different distance metric rather than standard Euclidean distance.
И объяснение:
You will always assign vertices to their closest cluster centroid, just as in k-means. But here the definition of «closest» is skewed by the covariance matrix so that it does not equally depend on each dimension and is thus not a Euclidean distance.
за ссылку спасибо, гляну сейчас -) оверинжениринг тут от того что я пытаюсь абстрагировать реализации конкретных алгоритмов кластеризации от их представления, что бы в процессе датамайнинга можно было бы использовать различные алгоритмы, не переделывая код
а вообще оба алгоритма являются частным случаем байесовой кластеризации
Да ладно? В вопросе нет ничего про байесовскую классификацию. Все еще не понимаю.
оверинжениринг тут от того что я пытаюсь абстрагировать реализации конкретных алгоритмов кластеризации от их представления
Именно это я и имел в виду.
Да ладно? В вопросе нет ничего про байесовскую классификацию. Все еще не понимаю.
оверинжениринг тут от того что я пытаюсь абстрагировать реализации конкретных алгоритмов кластеризации от их представления
Именно это я и имел в виду.
в общем случае в байесовой кластеризации вычисляются conditional probability distribution для каждого элемента P(x_i | C = c_k), т.е. вероятности отнесения элементов к классам — это называется soft assignment. если же выбрать класс с наибольшей вероятностью и отнести элемент к этому классу с P(x_i | C = c_k) = 1, то это будет называться hard assignment, похоже на Maximum-a-Posteriori или MAP.
моделируется вообще какое-то не конкретное распределение
предположим мы делаем байесову кластеризацию, и многомерное нормальное распределение (multivariate normal distribution) используется как условное распределение элементов в классе, т.е.
тогда, если матрица ковариации в нормальном распределении будет не единичной, и будет использоваться hard assignment, то тогда, байесова кластеризация будет случаем k-means для НЕ Евклидовой метрики
если же матрица ковариации будет единичной, и опять будет использоваться hard assignment, то это тогда будет k-means с Евклидовой метрикой
вполне себе частный случай общей байесовой кластеризации
моделируется вообще какое-то не конкретное распределение
предположим мы делаем байесову кластеризацию, и многомерное нормальное распределение (multivariate normal distribution) используется как условное распределение элементов в классе, т.е.
тогда, если матрица ковариации в нормальном распределении будет не единичной, и будет использоваться hard assignment, то тогда, байесова кластеризация будет случаем k-means для НЕ Евклидовой метрики
если же матрица ковариации будет единичной, и опять будет использоваться hard assignment, то это тогда будет k-means с Евклидовой метрикой
вполне себе частный случай общей байесовой кластеризации
Просто интересно, Andrew Ng по ходу курса говорит «воспользуйтесь готовыми библиотеками, они есть для всех мейнстримовых языков программирования». Для C# таковых нет или вы для саморазвития пишите? (хотя упоминаете вроде как реальные проекты, нет?)
упоминает конечно, но я привык контролировать процесс работы алгоритма, а для этого его нужно хотя бы раз написать
ну и каждая библиотека преследует свои цели и придерживается своей философии, например теано http://deeplearning.net/software/theano/ использует теорию тензоров для работы с сетями, ну как то впадлу разбираться если честно -)
или в том же матлабе все есть. но выполняя различные задачи дата майнинга на матлабе и других продуктах, возникает потребность унифицировать процедуры которые часто выполняются, от туда и родилась идея переписать все на свой лад -)
ну и каждая библиотека преследует свои цели и придерживается своей философии, например теано http://deeplearning.net/software/theano/ использует теорию тензоров для работы с сетями, ну как то впадлу разбираться если честно -)
или в том же матлабе все есть. но выполняя различные задачи дата майнинга на матлабе и других продуктах, возникает потребность унифицировать процедуры которые часто выполняются, от туда и родилась идея переписать все на свой лад -)
Использовать в k-means обобщённую метрику — первейший соблазн, но это не совсем правильно. Метрика — это не просто цифра, это в первую очередь функция, и эта функция является неотъемлемой частью минимизируемой функции стоимости. Если вы меняете метрику, вы меняете целевую функцию (функцию стоимости), а значит должны заново решить задачу минимизации этой функции. Ничего фантастического — построить лагранжиан и решить систему уравнений частных производных, но всё же до сих пор выходят статьи с адаптациями идеи k-means под всякие метрики. По сути, алгоритм целиком порождается именно метрикой, и k-means порождён именно квадратом эвклидова расстояния. Любая же подмена метрики «в лоб», то есть просто подмена циферки, возвращаемой функцией dist, работоспособна ровно в той степени, в которой новая метрика коррелирует с эвклидовой.
не совсем понятно что значит "работоспособна ровно в той степени, в которой новая метрика коррелирует с эвклидовой". в любом случае к-минс сходится к некоторому локальному минимуму в зависимости от инициализации. так же чем точнее будут вычислены новые центроиды на М-шаге, тем точнее будет результат. я привел простой способ вычисления кластероидов, и конечно это будет хуже чем при точном вычислении кластероидов. более точнее можно вычислить кластероиды если на М-шаге для каждого класса решать задачу оптимизации, используя например градиентный спуск, как раз и придется решить систему дифуров в частных производных, но не всегда это будет глобальным оптимумом, зависит от метрики.
но учитывая что метрика все-таки не просто функция, а она еще обладает и свойствами d(x, x) = 0, d(x, y) = d(y, x) и d(x, z) <= d(x, y) + d(y, z), то в любом случае результат такого алгоритма будет некоторое разбиение, и т.к. наша функция все таки метрика, то мы можем определить понятие радиуса кластера. так что на выходе мы получим разбиение на кластеры определенного радиуса, это и будет кластеризацией.
есть например алгоритм GRGPF (V. Ganti, R. Ramakrishnan, J. Gehrke, A. Powell, and
J. French) который создан для больших массивов данных в не Евклидовом пространстве. работает примерно по той же схеме.
теперь коснемся вот чего: " Если вы меняете метрику, вы меняете целевую функцию (функцию стоимости), а значит должны заново решить задачу минимизации этой функции". это было бы абсолютно верно, если бы к-минс был алгоритмом порожденным из этой функции стоимости (как например алгоритм обратного распространения ошибки для нейросети зависит от целевой функции, будь то минимизация Евклидового расстояния или минимизация логарифмического правдоподобия), но он порожден алгоритмом ЕМ, который максимизирует условное вероятностное распределение элементов при данном классе. в комменте выше http://habrahabr.ru/post/146556/#comment_4937430 я описал как раз то, что к-минс это частный случай байесовой кластеризации. так что меняя метрики, мы меняем матрицу ковариации нормального распределения.
получается что точность к-минса зависит от
но учитывая что метрика все-таки не просто функция, а она еще обладает и свойствами d(x, x) = 0, d(x, y) = d(y, x) и d(x, z) <= d(x, y) + d(y, z), то в любом случае результат такого алгоритма будет некоторое разбиение, и т.к. наша функция все таки метрика, то мы можем определить понятие радиуса кластера. так что на выходе мы получим разбиение на кластеры определенного радиуса, это и будет кластеризацией.
есть например алгоритм GRGPF (V. Ganti, R. Ramakrishnan, J. Gehrke, A. Powell, and
J. French) который создан для больших массивов данных в не Евклидовом пространстве. работает примерно по той же схеме.
теперь коснемся вот чего: " Если вы меняете метрику, вы меняете целевую функцию (функцию стоимости), а значит должны заново решить задачу минимизации этой функции". это было бы абсолютно верно, если бы к-минс был алгоритмом порожденным из этой функции стоимости (как например алгоритм обратного распространения ошибки для нейросети зависит от целевой функции, будь то минимизация Евклидового расстояния или минимизация логарифмического правдоподобия), но он порожден алгоритмом ЕМ, который максимизирует условное вероятностное распределение элементов при данном классе. в комменте выше http://habrahabr.ru/post/146556/#comment_4937430 я описал как раз то, что к-минс это частный случай байесовой кластеризации. так что меняя метрики, мы меняем матрицу ковариации нормального распределения.
получается что точность к-минса зависит от
- инициализации
- точности поиска кластероида
- ну и конечно от данных, как и от их распределения так и от размерности (существует понятие The Curse of Dimensionality, которое говорит что, две слуйчайно выбранные точки, скорее всего будут примерно на одном расстоянии друг от друга, как и другие две, и что случайные вектора будут скорее всего ортогональны)
1) Работоспособна — это значит сходимость доказуема. Оптимум, найденный k-means с подменённой метрикой, будет действительно оптимумом только если ему соответствует оптимум в евклидовой метрике. Попробуйте взять какую-нибудь экзотическую метрику, не коррелирующую с расстоянием в вашем пространстве признаков — например, largest common subset (его длину, точнее) для тех же строк — и получите результат разбиения на уровне случайного, а то и хуже.
2) K-Means это и есть решение задачи оптимизации, полностью эквивалентное градиентному спуску, за исключением того, что K-Means — это аналитическое решение системы уравнений частных производных, а градиентный спуск — приближеннное решение методами нелинейного программирования _той же самой_ системы уравнений.
3) Ваше описание — это просто смена нотации, с тем же успехом можно описать k-means как нейросеть, например (собственная, нейронная сеть Кохонена и является k-means в нейросетевой нотации, хоть и придумана совсем из других соображений). Это ни в коей мере не отменяет того, что k-means безусловно порождается функцией стоимости, и мы можем вместе это проверить, повторив вывод алгоритма — это всегда полезно для понимания.
4) Мне немного сложно понять ваши выводы, т.к. у нас явно очень разная терминологическая база. Для меня такого понятия как «точность» в кластеризации нет, потому что нет эталонного разбиения, кроме того, k-means никак не подвержен тому, что я знаю под названием «проклятие размерности», потому что число его параметров растёт линейно с размерностью пространства признаков (а не экспоненциально, как у традиционнных нейросетей, например).
Однако точность k-means несомненно зависит от инициализации (кстати, оптимально инициализировать матрицу разбиения, а не центроиды) и точности рассчёта центроида или его
заменителя. Кстати, поинтересуйтесь алгоритмом Густафсона-Кесселя, это обобщённый k-means для всех «околоевклидовых» метрик (довольно остроумная штука: оказывается, перед d^2 в целевой функции есть матрица, которая в случае k-means единичная. Изменения в этой матрице приводят к искажению пространства, и доказано, что можно найти оптимальное искажение для каждого центроида. Вы можете проверить, что разница между матрицами, оптимизированными в евклидовой метрике и в метрике Махаланобиса при одинаковой инициализации, будет ковариационной матрицей между этими метриками, если таковая существует).
2) K-Means это и есть решение задачи оптимизации, полностью эквивалентное градиентному спуску, за исключением того, что K-Means — это аналитическое решение системы уравнений частных производных, а градиентный спуск — приближеннное решение методами нелинейного программирования _той же самой_ системы уравнений.
3) Ваше описание — это просто смена нотации, с тем же успехом можно описать k-means как нейросеть, например (собственная, нейронная сеть Кохонена и является k-means в нейросетевой нотации, хоть и придумана совсем из других соображений). Это ни в коей мере не отменяет того, что k-means безусловно порождается функцией стоимости, и мы можем вместе это проверить, повторив вывод алгоритма — это всегда полезно для понимания.
4) Мне немного сложно понять ваши выводы, т.к. у нас явно очень разная терминологическая база. Для меня такого понятия как «точность» в кластеризации нет, потому что нет эталонного разбиения, кроме того, k-means никак не подвержен тому, что я знаю под названием «проклятие размерности», потому что число его параметров растёт линейно с размерностью пространства признаков (а не экспоненциально, как у традиционнных нейросетей, например).
Однако точность k-means несомненно зависит от инициализации (кстати, оптимально инициализировать матрицу разбиения, а не центроиды) и точности рассчёта центроида или его
заменителя. Кстати, поинтересуйтесь алгоритмом Густафсона-Кесселя, это обобщённый k-means для всех «околоевклидовых» метрик (довольно остроумная штука: оказывается, перед d^2 в целевой функции есть матрица, которая в случае k-means единичная. Изменения в этой матрице приводят к искажению пространства, и доказано, что можно найти оптимальное искажение для каждого центроида. Вы можете проверить, что разница между матрицами, оптимизированными в евклидовой метрике и в метрике Махаланобиса при одинаковой инициализации, будет ковариационной матрицей между этими метриками, если таковая существует).
перед d^2 в целевой функции есть матрица, которая в случае k-means единичная
я так подозреваю что это берется от того, что к-минс предполагает нормальное распределение значений каждой размерности, и в случае когда матрица ковариации единичная, то это эквивалентно Евклидовому расстоянию.
как видно из кода
функция стоимости считается от текущей метрики, т.е. матрица ковариации которая присутствует в расстоянии Махаланобиса тоже учитывается. если матрица явно не задается в какой либо метрике, то ее скорее всего можно вычислить, как корелляцию между метриками (правда я не знаю как, не пытался)
за совет про алгоритмом Густафсона-Кесселя спасибо, почитаю -)
я так подозреваю что это берется от того, что к-минс предполагает нормальное распределение значений каждой размерности, и в случае когда матрица ковариации единичная, то это эквивалентно Евклидовому расстоянию.
как видно из кода
cost += (from d in clusterization[key]
select Math.Pow(_metrics.Calculate(key, d.Input), 2)).Sum();
функция стоимости считается от текущей метрики, т.е. матрица ковариации которая присутствует в расстоянии Махаланобиса тоже учитывается. если матрица явно не задается в какой либо метрике, то ее скорее всего можно вычислить, как корелляцию между метриками (правда я не знаю как, не пытался)
за совет про алгоритмом Густафсона-Кесселя спасибо, почитаю -)
Да, главным преимуществом алгоритма ГК на практике считается способность строить несферические кластеры. Но взаимозаменяемость пространств тоже можно проверить.
Проблема с метрикой именно в том, что функция стоимости считается от текущей метрики, а алгоритм оптимизирует функцию от евклидовой метрики. Это разные функции. В случае метрики Махаланобиса — похожие, но это значит, что и результаты будут «похожие» на оптимальные.
Проблема с метрикой именно в том, что функция стоимости считается от текущей метрики, а алгоритм оптимизирует функцию от евклидовой метрики. Это разные функции. В случае метрики Махаланобиса — похожие, но это значит, что и результаты будут «похожие» на оптимальные.
я что то не догоняю может, но по моему алгоритм не оптимизирует именно Евклидово расстояние. исходя из предположения о нормальном распределении размерностей, алгоритм байесовой кластеризации оптимизирует параметры нормального распределения, т.е. мат ожидание и матрицу ковариации. (хотя можно вывести и оптимизацию параметров для другого распределения, говоря в общем он ищет достаточную статистику для вычисления параметров conditional probability distribution)
когда матрица ковариации фиксирована, то она задает сферическую форму гауссиан, и мы оптимизируем только мат ожидание, т.е. центроиды.
а вот в случае когда матрица ковариации фиксирована и единичная и используется хард ассигнмент, то это просто эквивалентно минимизации Евклидового расстояния.
в случае если матрица ковариации фиксирована, но не единичная, и хард ассигнмент опять, то это эквивалентно минимизации не Евклидового расстояния. в этом случае форма гауссиан просто искажена в какой нибудь эллипс
когда матрица ковариации фиксирована, то она задает сферическую форму гауссиан, и мы оптимизируем только мат ожидание, т.е. центроиды.
а вот в случае когда матрица ковариации фиксирована и единичная и используется хард ассигнмент, то это просто эквивалентно минимизации Евклидового расстояния.
в случае если матрица ковариации фиксирована, но не единичная, и хард ассигнмент опять, то это эквивалентно минимизации не Евклидового расстояния. в этом случае форма гауссиан просто искажена в какой нибудь эллипс
Интересный взгляд на k-means, я подумаю над этим. Я обычно описываю этот алгоритм как решение задачи гравитации множества тел, то есть поиск центра массы =) Также популярно описание как нейронной сети, что я уже упоминал. Впрочем, какой бы ни была метафора, математика не меняется. И эта математика занимается оптимизацией целевой функции — это не требующее доказательств утверждение, потому что вообще _любой_ итеративный алгоритм оптимизирует некоторую целевую функцию, которую можно из него восстановить интегрированием, даже если явно она не задумывалась. Так вот, я уверяю вас, что в функции, которую оптимизирует K-Means, метрика задана явно и это евклидова метрика.
Я хотел бы сослаться на что-то, но у меня литература в основном по нечёткой кластеризации, и даже в учебниках я даже что-то не могу найти полную выкладку KM, видимо, за давностью лет (для Fuzzy K-Means, вывод, впрочем, почти аналогичный). Однако у Вунша, например, таблица методов кластеризации расписана именно по метрикам, и напротив евклидовой стоит КМ:
В замечательной статье Fundmentals of Fuzzy Clustering тоже, насколько я помню, несколько раз упоминается, что многие алгоритмы полностью порождены метрикой, в частности КМ — евклидовой (ну например в параграфе 1.3: «In the previous section, we considered the case where the distance between cluster centers and data points
is computed using the Euclidean distance». Загляните, хорошая статья). Жаль, что не нашёл формул, если так и не найду, на выходных выведу сам — но эти свидетельства, по крайней мере, в мою пользу.
Я хотел бы сослаться на что-то, но у меня литература в основном по нечёткой кластеризации, и даже в учебниках я даже что-то не могу найти полную выкладку KM, видимо, за давностью лет (для Fuzzy K-Means, вывод, впрочем, почти аналогичный). Однако у Вунша, например, таблица методов кластеризации расписана именно по метрикам, и напротив евклидовой стоит КМ:
В замечательной статье Fundmentals of Fuzzy Clustering тоже, насколько я помню, несколько раз упоминается, что многие алгоритмы полностью порождены метрикой, в частности КМ — евклидовой (ну например в параграфе 1.3: «In the previous section, we considered the case where the distance between cluster centers and data points
is computed using the Euclidean distance». Загляните, хорошая статья). Жаль, что не нашёл формул, если так и не найду, на выходных выведу сам — но эти свидетельства, по крайней мере, в мою пользу.
в лекциях Дафны Келлер по probabalistic graphical models, точнее в 9 лекции рассматривается байесова кластеризация и к-минс как частный случай.
мне кажется в большинстве литературы именно по этому и говорится что к-минс — это минимизация именно Евклидовой метрики, т.к. по сути так и есть, когда матрица ковариации фиксирована и единична, и используется хард ассигнмент.
а если подменить метрику, то это наверное будет называться не к-минс, а как нибудь по другому =) но правда я не знаю как -) так что пока думаю буду называть этот к-минс-подобный способ, обобщенным к-минсом
мне кажется в большинстве литературы именно по этому и говорится что к-минс — это минимизация именно Евклидовой метрики, т.к. по сути так и есть, когда матрица ковариации фиксирована и единична, и используется хард ассигнмент.
а если подменить метрику, то это наверное будет называться не к-минс, а как нибудь по другому =) но правда я не знаю как -) так что пока думаю буду называть этот к-минс-подобный способ, обобщенным к-минсом
Да, если подменить метрику, это будет другой алгоритм и поэтому называться он будет иначе. Только метрика подменяется не в алгоритме, а в его целевой функции. Если вы подменяете метрику в алгоритме, вы просто искажаете входные данные. Впрочем, мы, кажется, пошли по кругу.
ну да -)
мы с вами немного с разных сторон видим этот алгоритм, я вижу что существует распределение данных, некоторое, не обязательно гауссово. существует достаточная статистика для подбора параметров этого распределения, и существует способ оптимизации параметров этого распределения, так что бы для некоторого множества вероятность попадания элемента в этот класс была максимальна. это в общем. далее если опускаться в частности, то можно предположить что данные распределены по хи квадрат… ну или скажем нормально распределеное -) у нормального два параметра. ок. далее фисксируем один ну и т.д. в общем много ограничение на байесову кластеризацию и получаем к-минс с евклидовой метрикой. снимая одно ограничение получаем не евклидово расстояние.
так что с моей стороны алгоритм не зависит от минимизации квадратов расстояний, а зависит от статистики. я рассматриваю к-минс как алгоритм в котором сделано предположение о нормальном распределении, фиксированной матрице ковариации в нем, хард ассигнмент и остается только искать матожидания. а какие были там значения в матрице ковариации по барабану.
мы с вами немного с разных сторон видим этот алгоритм, я вижу что существует распределение данных, некоторое, не обязательно гауссово. существует достаточная статистика для подбора параметров этого распределения, и существует способ оптимизации параметров этого распределения, так что бы для некоторого множества вероятность попадания элемента в этот класс была максимальна. это в общем. далее если опускаться в частности, то можно предположить что данные распределены по хи квадрат… ну или скажем нормально распределеное -) у нормального два параметра. ок. далее фисксируем один ну и т.д. в общем много ограничение на байесову кластеризацию и получаем к-минс с евклидовой метрикой. снимая одно ограничение получаем не евклидово расстояние.
так что с моей стороны алгоритм не зависит от минимизации квадратов расстояний, а зависит от статистики. я рассматриваю к-минс как алгоритм в котором сделано предположение о нормальном распределении, фиксированной матрице ковариации в нем, хард ассигнмент и остается только искать матожидания. а какие были там значения в матрице ковариации по барабану.
А разве используемая здесь метрика не сводится к евклидовой просто заменой системы координат, например, переходом в базис собственных векторов матрицы ковариации? Дешевле пересчитать все точки в этот базис, чем ломать голову над применимостью новой метрики. Расстояние будет считаться быстрее, центр искать привычнее. Но для метрик, неэквивалентных евклидовой, все может быть…
верно, для Евклидовой метрики существует связь между PCA и к-минсом en.wikipedia.org/wiki/K-means_clustering#Principal_components_analysis_.28PCA.29
я в это не вникал, так что мне трудно сказать про не Евклидову метрику в этом контексте
но зато к-минс можно применить вообще не к числам, например если на вход подаются строки, а в качестве метрики используется расстояние Левенштейна или Хэмминга
кстати недавно выкладывал из того же проекта реализацию PCA habrahabr.ru/post/146236/
я в это не вникал, так что мне трудно сказать про не Евклидову метрику в этом контексте
но зато к-минс можно применить вообще не к числам, например если на вход подаются строки, а в качестве метрики используется расстояние Левенштейна или Хэмминга
кстати недавно выкладывал из того же проекта реализацию PCA habrahabr.ru/post/146236/
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Реализация алгоритма k-means на c# (с обобщенной метрикой)