2

我有一个数据集，其中包含一些属于由1和2表示的两个类标签的特征。该数据集的处理是为了构建决策树：在树的构建过程中，我需要计算信息增益以找到数据集的最佳分区。

假设标签1有N1个特征，标签2有N2个特征，那么熵可以用以下公式计算：

Entropy = - (N1/N)*log2(N1/N) - (N2/N)*log2(N2/N), 其中N = N1 + N2

我需要计算三个熵值以获得信息增益：

  • entropyBefore，即当前数据集划分前的熵；
  • entropyLeft，即分割后左分裂的熵；
  • entropyRight，即分区后右拆分的熵。

因此，信息增益等于entropyBefore - (S1/N)*entropyLeft - (S2/N)*entropyRight，其中S1是属于分割 1的类别1的特征的数量，而S2是属于分割 2的类别2的特征的数量。

如何计算信息增益值以减少浮点逼近误差？当我在信息增益必须为零的情况下应用上述公式时，计算值等于一个非常小的负值。

更新（示例代码）

double N = static_cast<double>(this->rows());   // rows count of the dataset

double entropyBefore = this->entropy();   // current entropy (before performing the split)

bool firstCheck = true;
double bestSplitIg;

for each possible split
{
    // ...

    pair<Dataset,Dataset> splitPair = split(...,...);
    double S1 = splitPair.first.rows();
    double S2 = splitPair.second.rows();

    double entropyLeft = splitPair.first.entropy();
    double entropyRight = splitPair.second.entropy();

    double splitIg = entropyBefore - (S1/N*entropyLeft + S2/N*entropyRight);
    if (firstCheck || splitIg > bestSplitIg)
    {
        bestSplitIg = splitIg;
        // ...

        firstCheck = false;
    }
}
4

1 回答 1

2

如果你只是用熵来确定哪个方案更好，这样你只需要比较两个熵的结果而不需要它们的实际值，那么你可以省去一些计算。

你有这个函数：熵（N1，N2，N）->-N1/N*log2（N1/N）-N2/N*log2（N2/N）。

假设 N 在您的问题期间是一个常数，让我们将表达式乘以 N：

  • N1*log2(N1/N)-N2*log2(N2/N)

接下来，将“/N”从对数中分离出来：

  • N1*(log2(N1)-log2(N)) - N2*(log2(N2)-log2(N))

并展开：

  • N1*log2(N1) - N2*log2(N2) - (N1+N2)*log2(N)

并简化：

  • N1*log2(N1) - N2*log2(N2) - N*log2(N)

显然 N*log2(N) 是一个常数，不会影响一个熵是否大于另一个熵，因此我们可以丢弃它。

此外，乘以 ln(2)，这也不会改变一个熵是否大于另一个熵。这具有将 log2 函数更改为 ln 函数的效果，并且可以通过数学库稍微更准确地计算 ln（这是“自然”对数的原因）：

E(N1, N2, N) -> - N1*ln(N1) - N2*ln(N2)

该函数的操作较少，因此它的计算可能比熵函数更准确，并且它具有（当精确计算时）E(N1, N2, N) < E(M1, M2, N) iff Entropy(N1 , N2, N) < 熵(M1, M2, N)。

于 2013-02-19T00:48:11.040 回答