也谈网页正文提取[下]

上回书到使用行文本密度(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)