Hatena::ブログ(Diary)

Reinvention of the Wheel

2011-01-24

Scalaで集合知プログラミング その11


Scala de 集合知プログラミングも第3章に入っていきたいと思います(`・ω・´)

第3章では複数のアイテムをグループ化するクラスタリングの手法についてやっていきたいと思いますデス

クラスタリングを行うことで大規模データを扱いやすいように分類して可視化したり、分析したりすることが出来るようになるみたいですね(`・ω・´)

本書ではこのクラスタリングという手法について、データセットの作成・2種類のクラスタリングアルゴリズムの学習・生成したグループの可視化の3つを取り上げていくみたいです

教師あり学習 VS 教師なし学習

今回取り扱うクラスタリングは教師なし学習と言われるみたいです

教師なし学習とはコンピュータが判断するための見本となる模範解答を入力せずに、データセットのみを基にして予想や分析を行う学習アルゴリズムの種類を指すようです

また、教師なし学習はクラスタリングの他にも非負値行列因子分解や自己組織化マップなどがあるようです(´・ω・`)

なお、模範解答を適時入力することでデータに関する学習を行っていく教師あり学習にはニューラルネットワーク・決定木・サポートベクトルマシン・ベイジアンフィルタ等々…があるみたいです

これらの教師あり学習については本書の中盤以降で取り扱っていくようです(´・ω・`)


単語ベクトル

それではクラスタリングを行っていきましょう(`・ω・´)まずはクラスタリング用のデータを作成しますデス

ブロガーを分類する

今回クラスタリングの対象とするのは120件ほどの人気ブログのデータセットとし、各ブログフィードに特定の単語が現れた回数を基にクラスタリングしてみます

このようなクラスタリングを行うことで同じような話題を取り上げているブログのグループを探し出すことができるようになるみたいです

ようするに、特定の単語を座標軸とみなしてその出現数を大きさ(スカラー)としたベクトル空間を作成して、これをもとにクラスタリングを行う…って解釈でいいですかね?

まあ、実際のところはコードを眺めながら考えていきますよ(`・ω・´)

pythonフィード中の単語を数える

今回クラスタリングに利用する単語は全ブログ中で10%以上50%以下の頻度で出現するものとしてやります。

このようにある程度の単語を間引くことでニッチ過ぎる単語や、一般的すぎる単語を分析の対象から外してノイズを減らすことが出来るわけでね

なお、PythonブログRSSフィードを解析するためにはfeedperserモジュールを利用してやります(`・ω・´)

それではfeedparserモジュールを利用して単語の出現頻度をカウントアップしたデータセットを作成してやります

データセット作成用のコードは次のようにコマンドライン上から実行するタイプのものデス(`・ω・´)

# generatefeedvector.pyとして作成

# 必要なモジュールをインポートします
import feedparser
import re 

# 指定されたURLのRSSフィードから
# タイトルと単語の頻度の辞書を返します
def getwordcounts(url):
  # フィードをパースします
  d = feedparser.parse(url)
  # 単語の出現頻度を格納する変数を初期化します
  wc = {}
  
  # RSSフィード内のすべてのエントリについて処理します
  for e in d.entries:
    # フィード内容のテキストはsummaryまたはdescriptionという
    # 属性になるのでどちらでも取得できるように処理シマス 
    if 'summary' in e: summary = e.summary
    else: summary = e.description
    
    # 下記のgetwordsメソッドを利用して
    # フィード内容を単語に分解します
    words = getwords(e.title + ' ' + summary)
    # 取得した単語群をカウントアップしていきます
    for word in words:
      wc.setdefault(word, 0)
      wc[word] += 1
  # ブログタイトルと単語の出現頻度を返します
  return d.feed.title, wc

# フィードの内容から単語の出現頻度を返します
def getwords(html):
  # HTMLタグを取り除きます
  txt = re.compile(r'<[^>]+>').sub('', html)
  # 非アルファベット文字で分割して単語化します
  words = re.compile(r'[^A-Z^a-z]+').split(txt)
  # 小文字に変換して単語群を返します
  return [word.lower() for word in words if word != '']
  
