keyGraph®で特徴語抽出

# 1.最初に
* 特徴語の抽出方法（にも使える方法）で keyGraph®というものを発見。文章中の単語（など）を「土台」と「柱」と「屋根」に分けて、「屋根」に相当する単語（など）をその文章の重要部分（主張）と判定するようだ。
* いろんな土台から強い柱で支えられている屋根は確かに重要な言葉と直感的に感じたのでやってみたい。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/2b2bd4f6-c3a0-ca44-63d3-2821e2399fa9.png)
（出典：[「TopK アルゴリズムを用いた連続 KeyGraph SNS 上のキーワード」](https://proceedings-of-deim.github.io/DEIM2021/papers/H24-4.pdf#:~:text=KeyGraph%20%E3%81%A8%E3%81%AF%EF%BC%8C%E6%96%87%E6%9B%B8%E3%81%8B%E3%82%89%E4%B8%BB%E5%BC%B5%E3%81%A8%E6%A6%82%E8%A6%81%E3%82%92%E8%A1%A8%E3%81%99%E3%82%AD%E3%83%BC%E3%83%AF%E3%83%BC%E3%83%89%E3%82%92%E6%8A%BD%20%E5%87%BA%E3%81%99%E3%82%8B%E6%89%8B%E6%B3%95%E3%81%A7%E3%81%82%E3%82%8B%EF%BC%8E%E6%8A%BD%E5%87%BA%E3%81%95%E3%82%8C%E3%81%9F%E3%82%AD%E3%83%BC%E3%83%AF%E3%83%BC%E3%83%89%E3%81%AF%E6%96%87%E6%9B%B8%E6%A4%9C%E7%B4%A2%E3%82%84%E8%A6%81%E7%B4%84%E3%81%AB%20%E7%94%A8%E3%81%84%E3%82%8B%E3%81%93%E3%81%A8%E3%82%92%E6%83%B3%E5%AE%9A%E3%81%97%E3%81%A6%E3%81%84%E3%82%8B%EF%BC%8E%E5%90%84%E8%AA%9E%E3%82%92%E3%83%8E%E3%83%BC%E3%83%89%EF%BC%8C%E8%AA%9E%E3%81%A8%E8%AA%9E%E3%81%AE%E5%85%B1%E8%B5%B7%E3%82%92%E3%83%AA,%E3%83%B3%E3%82%AF%E3%81%A7%E8%A1%A8%E3%81%97%EF%BC%8C%E5%9B%B34%20%E3%81%AE%E3%82%88%E3%81%86%E3%81%AA%E3%82%B0%E3%83%A9%E3%83%95%E3%81%A8%E3%81%97%E3%81%A6%E8%A1%A8%E7%8F%BE%E3%81%99%E3%82%8B%EF%BC%8E%20%E5%9B%B34%20%E3%82%AD%E3%83%BC%E3%82%B0%E3%83%A9%E3%83%95%E3%81%AE%E4%BE%8B)）

* 東京大学の[大澤・早矢仕研究室](https://www.panda.sys.t.u-tokyo.ac.jp/)が10年ほど前に開発したアルゴリズムだそうで。[公開されているツール](https://www.panda.sys.t.u-tokyo.ac.jp/ohsawa/visual.html)も発見。登録商標も発見（[１](https://www.j-platpat.inpit.go.jp/c1800/TR/JP-2010-063855/B82E33767E69F5C9EC30C682E68541C4E9DBBACEEA08EBAF848488A68E7C20D9/40/ja)、[２](https://www.j-platpat.inpit.go.jp/c1800/TR/JP-2012-093371/987F9992CC6702ADF6D78F10DBF8C18861D0C975CBDE41609EACEB3C3169FED5/40/ja)）

* 現在取り組んでる特許データと有価証券報告書の研究開発部分について、tfidfの補完となるような抽出ができないかコードを組んでみた。


# 2.　さっそくプログラムを作成
* 具体的なソースコード（アルゴリズム）があまり書いてないのだが、下記２つの論文に抽出STEPがあったのでそれを見ながら試行錯誤。論文ではさらに先をいっているようですが。
 
####  [「連続KeyGraphによるソーシャルネットワーキングサービス上の要約」](https://db-event.jpn.org/deim2020/post/proceedings/papers/I8-4.pdf)
####  [「KeyGraph による主張点の極性評価」](https://db-event.jpn.org/deim2015/paper/349.pdf)

####  <font color="red">20220606:[もっと詳しい解説がある論文](https://dspace.jaist.ac.jp/dspace/handle/10119/10052)を発見したのでこちらの方法で書き換え予定</font>


# 3.  コード
論文の説明からコードを組むのが難しかった。最後の屋根とか特に

### STEP0:事前準備
<details>


```python
#必要なライブラリ入れる
!pip install pyvis
!pip install tinysegmenter
!pip install janome

#吉野データをローカルにダウンロード
!curl -o yoshino.csv https://storage.googleapis.com/yoshino/yoshino.csv

```


```python
#@title 事前準備
import numpy as np
import pandas as pd
import tinysegmenter
from janome.tokenizer import Tokenizer
from janome.analyzer import Analyzer
from janome.tokenfilter import *
from janome.charfilter import *


def wakati_ts(text):
    wakati_list = segmenter.tokenize(text)
    rev_wakati_list = [y for y in wakati_list if len(y)]
    return '|'.join(rev_wakati_list)


# アナライザーのフィルター
char_filters = [UnicodeNormalizeCharFilter(), RegexReplaceCharFilter(r"[IiⅠｉ?.*/~=()〝 <>:：《°!！!？（）-]+", "")]
tokenizer = Tokenizer()
token_filters = [POSKeepFilter(["名詞"]), POSStopFilter(["名詞,非自立", "名詞,数", "名詞,代名詞", "名詞,接尾"]),LowerCaseFilter()]
a = Analyzer(char_filters=char_filters, tokenizer=tokenizer, token_filters=token_filters)




def wakati_janome(text):
    stopwords = ["下記","手段","課題","特徴","範囲"]
    return "|".join([token.surface for token in a.analyze(text) if not (token.surface in stopwords or len(token.surface)==1)])

segmenter = tinysegmenter.TinySegmenter()



def make_co_occur_df(dataframe,colname,sep):
    df_co_occur_network = \
    pd.merge(dataframe[colname].str.split(sep,expand=True).stack().reset_index(),
             dataframe[colname].str.split(sep,expand=True).stack().reset_index(),
             on="level_0",how="outer")\
             .pipe(lambda df: df[df["0_x"] != df["0_y"]])\
             .groupby(["0_x","0_y"],as_index=False).size()\
             .reset_index()\
             .rename(columns={"0_x":"source","0_y":"target",0:"weight"})\
             .pipe(lambda df:df[pd.DataFrame(np.sort(df[['source','target']].values)).duplicated()])
             #20210408最終行追加


    #source,target,weight(共起回数)のdfを返す。
    return df_co_occur_network


```

```python
import networkx as nx
import pandas as pd

df = pd.read_csv("yoshino.csv",encoding="cp932")
#df['wakati'] = df['要約'].str.replace("【目的】","").apply(wakati)
df['wakati'] = df['請求項'].astype(str).apply(wakati_janome)
edges = make_co_occur_df(df,"wakati","|")

```

* 分かち書き後はこんな感じ
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/a9629e40-1aa7-30c0-71fd-6bfa02bf8c71.png)

</details>



### STEP1:土台語の抽出
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/394b3a80-3161-19aa-0248-d76c0d136490.png)

