c++ - 如何计算信息增益的值以减少浮点逼近误差？

Question

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

设 N1 个特征与标签 1 关联，N2 个特征与标签 2 关联，那么熵可以使用以下公式计算:

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 是类 < 的特征数量em>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;
    }
}

Answer 1

如果您只是使用熵来确定哪个替代方案更好，因此您只需要比较两个熵的结果，而不需要它们的实际值，那么您可以消除一些计算。

你有这个函数:Entropy(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)

该函数的运算次数较少，因此它的计算可能比 Entropy 函数更准确，并且它具有以下属性:(精确计算时)E(N1, N2, N) < E(M1, M2, N) iff熵(N1, N2, N) < 熵(M1, M2, N)。