哪种关键词最能区分两类人？

Question

我有一个不同群体的人在搜索时使用的关键字数据库。 比如：

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来做这个）

提前谢谢！在

Answer 1

我认为最好的选择是Chi^2，infogain，tfidf，条件概率。为什么所有这些都需要线性复杂性。当我们讨论文本数据库时，所有的决策树都不是很可伸缩的。但是为了计算这些属性，我们可以使用任何索引工具，比如Lucene。所以我的建议是计算每个单词的信息增益，然后选择最佳。http://en.wikipedia.org/wiki/Information_gain_in_decision_trees

Answer 2

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

ID3的输出是一个分类器，它具有二叉树结构（ID3，C4.5等）。通常被称为决策树。Decision Tree Learning的Wikipedia条目实际上有一个相当不错的ID3摘要（在算法级别）。在

ID3中的两个常用度量方法是确定给定节点上的数据部分应如何分割的，称为信息熵。（一个较少使用的度量是Gini implex）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分钟的有氧运动？）然后生成的两组类标签如下所示：

是组：[True，True，True，False]

无组：[假，假，假]

几乎，但不完全，两个群体之间的完全异质性。所以很明显，第4列是分割这些数据的“最佳”变量。在

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

这不是一个完美的（数学上精确的）类比，但是粗略地说，你可以把信息熵与范畴变量（离散值）相关，就像方差与连续变量（浮动）相关一样。换句话说，信息熵（粗略地）表示离散数据的方差（或标准差）。在

使用函数计算熵

^{pr2}$

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

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

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

Answer 3

基本上，他们所做的就是计算频率项乘以逆文档频率。tf–idf