### メインの処理です

# カウントアップ用の変数を初期化します
apccount = {}
wordcounts = {}

# 分析の対象となるブログのURLリストを
# http://kiwitobes.com/clusters/feedlist.txtからダウンロードして
# data/feedlist.txtとして保存します

# URLリストをリスト化して読み込みます
feedlist=[line for line in file('data/feedlist.txt')]
for feedurl in feedlist:
  try:
    # 各ブログごとに単語の出現頻度をカウントして
    # ブログ別に格納します
    title, wc = getwordcounts(feedurl)
    wordcounts[title]=wc
    # 各ブログに出現する単語を全単語リストに合算集計します
    for word, count in wc.items():
      apcount.setdefault(word, 0)
      if count > 1:
        apcount[word] += 1
    print 'Success to parse feed %s' % feedurl
  except:
    print 'Failed to parse feed %s' % feedurl

# 単語の全ブログ出現頻度で頻出度が高すぎる物、低すぎる物を除外します
wordlist = []
for w, bc in apcount.items():
  frac = float(bc) / len(feedlist)
  # 正確には出現頻度が指定した範囲内のものを
  # データとして格納します
  if frac > 0.1 and frac <0.5:
    wordlist.append(w)

# カウント結果をテキストファイルに書き出します
out = file('blogdata.txt', 'w')
# ヘッダー行を出力します
out.write('Blog')
for word in wordlist:
  out.write('\t%s' % word)
out.write('\n')
# ブログ毎に一行ずつ出力します
for blog, wc in wordcounts.item():
  out.write(blog)
  # 登録条件(指定出現頻度)を満たした単語のみ記録していきます
  for word in wordlist:
    if word in wc:
      out.write('\t%d' % wc[word])
    else:
      out.write('\t0')
   out.write('\n')

なんかUnicodeEncodeErrorがでてしまったので、こちらを参考に修正しております

naoeの日記


それでは実行してみますよ(`・ω・´)

% python generatefeedvector.py
Success to parse feed http://feeds.feedburner.com/37signals/beMH
<省略>

とりあえずそれっぽいデータファイルが作成されましたな(´・ω・`)

% head blogdata.txt
Blog	kids	music	want	wrong	service	needed	friend	tech	saying	lots	union	begin	choice	address	working	following	years	didn	i
Scalaフィード中の単語を数える

それではScalaに翻訳してみましょうかね(´・ω・`)

ちなみに今回からはイミュータブル縛りは挫折しますデス…集計処理系でミュータブル使えないのはつらいの...orz

それではやってみます(`・ω・´)

// GenerateFeedVector.scalaに記述します

// パッケージとして定義します
package org.plasticscafe.collective.cluster

// 必要なモジュールを読み込みます
import scala.io.Source
import scala.xml.{XML, NodeSeq}
//import scala.xml.parsing.XhtmlParser
// 効率化のためにイミュータブル使いまくり
import scala.collection.mutable

// 単語ベクトル空間データセットを作成するオブジェクトです
object GenerateFeedVector {
  // URLごとにブログタイトルと単語出現頻度を計算します
  def getwordcounts(url:String):(String, Map[String, Int]) = {
    // RSSフィードを読み込みます
    val source = Source.fromURL(url) 
    // XhtmlParserを使用するとメモリを食いつぶしてしまう
    // val feeds = XhtmlParser(source)
    val feeds = XML.loadString(source.getLines.mkString)
    source.close

    // タイトルを読み込みます
    val title = (feeds \\ "title" )(0).text
    
    // RSSフィード内のコンテンツを読み込みます
    val summary = feeds \\ "summary"
    val descriptions = if(0 < summary.size){
       summary } else { feeds \\ "description" }


    // テキスト内の単語分割処理です
    def getwords(html:String):List[String] = {
      "<[^>]+>".r.replaceAllIn(html, "").split("[^A-Z^a-z]+").
        map(_.toLowerCase).toList
    }
    
    // 取得したRSSフィードごとに単語頻出度をカウントアップします
    val wc = mutable.Map.empty[String, Int]
    for (description <- descriptions){
      for(word <- getwords(title + ' ' + description.text)){
        if(!wc.isDefinedAt(word)) wc(word) = 0
        wc(word) += 1
      } 
    }
    // タプルの形式で値を返します 
    (title, wc.toMap) 
  }
  
