通过权重评分得到更美味的番茄炒蛋

哼哼,我首先声明这不是一篇cookbook文:)

在今天互联网上,我们可以广泛的看到用户反馈(评分)系统的身影.评价区间有1-10分的心理测评,自然也有超级简单的+/-法:譬如很赞一个美女的时候,你可以送个玫瑰或者番茄啥的,不以为然的时候更可以砸个鸡蛋过去.

举个例子,如果一篇文章写得很不错,有100个人参与评价,80个人给了1,20个人给了0,那么这篇文章的评分(rating)应该是0.8.越是很有可能以加粗高亮的方式推荐给其他用户,得到了很不错的点击率.这时,问题就出来了:rating值很高的资源就一定真的评价高么?

好吧,请允许我邪恶的想一下,如果某用户写了一篇文章,然后自己先给打几个1分.于是,史上最满意文章(rating值是1)就这样来到了我们的网站！

想象一下大多数新产生的资源不是得分极高(评价少,分数普遍高)就是得分极低(无人问津).这也是上述评分机制一个非常突出的缺陷.我们意识到:对于那些只有极少数评价的资源,他们的rating相较于那些有着极多评价的资源缺乏一定的“certainty” or “believability”

因此,我们需要"修正"一下这个计算方法:

• 对于评价很少的资源,可以认为其本身既不受欢迎也没有啥争议(不能引起话题).它的rating更应该去接近去整体评价的平均水平;
• 那些评价很多的资源,通过修正也更多的体现出"相对的高",也就是更多的接近其本来的rating.

那么,我们可以给所有资源的平均rating和特定评价资源的平均rating各引入一个权值.这个权值就是整体平均评价人数和资源评价人数.这里的整体平均评价人数的设定可以根据真实的计算得出(动态值),当然也可以自己根据喜好设定一个.值越小说明你对评分要求越不严格，影响rating所需要的票数越少；值越大说明你越在意样本过少所带来的负面影响，同时说明资源必须保证一定的人气.

br = ( (avg_num_votes * avg_rating) + (this_num_votes * this_rating) )/(avg_num_votes + this_num_votes)

其中:

• avg_num_votes:整体平均评价人数
• avg_rating:资源平均rating
• this_num_votes:待评价资源人数
• this_rating:待评价资源rating

这也就是江湖上赫赫有名的贝叶斯评价(Bayesian probability),更多信息可以围观维基百科.
实际上这种评分系统广泛适用于很多知名的WEB2.0站点.

目前正在火热举行的 花儿朵朵等选秀活动,可以考虑在此基础上增加一个"人的可信度"(来鉴别社区、论坛的马甲号,具体可以采用积分等手段),这样或许对提高选手评价的准确性和有效性起到一定的积极作用,也可以衍生出更多有趣的现象.

也谈网页正文提取[下]

上回书到使用行文本密度(Text Density)来解决网页正文提取问题.给出了一个学术界定量的文本行密度阀值.一般来说武功秘籍的下半部总是看起来牛逼些的,就像当年梅超风练的<九阴真经>一样,练了半本书的一路掌法,已经是妇孺闻之变色的"女魔头"了.所以本博的这下半篇也来不得丝毫差池,怎么也得看起来十分有料才行.

前文所述之阈值估计过程本质上是一个全局统计各个密度的过程，并没有像学习算法一样考虑文本行的分布情况，如在页面的中间发生以及文本行可能在一起出现的可能性高等。但阈值估计有助于快速地选择行，而且可以在没有学习样本的情况下获得较好的表现。

但是不同的场景需求对结果的精度要求是不一样的,作为一直致力于追求更快,更准,更优的本博来说,自然是希望抽取的结果最优.这里的"最优"有两个方面的含义：

• 抽取的结果尽可能包含正确的行
• 抽取的结果尽量少地包含错误的结果

为了达到这样的效果,这里介绍两个主要的手段,神经网络(ANN)和错误控制(FDR).

首先来看看神经网络，对这个名字觉得耳熟的朋友肯定至少被忽悠过一次数据挖掘或者人工智能.至少本博第一次听说的时候,是被唬的不行,觉着以自己愚钝的天资还是做不明真相的围观群众好了.但是在我们这里,没有必要那么夸张,下面就由有着生物学背景的本博带领去一亲人工神经网络的芳泽.

既然是人工神经网络,从名字就知道这肯定是模仿其他某些神经组织结构机理而形成的模型.实际上,它所模仿的对象您现在也用着呢,那就是我们人类的"神经细胞"，专业的说法叫做神经元.

