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

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等通常称为决策树).决策树学习的维基百科条目实际上具有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分钟吗？)那么得到的两组课程标签如下所示:

是组:[真,真,真,假]

没有组:[假,假,假]

几乎,但不完全,两组之间完美的异质性.所以显然第4列是分离这些数据的"最佳"变量.

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

这不是一个完美的(数学上精确的)类比,但粗略地说,你可以认为信息熵与分类变量(离散值)有关,因为方差与连续变量(浮点数)有关.换句话说 - 信息熵(粗略地)表示离散数据的方差(或标准偏差).

这是一个计算熵的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))

完美异质性具有entropy = 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

总之,对于您的特定问题,要确定最"区分"关键字,请为两个类标签列表中的每一个计算熵,然后计算它们的加权平均值(按每个列表中的项目数加权).导致具有最低加权平均值熵的拆分的关键字就是您所追求的.