Реализация алгоритма k-means на c# (с обобщенной метрикой)

    Всем привет. Продолжая тему того, что Andrew Ng не успел рассказать в курсе по машинному обучению, приведу пример своей реализации алгоритма k-средних. У меня стояла задача реализовать алгоритм кластеризации, но мне необходимо было учитывать степень корреляции между величинами. Я решил использовать в качестве метрики расстояние Махаланобиса, замечу, что размер данных для кластеризации не так велик, и не было необходимости делать кэширование кластеров на диск. За реализацией прошу под кат.



    Проблема


    Для начала рассмотрим, в чем проблема, почему бы просто не заменить Евклидово расстояние на любую другую метрику. Алгоритму k-средних на вход подается два параметра: данные для кластеризации и количество кластеров, на которые необходимо разбить данные. Алгоритм состоит из следующих шагов.
    1. Начальная инициализация центроидов кластеров каким-либо способом (например, можно задать начальные значения случайно выбранными точками из пространства, в котором определены данные; можно выбрать случайные точки из входного массива данных и т.д.).
    2. E-шаг (expectation): происходит ассоциация между элементами данных и кластерами, которые представлены в виде своих центров (центроидами).
    3. M-шаг (maximization): пересчитываются центры кластеров, как средние значения от данных, которые были включены с соответствующий кластер (или, другими словами, происходит модификация параметров модели таким образом, чтобы максимизировать вероятность попадания элемента в выбранный кластер). В случае, если кластер после шага 2 оказался пустым, то происходит переинициализация каким-либо другим способом.
    4. Шаги 2-3 повторяются до сходимости, либо пока не будет достигнут другой критерий остановки алгоритма (например, если превышается некоторое количество итераций).


    Для вникания в математику, которая находится за этим простым алгоритмом, советую почитать статьи по Байесовой кластеризации и алгоритму expectation-maximization.

    Проблема замены Евклидова расстояния на другую метрику заключается в М-шаге. Например, если у нас текстовые данные и в качестве метрики используется расстояние Левенштейна, то найти среднее значение это не совсем тривиальная задача. Для меня даже найти среднее по Махаланобису оказалось не быстро решаемой задачей, но мне повезло и я наткнулся на статью, в которой описан очень простой способ выбора «центроида», и мне не пришлось ломать голову над средним значением по Махаланобису. В кавычках потому, что не ищется точное значение центроида, а выбирается его приближенное значение, которое в той статье называют кластеройд (или по аналогии с k-medoids можно назвать медоидом). Таким образом, шаг максимизации заменяется следующим алгоритмом.

    • M-шаг: среди всех элементов данных, которые были отнесены к центроиду, выбирается тот элемент, для которого сумма расстояний до всех остальных элементов кластера минимальна; этот элемент становится новым центром кластера.

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

    Функцией стоимости для текущего разбиения будет использоваться следующая формула: image, где K — это количество кластеров, image — текущий центр кластера, image — множество элементов, отнесенных к кластеру k, а image — i-й элемент кластера k.

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

    Метрики


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

    public interface IMetrics<T>
    {
        double Calculate(T[] v1, T[] v2);
    
        T[] GetCentroid(IList<T[]> data);
    }
    


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

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

    public abstract class MetricsBase<T> : IMetrics<T>
    {
        public abstract double Calculate(T[] v1, T[] v2);
            
        public virtual T[] GetCentroid(IList<T[]> data)
        {
            if (data == null)
            {
                throw new ArgumentException("Data is null");
            }
            if (data.Count == 0)
            {
                throw new ArgumentException("Data is empty");
            }
            double[][] dist = new double[data.Count][];
            for (int i = 0; i < data.Count - 1; i++)
            {
                dist[i] = new double[data.Count];
                for (int j = i; j < data.Count; j++)
                {
                    if (i == j)
                    {
                        dist[i][j] = 0;
                    }
                    else
                    {
                        dist[i][j] = Math.Pow(Calculate(data[i], data[j]), 2);
                        if (dist[j] == null)
                        {
                            dist[j] = new double[data.Count];
                        }
                        dist[j][i] = dist[i][j];
                    }
                }
            }
            double minSum = Double.PositiveInfinity;
            int bestIdx = -1;
            for (int i = 0; i < data.Count; i++)
            {
                double dSum = 0;
                for (int j = 0; j < data.Count; j++)
                {
                    dSum += dist[i][j];
                }
                if (dSum < minSum)
                {
                    minSum = dSum;
                    bestIdx = i;
                }
            }
    
            return data[bestIdx];
        }
    }
    


    В методе GetCentroid мы ищем элемент, для которого сумма квадратов расстояний до остальных элементов данных минимальна. Сперва составляем симметричную матрицу, в которой в элементах находятся расстояния между соответствующими элементами данных. Используя свойства метрик: d(x, x) = 0 и d(x, y) = d(y, x), мы можем смело заполнить диагональ нулями и отразить матрицу по главной диагонали. Затем суммируем по строкам и ищем минимальное значение.

    Для примера давайте создадим реализацию расстояний Махаланобиса и Евклида.

    internal class MahalanobisDistanse : MetricsBase<double>
    {
    
        private double[][] _covMatrixInv = null;
    
        internal MahalanobisDistanse(double[][] covMatrix, bool isInversed)
        {
            if (!isInversed)
            {
                _covMatrixInv = LinearAlgebra.InverseMatrixGJ(covMatrix);
            }
            else
            {
                _covMatrixInv = covMatrix;
            }
        }
    
        public override double Calculate(double[] v1, double[] v2)
        {
            if (v1.Length != v2.Length)
            {
                throw new ArgumentException("Vectors dimensions are not same");
            }
            if (v1.Length == 0 || v2.Length == 0)
            {
                throw new ArgumentException("Vector dimension can't be 0");
            }
            if (v1.Length != _covMatrixInv.Length)
            {
                throw new ArgumentException("CovMatrix and vectors have different size");
            }
    
            double[] delta = new double[v1.Length];
            for (int i = 0; i < v1.Length; i++)
            {
                delta[i] = v1[i] - v2[i];
            }
    
            double[] deltaS = new double[v1.Length];
            for (int i = 0; i < deltaS.Length; i++)
            {
                deltaS[i] = 0;
                for (int j = 0; j < v1.Length; j++)
                {
                    deltaS[i] += delta[j]*_covMatrixInv[j][i];
                }
            }
    
            double d = 0;
            for (int i = 0; i < v1.Length; i++)
            {
                d += deltaS[i]*delta[i];
            }
    
            d = Math.Sqrt(d);
    
            return d;
        }
    }
    


    Как видно из кода, метод GetCentroid не переопределен, хотя в следующей статье я попробую переопределить этот метод алгоритмом градиентного спуска.

    internal class EuclideanDistance : MetricsBase<double>
    {
    
        internal EuclideanDistance()
        {
        }
    
        #region IMetrics Members
    
        public override double Calculate(double[] v1, double[] v2)
        {
            if (v1.Length != v2.Length)
            {
                throw new ArgumentException("Vectors dimensions are not same");
            }
            if (v1.Length == 0 || v2.Length == 0)
            {
                throw new ArgumentException("Vector dimension can't be 0");
            }
            double d = 0;
            for (int i = 0; i < v1.Length; i++)
            {
                d += (v1[i] - v2[i]) * (v1[i] - v2[i]);
            }
            return Math.Sqrt(d);
        }
    
        public override double[] GetCentroid(IList<double[]> data)
        {
            if (data.Count == 0)
            {
                throw new ArgumentException("Data is empty");
            }
            double[] mean = new double[data.First().Length];
            for (int i = 0; i < mean.Length; i++)
            {
                mean[i] = 0;
            }
            foreach (double[] item in data)
            {
                for (int i = 0; i < item.Length; i++)
                {
                    mean[i] += item[i];
                }
            }
            for (int i = 0; i < mean.Length; i++)
            {
                mean[i] = mean[i]/data.Count;
            }
            return mean;
        } 
    
        #endregion
    }
    


    В реализации расстояния Евклида, метод GetCentroid переопределен, и ищет точное значение центроида: вычисляются средние значения каждой из координат.

    Кластеризация



    Перейдем к имплементации алгоритма кластеризации. Опять же, вначале создадим интерфейс для алгоритмов кластеризации.

    public interface IClusterization<T>
    {
        ClusterizationResult<T> MakeClusterization(IList<DataItem<T>> data);
    }
    


    Где результат кластеризации выглядит следующим образом:

    public class ClusterizationResult<T>
    {
        public IList<T[]> Centroids { get; set; }
        public IDictionary<T[], IList<DataItem<T>>> Clusterization { get; set; }
        public double Cost { get; set; }
    }
    


    И класс элемента данных:

    public class DataItem<T>
    {
    
        private T[] _input = null;
        private T[] _output = null;
    
        public DataItem(T[] input, T[] output)
        {
            _input = input;
            _output = output;
        }
    
        public T[] Input
        {
            get { return _input; }
        }
    
        public T[] Output 
        { 
            get { return _output; }
            set { _output = value; }
        }
    
    }
    


    Нам интересно только свойство Input, т.к. это обучение без учителя.

    Перейдем к реализации алгоритма k-means, используя вышеупомянутые интерфейсы.

    internal class KMeans : IClusterization<double>
    


    На вход алгоритму кластеризации подаются следующие данные (я немного сократил свой код, чтобы не заморачиваться на способах инициализации начальных центроидов, мы будем использовать случайную инициализацию точек, мы можем себе это здесь позволить, т.к. мы кластеризуем числовые данные IClusterization):
    • clusterCount - количество кластеров на которые необходимо разбить данные
    • IMetrics metrics - метрика для кластеризации
    Share post

    Comments 19

      +1
      1. Причем тут Байес? В c-means понятно, но тут же именно k-means?
      2. Оверинжинирнг такой оверинжиниринг. Используйте лямбды хотя бы.

      Приложу свою «учебную» реализацию — github.com/retran/pattern-recognition-examples/blob/master/clusterization/kmeans.rb
        0
        разница в понятиях 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.

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

          Да ладно? В вопросе нет ничего про байесовскую классификацию. Все еще не понимаю.

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

          Именно это я и имел в виду.
            0
            в общем случае в байесовой кластеризации вычисляются 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) используется как условное распределение элементов в классе, т.е.

            image

            тогда, если матрица ковариации в нормальном распределении будет не единичной, и будет использоваться hard assignment, то тогда, байесова кластеризация будет случаем k-means для НЕ Евклидовой метрики

            если же матрица ковариации будет единичной, и опять будет использоваться hard assignment, то это тогда будет k-means с Евклидовой метрикой

            вполне себе частный случай общей байесовой кластеризации
              0
              Ок, теперь убедили. Спасибо за развернутый ответ.
        0
        Просто интересно, Andrew Ng по ходу курса говорит «воспользуйтесь готовыми библиотеками, они есть для всех мейнстримовых языков программирования». Для C# таковых нет или вы для саморазвития пишите? (хотя упоминаете вроде как реальные проекты, нет?)
          0
          упоминает конечно, но я привык контролировать процесс работы алгоритма, а для этого его нужно хотя бы раз написать

          ну и каждая библиотека преследует свои цели и придерживается своей философии, например теано http://deeplearning.net/software/theano/ использует теорию тензоров для работы с сетями, ну как то впадлу разбираться если честно -)

          или в том же матлабе все есть. но выполняя различные задачи дата майнинга на матлабе и других продуктах, возникает потребность унифицировать процедуры которые часто выполняются, от туда и родилась идея переписать все на свой лад -)
          0
          Использовать в k-means обобщённую метрику — первейший соблазн, но это не совсем правильно. Метрика — это не просто цифра, это в первую очередь функция, и эта функция является неотъемлемой частью минимизируемой функции стоимости. Если вы меняете метрику, вы меняете целевую функцию (функцию стоимости), а значит должны заново решить задачу минимизации этой функции. Ничего фантастического — построить лагранжиан и решить систему уравнений частных производных, но всё же до сих пор выходят статьи с адаптациями идеи k-means под всякие метрики. По сути, алгоритм целиком порождается именно метрикой, и k-means порождён именно квадратом эвклидова расстояния. Любая же подмена метрики «в лоб», то есть просто подмена циферки, возвращаемой функцией dist, работоспособна ровно в той степени, в которой новая метрика коррелирует с эвклидовой.
            0
            не совсем понятно что значит "работоспособна ровно в той степени, в которой новая метрика коррелирует с эвклидовой". в любом случае к-минс сходится к некоторому локальному минимуму в зависимости от инициализации. так же чем точнее будут вычислены новые центроиды на М-шаге, тем точнее будет результат. я привел простой способ вычисления кластероидов, и конечно это будет хуже чем при точном вычислении кластероидов. более точнее можно вычислить кластероиды если на М-шаге для каждого класса решать задачу оптимизации, используя например градиентный спуск, как раз и придется решить систему дифуров в частных производных, но не всегда это будет глобальным оптимумом, зависит от метрики.

            но учитывая что метрика все-таки не просто функция, а она еще обладает и свойствами 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, которое говорит что, две слуйчайно выбранные точки, скорее всего будут примерно на одном расстоянии друг от друга, как и другие две, и что случайные вектора будут скорее всего ортогональны)
              0
              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 единичная. Изменения в этой матрице приводят к искажению пространства, и доказано, что можно найти оптимальное искажение для каждого центроида. Вы можете проверить, что разница между матрицами, оптимизированными в евклидовой метрике и в метрике Махаланобиса при одинаковой инициализации, будет ковариационной матрицей между этими метриками, если таковая существует).
                0
                перед d^2 в целевой функции есть матрица, которая в случае k-means единичная

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

                как видно из кода

                cost += (from d in clusterization[key]
                                    select Math.Pow(_metrics.Calculate(key, d.Input), 2)).Sum();
                


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

                за совет про алгоритмом Густафсона-Кесселя спасибо, почитаю -)
                  0
                  Да, главным преимуществом алгоритма ГК на практике считается способность строить несферические кластеры. Но взаимозаменяемость пространств тоже можно проверить.

                  Проблема с метрикой именно в том, что функция стоимости считается от текущей метрики, а алгоритм оптимизирует функцию от евклидовой метрики. Это разные функции. В случае метрики Махаланобиса — похожие, но это значит, что и результаты будут «похожие» на оптимальные.
                    +1
                    я что то не догоняю может, но по моему алгоритм не оптимизирует именно Евклидово расстояние. исходя из предположения о нормальном распределении размерностей, алгоритм байесовой кластеризации оптимизирует параметры нормального распределения, т.е. мат ожидание и матрицу ковариации. (хотя можно вывести и оптимизацию параметров для другого распределения, говоря в общем он ищет достаточную статистику для вычисления параметров conditional probability distribution)

                    когда матрица ковариации фиксирована, то она задает сферическую форму гауссиан, и мы оптимизируем только мат ожидание, т.е. центроиды.

                    а вот в случае когда матрица ковариации фиксирована и единичная и используется хард ассигнмент, то это просто эквивалентно минимизации Евклидового расстояния.

                    в случае если матрица ковариации фиксирована, но не единичная, и хард ассигнмент опять, то это эквивалентно минимизации не Евклидового расстояния. в этом случае форма гауссиан просто искажена в какой нибудь эллипс
                      +1
                      Интересный взгляд на k-means, я подумаю над этим. Я обычно описываю этот алгоритм как решение задачи гравитации множества тел, то есть поиск центра массы =) Также популярно описание как нейронной сети, что я уже упоминал. Впрочем, какой бы ни была метафора, математика не меняется. И эта математика занимается оптимизацией целевой функции — это не требующее доказательств утверждение, потому что вообще _любой_ итеративный алгоритм оптимизирует некоторую целевую функцию, которую можно из него восстановить интегрированием, даже если явно она не задумывалась. Так вот, я уверяю вас, что в функции, которую оптимизирует K-Means, метрика задана явно и это евклидова метрика.

                      Я хотел бы сослаться на что-то, но у меня литература в основном по нечёткой кластеризации, и даже в учебниках я даже что-то не могу найти полную выкладку KM, видимо, за давностью лет (для Fuzzy K-Means, вывод, впрочем, почти аналогичный). Однако у Вунша, например, таблица методов кластеризации расписана именно по метрикам, и напротив евклидовой стоит КМ:
                      image
                      В замечательной статье 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». Загляните, хорошая статья). Жаль, что не нашёл формул, если так и не найду, на выходных выведу сам — но эти свидетельства, по крайней мере, в мою пользу.
                        0
                        в лекциях Дафны Келлер по probabalistic graphical models, точнее в 9 лекции рассматривается байесова кластеризация и к-минс как частный случай.

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

                        а если подменить метрику, то это наверное будет называться не к-минс, а как нибудь по другому =) но правда я не знаю как -) так что пока думаю буду называть этот к-минс-подобный способ, обобщенным к-минсом
                          0
                          Да, если подменить метрику, это будет другой алгоритм и поэтому называться он будет иначе. Только метрика подменяется не в алгоритме, а в его целевой функции. Если вы подменяете метрику в алгоритме, вы просто искажаете входные данные. Впрочем, мы, кажется, пошли по кругу.
                            0
                            ну да -)
                            мы с вами немного с разных сторон видим этот алгоритм, я вижу что существует распределение данных, некоторое, не обязательно гауссово. существует достаточная статистика для подбора параметров этого распределения, и существует способ оптимизации параметров этого распределения, так что бы для некоторого множества вероятность попадания элемента в этот класс была максимальна. это в общем. далее если опускаться в частности, то можно предположить что данные распределены по хи квадрат… ну или скажем нормально распределеное -) у нормального два параметра. ок. далее фисксируем один ну и т.д. в общем много ограничение на байесову кластеризацию и получаем к-минс с евклидовой метрикой. снимая одно ограничение получаем не евклидово расстояние.

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

              0
              А разве используемая здесь метрика не сводится к евклидовой просто заменой системы координат, например, переходом в базис собственных векторов матрицы ковариации? Дешевле пересчитать все точки в этот базис, чем ломать голову над применимостью новой метрики. Расстояние будет считаться быстрее, центр искать привычнее. Но для метрик, неэквивалентных евклидовой, все может быть…
                0
                верно, для Евклидовой метрики существует связь между PCA и к-минсом en.wikipedia.org/wiki/K-means_clustering#Principal_components_analysis_.28PCA.29

                я в это не вникал, так что мне трудно сказать про не Евклидову метрику в этом контексте

                но зато к-минс можно применить вообще не к числам, например если на вход подаются строки, а в качестве метрики используется расстояние Левенштейна или Хэмминга

                кстати недавно выкладывал из того же проекта реализацию PCA habrahabr.ru/post/146236/

            Only users with full accounts can post comments. Log in, please.