TF-IDFとTextRankアルゴリズム抽出キーワードソース分析

TF-IDFとTextRankアルゴリズム抽出キーワードソース分析
jieba分詞のキーワード抽出機能は,jieba/analyseディレクトリの下で実現される.
ここで、

__ init__.pyは主にjieba分詞をカプセル化するキーワード抽出インタフェースに用いられる.

tfidf.pyはTF-IDFアルゴリズムに基づいてキーワードを抽出することを実現した.

textrank.pyはTextRankアルゴリズムに基づくキーワード抽出を実現した.

1.TF-IDFアルゴリズム
TF-IDFアルゴリズムに基づいてキーワードを抽出する主調関数はTFIDFである.extract_tags関数は主にjieba/analyse/tfidfである.pyで実装します.
ここで、TFIDFは、TF−IDFアルゴリズムのキーワード抽出のために定義されたクラスである.クラスは初期化時に、デフォルトで分詞関数tokenizer=jiebaをロードします.dt、品詞表記関数postokenizer=jieba.posseg.dt、ストップワードstop_words = self.STOP_WORDS.copy()、idf辞書idf_loader=IDFLoader(idf_path or DEFAULT_IDF)などを取得し、idf辞書およびidf中値(ある語がidf辞書に表示されない場合、idf中値をこの語のidf値とする)を取得する.

def __init__(self, idf_path=None):
    #   
    self.tokenizer = jieba.dt
    self.postokenizer = jieba.posseg.dt
    self.stop_words = self.STOP_WORDS.copy()
    self.idf_loader = IDFLoader(idf_path or DEFAULT_IDF)
    self.idf_freq, self.median_idf = self.idf_loader.get_idf()

そして,TF−IDFアルゴリズムによるキーワード抽出を開始する.
まず,品詞制限セットが入力されたか否かに基づいて,品詞注釈インタフェースを呼び出すか分詞インタフェースを呼び出すかを決定する.例えば,品詞制限集合は,["ns","n","vn","v","nr"]であり,品詞が地名,名詞,動名詞,動詞,人名といった品詞のみからキーワードを抽出できることを示す.

語性制限集合が伝達された場合、まず語性表示インタフェースを呼び出し、入力文に対して語性表示を行い、分詞と対応する語性を得る.分詞結果を順次遍歴し、その語の語性が語性制限集合にない場合はスキップする.単語の長さが2未満、または単語が無効な場合はスキップします.最後に条件を満たす語を語周波数辞書に追加し、出現回数を1とする.その後、語周波数辞書を遍歴し、idf辞書に基づいて各語のidf値を得、語周波数辞書の回数の総和で割って、各語のtf*idf値を得る.重みフラグビットが設定されている場合、tf-idf値に基づいて語周波数辞書の語を降順に並べ替え、topK個の語をキーワードとして出力する.

語性制限集合が入力されていない場合、まず分詞インタフェースを呼び出し、入力文を分詞し、分詞を得る.分詞の結果を順次遍歴し、語の長さが2未満、または語が停用語であればスキップする.最後に条件を満たす語を語周波数辞書に追加し、出現回数を1とする.その後、語周波数辞書を遍歴し、idf辞書に基づいて各語のidf値を得、語周波数辞書の回数の総和で割って、各語のtf*idf値を得る.重みフラグビットが設定されている場合、tf-idf値に基づいて語周波数辞書の語を降順に並べ替え、topK個の語をキーワードとして出力する.

ソース分析:

def extract_tags(self, sentence, topK=20, withWeight=False, allowPOS=(), withFlag=False):
    #          
    if allowPOS:
        allowPOS = frozenset(allowPOS)
        #         
        words = self.postokenizer.cut(sentence)
    #           
    else:
        #       
        words = self.tokenizer.cut(sentence)
    freq = {}
    for w in words:
        if allowPOS:
            if w.flag not in allowPOS:
                continue
            elif not withFlag:
                w = w.word
        wc = w.word if allowPOS and withFlag else w
        #           2，         
        if len(wc.strip()) < 2 or wc.lower() in self.stop_words:
            continue
        #           ，   1
        freq[w] = freq.get(w, 0.0) + 1.0
    #            
    total = sum(freq.values())
    for k in freq:
        kw = k.word if allowPOS and withFlag else k
        #       tf-idf 
        freq[k] *= self.idf_freq.get(kw, self.median_idf) / total
    
    #   tf-idf     
    if withWeight:
        tags = sorted(freq.items(), key=itemgetter(1), reverse=True)
    else:
        tags = sorted(freq, key=freq.__getitem__, reverse=True)
    #   topK       
    if topK:
        return tags[:topK]
    else:
        return tags

