matlab - VLFeat 分层 k-means：词汇树中的节点数

Question

在hierarchical k-means中，深度为D、分支因子K的词汇树应该有如下的节点总数（不包括根节点）：

nodes = K + K^2 + ... + K^D
nodes = (K^(D+1)-K)/(K-1)  

但是，vl_hikmeanshist给出带有一个额外 bin 的直方图。在他们的网站上，节点数计算为：

nodes = (K^(D+1)-1)/(K-1)  

他们还说他们“不计算没有信息的根”。那么为什么他们的公式不同呢？他们没有在网站上发布他们的联系方式，所以我无法询问他们。有人可以解释一下这个问题吗？

Answer 1

不包括根节点，因为它不包含其他信息。根节点将始终是数据集的平均值。看这里

举个简单的例子，假设您在深度为 2 的树中有 5 个节点。对于您的公式，您将有(5^3-5)/(4)=120/4=30节点（不包括根节点）

他们的公式只是在根节点中添加：(5^3-1)/(4)=124/4=31节点。这与之前的 30 加一个根节点相同。

基本上它们都意味着同样的事情。只知道额外的 bin 是根目录，并没有真正的用处。