神经元结构上大致都可分成胞体和突起两部分,突起又分树突和轴突两种。轴突开始一段称为始段，离开细胞体若干距离后始获得髓鞘，成为神经纤维。我们日常感受的刺激在神经结构上就由树突将冲动转向细胞体.典型的神经突触是在两个神经元之间形成的单向通信机制。神经信息的流向是从突触前细胞到突触后细胞。突触通常形成在突触前细胞的轴突和突触后细胞的细胞体或树突之间.如下图所示

人工神经网络就是模仿上述神经突触联接的结构进行信息处理的数学模型.由大量的节点（或称“神经元”）和之间相互联接构成。每个节点代表一种特定的输出函数.每两个节点间的连接都代表一个对于通过该连接路径的加权值,也叫权重,这相当于人工神经网络的记忆. 输出则依赖节点间的链接方式，权重值和节点输出函数.神经网络的构建一般用来模拟自然界某种算法或者函数的逼近,或者某种逻辑的推演(例如本文的问题).


一个典型的单层神经元网络由有限个神经元构成,上图.

从左到右分别是:

• 输入层,众多神经元接受大量非线形输入信息。
• 隐藏层,简称“隐层”，是输入层和输出层之间众多神经元和链接组成的各个层面，也是实现监督学习算法的主要层面.
  
• 输出层,信息在神经元链接中传输、分析、权衡,形成输出结果。

在我们解决网页正文提取这个特定的场景下,我们采用的神经元学习算法可以归类为监督式学习网络,即从问题领域中提供训练范例，包含输入资料与输出资料。 网络从中学习输入资料与输出资料的内在对映规则.很像老师教学生几个例题,告诉答案,然后训练学生做新的题目.

"ANN是不是一种很复杂的东西?"
    "也许以前是,但现在已经不是了"
"为什么"
    "因为名气大的招数,往往也是高手努力去研究的东西,像ANN这样的利器,江湖甚至出了一个FANN"

首先建立一个fann的训练工程，然后丢给他我们预先标记好的训练文本,过程就是这么简单吖.
关于生成训练文本这里,如果完全手工的话,估计也是一件吐血的事情.但是这活儿又不能没有人工干预,所以折中的办法是预先制定一个训练数据生成算法,然后人工标记检查一下.

训练数据文本格式如下:

3 2 1 //训练对总数 每训练对输入数 每训练对输出数

1 1   //训练对 输入

1     //训练对 输出

1 0

1

-1 1

1

生成算法大致如下:

• 分别计算当前行与前行以及后行的文本密度、文本字节数、总字节数
• 若当前行文本密度在0.3以上,则标记输出结果为1，反之为0

out = map(lambda x,y,z:[x,y,z],[Para()]+d[0:-1],d,d[1:]+[Para()])
f.write("%s %s %s\n"%(len(d),3,1))
line = 3*"%s "+"\n"
for x,y,z in out:
    f.write(line%(y.density,y.bytes,len(y.text)))
    if (y.density > 0.3):        f.write("1\n")
    else:        f.write("0\n")

使用FANN进行训练的主要过程，在前文的LineWirter中加入一个方法:

def get_density_with_ann(self):
        obj = libfann.fann_create_standard_array(2, (3, 1))
        ann = fann.fann_class(obj)
        patterns = fann.read_train_from_file('train_data.txt')
        ann.train_on_data(patterns, 1000, 1, 0.0)
        return [line[3] for line in map(lambda x:[x.density,x.bytes,len(x.text),x.text] , self.lines) if ann.run(line[0:2])[0] > 0]    

使用ANN处理文本提取,可以根据输入的上下文进行启发式学习，从而使得输出更加适合于实际情况.利用机器学习来处理每一文本行的信息，可以找出有用的模式.从人工的决策过程分析，我们采用了九个因素用于决定如何过滤文本行。这些因素分别是当前行的密度、当前行的HTML字节数、当前行的输出文本长度、前一行的这三个值、后一行的这三个值。

当然神经网络也不是完美的,它需要一定量的网页学习.而且如果网页的结构变化较大，那么感知器反而会带来一些弊病.造成精度缺失的情况.本博的实际实验情况中,由于对多种类型的网页都进行了训练,结果在我们给出的示例网页中,结果稍微逊于另外一个测试用例.

如果对抽取的结果准确要求相对教高,并且又没有那么多的训练数据可供使用,那又该怎么办呢?本博这里隆重推出终极杀器----FDR 也有人称之为检出率算法,因为其只考虑期望部分的错误率.这里简要阐述FDR的意义以及应用过程。

