2020-05-08

RankClus：クラスタリングとランキングの統合異種情報ネットワーク分析

最近読んでたソンさんの論文「RankClus: Integrating Clustering with Ranking for Heterogeneous Information Network Analysis」理論的に難しくないですが，よく理解までちょっと時間かかると思って，要点をまとめていきます．

ネットワーク分析は最近，情報ネットワークから知識を抽出する重要な手法としてます．そして，ランキングやクラスタリングは情報ネットワークの全体的なビューを提供しています．ただし，対象が属するクラスタを考慮せずに全体的にランク付けると，あまり意味がない結果になってしまいます．同様に，膨大な数の対象をランクを考えなくてクラスタ結果もおかしくなります．

そして，ソンさんの論文では，マルチライプの情報ネットワークに基づいてランク付けと統合されたクラスタリング手法RankClusを提案しました．

まず，RankClusに関するいくつかの定義を述べます．

１．バイタイプ情報ネットワーク

まず，グラフの中のノードのタイプをXとY2つの集合に分けます． $X=\left\{x_{1}, x_{2}, \ldots, x_{m}\right\}$ と $Y=\left\{y_{1}, y_{2}, \ldots, y_{n}\right\}$ ．xとyはそれぞれの対象です．

そして，グラフ $G=\langle V, E\rangle$ では，ノードの集合は $V(G)=X \cup Y$ ノード間のリンクの集合は $E(G)=\left\{\left\langle o_{i}, o_{j}\right\rangle\right\}, \text { where } o_{i}, o_{j} \in X \cup Y$ とします．

各リンクが存在する数はリンクの重み付け係数として，グラフの隣接行列 $W_{(m+n) \times(m+n)}=\left\{w_{o_{i} o_{j}}\right\}$ を算出できます．グラフ $G=\langle\{X \cup Y\}, W\rangle$ すると，このグラフGはバイタイプ情報ネットワークといいます．

簡単に表すため，隣接行列Wを $W_{X X}, W_{X Y}, W_{Y X}, W_{Y Y}$ 4つのブロックに分け，各対象のサブグラフとすることができます．

$W=\left(\begin{array}{ll} W_{X X} & W_{X Y} \\ W_{Y X} & W_{Y Y} \end{array}\right)$

2．ランキング関数

バイタイプグラフGでは，ランキング関数は全てのノードのランクスコアを与えます． $f: G \rightarrow\left(\vec{r}_{X}, \vec{r}_{Y}\right)$
このランクスコアは以下の条件を満たす．
$\forall x \in X, \vec{r}_{X}(x) \geq 0, \sum_{x \in X} \vec{r}_{X}(x)=1$
$\forall y \in Y, \vec{r}_{Y}(y) \geq 0, \sum_{y \in Y} \vec{r}_{Y}(y)=1$
つまり，ランクスコアは非負，タイプXに属する全ての対象のランクスコアの和は1になる，Yは同様に．
ここのランキングはPageRankみたいに，それぞれの対象に対する重要度を与えるためです．ソンさんの論文では，2つのラインキング関数を提案しました．あとで述べます．

