0

我正在用 C 编写决策树的代码。现在它给了我正确的结果（0% 的训练错误，低测试错误），但是运行需要很长时间。

问题在于我运行 qsort 的频率。我的基本算法是这样的：

    for every feature
        sort that feature column using qsort
        remove duplicate feature values in that column
        for every unique feature value
          split
          determine entropy given that split
    save the best feature to split + split value
    for every training_example
      if training_example's value for best feature < best split value, store in Left[]
      else store in Right[]
    recursively call this function, using only the Left[] training examples
    recursively call this function, using only the Right[] training examples

因为最后两行是迭代调用，并且因为树可以扩展到几十个分支，所以对 qsort 的调用数量是巨大的（特别是对于我的数据集具有 > 1000 个特征）。

我减少运行时间的想法是创建一个二维数组（在一个单独的函数中），其中每一列都是一个排序的特征列。然后，只要我为每个递归调用在 Left[] 和 Right[] 中维护训练示例的行号向量，我就可以调用这个单独的函数，在预排序的特征向量中获取我想要的行，并节省每次必须进行 qsort 的成本。

我对C相当陌生，所以我不确定如何编写代码。在 MatLab 中，我可以拥有一个任何函数都可以更改或访问的全局数组，在 C 中寻找类似的东西。

4

1 回答 1

0

C 中的全局数组是完全可能的。实际上有两种方法可以做到这一点。在第一种情况下，数组的维度对于应用程序是固定的：

#define NROWS   100
#define NCOLS   100
int array[NROWS][NCOLS];

int main(void)
{
        int     i, j;

        for (i = 0; i < NROWS; i++)
        for (j = 0; j < NCOLS; j++)
        {
                array[i][j] = i+j;
        }
        return 0;
}

在第二个示例中，维度可能取决于来自输入的值。

#include <stdlib.h>
int **array;

int main(void)
{
        int     nrows = 100;
        int     ncols = 100;
        int     i, j;

        array = malloc(nrows*sizeof(*array));
        for (i = 0; i < nrows; i++)
        {
                array[i] = malloc(ncols*sizeof(*(array[i])));
                for (j = 0; j < ncols; j++)
                {
                        array[i][j] = i+j;
                }
        }
}

尽管两个示例中对数组的访问看起来非常相似，但数组的实现却大不相同。在第一个示例中，数组位于一块内存中，访问行的步幅是整行。在第二个示例中，每个行访问都是指向行的指针，该行是一块内存。然而，不同的行可以位于存储器的不同区域。在第二个示例中，行也可能具有不同的长度。在这种情况下，您还需要将每行的长度存储在某处。

我不完全理解您要达到的目标，因为我不熟悉决策树、特征和训练集的标准方法的术语。但您可能还想看看其他数据结构来维护排序数据：

  1. http://en.wikipedia.org/wiki/Red –black_tree 维护了一个或多或少平衡和排序的树。
  2. AVL 树有点慢，但更平衡和排序树。
  3. 在元素列表上尝试排序树。
  4. 散列函数可以轻松地将复杂元素映射到可用于对元素进行排序的整数值。适合查找精确的元素，但元素本身没有真正的顺序。

P.S1：来自 Matlab，您可能需要考虑使用与 C 不同的语言来迁移。C++ 有标准库来支持上述数据结构。如果你有胆量的话，你会想到 Java、Python 甚至 Haskell。C 中的指针处理可能非常乏味且容易出错。

P.S2：我无法-在 StackOverflow 的 URL 中包含一个。所以红黑树链接有点偏，不能点击。如果有人可以编辑我的帖子以修复它，那么我将不胜感激。

于 2013-04-20T09:26:16.957 回答