假设问题有N个可能的候选输出，每个输出可以采用一个概率或可能性值表示输出结果的正确性概率，根据输出的概率从N个选择中选择一定数量的结果作为最后的输出。假设挑选了 个输出作为结果，其中有s个是真正正确的，另外有 个是错误的，实践中希望错误比例Q=V/R平均而言不能超过某个预先设定的值(如0．05)，在统计学上，这也就等价于控制FDR不能超过5%.

"看起来很复杂的东西,背后往往相当简单"

这个问题可以转化成：设总共有n个候选输出，每个输出对应的P值从小到大排列分别是P(1)..P(m)，若想控制FDR不能超过q，则只需找到最大的正整数i，使得P(i)<=(i*q)/m；然后，挑选对应P(1)，p(2)，⋯ ，P(i)作为输出结果,这样就能从统计学上保证FDR不超过q.

在前文的LineWriter里加入如下代码即可:

def output_fdr(self):

        self.compute_density()

        pvalue = map(lambda x:1.0/x.density ,self.lines)

        pvalue.sort(reverse=True)

        i = len(self.lines)

        m = [j for j in range(i) if pvalue[j] <= (j*5)/i][0]

        density = 1.0/pvalue[m]

        output = StringIO.StringIO()

        output.writelines(''.join([l.text for l in self.lines if l.density > density]))

        return output.getvalue()

   

采用FDR方法统计意义上的学习之后,得到的新的文本密度p为0.59.

最后简单对比下本文设计和实现的三种算法:ANN算法和估值算法总体性能较好，但是FDR在控制错误上具有很好的表现；如果应用需求很高的错误率，那么FDR是一个较好的选择；NN算法的最大问题是需要有学习的样本；估值算法对于简单的网页具有简单高效的特点.

光風(gfn)

也谈网页正文提取[上]

看到这里,如果有看官不知道啥叫正文提取,那我只能说,大哥我真的没有忽悠您，我既没说"网页去噪",也没说互联网的"自动摘要",更没说海量互联网数据的"文本挖掘"。由此可见本博是个很厚道的人,会手把手教你如何完成这个看起来牛逼实则很简单的一件事情,绝对让你感到物超所值(阅读的时间)。

从字面意思上理解,网页的正文提取嘛,无非就是把网页当中对咱最有价值的那部分文章给取出来撒.有点编程经验的朋友肯定都知道,右键网页源文件,看看html代码,取出来有正则匹配一下也就几分钟而已的事情。更好一点的办法,那自然是用上像DOM或者XPath这样专门对付html的利器,多写几次估计一分钟也不要。如果本博也这么干的话,那还怎么体现您的慧眼如矩呢:)

上面说的方法,实际上在垂直搜索引擎的定向抓取中,给一个目标站点利用DOM建立抽取模板是一个很常用也很准确的办法。但是当问题域变得稍微大那么一点点,比方说吧,我觉着谷歌做的不错，我也想搞一个的话,那咋整呢?再利用上面的办法,机械的给每一个页面建立DOM,是会死人的哟XD

那么问题其实就变成了对于任意篇网页,有没有办法"聪明"点的法子,能识别出正文部分呢?
既然我们人是可以做到这一点的,那么就说明存在利用人工智能去解决这个问题的可能性.当然,我们现在不急,先从简单的做起.

网页里面除了可读文本就是链接,图片,视频,以及其他媒体类型.而后面这些东东在HTML里面都是用专有的标签来显示的,而且还是被标签所"夹住"的。那我们来看看一个文本块里,除了标签还剩下来的东西有多少.

通过Python内置的htmllib模块和formatter的配合,我们可以统计出网页中每一行文本中标签和正文的数量.代码如下:

#coding:utf-8

import htmllib,urllib2
import formatter,StringIO

class TrackParser(htmllib.HTMLParser):

    def __init__(self, writer, *args):
        htmllib.HTMLParser.__init__(self,*args)
        self.writer = writer
  
    def parse_starttag(self,i):
        index = htmllib.HTMLParser.parse_starttag(self,i)
        self.writer.index = index
        return index

    def parse_endtag(self,i):
        self.writer.index = i
        return htmllib.HTMLParser.parse_endtag(self,i)


class Para:

    def __init__(self):
        self.text = ''
        self.bytes = 0
        self.density = 0.0