与えたクラスタ数Kにたいし，クラスタリングは目標タイプXに属する全ての対象にクラスタラベルを付けます． $X_{k}$ はクラスタkの対象集合です． $X^{'}$ は任意のクラスタ集合です．

多くのバイタイプネットワークでは，2つタイプの対象数が非対称になっています．例えば，DBLPのデータベースでは，著者の数はおよそ50万，学会の数は4千ぐらいしかない．

それに対し，ソンさんの論文では，より少ない数を持つ対象タイプはこの情報ネットワークの目標タイプとし，他のは属性タイプとします．もっと少ない数かつ意味があるクラスタを生成するため，クラスタリングは目標タイプしか行いません．一方，属性タイプはクラスタリングを補助します．

DBLPの例では，学会を目標タイプとしてクラスタリングする理由は，生成された学会クラスタは数が少なくなるし，固有的な研究分野の意味があります．著者が各学会におけるランクスコアは十分な情報を提供できます．

最初に言ったように，属するクラスタを考えずに，対象をランキングすれば，結果はあまり意味がありません．ゆえに，条件付きランクとクラスタ内ランクの概念を定義します．

3．条件付きランクとクラスタ内ランク
目標タイプX，クラスタ $X^{\prime} \subseteq X$ を与えると，サブネットワーク $G^{\prime}=\left\langle\left\{X^{\prime} \cup Y\right\}, W^{\prime}\right\rangle$ は，Gが頂点 $X^{\prime} \cup Y$ で誘導されたグラフです．Yの条件付きランク $\vec{r}_{Y | X^{\prime}}$ とX'のクラスタ内のランク $\vec{r}_{X^{\prime} | X^{\prime}}$ は直接にランキング関数で算出します． $G^{\prime}:\left(\vec{r}_{X^{\prime} | X^{\prime}}, \vec{r}_{Y | X^{\prime}}\right)=f\left(G^{\prime}\right)$ .
全てのXの対象はサブグラフに存在するわけではないので，Xの条件付きランク $\vec{r}_{X | X^{\prime}}$ はちょっと複雑になっています．ここは，ネットワークGにおける $\vec{r}_{Y | X^{\prime}}$ の伝播スコアとして算出します．

$\vec{r}_{X | X^{\prime}}(x)=\frac{\sum_{j=1}^{n} W_{X Y}(x, j) \vec{r}_{Y | X^{\prime}}(j)}{\sum_{i=1}^{m} \sum_{j=1}^{n} W_{X Y}(i, j) \vec{r}_{Y | X^{\prime}}(j)}$

つまり，クラスタX'が与えられる時，Yの条件付きランクが算出できます．一方，X’に関するXの条件付きランクは今のYのランクにしたがっています．

例えば，DBDM分野クラスタが与えられたら，DBDM分野クラスタにおける著者の条件付きランクが得られます．ある会議がDBDM分野クラスタでの条件付きランクはこの会議に参加する著者の条件付きランクにしたがっています．

この概念に基づいて，この論文の目的は簡略化します．バイタイプグラフは $G=\langle\{X \cup Y\}, W\rangle$ ，目標タイプはX，特定的なクラスタ数はKにすると，今回の目的はXのK個のクラスタ，Xクラスタ内のランク付けと，Xクラスタに対するYのランク付けを生成することです．

4．ランキング関数
4.1　シンプルランキング
会議と著者のシンプルランキングは学会に受け入れた論文数と著者が公開する論文数にしたがっています．
情報ネットワーク $G=\langle\{X \cup Y\}, W\rangle$ が与えられたら，XとYのシンプルランキングが以下に生成されます．
$\left\{\begin{array}{l} \vec{r}_{X}(x)=\frac{\sum_{j=1}^{n} W_{X Y}(x, j)}{\sum_{i=1}^{m} \sum_{j=1}^{n} W_{X Y}(i, j)} \\ \vec{r}_{Y}(y)=\frac{\sum_{i=1}^{n} W_{X Y}(i, y)}{\sum_{i=1}^{m} \sum_{j=1}^{n} W_{X Y}(i, j)} \end{array}\right.$

シンプルランキングでは，参加の会議の質と関係なく，著者が論文の発表数が多ければ多いほど，ランクスコアが高くなる．しかし，現実では，会議と論文の質は数より重要だと思われます．そのため，権威ランキングが提案されました．

4.2 権威ランキング

ここ提案された権威ランキングは権威が高い対象に高いランクスコアを与えます．だから，権威ランキンは最初に情報が少ない時期は，計算が不可能になってしまうと思われます．
そして，以下の経験則は手がかりを与えました．

ルール1：ランクが高い著者はランクが高い会議に論文を発表する．

ルール2：ランクが高い会議はランク高い著者からの論文を引きつける．

ヒューリスティック的に考えると，著者と会議のランクを以下に定義します．

ルール1に基づいて，
各著者のスコアは論文の発表数と発表する会議にしたがっています．
$\vec{r}_{Y}(j)=\sum_{i=1}^{m} W_{Y X}(j, i) \vec{r}_{X}(i)$

正規化すると，
$\vec{r}_{Y}(j) \leftarrow \frac{\vec{r}_{Y}(j)}{\sum_{j^{\prime}=1}^{n} \vec{r}_{Y}\left(j^{\prime}\right)}$ になります．

ルール2に基づいて，
各会議のスコアは論文の数と質にしたがっています．論文の質は著者のランクスコアに従っています．
$\vec{r}_{X}(i)=\sum_{j=1}^{n} W_{X Y}(i, j) \vec{r}_{Y}(j)$

正規化すると， $\vec{r}_{X}(i) \leftarrow \frac{\vec{r}_{X}(i)}{\sum_{i^{\prime}=1}^{m} \vec{r}_{X}\left(i^{\prime}\right)}$ になります．

以上の2つの式を行列で表すと，
$\left\{\begin{array}{l} \vec{r}_{X}=\frac{W_{X Y} \vec{r}_{Y}}{\left\|W_{X Y} \vec{r}_{Y}\right\|} \\ \vec{r}_{Y}=\frac{W_{Y X} \vec{r}_{X}}{\left\|W_{Y X} \vec{r}_{X}\right\|} \end{array}\right.$

定理として，反復式を通じて得られる $\vec{r}_{X}$ と $\vec{r}_{Y}$ それぞれは $W_{X Y} W_{Y X}$ と $W_{Y X} W_{X Y}$ の固有ベクトルである．

証明
$\vec{r}_{X}=\frac{W_{X Y} \vec{r}_{Y}}{\left\|W_{X Y} \vec{r}_{Y}\right\|}=\frac{W_{X Y} \frac{W_{Y X} \vec{r}_{X}}{\left\|W_{Y X} \vec{r}_{X}\right\|}}{\left\|W_{X Y} \frac{W_{Y X} \vec{r}_{X}}{\left\|W_{Y X} \vec{r}_{X}\right\|}\right\|}=\frac{W_{X Y} W_{Y X} \vec{r}_{X}}{\left\|W_{X Y} W_{Y X} \vec{r}_{X}\right\|}.$

ルール3: ある著者の共著者のランクが高ければ，この著者のランクも高くなる．

このルールに基づいて，以下の式が得られる
$\vec{r}_{Y}(i)=\alpha \sum_{j=1}^{m} W_{Y X}(i, j) \vec{r}_{X}(j)+(1-\alpha) \sum_{j=1}^{n} W_{Y Y}(i, j) \vec{r}_{Y}(j)$

2019-11-29

シルエットスコア算出するカスタマイズ関数

シルエットスコア算出する関数

def similar(dtw1_vector,indices,indice):
        s=0
        x=0
        j=0
        while j < len(dtw1_vector):
            if indices[j]==indice:
                s+=dtw1_vector[j]
                x+=1
            j+=1
        return  s/x
    
def diff(dtw1_vector,indices,difffin):
    i=0
    s=0
    x=0
    while i<len(dtw1_vector,):
        if indices[i]==difffin:
            s+=dtw1_vector[i]
            x+=1
        i+=1
    return s/x

def mins(dtw1_vector,indices,indice):
    mins=float("inf")
    j=0
    tol=np.unique(indices).tolist()
    difffin=tol.remove(indice)
    while j< len(tol):
        if diff(dtw1_vector,indices,tol[j])<mins:
            mins=diff(dtw1_vector,indices,tol[j])
        j+=1
    return mins

def silhouette(dtw1_vector,indices,indice):
    fz=mins(dtw1_vector,indices,indice)-similar(dtw1_vector,indices,indice)
    fm=max(mins(dtw1_vector,indices,indice),similar(dtw1_vector,indices,indice))
    sil=fz/fm
    return sil
            
def silhouette_score(dtw1_matirx,indices):
    silhouette_score=[silhouette(dtw1_matirx[i],indices,indices[i])for i in range(0,len(dtw1_matirx))]
    return silhouette_score
| |<

グラフで表現するコード

>|python|
from matplotlib import cm
cluster_labels=np.unique(indices)
n_clusters=cluster_labels.shape[0]
silhoutte_vals = np.array(silhouette_score(dw_dtw1_matrix,indices))
y_ax_lower,y_ax_upper=0,0
yticks=[]
for i,c in enumerate(cluster_labels):
        #获取不同簇的轮廓系数
    c_silhouette_vals = silhoutte_vals[indices == c]
        #对簇中样本的轮廓系数由小到大进行排序
    c_silhouette_vals.sort()
        #获取到簇中轮廓系数的个数
    y_ax_upper += len(c_silhouette_vals)
        #获取不同颜色
    color = cm.jet(i / n_clusters)
        #绘制水平直方图
    plt.barh(range(y_ax_lower,y_ax_upper),c_silhouette_vals,
                 height=1.0,edgecolor="none",color=color)
        #获取显示y轴刻度的位置
    yticks.append((y_ax_lower+y_ax_upper) / 2)
        #下一个y轴的起点位置
    y_ax_lower += len(c_silhouette_vals)
    #获取轮廓系数的平均值
silhouette_avg = np.mean(silhoutte_vals)
    #绘制一条平行y轴的轮廓系数平均值的虚线

plt.axvline(silhouette_avg,color="red",linestyle="--")
    #设置y轴显示的刻度
plt.yticks(yticks,cluster_labels+1)
plt.ylabel("cluster")
plt.xlabel("silhouette score")
plt.show()

2019-11-29

DTW距離行列を作成するコード

関数コードまず載せる．
解釈後にします

#DTWで2つ時系列距離を計算する関数
#入力は2つデバイスの時系列特徴量，出力は2つデバイスの距離
def dtw_1(s1,s2,ww):
    r, c = len(s1), len(s2)
    dist = np.zeros((r+ww+1,c+ww+1))
    dist[0,1:] = float("inf")
    dist[1:,0] = float("inf")
    D = dist[1:,1:]
    DTW= dist[1:,1:]
#ユークリッド距離行列D
    for i in range(r+ww):
        for j in range(c+ww):
            if i<r and j<c:
                D[i,j] = np.sqrt(sum((s1[i]-s2[j])**2))
            elif i>r-1 and j<c:
                D[i,j] = np.sqrt(sum((s1[ww-1]-s2[j])**2))
            elif i<r and j>c-1:
                D[i,j] = np.sqrt(sum((s1[i]-s2[ww-1])**2))
            elif i>r-1 and j>c-1:
                D[i,j] = np.sqrt(sum((s1[ww-1]-s2[ww-1])**2))
#累積距離行列DTW
    for i in range(r+ww):
        for j in range(c+ww):
            if i-j<ww and j-i<ww:
                DTW[i,j] = min(dist[i,j]+DTW[i,j]*2,dist[i,j+1]+DTW[i,j],dist[i+1,j]+DTW[i,j])    
    return DTW[-1,-1]
#全てデバイス間のDTW距離のマトリックスを生成する関数
#入力は25カテゴリ×24時間帯の特徴量（600次元）
#出力は各デバイス間DTW距離尺度の行列
def dtw_matrix_1(feature,ww):
    F=np.array(feature)
    dtw_matrix = np.zeros((F.shape[0],F.shape[0]))
    for A in range(F.shape[0]):
        for B in range(F.shape[0]):
            dtw_matrix[A,B] = dtw_1(feature[A],feature[B],ww)     
    return dtw_matrix

2019-11-29

DTW距離行列そのままk-medoids法に使うクラスタリング

やってみったこと：算出されたDTWの距離行列そのままk-medoids法に使ってクラスタリングすること
phpのコードを参考しながらpythonで関数を書いた．
自分書いたもの忘れないように，コードを載せておきます．
もし間違いがあれば，お気軽にお声掛けてください．

#k-medoids第1段階の関数
#ランダムにデバイスk個を選んで初期のクラスター中心点とする
#入力：デバイス間のDTW距離行列，中心点の数
#出力：選んだ中心点のデバイス番号のリスト
import random
def initialize_medoids(dist_M, k):
        l=list(range(1,len(dist_M)))
        medoids=random.sample(l, k)  
        return np.array(medoids)
#k-medoids第2段階の関数
#各デバイスを一番近い中心点属するクラスターに割り当てる
#入力：デバイス間のDTW距離行列，中心点としてのデバイス番号のリスト
#出力：各デバイス属するクラスタの番号のリスト
def nearest(d,medoids):
    mindist=float("inf")
    nearest=0
    k=len(medoids)
    i=0
    while (i<k):
        n=medoids[i]
        if d[n]< mindist:
            mindist=d[n]
            nearest=i
        i+=1
    return nearest
def assign_to_nearest(dist_M,medoids):
    dist_M_list=dist_M.tolist()
    indices=[nearest(dist_M_list[m],medoids) for m in range(0,len(dist_M))]
    return indices
#k-medoids第3段階の関数
#各クラスタの中心点を更新する
#入力：デバイス間のDTW距離行列,各デバイス属するクラスタの番号のリスト,中心点の数
#出力：中心点のデバイス番号のリスト
def update_medoids(dist_M,indices,k):
    mindists=np.full(k,float("inf"))
    medoids=np.full(k,float("nan"))
    i=0
    while i<len(dist_M):
        dist_M_list=dist_M.tolist()
        m=indices[i]
        j=0
        dist=0
        while j<len(dist_M):
            if indices[j]== m:
                dist=dist+dist_M_list[i][j]
            j+=1
        dist
        if dist<mindists[m]:
            mindists[m]=dist
            medoids[m]=i
        i+=1
    return medoids.astype(int)
#まとめ関数
#入力：デバイス間のDTW距離行列,中心点の数，最大再帰回数
#出力：各デバイス属するクラスタの番号のリスト，各クラスタの中心点のデバイス番号のリスト
def kmedoids(dtw_matrix,k,maxiter):
    medoids=initialize_medoids(dtw_matrix, k)
    indices=np.full(len(dtw_matrix),float("nan")).tolist()
    itr=0
    while itr<maxiter:
        nex=assign_to_nearest(dtw_matrix,medoids)
        if (np.array(nex)==np.array(indices)).all()=='True':
            break
            print('brk')
        indices=nex
        medoids=update_medoids(dtw_matrix,indices,k)
        itr+=1
    return medoids