これは集計だけなので簡単。

<details>

```python
#@title STEP1:文書中の単語の出現頻度を算出し，頻出語上位 M 語を土台語とする

#上位M語の指定
nodeM = 200
edgeM = nodeM-1

#間違え：node_freq_list = pd.concat([edges['source'],edges['target']]).value_counts()
node_freq_list = df['wakati'].str.split("|",expand=True).stack().value_counts()
base_words_list = node_freq_list[0:nodeM].index.tolist()

```

* 上位語。もっと意味なさそうな言葉を削ってもいいかも
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/583a4c1b-8659-2b36-1b6a-ef60393416a5.png)




</details>


### STEP2: 土台語のクラスタの生成
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/a3df38a7-701b-1df4-e4b0-30a58cefff85.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/44981fd6-6e87-159e-192c-6149a403778b.png)


※「共起度」についていくつか計算方法があるようだが、こちら（後者）を採用

<details>

```python
#@title STEP2 :頻度上位 M 個の単語同士の共起度 Co を測り，共起度の高い順にソートし，M-1 番目までに単語同士に枝を張る．共起度 Co に関しては Jaccard 係数を用いる．

#共起dataframeからjaccard共起度計算
#HighF req 中で文書 D における共起度の高い語の対を、それぞれ枝 (リンク) で結ぶ。ここで語の対の共#起度 co(wi, wj ) は、式 2.3 のように文 s における語の出現回数の積の総和で定義される。
#|x|s は文 s における要素 x の出現回数で、 x が語の場合に |x|s は文 s 中の語 x の出現回数になる。key(w) の対象となる語 w は、文書 D における特徴語となり得る全ての語である。
#すなわち文書 D よりストップワードに含まれる語を除いた全ての語となる。


def calc_C0(dataframe):
    and_df = dataframe[["source","target","size"]].rename(columns={"size":"and_sum"})
    or_df1 = dataframe.groupby("source",as_index=False).sum().rename(columns={"size":"or1_sum"})
    or_df2 = dataframe.groupby("target",as_index=False).sum().rename(columns={"size":"or2_sum"})
    jac_df = pd.merge(pd.merge(and_df,or_df1),or_df2,left_on="target",right_on="target")\
    .assign(jaccard=lambda df:df["and_sum"]/(df["or1_sum"]+df["or2_sum"]-df["and_sum"]))
    return jac_df[["source","target","jaccard"]]    

C0_df = edges[(edges['source'].isin(base_words_list))|(edges['target'].isin(base_words_list))]
C0_df = calc_C0(edges)
base_edges = C0_df.sort_values(by="jaccard",ascending=False).head(edgeM)

```




