python - 哪些关键词最能区分两组人？

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

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

ID3 的输出是一个分类器，它具有二叉树结构(ID3、C4.5 等通常称为决策树)。 Decision Tree Learning 的维基百科条目实际上对 ID3 有一个不错的总结(在算法层面)。

ID3 中的两个常用指标称为信息熵，用于确定给定节点处的数据部分应如何拆分。 (一个较少使用的指标是 Gini Impurity。)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]

没有分组:[False, False, False]

两组之间几乎但不完全是完全异质性。因此，显然第 4 列是拆分此数据的“最佳”变量。

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

这不是一个完美的(数学上精确的)类比，但粗略地说，您可以认为信息熵与分类变量(离散值)相关，因为方差与连续变量( float )相关。换句话说——信息熵(粗略地)表示离散数据的方差(或标准差)。

这是一个计算熵的 python 函数(使用 NumPy):

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

总而言之，对于您的特定问题，要确定最“与众不同”的关键字，请计算两个类标签列表中每一个的熵，然后计算它们的加权平均值(由每个列表中的项目数加权)。导致具有最低加权平均熵的拆分的关键字就是您所追求的。