14

我有一个数据集。该集合的每个元素都由数字和分类变量组成。分类变量是名义变量和有序变量。这个数据集中有一些自然的结构。通常，专家使用他们的“专业知识”对我的数据集进行聚类，但我想自动化这个聚类过程。

大多数聚类算法使用对象之间的距离（欧几里得、马氏距离等）将它们分组到集群中。但是很难为混合数据类型找到一些合理的度量标准，即我们无法找到“玻璃”和“钢”之间的距离。所以我得出结论，我必须使用条件概率 P(feature = 'something' | Class)和一些依赖于它们的效用函数。这对于分类变量是合理的，并且假设它们是正态分布的，它适用于数值变量。

所以我很清楚，像K-means这样的算法不会产生好的结果。

此时我尝试使用COBWEB算法，这完全符合我使用条件概率的想法。但是我遇到了另一个障碍：集群化的结果真的很难解释，如果不是不可能的话。结果，我想得到一组描述每个集群的规则（例如if feature1 = 'a' and feature2 in [30, 60], it is cluster1），比如用于分类的决策树。

所以，我的问题是：

是否有任何现有的聚类算法适用于混合数据类型并产生可理解的（并且对人类来说是合理的）集群描述。

附加信息：

据我了解，我的任务是在概念聚类领域。由于研究领域的原因，我无法像建议的那样定义相似函数（它是整个项目的最终目标） - 它在形式化方面非常复杂且无情。据我了解，最合理的方法是COBWEB中使用的方法，但我不确定如何适应它，所以我可以得到一个难以理解的集群描述。

决策树

正如建议的那样，我尝试在聚类输出上训练决策树，从而将聚类描述为一组规则。但不幸的是，对这条规则的解释几乎和原始聚类输出一样难。首先，来自根节点的一些第一级规则确实有意义：更接近叶 - 我们拥有的意义较小。其次，这些规则不符合任何专业知识。

因此，我得出结论，聚类是一个黑箱，不值得尝试解释其结果。

还

我有一个有趣的想法，以某种方式修改“回归决策树”算法：而不是计算组内方差，而是计算类别效用函数并将其用作分割标准。因此，我们应该有一个开箱即用的带有叶子集群和集群描述的决策树。但我没有尝试这样做，我不确定准确性和其他一切。

4

3 回答 3

11

对于大多数算法，您需要定义相似性。它不需要是适当的距离函数（例如满足三角不等式）。

K-means 特别糟糕，因为它还需要计算均值。因此，如果您无法计算均值，或者使用与欧几里得不同的距离函数，最好远离它。

但是，请考虑定义一个距离函数来捕获您的相似性领域知识。它可以由其他距离函数组成，比如您使用欧几里德距离的调和平均值（可能使用一些比例因子加权）和类别相似度函数。

一旦你有了一个不错的相似度函数，你就可以使用一大堆算法。例如DBSCAN（维基百科）或OPTICS（维基百科）。你可能对 ELKI 感兴趣，他们有一个关于编写自定义距离函数的教程。

解释是另一回事。不幸的是，很少有聚类算法会给你一个人类可读的他们发现的解释。它们可能会给您诸如代表之类的东西（例如，k-means 中集群的平均值），但仅此而已。但是当然，您接下来可以在聚类输出上训练决策树，并尝试解释从聚类中学习到的决策树。因为决策树的一个非常好的特性是它们在某种程度上是人类可以理解的。但是就像支持向量机不会给你解释一样，大多数（如果不是全部）聚类算法也不会这样做，对不起，除非你做这种后处理。另外，它实际上可以与任何聚类算法，如果您想比较多种算法，这是一个很好的属性。

去年有一个相关的出版物。它有点晦涩和实验性（在 ECML-PKDD 的一个研讨会上），并且要求数据集以排名的形式具有相当广泛的基本事实。在示例中，他们使用了颜色相似度排名和一些标签。关键思想是分析集群并使用给定的基本事实找到最佳解释。他们试图用它来例如说“发现的这个集群主要基于这个特定的绿色阴影，所以它不是很有趣，但是另一个集群不能很好地解释，你需要更仔细地研究它——也许是算法在这里发现了一些新东西”。但这是非常实验性的（研讨会是针对正在进行的研究类型的）。你可能只需将您的特征用作基本事实，就可以使用它。然后它应该检测一个集群是否可以很容易地用诸如“attribute5 is about. 0.4 with low variance”之类的东西来解释。但它不会强行创建这样的解释！

  • 生命值。Kriegel, E. Schubert, A. Zimek在第二届 MultiClust 研讨会上
    评估多个聚类解决方案
    ：发现、总结和使用与 ECML PKDD 2011 结合举行的多个聚类。http: //dme.rwth-aachen.de/en/MultiClust2011
于 2012-08-28T16:35:07.683 回答
4

解决此类聚类问题的一种常用方法是定义一个统计模型来捕获数据的相关特征。可以通过使用混合模型（如在高斯混合模型中）得出聚类分配，然后找到特定数据点概率最高的混合分量。

在您的情况下，每个示例都是一个具有实数和分类分量的向量。一种简单的方法是分别对向量的每个分量进行建模。

我生成了一个小的示例数据集，其中每个示例都是二维向量。第一个维度是一个正态分布的变量，第二个维度是五个类别的选择（见图）：

在此处输入图像描述

有许多框架可用于为统计模型运行蒙特卡罗推理。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 模型，并使用最终样本中的参数来计算每个混合分量下每个数据点的概率。然后，我将每个数据点分配给混合组件（集群），以恢复以下集群分配的概率更高：

在此处输入图像描述

基本上，如果您创建了适合您的数据集的模型，则每个混合组件的参数将为您提供每个集群的核心特征。

于 2012-09-05T22:31:22.383 回答
2

对于您描述的异构、非欧几里得数据向量，层次聚类算法通常效果最好。您描述的条件概率条件可以合并为用于执行集群聚集或划分的属性排序。生成的集群的语义很容易描述。

于 2012-09-03T15:55:40.220 回答