分类 算法 下的文章

很久之前参加了个比赛，实现了一个提取论坛内容的算法。

一、挖掘目标

将论坛之中的内容按以下方式存储：

二、总体流程

总体流程图

三、主要贡献

本文做的主要贡献是实现了根据楼层相似结构地位并分割楼层。

我们查看BBS论坛页面的网页结构发现以下特征：

1.在同一个web页面中，每个楼层所在的DOM结构的节点的子树都很相似。

2.不同楼层都位于同一个父节点下面。

3.不同楼层之间为兄弟节点。

如下图所示：

楼层分割算法具体步骤：

1.筛选标签

首先将web页面转化为DOM结构，找出不可能成为节点的标签并剔除例如：

<link><head><p>......

对于一个帖子而言，有这么几方面重要的内容：作者、时间、正文内容，这三个方面之中，作者、正文内容结构是难以预测的，但是时间我们可以通过使用正则表达式进行匹配。因此，我们遍历出所有节点，将节点中不含有时间的节点剔除。

另外我们发现，一个楼层块中必定有很多的标签块，如作者、时间、内容等等，我们对每个楼层下的节点进行递归循环，发现楼层下的标签数量比较多，因此我们设置一个阈值进行过滤。将的标签数目少的节点过滤。

2.定位楼层

经过以上几个步骤之后，我们将每一块与他的所有兄弟节点进行比较，找到相同的块，并作为一个列表存储。如下图：

将2、3与4进行比较，8、9、10进行比较，最终我们会得到几个列表：

[2] [3] [4] [5,6] ...[8,9,10]...

列表内节点个数最多的为楼层序列。

一、简介

Anti-Trust Rank算法经过Trust Rank算法思想而设计出，由作弊的页面开始，向相反的方向传播反信任值（也就是作弊值），目的是检测垃圾页面，然后由搜索引擎过滤。Anti-Trust Rank算法准则大致等同于Trust Rank算法即好的页面很少指向垃圾页面。这个原则其实也暗示了一点，那就是指向垃圾页面的有很大的可能也是垃圾页面。Trust Rank算法从一组可信赖的页面开始，经过外链接将信任值进行传播。同样的，在Anti-Trust Rank算法中，从一组垃圾种子页面开始，通过内链接（即外链接指向这些垃圾页面的网页）反向传播传播反信任值。我们可以设置一个阀值如果页面的反信任值高于这个阀值，就可归类为作弊网页。

二、公式使用

对于Anti-Trust Rank算法来说，我们首先要做的是选取种子页面，注意与Trust Rank算法不同的是，Anti-Trust Rank算法选取的是作弊网页作为种子页面。

Anti-Trust Rank算法的计算公式为：
QQ20180713152017

其中α为衰减因子取值一般为0.80或0.85，关系矩阵U的计算公式如下：20180713155309
初始值A的公式为：QQ20180713160409
初始值d的公式为： QQ20180713160529

三、算法示例

我们首先设计一个网站链接关系图，圆代表不同的网站或网页，圆之间的箭头代表网站之间的链接关系：201807131610

QQ20180713161045

注意，此时的U与Trust Rank算法中的T是不同的，然后按照公式迭代，不断更新A的值。

下面解释下TrustRank算法

一、简介

搜索引擎在使用Page Rank算法计算网页排名的时候，非常依赖网络页面之间的链接关系，因此，链接的质量计算排名变得越来越重要。但是，有些网页采用作弊的行为来提升自己的排名，因此，一个良好的检测作弊网页的算法变得越来越重要。Google为了提高网站的检索质量，设计出了TrustRank算法来检测垃圾作弊网站。

Trust Rank算法基于了一个重要的观察的经验：好的页面很少指向坏的页面。这个概念是相当直观的，作弊页面是为了误导搜索引擎而被建立的，不能提供有效地信息。因此，人们创建可信赖的页面很少有原因指向作弊页面。

这个假设的发过来说是不成立的，即坏的页面很少指向好的页面，因为作弊网页为了提高网页的信任指数，通常会链接到许多的高质量的、权威的网站。

基于以上假设，挑选完全可以信赖的网站，将网站的TrustRank值设为最高，通过迭代运算将可信任值传播出去。也有一些可信赖的网站被欺骗链接到作弊网站，不过距离第一级网站越远信任值指数便会逐渐下降。这样通过TrustRank算法就可以对所有网站计算相应的信任值，信任孩子越高的网站可信赖信就越大。

