哪些关键词最能区分两组人？（这是一个关于IT技术的问题）

Question

哪些关键词最能区分两组人？（这是一个关于IT技术的问题）

pythonalgorithmstatisticsmachine-learning

7

我有一个关键词数据库，记录了不同群体的搜索使用情况。类似于：

group1person1: x, y, z
group1person2: x, z, d
...
group2person1: z, d, l
...

我希望能够查看给定组的最具特色的关键词。我想做的是 OkCupid 在他们的博客中所做的：http://blog.okcupid.com/index.php/the-real-stuff-white-people-like/ 有人可以推荐适合这个任务的算法 / 术语 / 建议吗？

（我将在 Python 中完成此操作）

提前致谢！

- DrMisha

2

在做任何其他事情之前，请确保样本大小足以进行推断。您不希望从太小的样本中得出结论。 - Rafe Kettler

2

黑色和白色不是种族。 - user unknown

3个回答

2

基本上，他们所做的是计算词项频率乘以倒文档频率。 tf-idf

- Jacob Eggers

我认为这个想法的问题在于定义你的文档是什么。如果我从A组中汇总所有关键字并将其称为文档A，同样对于B组，那么我只有两个文档，这对于tf-idf来说太过粗糙了。如果每个人的关键字被视为一个文档，那么我们就失去了A/B组的区分。 - DrMisha

0

我认为最好的选择是Chi^2、infogain、tfidf和条件概率。因为它们都需要线性复杂度。当我们谈论文本数据库时，所有决策树的可扩展性都不是很强。但是对于计算这些属性，我们可以使用像Lucene这样的任何索引工具。所以我的建议是计算每个词的信息增益并选择最佳选项。http://en.wikipedia.org/wiki/Information_gain_in_decision_trees

- yura

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- doug · Accepted Answer

您的问题或多或少地描述了ID3算法的核心用例。

ID3的输出是一个分类器，具有二叉树结构（ID3、C4.5等通常被称为决策树）。维基百科关于Decision Tree Learning的条目实际上在算法级别上有一个不错的总结。

ID3中用于确定给定节点处的数据应如何拆分的两个常用度量标准称为信息熵。（较少使用的指标是Gini不纯度。）ID3算法只是一个递归下降解析器，它测试所有变量/值组合并在组合上进行节点拆分，以给出加权平均熵最低的结果。

直观地说，信息熵试图识别最好地拆分数据的变量（列）和该变量内的值。最佳拆分符合我们的直觉。这比通过散文来描述要容易得多。考虑这个数据集：

Height      Weight      Age     90 min aerobics/wk?     completed 5 mile run?
 155         45          31           Yes                      True
 160         51          33           No                       False
 168         52          28           No                       False
 155         61          25           Yes                      True
 169         57          52           Yes                      True
 172         81          35           No                       False
 164         70          23           Yes                      False

如果数据按第4列分割（一个人是否每周至少进行90分钟的有氧运动？），则产生的两组类别标签如下：

Yes Group: [True, True, True, False]

No Group: [False, False, False]

这两组之间几乎完全不同。因此，显然第4列是最好的变量来拆分这个数据。

ID3算法中用于确定最佳拆分的度量标准只是这种直觉的数学形式化。

这并不是一个完美的（数学上精确的）比喻，但大致上可以将信息熵与分类变量（离散值）相关联，就像方差与连续变量（浮点数）相关联一样。换句话说，信息熵（大致上）表达了离散数据的方差（或标准偏差）。

这是一个使用NumPy计算熵的Python函数：

def entropy(arr1) :
    import numpy as NP
    ue = NP.unique(x)
    p, entropy = 0., 0.
    for itm in ue :
        ndx = arr1 == itm
        p += NP.size(x[ndx]) / float(x.size)
        entropy -= p * NP.log2(p)
    return entropy

上面的熵函数只是这两个表达式合并并简化为代码的结果：

p(i) = frequency(outcome) = count(outcome) / count(total_rows)

entropy = sum of p(i) x log2(p(i))

完全异质性的熵值为0，因此最具“区分度”的变量/值是当您根据该变量和值拆分数据时，加权平均熵最低的变量/值。接近1的熵值几乎完全是“混合”的或接近随机的。

# simulate a data set with three class labels (0 1, 2)
# for your problem, the class labels are the keywords, 
# so just map each unique keyword to an integer value (e.g., { 'keyword1' : 0, 'keyword2' : 1}
>>> x = NP.random.randint(0, 3, 20)
>>> x
   array([1, 0, 0, 0, 1, 1, 2, 1, 1, 1, 2, 2, 0, 2, 0, 1, 1, 1, 1, 1])

>>> print("{0:.3f}".format(entropy(x)))
   0.758

总之，对于您的特定问题，要确定最具“区分性”的关键字，请计算两个类标签列表的熵，然后计算它们的加权平均值（按每个列表中的项目数加权）。导致加权平均熵最低的拆分所使用的关键字就是您需要的。