TextRank演算法

TD-IDF是基于詞頻的演算法，而TextRank是基于圖形的演算法，

TextRank是受到PageRank演算法的啟發，

PageRank演算法

PageRank主要用于對在線搜索結果中的網頁進行排序，

PageRank對于每個網頁頁面都給出一個正實數，表示網頁的重要程度，PageRank值越高，表示網頁越重要，在互聯網搜索的排序中越可能被排在前面，同樣，被鏈接的網頁的PageRank值也會相應的因此而提高，

假設整個互聯網是一個有向圖，節點是網頁，每條邊是轉移概率，網頁瀏覽者在每個頁面上依照連接出去的超鏈接，以等概率跳轉到下一個網頁，并且在網頁上持續不斷地進行這樣的隨機跳轉，這個程序形成了一階馬爾科夫鏈，比如下圖：
在這里插入圖片描述
　　每個笑臉是一個網頁，既有其他網頁跳轉到該網頁，該網頁也會跳轉到其他網頁，在不斷地跳轉之后，這個馬爾科夫鏈會形成一個平穩分布，而PageRank就是這個平穩分布，每個網頁的PageRank值就是平穩概率，

　　PageRank的核心公式是PageRank值的計算公式，公式如下：

　　其中，PR(Vi)表示結點Vi的rank值，In(Vi)表示結點Vi的前驅結點集合，Out(Vj)表示結點Vj的后繼結點集合，
　　這個公式來自于《統計學習方法》，等號右邊的平滑項（通過某種處理，避免一些突變的畸形值，盡可能接近實際情況）不是（1-d），而是(1-d)/n，
　　阻尼系數d(damping factor)的意義是，在任意時刻，用戶到達某頁面后并繼續向后瀏覽的概率，1-d就是用戶停止點擊，隨機跳到新URL的概率，
　　加平滑項是因為有些網頁沒有跳出去的鏈接，那么轉移到其他網頁的概率將會是0，這樣就無法保證存在馬爾科夫鏈的平穩分布，
　　于是，我們假設網頁以等概率（1/n）跳轉到任何網頁，再按照阻尼系數d，對這個等概率（1/n）與存在鏈接的網頁的轉移概率進行線性組合，那么馬爾科夫鏈一定存在平穩分布，一定可以得到網頁的PageRank值，

　　所以PageRank的定義意味著網頁瀏覽者按照以下方式在網上隨機游走：以概率d按照存在的超鏈接隨機跳轉，以等概率從超鏈接跳轉到下一個頁面；或以概率(1-d)進行完全隨機跳轉，這時以等概率（1/n）跳轉到任意網頁，

　　PageRank的計算是一個迭代程序，先假設一個初始的PageRank分布，通過迭代，不斷計算所有網頁的PageRank值，直到收斂為止，也就是：
在這里插入圖片描述

從PageRank到TextRank演算法

　　和基于詞頻( TF-IDF )相比，TextRank進一步考慮了檔案內詞條之間的語意關系， 也就是說考慮到額這個詞條的背景關系，如果這個詞的背景關系都是一些很重要的詞，那么這個詞大概率也是很重要的詞，

基本原理：

將檔案按照整句進行分割
分詞并清理，只保留指定詞性的詞條
以整句為單位計算詞條的共現矩陣（主要用于發現主題，解決詞向量相近關系的表示），只要在一個句子里出現，就要考慮共現性了，
按指定視窗長度K，構建詞條網路
基于網路連接特征計算詞條重要性
排序并輸出結果

TextRank演算法介紹

TextRank

TextRank 演算法是一種用于文本的基于圖的排序演算法，其基本思想來源于谷歌的 PageRank演算法, 通過把文本分割成若干組成單元(單詞、句子)并建立圖模型, 利用投票機制對文本中的重要成分進行排序, 僅利用單篇檔案本身的資訊即可實作關鍵詞提取、文摘，和 LDA、HMM 等模型不同, TextRank不需要事先對多篇檔案進行學習訓練, 因其簡潔有效而得到廣泛應用，

　　TextRank 一般模型可以表示為一個有向有權圖 G =(V, E), 由點集合 V和邊集合 E 組成, E 是V ×V的子集，圖中任兩點 Vi , Vj 之間邊的權重為 w_ji , 對于一個給定的點 V_i, In(V_i) 為指向該點的點集合 , Out(V_i) 為點 V_i指向的點集合，點 V_i 的得分定義如下:

　　其中, d 為阻尼系數, 取值范圍為 0 到 1, 代表從圖中某一特定點指向其他任意點的概率, 一般取值為 0.85，使用TextRank 演算法計算圖中各點的得分時, 需要給圖中的點指定任意的初值, 并遞回計算直到收斂, 即圖中任意一點的誤差率小于給定的極限值時就可以達到收斂, 一般該極限值取 0.0001，

1. 基于TextRank的關鍵詞提取

