糞ネット弁慶

■[論文] WWW2012で気になる論文 19:08

Main scientific tracks | www2012

• Are Web users really Markovian?
• Branded with a Scarlet « C »: Cheaters in a Gaming Social Network
  • 参考に同著者の別論文 [1112.4915] Cheaters in the Steam Community Gaming Social Network
• Build Your Own Music Recommender by Modeling Internet Radio Streams
• Care to Comment? Recommendations for Commenting on News Stories
• Community Detection in Incomplete Information Networks
• Distributed Graph Pattern Matching
• Economics of BitTorrent Communities
  • Economics of BitTorrent Communities - Microsoft Research
• How Effective is Targeted Advertising?
• Investigating the Distribution of Password Choices
• Learning and Predicting Behavioral Dynamics on the Web
• Your Two Weeks of Fame and Your Grandmother's
• Rewriting Null e-commerce Queries to Recommend Products

twitter絡みが多いのはさておき，SPARQL絡みの論文をいくつか見かけた

■[メモ] Rのhashライブラリで予約語をkeyにする時一点だけ気をつける事 23:06

CRAN - Package hash

LL脳なので連想配列が使いたくなってしまいhashを導入したら比較的捗った．

しかし，keyが存在しない状態でもhas.keyを使うとTRUEが返ってくる．2時間ぐらいはまった．

> library(hash)
> h <- hash()
> h
<hash> containing 0 key-value pair(s).
  NA : NULL
> has.key("a", h)
    a 
FALSE 
> has.key("order", h)
order 
 TRUE 
> 

■[メモ] Rのmvpartパッケージのrpartで得られる決定木について分岐毎のGini Indexの増減を取得したい 22:07

CRAN - Package mvpart

タイトルそのまま．決定木の分岐でGini Indexが増減するのでそれを取得して足しあわせて1つの木における特徴量でどれが有効に働いているかを調べたい．

help読んだらimproveっぽいけどスケールが大きすぎるし，indexの説明は書かれてないし謎．

あとrandomForestパッケージでは変数の重要性をGini indexの増減の平均値で出してるっぽいけどそれの文献情報も知りたい．

> library(mvpart)
> library(kernlab)
> data(spam)
> # 木の学習
> tree.model <- rpart(type~., spam)
> tree.model
n= 4601 

node), split, n, loss, yval, (yprob)
      * denotes terminal node

 1) root 4601 1813 nonspam (0.60595523 0.39404477)  
   2) charDollar< 0.0555 3471  816 nonspam (0.76490925 0.23509075)  
     4) remove< 0.055 3141  516 nonspam (0.83572111 0.16427889)  
       8) charExclamation< 0.378 2737  275 nonspam (0.89952503 0.10047497) *
       9) charExclamation>=0.378 404  163 spam (0.40346535 0.59653465)  
        18) capitalTotal< 55.5 182   52 nonspam (0.71428571 0.28571429)  
          36) free< 0.845 161   32 nonspam (0.80124224 0.19875776) *
          37) free>=0.845 21    1 spam (0.04761905 0.95238095) *
        19) capitalTotal>=55.5 222   33 spam (0.14864865 0.85135135) *
     5) remove>=0.055 330   30 spam (0.09090909 0.90909091) *
   3) charDollar>=0.0555 1130  133 spam (0.11769912 0.88230088)  
     6) hp>=0.4 70    7 nonspam (0.90000000 0.10000000) *
     7) hp< 0.4 1060   70 spam (0.06603774 0.93396226) *
> 
> # ここで gini index を取得したい
> # それっぽい値はあるがどれが適切か
> tree.model$splits
                count ncat    improve   index adj
charDollar       4601   -1 714.169725  0.0555   0
charExclamation  4601   -1 711.963840  0.0795   0
remove           4601   -1 597.850385  0.0100   0
free             4601   -1 559.663354  0.0950   0
your             4601   -1 543.249610  0.6050   0
remove           3471   -1 331.322255  0.0550   0
charExclamation  3471   -1 284.613432  0.0915   0
free             3471   -1 266.016363  0.1350   0
your             3471   -1 165.992936  0.6150   0
capitalAve       3471   -1 158.646412  3.6835   0
charExclamation  3141   -1 173.255121  0.3780   0
free             3141   -1 152.118989  0.2000   0
capitalAve       3141   -1  79.004921  3.6380   0
your             3141   -1  69.839590  0.8650   0
hp               3141    1  64.000297  0.0250   0
capitalTotal      404   -1  63.995394 55.5000   0
capitalLong       404   -1  54.957900 10.5000   0
capitalAve        404   -1  53.678467  2.6540   0
free              404   -1  40.704143  0.0400   0
# 以下略

■[論文] NLP2012で気になる発表 01:06

言語処理学会第18回年次大会(NLP2012)

語彙・辞書(1)

