具有Levenshtein距离和附加特征/变量的聚类算法

Question

我有一个由文本标记(单词、不同类型的标识号和一些附加类型)组成的数据集，我希望使用某种无监督分类算法对其进行分类。

给定我从文本中提取的某些类型的特征(字符#，数字#，字母#，一些正则表达式等)算法，例如kmeans (仅作为示例，我没有绑定到kmeans)工作得很好，但我想添加一些更多的细节，比如我可以在hclust中使用的Levenshtein-distance。

但是，我没有找到如何组合这两种不同数据类型的起点(链接到两个观察值的数据，比如距离度量，以及只链接到一个观察值的数据，比如每个令牌的字符数)。

我是不是遗漏了一些简单的部分，有没有可能，或者我只是找错了算法？

下面，您可以找到一个小数据集的示例，以及我到目前为止所采用的不同方法。

MWE数据

# create some data
set.seed(123)
x <- sapply(1:20, function(i) {
 paste(c(
  sample(LETTERS, sample(1:10, 1), replace = T),
  sample(1:9, sample(1:10, 1), replace = T),
  sample(LETTERS[1:10], 2)
 ), collapse = "")
})
head(x)
#> [1] "UKW1595595761IC" "I9769675632JI"   "UAMTFIG44DB"     "GM814HB"        
#> [5] "FDTXJR4CH"       "VVULT7152464BC"

# apply the different algorithms
# 1. K-means
df <- data.frame(x)
df$nchars <- nchar(x)
df$n_nums <- nchar(gsub("[^[:digit:]]", "", x))
# etc.

kclust <- kmeans(df[, 2:3], centers = 2)
pairs(df, col=c(2:3)[kclust$cluster]) 

​

​

# 2. Levensthein distance and hclust
distance <- adist(x)
rownames(distance) <- x
hc <- hclust(as.dist(distance)) 
plot(hc)

​

​

# 3. Combination of adist(x) and the df-variables
# ???

Answer 1

如果您需要一种方法来组合Levenshtein的度量和欧几里德距离之类的东西，您可以通过组合距离矩阵来实现，因为它们具有相同的形状，并将其发送到hclust。

stats <- cbind(df$nchars, df$n_nums)

euc <- as.matrix(dist(stats))
rownames(euc) <- x

lev <- adist(x)
rownames(lev) <- x

scale01 <- function(x) {
    z <- (x - min(x))
    z / max(z)
}

combi <- scale01(euc) + scale01(lev)

hc.combi <- hclust(as.dist(combi))
plot(hc.combi)

当然，您可以随心所欲地加权这两个矩阵。

如果你想结合k-means和层次聚类，我知道有一种方法可以做到这一点。本质上，您对矩阵执行分层聚类，将其划分为k个组，计算每个组的平均值，并将这些平均值作为k-means的起始质心传递。

hc2 <- hclust(dist(stats))
clusters <- cutree(hc2, k=3)

centers <- aggregate(stats, list(clusters), mean)[, -1]

hkclust <- kmeans(stats, centers)
pairs(df, col=c(2:4)[hkclust$cluster])

如果你想把k-means和Levenshtein结合起来，我恐怕不知道该怎么做，因为把一个距离矩阵传递给k-means没有多大意义。也许k-medoids可以工作？