</details>


### STEP3:土台の抽出
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/e0fc86fb-0a04-a0ba-405e-ff223d671c7c.png)

<details>

```python
#「強連結」（直接リンクを削除してもつながっているか）の判定関数
def haspath(rows):
    source = rows['source']
    target = rows['target']
    G = nx.from_pandas_edgelist(base_edges, edge_attr=True)
    G.remove_edge(source, target)
    return nx.has_path(G,source,target)

#Step3: 土台の抽出
#Step2 で張ったリンクのうち，強連結を形成するリンク以外を削除する．
#強連結とは対となるノード wi，wj において wi，wj 間のリンクを削除しても他のノードを経由することによって他方のノードに到達できる場合のことを指す
base_edges["strong_connect"] = base_edges.apply(haspath,axis=1)
strong_base_edges = base_edges[base_edges['strong_connect']==True]

```

</details>


### STEP4:柱の抽出
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/6b63ea50-410f-e63a-61c7-9fd99541cde0.png)

※共起度Basedの計算が怪しいが「共起度」はjaccardとしてる。

<details>

```python
#@title STEP4:文書内の全ての単語と土台の単語の共起度を算出する．

#文書内の全ての単語の抽出
node_df = node_freq_list.reset_index()
strong_base_edges_G = nx.from_pandas_edgelist(strong_base_edges)

#土台の単語群抽出
base_node_list = list(strong_base_edges_G.nodes())

#柱（橋）の抽出
bridge_df = C0_df[(C0_df["source"].isin(base_node_list))|(C0_df["target"].isin(strong_base_nodes_list))]
bridge_df.rename(columns={"jaccard":"bridge_score"},inplace=True)

```

* node_dfの様子(bridge_scoreに、各土台語と単語とのjaccard共起度が入っている)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/b70489bd-0dd6-54fb-8f21-4ac4f326024b.png)




