1

这可能是一个相当深奥的问题。

我正在尝试将 Albatineh 等人 (2006) (DOI: 10.1007/s00357-006-0017-z) 的一些想法用于空间聚类算法。基本思想是评估聚类结果稳定性的一种方法是检查成对的观察结果出现在同一类中的频率。在定义明确的解决方案中，成对的观察结果应该经常出现在同一组中。

挑战在于，在大型数据集中有 n^2 对可能的对（并且大多数不会出现）。我们的输出结构如下：

A  B  C  C  A
B  A  A  A  B
A  B  C  C  A

其中列索引是观察 ID，每一行代表聚类算法的一次运行。在这个例子中，有 5 个观察值，算法运行了 3 次。集群标签 A:C 在运行之间基本上是任意的。我想要一种有效的方法来计算这样的东西：

ID1 ID2 
1    5
2   
3    4
4    3
5    1
1    2
2    3
2    4
...

这实现了我的目标，但速度非常慢，尤其是对于大型数据框：

testData <- matrix(data=sample(x=c("A", "B", "C"), 15, replace=TRUE), nrow=3)

cluPr <- function(pr.obs){
    pairs <- data.frame()
    for (row in 1:dim(pr.obs)[1]){
        for (ob in 1:dim(pr.obs)[2]){
            ob.pairs <- which(pr.obs[row,] %in% pr.obs[row,ob], arr.ind=TRUE)
            pairs <- rbind(pairs, cbind(ob, ob.pairs))
        }

    }
    return(pairs)   
}

cluPr(testData)
4

3 回答 3

1

这是使用该combn()功能的相对快速的方法。我假设您的矩阵的名称是m.

results <- t(combn(dim(m)[2], 2, function(x) c(x[1], x[2], sum(m[, x[1]] == m[, x[2]]))))
results2 <- results[results[, 3]>0, ]
于 2013-06-18T18:12:08.670 回答
0

我的第一个实现（不是在 R 中；我的代码在 Java 中要快得多）配对计数指标是使用有序生成器，然后采用合并排序方式计算交集。它仍然处于O(n^2)运行时的顺序，但内存使用量要低得多。

但是，您需要意识到您不需要知道确切的配对。您只需要相交中的数量，并且可以直接从相交​​矩阵中计算出来，就像大多数其他相似性度量一样。如果您只需要计算设置的交叉点大小，它会更快；使用哈希表，设置交集应该在O(n).

我没时间查。但我们可能在讨论

聚类评估——度量​​和视觉支持

数据工程 (ICDE)，2012 年 IEEE 第 28 届国际会议

艾尔克·阿克特、萨莎·戈德霍夫、汉斯-彼得·克里格尔、埃里希·舒伯特、亚瑟·齐梅克

我们展示了一个可视化工具来探索基于对计数的度量，也适用于两个以上的聚类解决方案（不幸的是，视觉检查主要适用于玩具数据集，而不适用于通常过于混乱和高维的真实数据）。

粗略地说：尝试使用您引用的出版物中第 303 页的公式计算值，而不是按照直觉/动机中的说明计算然后计算对！

于 2013-06-19T11:33:51.503 回答
0

尝试这个：

clu.pairs <- function(k, row)
{
    w <- which(row==k)

    expand.grid(w, w)
}

row.pairs <- function(row)
{
    do.call(rbind, lapply(unique(row), function(k) clu.pairs(k, row)))
}

full.pairs <- function(data)
{
    do.call(rbind, lapply(seq_len(nrow(data)), function(i) row.pairs(data[i,])))
}

并使用full.pairs(testData). 结果与您的顺序不同，但它是等效的。

于 2013-06-18T19:43:52.277 回答