2

test我正在寻找一种实现，该实现确定一个（例如）数据帧中的所有记录到第二个（例如）数据帧中的任何记录的 Gower 距离的最小值training。结果是一个向量，其中的每一行都有一个元素test。

数据是具有无序分类属性的分类数据，并且可以生成，例如，如下所示：

set.seed(20130926L)
DIMS <- 12
CATS <- 2

create.data <- function(SPARSITY) {
  sparse.data <- rbinom(CATS ** DIMS, 1, SPARSITY)
  sparse.array <- array(sparse.data, dim=rep(CATS, DIMS))
  sparse.table <- as.table(sparse.array)
  sparse.df <- as.data.frame(sparse.table)
  sparse.df <- subset(sparse.df, Freq > 0, select=-Freq)
  sparse.df
}

data.train <- create.data(0.001)
data.test <- create.data(0.01)

head(data.train, 3)

##      Var1 Var2 Var3 Var4 Var5 Var6 Var7 Var8 Var9 Var10 Var11 Var12
## 745     A    A    A    B    A    B    B    B    A     B     A     A
## 1156    B    B    A    A    A    A    A    B    A     A     B     A
## 1574    B    A    B    A    A    B    A    A    A     B     B     A

summary(data.test)

##  Var1   Var2   Var3   Var4   Var5   Var6   Var7   Var8   Var9   Var10 
##  A:24   A:31   A:23   A:20   A:30   A:27   A:22   A:20   A:26   A:23  
##  B:24   B:17   B:25   B:28   B:18   B:21   B:26   B:28   B:22   B:25  
##  Var11  Var12 
##  A:24   A:22  
##  B:24   B:26

data.test对于 中的所有行，我如何找到data.training高尔距离最小的行（或者至少是到该特定行的距离）？下面的代码有效，但对于 20 个属性或超过 2 个类别已经需要太多内存：

nrow(data.test)

## [1] 48

library(StatMatch, quietly=T, warn.conflicts=F)
apply(gower.dist(data.train, data.test), 2, min)

##  [1] 0.3333 0.4167 0.2500 0.5000 0.3333 0.4167 0.2500 0.3333 0.2500 0.4167
## [11] 0.5000 0.3333 0.3333 0.3333 0.4167 0.4167 0.2500 0.4167 0.1667 0.3333
## [21] 0.4167 0.3333 0.4167 0.5000 0.3333 0.5000 0.5000 0.4167 0.3333 0.3333
## [31] 0.2500 0.4167 0.5000 0.4167 0.3333 0.5000 0.3333 0.4167 0.3333 0.3333
## [41] 0.5000 0.5833 0.5000 0.2500 0.3333 0.4167 0.3333 0.5000

该函数cluster::daisy()还返回一个距离矩阵。

类似：如何计算大数据帧的欧几里得距离（并仅保存摘要）。在那里，建议对 的子集多次调用距离函数data.train。我可以做到这一点，但计算时间仍然令人望而却步。

毕竟，高尔距离的定义允许更有效的算法，也许是递归的分治法，逐个属性地操作属性并在子集上调用自身。回想一下，Gower 的距离是属性距离的（加权）总和，定义为

  • 对于分类属性：如果相等则为 0，否则为 1
  • 对于有序属性：如果相等，则为 0，否则与排名距离成正比
  • 对于连续属性（此处不需要）：与属性的距离和范围的比率成正比

下面是一个简单的演示，其中计算了 和 的所有组合之间的高尔(A, A) 距离。一个属性不同的行的距离为 0.5，两个属性不同的行的最大距离为 1.0：AB

(ex.train <- expand.grid(Var1=LETTERS[1:2], Var2=LETTERS[1:2]))

##   Var1 Var2
## 1    A    A
## 2    B    A
## 3    A    B
## 4    B    B

ex.test <- ex.train[1, ]
gower.dist(ex.train, ex.test)

##      [,1]
## [1,]  0.0
## [2,]  0.5
## [3,]  0.5
## [4,]  1.0

如果两者train.data和test.data都按列进行分析，可能的实现可能如下所示：

  1. v对于第一列的 所有值级别
    1. 选择test.data第一列具有价值的子集v
    2. 选择train.data第一列具有价值的子集v
    3. 递归调用过程以获得最小值的上限
    4. 选择train.data第一列具有价值的子集<> v
    5. 使用先前获得的早期截止上限递归调用过程

是否真的没有实现，或者可能有描述这种算法的论文？

4

2 回答 2

5

我不熟悉高尔的距离，但从你的描述看来，对于无序的分类属性，高尔的距离等于汉明距离除以向量的长度。换句话说，向量x和之间的高尔距离y很简单mean(x!=y)。在这种情况下，您可以避免计算整个距离矩阵，而是使用colSums. 这是一个示例，具有三个级别和 10000 个训练行：

> set.seed(123)
> train.rows<-10000
> test.rows<-100
> cols<-20
> levels<-c("a","b","c")
> train.set<-sample(levels,train.rows*cols,T)
> dim(train.set)<-c(train.rows,cols)
> test.set<-sample(levels,test.rows*cols,T)
> dim(test.set)<-c(test.rows,cols)
> system.time(gdist<-apply(gower.dist(train.set,test.set),2,min))   
   user  system elapsed 
 13.396   0.324  13.745 
> system.time(hdist<-apply(test.set,1,function(x) min(colSums(x!=t(train.set))/cols)))
   user  system elapsed 
  0.492   0.008   0.504 
> identical(hdist,gdist)
[1] TRUE

如果数据不是离散且无序的，那么 Gower 距离的公式是不同的，但我怀疑有一种类似的方法可以更有效地计算它，而无需通过 计算整个距离矩阵gower.dist。

更新：这可以通过使用@Frank 的建议来提高效率，并t(train.set)预先生成而不是在函数内生成：

require(microbenchmark)
ttrain.set<-t(train.set)
microbenchmark(
  a=apply(test.set,1,function(x) min(colSums(x!=t(train.set))/cols)),
  b=apply(test.set,1,function(x) min(colSums(x!=ttrain.set)/cols)))

## Unit: milliseconds
##  expr      min       lq   median       uq      max neval
##     a 523.3781 533.2950 589.0048 620.4411 725.0183   100
##     b 367.5428 371.6004 396.7590 408.9804 496.4001   100
于 2013-10-01T04:08:39.950 回答
0

这是我评论的一部分，但它确实是一个候选答案，除非我错过了问题的重点：不应该只是：

 ddat <- gower.dist(data.train, data.test)
 which(ddat==min(ddat), arr.ind=TRUE)

#     row col
#[1,]   3  19

? （它本身已经设计为执行“应用”操作。）

如果目标是让最小距离到“data.test”中的特定行，那么它会更快并且占用更少的空间。我仍然不明白为什么这会导致记忆困难。并且目标是找到最小距离或找到每个 data.test 行的最小值。

于 2013-09-30T01:29:04.083 回答