</details>


### STEP5:屋根の抽出
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/b8a1f50c-4d10-403f-84cd-6e6e2dc71ada.png)

>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/4ed1b161-fcd7-0a0a-eeb4-e0415c38190b.png)

ってどうやって作るのか悩んだ結果、さきほど作成した表の土台語（targetの方）毎にbridge_scoreの合計をとって分母にする処理を加えればいいんじゃないかということで計算。「key」というのが最終的に欲しい数値

<details>

```python

#@title STEP5 keyの計算＆屋根抽出

#key上位の単語（屋根）の抽出
headR =  50#@param {type:"integer"}


#橋の可視化の基準(0-1)
BRIDGE_SCORE_CRIT = 0.01 #@param {type:"number"}

sum_bridgescore_df = bridge_df.groupby(["target"],as_index=False)["bridge_score"].sum()

keydf = pd.merge(bridge_df,sum_bridgescore_df.rename(columns={"bridge_score":"bridge_scoresum"}))\
    .assign(temp_score=lambda df:1-df["bridge_score"]/df["bridge_scoresum"])\
    .groupby(["source"],as_index=False)["temp_score"].prod()\
    .assign(key=lambda df:1-df["temp_score"])\
    .sort_values(by="key",ascending=False)\
    .rename(columns={"source":"target"})


#keyに基づく屋根の抽出

roof_node_list = keydf["target"].head(headR).tolist()
bridge_df2 = bridge_df[bridge_df["target"].isin(roof_node_list)]

roofwd_top_df = bridge_df2[bridge_df2["bridge_score"]>=BRIDGE_SCORE_CRIT]

#roofwd_top_df = bridge_df2[bridge_df2["bridge_score"]>=BRIDGE_SCORE_CRIT]

#土台語のdataframeにkey上位の単語（屋根）を含む共起dataframeを連結
alledge_df = pd.concat([
        strong_base_edges[["source","target","jaccard"]].rename(columns={"jaccard":"bridge_score"})
        ,
        roofwd_top_df[["source","target","bridge_score"]]#.rename(columns={"score2":"score"})
        ])




```

* node_df2
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/12045a44-19b8-7ea4-6020-b0a5e344abcd.png)


</details>

# 4.結果
上記のとおり、昔使った吉野特許群の「特許請求の範囲」で「屋根」にあたる単語群を抽出。
う～ん・・・結構一般的な語が出てるので重要語か微妙？

```python
keydf[["target","key"]].head(30)
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/75dca0af-c12b-5f2b-ac4d-ccc487ec8a76.png)




# 5. 可視化
* おなじみpyvisを利用させてもらう。

### 土台
* 結構よさそう
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/1e0a5ca4-26d3-33ed-3fe1-8b06595097d4.png)







### 柱と屋根の追加結果
ピンク色＝屋根語、青色＝土台語、ピンク線＝柱
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/3093ffdb-0339-29e6-1e37-bf57d9365d27.png)



[全体図](https://storage.googleapis.com/yoshino/keygraph%20(12).html)

# 6. tfidfの抽出結果との比較（作成中）
* 結構違う感じに出てきてくれてるので、補完としていいかもしれない。topicmodelなどを追加してみたい

|keygrap|tfidf|
|---|---|
|![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/75dca0af-c12b-5f2b-ac4d-ccc487ec8a76.png)|![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/385220/8975849a-8306-9d49-4e34-dbe1425618a0.png)
|




# 7. その他
* すでに[pythonのコード](https://github.com/ShinsakuSegawa/keygraph)もあったので要確認。
* networkx2.XXのhas_path関数など便利な機能があるのを発見できてよかった。
* pandasのgroupby後のprodという関数を始めて使った。
* 基本的に文章群の入ったdataframeを投入したら図やデータがかえってくる形に整理したい。
* BigQueryで作りたいけど、現状イメージできない。
* 文章が多くなると、自作のmake_co_occur_dfでクラッシュするので要改善！