class LineWirter(formatter.AbstractWriter):
    """
    a Formatter instance to get text in lines
    """

    def __init__(self):
        self.last_index = 0
        self.lines = [Para()]
        formatter.AbstractWriter.__init__(self)

    def send_flowing_data(self, data):
        t = len(data)
        self.index += t
        b = self.index - self.last_index
        self.last_index = self.index
        l = self.lines[-1]
        l.text += data
        l.bytes += b

    def send_paragraph(self,blankline):
        if self.lines[-1].text == '':
            return
        self.lines[-1].text += 'n'*(blankline+1)
        self.lines[-1].bytes += 2*(blankline+1)
        self.lines.append(Para())
      
    def send_literal_data(self,data):
        self.send_flowing_data(data)
  
    def send_line_break(self):
        self.send_paragraph(0)



def extract_text(html):

    writer = LineWirter()
    fmt = formatter.AbstractFormatter(writer)
    parser = TrackParser(writer,fmt)
    parser.feed(html)
    parser.close()
    return writer.lines


htmls = urllib2.urlopen("http://ent.hunantv.com/d/x/20091128/503722.html")
print map(lambda x:[x.bytes,len(x.text)],extract_text(htmls.read()))

看着飞速跑过的列表,你是不是恨不得把他给全部写入一个文件来看看结果?在文件尾部加入

q = open("e.csv","w+").writelines('\n'.join(["%s,%s"%(x[0],x[1]) for x in s]))

现在结果变成了一个csv文件鸟,来上个图看看:

上图清晰的表达了该网页的文本分布,根据与页面的比对,我们发现文本所在的区域与相对应的行域保持了某种关系.这似乎说明我们的思路是正确的.

实际上行文本字节数与行总字节数的比值被称为行文本密度.有了这个概念,我们就可以对网页全文扫描计算相应的文本密度,这里我们不妨做一个假设,文本密度在0.5以上的就是我们需要的文本部分，也就是说我们认定某行的文本至少和该行的标签一样多的话,他就可能是我们需要的文本区域.

修改上述代码的两个地方,我们来初试下身手,
在原有的LineWriter里加入:

    def output(self):
        self.compute_density()
        output = StringIO.StringIO()
        for l in self.lines:
            if l.density > 0.5: //这里就是我们设置的行文本密度
                output.write(l.text)
        return output.getvalue()

修改extract_text函数

def extract_text(html):
        writer = LineWirter()
        fmt = formatter.AbstractFormatter(writer)
        parser = TrackParser(writer,fmt)
        parser.feed(html)
        parser.close()
        return writer.output()

文件末尾改成

htmls = urllib2.urlopen("http://ent.hunantv.com/d/x/20091128/503722.html")
s = open('e.html','w+').write(extract_text(htmls.read()))

先透口气,然后平静的点开e.html，喔,你看见了什么！

激动之后,应该会有这么一个疑问,刚才我们设置的文本密度为0.5，这个数字到底是怎么来的?他具有普适性么?

其实这个文本密度是可以计算出来的:
设y为行文本集合,z为行标签集合,则文本密度p为:

设i代表任意行,分别用yi,zi代表任意行文本/标签的长度,设且均符合正态分布.uy,uz分别代表行文本和行标签的平均长度：

计算方差:

如果选择文本行的概率为p,那么标签行就为1-p.相应的各文本项平均长度为

最后得到p的估值:

将我们选用的网页实际情况带入以后,我们得到真实的文本密度p大约为0.53,和估计值很相近.学术界有针对行的做了大量实验,得出新闻资讯类网站的文本密度大约在0.4-0.6左右,sina和sohu的这个值大约都是0.6;博客类网站的文本密度大约在0.7-0.8之间.

作为这个话题上半部分的结束,谈谈这个文本密度的实际应用,除了本文所涉及到的文本抽取以外,文本密度现在被广泛应用于搜索引擎网页价值分析的预处理,同时我们也大体可以看出网站内容的大致分布.

下半部分,本博将引入ANN(神经网络)和FDR(错误控制)的相关方法继续探讨这个话题.敬请围观.


光風(gfn)

数组过滤之bitmap解法

求一个数组中过滤掉重复的元素,并保证原有的元素均存在。

>>> data
['a', 'a', 'z', 'b', 'a', 'b', 'c']
>>> def foo(f,n=0):
    if f%2 != 0:
        l.append(n)
    if f/2 == 1:
        l.append(n+1)
        return l
    n += 1
    foo(f/2,n)

   
>>> l = []
>>> p = foo(reduce(lambda x,y:x|y,map(lambda x:1<<(128-ord(x)),data)))
>>> r = map(lambda x:chr(128-x),l)
>>> r
['z', 'c', 'b', 'a']

March Liu大法

>>def refoo(d, k):
c = d.get(k, 0)
d[k] = c+1
return d

>>> map(lambda p: p[0], filter(lambda p:p[1]==1, reduce(refoo, data, {}).iteritems()))