Кластеризация k-means в

Иван Megapinion14 декабря 20131 комментарий

Кластеризация k-means в «разреженном» пространстве - как строить метрику?

Задача: есть многомерное пространство Y (очень многомерное – скажем, размерности M=170 000) и в нём находятся объекты Oi (числом, скажем, I=60 000). «Разреженность» означает, что каждый индивидуальный объект имеет значения координат (Yi(m)) не по всем измерениям, а только по некоторым из них. В результате на различные оси координат проецируется различное количество объектов – Nm от 2-х до, скажем, 7000. Индивидуальные объекты проецируются на от 2-х до, скажем, 120 000 осей координат.

Хочется: произвести кластеризацию этих объектов в этом пространстве по методу k-means. Для начала, например, разделить их на два кластера (K=2).

Ядро метода:
1. для каждого кластера вычисляется вектор (Ck) его центра («центра тяжести»), состоящий из (Ck(m)) средних значений координат членов кластера. Естественно, по каждой оси значения координат усредняются только по тем членам кластера, которые спроецированы на эту ось координат.

2. чтобы отнести объект Oi к какому-то кластеру Ck, нужно вычислить расстояния D(i,k) от этого объекта до центра (каждого) кластера, которое является «агрегацией» парциальных расстояний d(i,k,m) = Abs(Oi(m)-Ck(m)).

Вопрос: как правильно (содержательно правильно) агрегировать d(i,k,m) в D(i,k)?

Ремарка: понятно, что перед агрегацией нужно «парциально» нормализовать d(i,k,m), т.е. отнормировать их на среднеквадратичный разброс – поделить на S(m) = StDev[Yi(m)]

Проблема состоит в том, будут ли «равноправны» «густозаселённые» оси координат и «слабозаселённые», если в качестве метода агрегации использовать простое усреднение (D(i,k) = Avg(d(i,k,m)))?

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