• C1-4 放送ニュースの基本語彙の抽出

情報抽出

• E4-4 オークション検索クリックスルーログからの属性値抽出

情報検索

• E5-5 キーワード周辺語のリンク先内容を考慮したキーワード関連付け手法

テキスト・データマイニング

• F1-9 カテゴリに強く関連する語の発見と商品データクリーニングへの適用

要約

• F4-2 クエリ中の語を含むことを保証するクエリフォーカス要約
• F4-6 潜在的トピックの類似度グラフに基づく要約文生成
• F4-8 ラグランジュ緩和による複数文書要約の高速求解

ポスター

• P2-1 カルテの文書における副作用表現の分析
• P2-28 料理レシピテキストの構造解析とその応用
• P3-35 逆トピックワードを利用した外れ値文書検出

■[論文] New Perspectives and Methods in Link Prediction(KDD 2010) 実装した 00:32

New perspectives and methods in link prediction

概要

入力としてグラフ，開始ノード，深さを入力として，からエッジが存在しそうなノード集合を返す．

使い道としては，following関係のグラフデータに使ってあるユーザに他のユーザをレコメンドするとか．

アルゴリズム

アルゴリズムの考え方としては，ノードから始まりノードで終わるステップ以下の制約付きランダムウォークの到達確率を計算し，それをエッジが存在するスコアとする．rooted PageRankに似てるとか大体言わんとしてる事はわかるけどアルゴリズムの説明少なすぎでは．

コード

一旦書いときゃ今度使う時に楽だろうと思って書いた．

karate networkで適当に試したらそれっぽく動いた．

nodeのfilteringみたいな操作は元論文の擬似コードには載ってない．この操作ではスコアの一覧から既にエッジがあるノードを削除するようにしている．

どれぐらいの規模までスケールするかは謎．

# -*- coding: utf-8 -*-
# filename: link_prediction_kdd10.rb
# usage
# ruby link_prediction_kdd10.rb input_file_name start_node depth

class Graph
  def initialize(directed = true)
    @vertexes = [ ]
    @neighbors = Hash.new{|h, k|h[k] = Array.new}
    @weights = Hash.new{0.0}

    @directed = directed
  end

  def read_file(file)
    open(file, "r"){|f|
      f.each do |l|
        # format
        # from \t to \t weight
        v_1, v_2, w = l.chomp.split("\t")
        @vertexes.push v_1
        @vertexes.push v_2
        @neighbors[v_1].push v_2
        @weights[v_1 => v_2] += w.to_f
        
        @neighbors[v_2].push v_1 if !@directed
      end
    }
    @vertexes.uniq!
  end

  def weight(v_1, v_2)
    @directed ? @weights[v_1 => v_2] : [@weights[v_1 => v_2], @weights[v_2 => v_1] ].max
  end

  def prediction(v_s, length)
    found = [ ]; found.push v_s
    new_search = [ ]; new_search.push v_s
    large_s = Hash.new{0.0}; large_s[v_s] = 1
    
    0.upto(length) do |current_degree|
      old_search = Marshal.load(Marshal.dump(new_search))
      new_search.clear
      while !old_search.empty?
        v_i = old_search.pop
        # ここが合ってるか不明
        w_v_s = large_s[v_s]
        sum_output = 0.0
        
        @neighbors[v_i].each do |v_j|
          sum_output += weight(v_i, v_j)
        end
        
        flow = 0.0

        @neighbors[v_i].each do |v_j|
          flow = w_v_s * weight(v_i, v_j) / sum_output
          large_s[v_j] += flow
          if !found.include?(v_j)
            found.push v_j
            new_search.push v_j
          end
        end
      end
    end
    # filtering
    large_s.delete(v_s)
    @neighbors[v_s].each do |v_i|
      large_s.delete(v_i)
    end
    large_s
  end
end

if __FILE__ == $0
  g = Graph.new
  g.read_file(ARGV[0])
  p g.prediction(ARGV[1], ARGV[2].to_i)
end

■[論文] Efficiently Matching Sets of Features with Random Histograms(MM 2008) 読んだ 17:33

Efficiently matching sets of features with random histograms

概要

id:tsubosakaさんから教わった．特徴ベクトルの集合(sets of features)間の類似度を計る．

手法

集合をヒストグラムで表現する．Fig.4が非常にわかりやすい．

具体的には

• 集合の要素をLSHでhash化
• 得られたM個のhashを足しあわせてヒストグラムにするとこれが集合の特徴ベクトル
  • 元データがどんなに高次元でもおｋ
• これをN個のhash functionで試す
• あとはこれをつなげてsuper histogramにすれば比較可能に

あとはnormとかsimilarity functionとの関係性を述べている．

そもそも

2つのデータ集合間の類似度をどう測ればいいかというのが分からずにtwitterで聞いたら教わった．