二、公式实现

对于TrustRank算法来说，我们需要首先选取种子页面（即完全可以信赖的页面），然后在进行Trust Rank算法的计算。

TrustRank算法计算公式为：

20180706202113

其中α为衰减因子一般取值为0.80或0.85关系矩阵T的计算公式如下：QQ20180706202310

初始值r的公式为：

QQ20180706202428

d的公式为：

20180706202612

三、算法示例

我们首先设计一个网站链接关系图，圆代表不同的网站或网页，圆之间的箭头代表网站之间的链接关系：

201807062028

QQ20180706203132

然后依据以上公式迭代20次每次更新r值。

今天来讲一下搜索引擎的PageRank算法

一、算法介绍

早期的搜索引擎大都采用分类检索的方式，即靠人工辨别来对网站进行分类,类似hao123这样的网站。

随着时代的发展，网页变得越来越多，用人工识别的方式对网页进行识别变得越来越不现实，搜索引擎开始采用文本检索的方式来对返回用户所查询的信息，就是根据用户搜索的文本与网页内容的相关联程度来返回搜索的网站。但是这种方法的搜索结果不好，因为，有一些网站采用作弊的方式，在网页中添加许多关键词来提高自己的排名，在这种情况下，Google的两名创始人Larry Page与Sergey Brin开始对网页排序问题进行研究，依据学术界评判论文的重要程度的方法，查看论文引用次数，将这种方法用到了网页排序中，PageRank算法就产生了。

PageRank算法是最流行的基于链接的方法来确定页面的全局相关性或重要性。PageRank算法分配一个重要的分数比（页面排名），对于指向它的其他网页。一个页面的分数，由所有指向它的页面的分数来确定即一个页面的排名是由所有指向它的页面的重要性经过递归算法得到。一个页面如果有较多的链如页面便会有较高的等级，相反，如果一个页面没有任何链入页面，那么它没有等级。

二、公式实现

PageRank算法中页面p的得分可用r(p)来计算，计算公式如下：

20180630171951

其中是α衰减因子,一般取值0.8或0.85，outdegree(q)是页面q指向页面p的出度，N为页面的数量。

上面公式可简化如下：

20180630183008

初始化R的值均为1/N。

如果PageRank算法被执行在网站的链接结构上，每个网站会有一个全局重要性分数。如果网站被按照他们的PageRank算法分数从大到小排序，那些位于序列顶端的网站被认为是值得信赖的。在这些网站汇总标签为可信赖的网站被选作种子。

在上面的公式之中，我们能看出页面p的PageRank算法分数是由两个部分组成。一部分来自指向它的页面，另一部分来自其他所有页面的平均值。前者说明指向一个网页的重要网页越多这个页面就越重要。结果，PageRank算法高排名的页面都有很高的入度。

三、算法示例

我们首先设计一个简单的网络链接关系图，每个圆代表一个网站，然后圆之间的箭头代表网站之间的链接关系：

20180630202416

初始化：

20180630202531

通过公式20180630203523不断地迭代运算，最后得到结果R。

def subseque(s1, s2):
    res = [['0' for x in range(len(s2) + 1)] for y in range(len(s1) + 1)]
    m = [[0 for x in range(len(s2) + 1)] for y in range(len(s1) + 1)]
    # print m
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                m[i + 1][j + 1] = m[i][j] + 1
                res[i + 1][j + 1] = 'xie'
            elif m[i + 1][j] > m[i][j + 1]:
                m[i + 1][j + 1] = m[i + 1][j]
                res[i + 1][j + 1] = 'zuo'
            else:
                m[i + 1][j + 1] = m[i][j + 1]
                res[i + 1][j + 1] = 'shang'
    (i, j) = (len(s1), len(s2))
    print numpy.array(res)
    result = []
    while m[i][j]:
        c = res[i][j]
        if c == 'xie':
            result.append(s1[i - 1])
            i -= 1
            j -= 1
        if c == 'zuo':
            j -= 1
        if c == 'shang':
            i -= 1
    print result

def random_str(randomlength=20):
    str = ''
    chars = 'abcdefghigklmnopqrstuvwxyz'
    length = len(chars) - 1
    random = Random()
    for i in range(randomlength):
        str+=chars[random.randint(0, length)]
    return str
  1. 1
  2. 2
  3. 3