　　關鍵詞抽取的任務就是從一段給定的文本中自動抽取出若干有意義的詞語或詞組，TextRank演算法是利用區域詞匯之間關系（共現視窗）對后續關鍵詞進行排序，直接從文本本身抽取，其主要步驟如下：

　　（1）把給定的文本T按照完整句子進行分割，即

　　（2）對于每個句子，進行分詞和詞性標注處理，并過濾掉停用詞，只保留指定詞性的單詞，如名詞、動詞、形容詞，即，其中是保留后的候選關鍵詞，

　　（3）構建候選關鍵詞圖G = (V,E)，其中V為節點集，由（2）生成的候選關鍵詞組成，然后采用共現關系（co-occurrence）構造任兩點之間的邊，兩個節點之間存在邊僅當它們對應的詞匯在長度為K的視窗中共現，K表示視窗大小，即最多共現K個單詞，

　　（4）根據上面公式，迭代傳播各節點的權重，直至收斂，

　　（5）對節點權重進行倒序排序，從而得到最重要的T個單詞，作為候選關鍵詞，

　　（6）由（5）得到最重要的T個單詞，在原始文本中進行標記，若形成相鄰詞組，則組合成多詞關鍵詞，例如，文本中有句子“Matlab code for plotting ambiguity function”，如果“Matlab”和“code”均屬于候選關鍵詞，則組合成“Matlab code”加入關鍵詞序列，

用jieba實作TextRank演算法

from gensim.corpora import Dictionary

import wordcloud
import pandas as pd
import jieba
import jieba.analyse
import matplotlib.pyplot as plt
from nltk.corpus import brown

from sklearn.feature_extraction.text import CountVectorizer

# 資料準備
# ============================================================================================================
#
raw = pd.read_table('./金庸-射雕英雄傳txt精校版.txt',names=['txt'],encoding='GBK')
# print(raw)

# 加入章節標識
# 章節判斷用變數預處理
def m_head(tmpstr):
    return tmpstr[:1]  #取第一個字

def m_mid(tmpstr):
    return tmpstr.find("回 ")

# 用apply函式將下面的屬性加入到對應列
raw['head'] = raw.txt.apply(m_head)
raw['mid'] = raw.txt.apply(m_mid)
raw['len'] = raw.txt.apply(len)


# 章節判斷
chapnum = 0
for i in range(len(raw)):
    if raw['head'][i] == "第" and raw['mid'][i] >0 and raw['len'][i]<30:
        chapnum += 1
    if chapnum >= 40 and raw['txt'][i] == "附錄一：成吉思汗家族":
        chapnum=0
    raw.loc[i,'chap'] = chapnum

# 洗掉臨時變數
del raw['head']
del raw['mid']
del raw['len']

# 段落聚合  根據章節聚合
rawgrp = raw.groupby('chap')

chapter = rawgrp.agg(sum)

chapter = chapter[chapter.index != 0]
# 設定分詞以及清理停用詞函式
# 先用pandas將停用詞讀出，存到變數w中，最后取出w，轉為list
stoplist = list(pd.read_csv('停用詞.txt',names=['w'],sep='aaa',encoding='utf-8',engine='python').w)
# 清理停用詞哈數
def m_cut(intxt):
    return [w for w in jieba.cut(intxt) if w not in stoplist and len(w)>1]
countvec = CountVectorizer()

analyze = countvec.build_analyzer()
# 使用空格分開
t = analyze('郭靖 和 哀牢山 三十六 劍 ，')
# 默認刪去停用詞串列中的詞和符號
print(t)
# ['郭靖', '哀牢山', '三十六']


#
# ============================================================================================================
# 資料準備結束


# TextRank演算法的jieba實作

# 對射雕英雄傳的第一章進行關鍵詞抓取，取前20個
t = jieba.analyse.textrank(
    chapter.txt[1],
    topK=20,#詞頻前20
    withWeight=True
)
# 默認是過濾詞性的 也就是allowPOS=('ns','n','vn','v')  默認值
print(t)
# 這個結果和前面的TF-IDF結果差異較大，因為TextRank演算法過濾掉了一些詞性，只保留了名詞和動詞
# [('官兵', 1.0), ('武官', 0.9334143199050102), ('丘處機', 0.7358359699167335), ('娘子', 0.6744231421648419), ('丈夫', 0.5830294283456839), ('金兵', 0.5781198085682175), ('臨安', 0.5770670188243039), ('說道', 0.5770566609658306), ('小人', 0.5090129786491732), ('只見', 0.4571074590990817), ('皇帝', 0.44602714989497655), ('出來', 0.44153726005111005), ('妻子', 0.3806600930485957), ('道人', 0.37477396448704836), ('道長', 0.3700338339927484), ('百姓', 0.326847924487172), ('短劍', 0.30052710293852547), ('雙手', 0.29602787925127344), ('心想', 0.29137224579945303), ('貧道', 0.28869640746976294)]

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/179033.html

標籤：其他

上一篇：0188. Best Time to Buy and Sell Stock IV (H)

下一篇：TextRank演算法