グループ判定アルゴリズムの実装

本節ではグループ判定アルゴリズムの実装について述べる．

図4.1:各ソフトウェアの連携

表4.1:ソフトウェア構成

要素 詳細

OS Debian GNU/Linux 5.0.7(lenny)

Webサーバ Apache HTTP Server 2.2.9

解析スクリプト PHP ver. 5.2.6 with Suhosin-Patch 0.9.6.2 データベース MySQL ver. 5.0.51a クラスタリング解析 R ver. 2.7.1

4.3.1 ソーシャルメディアにおける位置情報付き発言の取得

今回はTwitterにおける位置情報付きの発言を取得した．TwitterのStreamingAPIから発 言を取得し，グループ情報データベースに保存する．発言の取得は，発言取得モジュール，

発言解析モジュールが行う．実装についての詳細は4.4.1と4.4.2において述べる．

4.3.2 発言のクラスタリング

取得した発言を，K-means方を用いてクラスタリング解析する．解析は，指定した期間 に取得した発言について行う．

解析の実行には，R言語を用いた．詳細は4.4.3において述べる．

4.3.3 類似度判定

類似度判定の実装について述べる．類似度判定は，発言数カウント，ユーザ類似度計算の 2段階に分かれている．複数のクラスタ分割数でクラスタリング解析を行った場合は，そ れぞれについて類似度判定を行う．

まず発言数カウントのアルゴリズムCountT weets について，Algorithm 1に示す．ク ラスタリング解析された発言は，それぞれuserId, clusterIdを含み，それらの集合をT とする．T_i.userId, T_i.clusterIdは，i番目の発言におけるuserId, clusterIdを表す．解析 対象となるユーザ数をusersNumとし，クラスタ分割数をclusterNumとする．これらの

T, usersNum, clustersNumを引数として与え，ユーザがどのクラスタで何回発言している

かという二次元配列counts[userId][clusterId]を取得する．

Algorithm 1CountTweets(T, usersNum, clustersNum)

Input: クラスタリング済の発言T,全ユーザ数usersNum,全クラスタ数clustersNum Output: 各クラスタにおけるユーザの発言数counts[userId][clusterId]

1: i=0, tweetsNum=|T|;

2: counts[usersNum][clustersNum];

3: whilei<tweetsNumdo

4: counts[Ti.userId][Ti.clusterId] :=COU NT[Ti.userId][Ti.clusterId]+1;

5: i:=i+1;

6: end while

7: returncounts[userId][clusterId]

次に，ユーザ類似度計算のアルゴリズムCalculateS imilarityについて，Algorithm 2に 示す．CountT weetsから出力されたcounts[userId][clusterId]と，解析対象となるユーザ数 usersNumを引数として与える．基準ユーザ f romU serIdから対象ユーザtoU serIdに対す る類似度をS とし，S.f romU serId, S.toU serId,S.similarityの属性を持つ．

また，S L.insert(S)の操作によって集合S Lに追加する．対象となるすべてのユーザの組 み合わせに対して類似度を計算した結果S Lを取得する．類似度計算において，f romT otal は基準ユーザの全発言数，sharedはあるクラスタにおける基準ユーザと対象ユーザの発言 共有数を示す．

Algorithm 2CalculateSimilarity(counts[userId][clusterId], usersNum)

Input: 各クラスタにおけるユーザの発言数counts[userId][clusterId],全ユーザ数usersNum Output: 各ユーザ間における類似度の集合S L={S}

1: i=0, j=0;

2: whilei<usersNumdo

3: while j<usersNumdo

4: ifi= jthen

5: break;

6: end if

7: f romT otal=0, shared=0;

8: whilec<clustersNumdo

9: f romT otal:= f romT otal+counts[i][c];

10: shared:=shared+min(counts[i][c],counts[j][c]);

11: end while

12: S.f romU serId:=i;

13: S.toU serId:= j;

14: S.similarity:=shared/f romT otal;

15: S L.insert(S);

16: j:= j+1;

17: end while

18: i:=i+1;

19: end while

20: returnS L

4.3.4 グループ判定

グループ判定部の実装について述べる．グループ判定のアルゴリズムDetectGroupにつ いて，Algorithm 3に示す．

今回は，クラスタ分割数を10，100，1000に設定してクラスタリング解析を行い，類似度 判定を行ったデータについてグループ判定を行うことを想定する．S L10はクラスタ分割数 10のデータでCalculateS imilarityから出力された各ユーザ間における類似度の集合である．

同様にS L₁₀₀，S L₁₀₀₀はクラスタ分割数100，1000における類似度の集合である．また，ク ラスタ分割数10，100，1000に対する重み付けの値を，weight10，weight100，weight1000と する．さらに，類似ユーザであると見なす類似度の閾値をsimilarT hreshとする．usersNum は解析対象となるユーザ数を示す．これらの値を引数として与える．

グループ判定結果をGとし，基準ユーザのIDであるG.userId，グループであるユーザ IDの集合G.groupIdsの属性を持つ．G.groupIds.insert(userId)の操作によって，グループ と判定したユーザIDをG.groupIdsに追加する．また，GL.insert(G)の操作によって，G をグループ判定結果の集合であるGLに追加する．

Algorithm 3DetectGroup(S L10, S L100, S L100, usersNum, similarT hresh, weight10, weight100, weight1000)

Input: S L₁₀, S L₁₀₀, S L₁₀₀₀, 全ユーザ数 usersNum, グループ判定閾値 similarT hresh, weight10,weight100,weight1000

Output: グループ判定結果GL={G}

1: i=0, j=0;

2: whilei<usersNumdo

3: G.userId:= j;

4: while j<usersNumdo

5: ifi= jthen

6: break;

7: end if

8: {S Lから f romU serIdとtoU serIdをキーにしてS を検索する}

9: S10:=(S L10.f romU serId=i&&S L10.toU serId= j);

10: S₁₀₀:=(S L₁₀₀.f romU serId=i&&S L₁₀₀.toU serId= j);

11: S1000:=(S L1000.f romU serId=i&&S L1000.toU serId= j);

12: totalS imilarity:=(S₁₀∗weight₁₀+S₁₀₀∗weight₁₀₀+S₁₀₀₀∗weight₁₀₀₀)/(weight₁₀+ weight100+weight1000);

13: iftotalS imilarity>similarT hreshthen

14: G.groupIds.insert(j);

15: end if

16: j:= j+1;

17: end while

18: GL.insert(G);

19: i:=i+1;

20: end while

21: returnGL