  // RSSフィードの読み込み集計処理です
  def parseFeed(datafile:String="data/feedlist.txt"):(Int, 
    Map[String, Int], Map[String, Map[String, Int]]) = {
    
    // URL一覧のリストファイルを取得します
    val source = Source.fromFile(datafile)
    val feedlist = source.getLines().toList
    source.close
    
    // 集計用のミュータブルな変数を初期化します
    val apcount = mutable.Map.empty[String, Int]
    val wordcounts = mutable.Map.empty[String, Map[String, Int]]
     
    // URLごとに取得処理をします
    for(feedurl <- feedlist){
      try{
        // 単語頻出度を取得します
        var (title, wc) = getwordcounts(feedurl)
        // 集計を行います
        wordcounts(title) = wc
        // 全ブログの単語頻出度を記録します
        for(w <- wc){
          if(!apcount.isDefinedAt(w._1)) apcount(w._1) = 0
          if(1 < w._2) apcount(w._1) += 1
        }
        println("Success to parse feed " + feedurl)
      }catch{
        case e:Exception => println("Failed to parse feed " + feedurl)
      }
    }
    // 値をセットで返します
    return (feedlist.size, apcount.toMap, wordcounts.toMap)
  }
  
  // 高頻出単語と、低頻出単語をノイズとして除去します
  def filterData(apcount:Map[String, Int], feednum:Int):List[String] = {
    apcount.filter(x => 0.1 < x._2.toDouble / feednum && x._2.toDouble / feednum < 0.5).
      map(x => x._1).toList    
  }
  
  // 集計したデータをファイルに書き込みます
  def writeData(wordlist:List[String],
    wordcounts:Map[String, Map[String, Int]], datafile:String = "blogdata.txt"){
    // ファイルの書き込み用モジュールをインポートします 
    import java.io.PrintWriter
    // ヘッダーを書き込みます
    val out = new PrintWriter(datafile)
    out.print("Blog")
    wordlist.map(x => out.print("\t" + x))
    out.print("\n")
    // データ内容を書き出します
    wordcounts.map{
      case(title, wc) => {
        out.print(title)
        for(word <- wordlist){
          if(wc.contains(word)) out.print("\t" + wc(word))
          else out.print("\t0")
        }
        out.print("\n")    
      }
    }
    out.close()
  }
  // メイン処理として各メソッドを呼び出します 
  def main(args: Array[String]){    
    val (feedsize, apcount, wordcounts) = parseFeed("data/feedlist.txt") 
    
    val wordlist = filterData(apcount, feedsize)
    writeData(wordlist, wordcounts)
  }
}

うん、なんとかできましたな…途中で変なところに引っかかってお昼休み中に終わらなかったので、結局帰宅後に検証し直すはめに(´;ω;`)あ、引っかかった所は別エントリーにまとめます

…とりあえず実行してみますよ

% scala org.plasticscafe.collective.cluster.GenerateFeedVector
Success to parse feed http://feeds.feedburner.com/37signals/beMH
Success to parse feed http://feeds.feedburner.com/blogspot/bRuz
<省略>

なんとかデータソースもできたみたいです(´・ω・`)

% head blogdata.txt
Blog	looks	nbsp	used	e	down	side	please	interesting	read	number	able	behind	ways	drive	network	maybe	find	business
<省略>

ふう、これで漸くクラスタリングの話に進めますね(´・ω・`)

まとめ

今回はクラスタリングのためのデータセットを作成しました。途中でXhtml Parser関連の変な挙動に引っかかってしまったのですが、とりあえず回避できたのでドン( ゚д゚)マイで

次回は今回作成したデータを利用して階層的クラスタリングをやりたいと思います(´・ω・`)

投稿したコメントは管理者が承認するまで公開されません。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証