Алгоритм кластеризации по Гюстафсону-Кесселю

>>Ведь не у каждой квадратной матрицы есть обратная!!

А разве ковариационная матрица несимметрична?

Вот получается такая ковариационная матрица
     # # 0
A =  # # 0
     0 0 0
здесь # - вещественные числа

Очевидно, |A| = 0

Однако определитель обратной матрицы |A'| должен быть равен 
1/|A|, т.е. сами понимаете чему!

А-а, понял. Ну, на мой взгляд, даннае как-то очень неудачно кластеризованы, стоило бы сделать проверку на ноль и переходить к следующему шагу (попытаться перегруппировать данные). Или считать, что алгоритм расходится и аварайно останавливаться?

Понимаешь в чём дело - данные изначально вообще никак не 
кластеризованы и их то как раз и нужно распределить по кластерам.

В алгоритме есть только один элемент случайности - выбор начальной
матрицы разбиения (partition matrix).
В остальном алгоритм полностью детерминирован!

Так вот на данных вида:
      #       #             #
v1 =  #  v2 = # ..... vn =  #
      1       1             1
т.е. n-мерные вектора с одинаковой n-ой компонентой
Всегда будем получать коварационную матрицу размера n на n
в которой n-я строка и n-й столбец нулевые.

Это легко понять т.к. берутся разности вида v_i - c_j, где
v_i - вектор данных, а c_j - прототип кластера.
А прототипы вычисляются таким образом, что для таких входных данных,
n-ая компонента прототипа совпадает с n-ой компонентой векторов
данных. Поэтому при разности получаем 0-ую n-ую компоненту и как
следствие приведённую выше матрицу.

А значит и расстояния по Махаланобису рассчитать нельзя!

Получается что алгоритм просто напросто не устойчив к такого рода
данным? Ну это же бред, алгоритму уже 26 лет, неужели эту багу
никто не нашёл раньше?

Ведь единственное ограничение на входные данные - вещественные и
равноправные атрибуты.

Est' ochen' moschnii metod razlozheniya matric - SVD. Im mozhno stroit "psevdoobratnuyu" matritsu k dannoi. Mozhet eto pomozhet?

Yu

P.S. A gde mozhno prochitat' pro etot algoritm Gyustafsona-Kesselya?

Yu

>Est' ochen' moschnii metod razlozheniya matric - SVD. Im mozhno stroit "psevdoobratnuyu" matritsu k dannoi. Mozhet eto pomozhet?

Я обязательно посмотрю.


На самом деле моя главная проблема в том, что я не знаю точно
что физически означают некоторые шаги алгоритма :((

Почитать об этом негде, информации крайне мало.

Obyazatel'no posmotri, naprimer tut: http://library.lanl.gov/numerical/bookcpdf/c2-6.pdf

Etot metod legko tebe dast matritcu, kotoraya maksimal'no blizka k obratnoi. Dazhe esli u ishodnaya matritsa virozhdena.

К сожалению, я не знаю, что такое "Алгоритм кластеризации по Гюстафсону-Кесселю", но предложенный выше SVD является основой для одного из наиболее популярных нынче методов кластеризации, на котором основаны поисковики, использующие latent semantic, (см. напр. http://lsa.colorado.edu/papers/dp1.LSAintro.pdf).

На самом деле я понял в чём дело.
Скорее всего в алгоритме неявно предполагается, что не существует
компонент векторов, одинаковых для всех векторов.

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

Однако всем спасибо за интересную информацию!