Понятная кластеризация

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

Большинство алгоритмов кластеризации используют расстояние (Евклида, Махаланобдис и т.д.) между объектами для группировки их в кластерах. Но трудно найти некоторые разумные показатели для смешанных типов данных, т.е. Мы не можем найти расстояние между "стеклом" и "сталью". Поэтому я пришел к выводу, что я должен использовать условные вероятности P(feature = 'something' | Class) и некоторую функцию полезности, которая зависит от них. Это разумно для категориальных переменных, и он отлично работает с числовыми переменными, предполагая, что они распределены нормально.

Итак, мне стало ясно, что алгоритмы, такие как K-означает, не приведут к хорошим результатам.

В это время я пытаюсь работать с алгоритмом COBWEB, который полностью соответствует моим идеям использования условных вероятностей. Но я столкнулся с другими обложками: результаты кластеризации действительно трудно интерпретировать, если не невозможно. В результате я хотел получить что-то вроде набора правил, описывающих каждый кластер (например, if feature1 = 'a' and feature2 in [30, 60], it is cluster1), например деревья дескрипции для классификации.

Итак, мой вопрос:

Существует ли какой-либо существующий алгоритм кластеризации, который работает со смешанным типом данных и дает понятное (и разумное для людей) описание кластеров.

Дополнительная информация:

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

Дерево решений

Как было предложено, я попытался подготовить дерево решений на выходе кластеризации, тем самым получив описание кластеров как набор правил. Но, к сожалению, интерпретация этих правил почти такая же сложная, как с исходным выпуском кластеризации. Первый из немногих первых уровней правил из корня node действительно имеет смысл: ближе к безличному смыслу, который у нас есть. Во-вторых, эти правила не соответствуют никаким экспертным знаниям.

Итак, я пришел к выводу, что кластеризация - это черный ящик, и не стоит пытаться интерпретировать его результаты.

У меня была интересная идея модифицировать алгоритм "дерева решений для регрессии" определенным образом: istead вычисления вычисления групповой дисперсии a утилита категории функции и использовать его как критерий split. В результате у нас должно быть дерево решений с описанием листовых кластеров и кластеров из коробки. Но я не пытался это сделать, и я не уверен в точности и во всем остальном.

Ответ 1

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

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

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

Как только у вас будет хорошая функция подобия, вам будет доступна целая куча алгоритмов. например DBSCAN (Wikipedia) или ОПТИКА (Википедия). ELKI может вас заинтересовать, у них есть Учебник по написанию пользовательских функций расстояния.

Интерпретация - это отдельная вещь. К сожалению, несколько алгоритмов кластеризации дадут вам понятную для человека интерпретацию того, что они нашли. Они могут дать вам такие вещи, как представитель (например, среднее кластера по k-значению), но немного больше. Но, конечно, вы могли бы подготовить дерево решений на выходе кластеров и попытаться интерпретировать дерево решений, извлеченное из кластеризации. Потому что одна очень хорошая особенность в деревьях решений - это то, что они несколько понятны для человека. Но так же, как поддержка Vector Vector Machine не даст вам объяснений, большинство (если не все) алгоритмов кластеризации тоже этого не сделают, извините, если вы не выполните такую пост-обработку. Кроме того, он будет работать с любым алгоритмом кластеризации, который является хорошим свойством, если вы хотите сравнить несколько алгоритмов.

В прошлом году была опубликована соответствующая публикация. Это немного неясно и экспериментально (на семинаре в ECML-PKDD), и требует, чтобы набор данных имел довольно обширную правду в виде ранжирования. В этом примере они использовали ранжирование сходства цвета и некоторые метки. Основная идея состоит в том, чтобы проанализировать кластер и найти наилучшее объяснение с использованием заданной истины (-ей) земли. Они пытались использовать его, например, скажем, "этот кластер найден в значительной степени основан на этом конкретном оттенке зеленого цвета, поэтому он не очень интересен, но другой кластер нельзя объяснить очень хорошо, вам нужно исследовать его ближе - возможно, алгоритм обнаружил что-то новое здесь". Но это было очень экспериментально (Семинары предназначены для исследования результатов исследований). Возможно, вы сможете использовать это, просто используя свои функции в качестве истины. Затем он должен определить, можно ли легко объяснить кластер такими вещами, как "атрибут5 составляет около 0,4 с низкой дисперсией". Но он не будет насильно создавать такое объяснение!

Х.-П. Кригель, Э. Шуберт, А. Зимек
Оценка решений с несколькими кластерами
Во 2-м семинаре MultiClust: открытие, подведение итогов и использование нескольких кластеров, связанных с ECML PKDD 2011. http://dme.rwth-aachen.de/en/MultiClust2011

Ответ 2

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

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

Я создал небольшой примерный набор данных, где каждый пример представляет собой вектор двух измерений. Первое измерение - это нормально распределенная переменная, а вторая - выбор из пяти категорий (см. График):

Существует несколько фреймворков, доступных для запуска monte carlo для статистических моделей. BUGS, вероятно, самый популярный (http://www.mrc-bsu.cam.ac.uk/bugs/). Я создал эту модель в Stan (http://mc-stan.org/), которая использует различную технику выборки, чем BUG, и более эффективна для многих проблем:

data {
  int<lower=0>  N; //number of data points
  int<lower=0>  C; //number of categories

  real x[N]; // normally distributed component data
  int y[N];  // categorical component data
}
parameters {
  real<lower=0,upper=1> theta; // mixture probability
  real mu[2]; // means for the normal component
  simplex[C] phi[2]; // categorical distributions for the categorical component
}

transformed parameters {
  real log_theta;
  real log_one_minus_theta;
  vector[C] log_phi[2];
  vector[C] alpha;

  log_theta <- log(theta);
  log_one_minus_theta <- log(1.0 - theta);

  for( c in 1:C)
    alpha[c] <- .5;

  for( k in 1:2)
    for( c in 1:C)
        log_phi[k,c] <- log(phi[k,c]);
}
model {
  theta ~ uniform(0,1); // equivalently, ~ beta(1,1);
  for (k in 1:2){
    mu[k] ~ normal(0,10);
    phi[k] ~ dirichlet(alpha);
  }

  for (n in 1:N) {
    lp__ <- lp__ + log_sum_exp(log_theta + normal_log(x[n],mu[1],1) + log_phi[1,y[n]],
                               log_one_minus_theta + normal_log(x[n],mu[2],1) + log_phi[2,y[n]]);
  }
}

Я скомпилировал и запустил модель Stan и использовал параметры из окончательного образца, чтобы вычислить вероятность каждого datapoint под каждым компонентом смеси. Затем я назначил каждому datapoint компоненту смеси (кластера) с большей вероятностью для восстановления кластерных присвоений ниже:

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

Ответ 3

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