2.TextRankアルゴリズム
TextRankアルゴリズムに基づいてキーワードを抽出する主調関数はTextRankである.textrank関数は、主にjieba/analyse/textrankである.pyで実装します.
ここで,TextRankはTextRankアルゴリズムのキーワード抽出のために定義されたクラスである.クラスは初期化時に、デフォルトで分詞関数と品詞寸法関数tokenizer=postokenizer=jiebaをロードします.posseg.dt、ストップワードテーブルstop_words = self.STOP_WORDS.copy()、語フィルタ集合pos_filt=frozenset(‘ns’,‘n’,‘vn’,‘v’),ウィンドウspan=5,((‘ns’,‘n’,‘vn’,‘v’))は語性が地名,名詞,動名詞,動詞であることを表す.
まず無方向有権図を定義し、文を分詞する.分詞の結果を順次たどり、ある語iがフィルタ条件(語性は語性フィルタ集合にあり、語の長さは2以上であり、語は停用語ではない)を満たした後、その語の後のウィンドウ範囲内の語j(これらの語もフィルタ条件を満たす必要がある)をkeyとし、出現回数をvalueとし、共起辞書に追加します.
次に、共起辞書を順に巡回し、辞書内の各要素、key=(語i、語j)、value=語iおよび語jが出現する回数を、語i、語jをエッジの開始点および終了点とし、共起の回数をエッジの重みとして、前に定義した無方向有権図に追加する.
その後、この無方向有権図に対して反復演算textrankアルゴリズムを行い、最終的にいくつかの反復を経た後、アルゴリズムは収束し、各語は1つの指標値に対応する.
重みフラグビットが設定されている場合、無方向有権図の語を指標値に基づいて降順に並べ替え、最後にtopK個の語をキーワードとして出力する.

def textrank(self, sentence, topK=20, withWeight=False, allowPOS=('ns', 'n', 'vn', 'v'), withFlag=False):

    self.pos_filt = frozenset(allowPOS)
    #        
    g = UndirectWeightedGraph()
    #       
    cm = defaultdict(int)
    #   
    words = tuple(self.tokenizer.cut(sentence))
    #        
    for i, wp in enumerate(words):
        #  i       
        if self.pairfilter(wp):
            #      i          
            for j in xrange(i + 1, i + self.span):
                #  j         
                if j >= len(words):
                    break
                #  j       ，   
                if not self.pairfilter(words[j]):
                    continue
                #   i  j  key，       value，        
                if allowPOS and withFlag:
                    cm[(wp, words[j])] += 1
                else:
                    cm[(wp.word, words[j].word)] += 1
    #              ，  i， j            ，           
    for terms, w in cm.items():
        g.addEdge(terms[0], terms[1], w)
    
    #   textrank  
    nodes_rank = g.rank()
    
    #          
    if withWeight:
        tags = sorted(nodes_rank.items(), key=itemgetter(1), reverse=True)
    else:
        tags = sorted(nodes_rank, key=nodes_rank.__getitem__, reverse=True)

    #   topK       
    if topK:
        return tags[:topK]
    else:
        return tags

ここで,無重みマップの定義と実装はUndirectWeightedGraphクラスで実現される.UndirectWeightedGraphクラスによる初期化関数_init__,無方向有権図とは辞書であり,辞書のkeyは後続に追加する語であり,辞書のvalueは,(開始点,終了点,エッジの重み)からなる三元群からなるリストであり,この語を開始点とするすべてのエッジを表すことが分かった.
無方向図にエッジを追加する操作はaddEdge関数で行われます.無方向図であるため、startを開始点とし、endを終了点とし、startを終了点とし、endを開始点とする必要があります.この2つのエッジの重みは同じです.

def addEdge(self, start, end, weight):
    # use a tuple (start, end, weight) instead of a Edge object
    self.graph[start].append((start, end, weight))
    self.graph[end].append((end, start, weight))

textrankアルゴリズム反復の実行はrank関数で行われる.
まず、各ノードに同じ重みを付与し、そのノードのすべての出度の和を算出する.
その後、安定した結果が得られるように何回か反復する.
反復ごとに、各ノードを順次巡回します.ノードnについては、まず、無方向有権図からノードnの全ての入度ノード(無方向有権図については、入度ノードは出度ノードと同じであり、いずれもノードnに接続されたノードである)を得る、この入度ノードの全ての出度の回数を先に算出したが、一方、ノードnに対する重み値の寄与は、ノードnとの共起回数/このノードのすべての出度の回数に、それ自体の重み値を乗じ、各入度ノードで得られた重み値を加算し、一定の減衰係数を乗じることで、ノードnの重み値を得ることができる.
反復が完了すると、重み値が正規化され、各ノードと対応する重み値が返されます.

def rank(self):
    ws = defaultdict(float)
    outSum = defaultdict(float)

    wsdef = 1.0 / (len(self.graph) or 1.0)
    #           
    #               
    for n, out in self.graph.items():
        ws[n] = wsdef
        outSum[n] = sum((e[2] for e in out), 0.0)

    # this line for build stable iteration
    sorted_keys = sorted(self.graph.keys())
    #      
    for x in xrange(10):  # 10 iters
        #       
        for n in sorted_keys:
            s = 0
            #          
            for e in self.graph[n]:
                #                
                #     =        n      /             
                s += e[2] / outSum[e[1]] * ws[e[1]]
            #     n   
            ws[n] = (1 - self.d) + self.d * s

    (min_rank, max_rank) = (sys.float_info[0], sys.float_info[3])

    #             
    for w in itervalues(ws):
        if w < min_rank:
            min_rank = w
        if w > max_rank:
            max_rank = w

    #         
    for n, w in ws.items():
        # to unify the weights, don't *100.
        ws[n] = (w - min_rank / 10.0) / (max_rank - min_rank / 10.0)

    return ws