‘Datamining’ カテゴリーのアーカイブ

What are the best similarity search engines? (Quora和訳)

2012年1月3日 火曜日

http://www.quora.com/What-are-the-best-similarity-search-engines

 

What are the best similarity search engines?

最も優れた類似検索エンジンは?

How do you find people with similar interests on the web (not limited to FB, Quora, LinkedIn), How do you find similar cars, music, videos, clothes, images, products, books (not only on Amazon), electronic parts, web sites, related academic papers, stocks, homes for sale, service providers etc

あなたは、ウェブ上(FB、quora、LinkedInに限定されない)で似たような関心を持つ人々をどのように見つけるのですか 。
またあなたは、同じような、車、音楽、ビデオ、洋服、画像、製品、書籍(だけではなくアマゾンで)、電子部品、ウェブサイト、関連する学術論文、株、売り家、サービスプロバイダー、をどのように見つけるのか。

 

回答1

You can cluster queries in user query logs to suggest similar queries. I suggest to look at Microsoft researcher Ji-Rong Wen work.

ユーザーのクエリによるクラスタクエリは、類似クエリを推薦する。 私はMicrosoftの研究者の論文をお勧めします。

 

回答2

I assume you are talking about similarity search of images.

Tineye

It is a popular image matching site (frequented by quizzers like me anyway). It checks for proper copies of images and its database has grown significantly since its launch.

http://www.tineye.com/

 

私はあなたの画像の類似検索について話していると仮定します。
Tineye
それは一般的なイメージのマッチングサイトです。 それは画像の適切なコピーをチェックし、そのデータベースは、ローンチ以降大幅に成長してきました。
他のエンジンはあなたが入力したキーワードの少なくと少しは依存します。でも、これは私の知っている唯一の純粋な画像ベースの検索エンジンです。

What is a good way to create an item-item similarity matrix for a recommendation engine where items aren’t actually rated by users, but rather “used”, “clicked”, “bought” or “played” by users? (Quora和訳)

2012年1月2日 月曜日

http://www.quora.com/What-is-a-good-way-to-create-an-item-item-similarity-matrix-for-a-recommendation-engine-where-items-arent-actually-rated-by-users-but-rather-used-clicked-bought-or-played-by-users

What is a good way to create an item-item similarity matrix for a recommendation engine where items aren’t actually rated by users, but rather “used”, “clicked”, “bought” or “played” by users?

ユーザーによる評価ではなく、ユーザーによって”クリック”、”使用”、”購入”、”プレイ”されたアイテムの場合で、
レコメンデーションエンジンのためのアイテムxアイテムの類似度行列を作成するための良い方法は何ですか?

 

 

This has to do with Collaborative Filtering. Looks like many algorithms assume users have given ratings for the items. I think there are countless scenarios where users do not “rate” an item on some scale, but their behavior provides a “rating” which is just as valuable. I’m looking to figure out how to calculate similarity between items in this scenario.

協調フィルタリング関連の話です。
多くのアルゴリズムは、ユーザーが項目の評価を与えていると仮定しています。
私はユーザの行動で実際に”評価”をしない無数のシナリオがあると考えます。
しかしユーザの行動は、実は価値のある”評価”をしています。
私はこのシナリオで項目間の類似度を計算する方法知りたいと思ってます。

 

 

回答1

 I’ve been using the Jaccard Coefficient, and specifically, the Tanimoto Coefficient, both described at http://en.wikipedia.org/wiki/Jaccard_index to calculate item-item similarity. They are both measures of overlap.

The formula is

AB / ( A + B – AB)

Where AB is the number of times both items were rated(bought) together, A is the number of times item A was bought, and B is the number of times item B was bought.

How I calculate this, in a map-reduce friendly way:
For each user, generate all of the (itemA, itemB) pairs for all of the items bought, and then keep track of the number of occurrences of each item-item pair.

The hard part is determining AB for each item-item pair. Once you have that figured out, calculating the Tanimoto coefficient is easy(refer to formula).

Consider this simplified example:
Customer A bought items 1, 2, and 3
Customer B bought items 2, 3, 4, and 6
Customer C bought items 1, 2 and 5

Items 1 and 2 would be considered most similar because they were bought together most often, compared to the number of times they were individually bought, and and thus their Jaccard score is .66. The AB would be 2 while A(item 1) = 2 and B(item2) = 3.

The similarity between items 3 and 6 would be 1 / (2 + 1 – 1), or .50 since they were bought together only once.

How you get the number of times (itemA/itemB) were bought together is up to you, my approach involved using python streaming so that I can run it on a hadoop cluster. I was inspired by Peter Skomoroch ‘s excellent article on similarity calculations using python streaming, found at

http://aws.amazon.com/articles/2294

I’m currently computing item-item similarity on about 10k items using over 3.5 million ‘purchase’ records, and it runs in only a few minutes. When you generate the (item,item) pairs for each item in a user’s history, you will generate a LOT of data but then you can reduce this when you sum the counts of occurrences.

A white-paper on this can be found at http://www.infosci.cornell.edu/weblab/papers/Bank2008.pdf

私はジャカール係数を使用しています、そしてまた谷本係数も関連します。それらのアイテム-アイテムの類似性を計算についてはwikipedia参照。

それらは両方ともオーバーラップの手段です。
その計算式は、
AB / ( A + B – AB)
ここでABは、AB同時に購入された回数、AはAがく購入された回数、BはBが購入された回数です。
私はこれを計算する方法として、MapReduceアルゴリズムに沿った方法として、

各ユーザーに対して、購入したアイテムのすべての「アイテム – アイテム」ペアを生成し、
その後、各「アイテム – アイテム」ペアの出現回数を追跡する。

難しい部分は、各アイテム-アイテムペアのABを決定することである
谷本係数を算出するのは簡単です。
以下のシンプルな例:
顧客Aは商品1,2,3を購入
顧客Bは商品2,3,4,6を購入
顧客Cは商品1,2,5を購入

 

アイテム1と2は、彼らが購入した回数に対して、最も頻繁に一緒に購入されているため、最も類似していると見なす、
ジャカールスコアは0.66である。AB=2、A=2、B=3。(これを上記の計算式に当てはめる)
アイテム3と6は、一度だけ一緒に購入されており、ジャカールスコアは0.50。
どのようにアイテムペアの同時購入回数を計算するか、pythonによるhadoop streamingのアプローチがあります。
私は現在350万人以上”購入”レコードを使用して約10,000のアイテム対し、アイテム-アイテム類似度を計算しています。
そしてそれはわずか数分で実行されます。
あなたがユーザの購入履歴らアイテム-アイテムペアを生成するときに大量のデータを生成しますが、出現回数のカウントすることとで、それを集計します。

参考論文があります。http://www.infosci.cornell.edu/weblab/papers/Bank2008.pdf

回答2

Perform cohort analysis on how much these different events lead to each other. Then you’ll be able to normalize the “downstream” likelihood (i.e., conditional probability) of events in relation to each other. For example, if 1 “clicked” event has .03 probability of leading to a “bought” event, now you can normalize to find the expected value of 1000 “clicked” events, in terms of “bought” outcomes.

これらの異なる出来事がどれくらい互いヘ導くかについての同世代分析を行なってください。
その後、互いに関しての出来事の「下流の」可能性(つまり条件付き確率)を標準化することができるでしょう。
例えば、今、1つの「クリックされた」出来事が「買われた」出来事に結びつく.03の可能性を持っている場合、1000の「クリックされた」出来事の期待値を見つけるために「買われた」結果の点から標準化することができます。

 

回答3

I think you might be interested in looking at this paper:
H. Yu, Y. Koren, C. Volinsky. Collaborative Filtering for Implicit Feedback Datasets. IEEE International Conference on Data Mining 2008.

http://research.yahoo.com/pub/2433

It includes a very thorough discussion of how to deal with implicit data (like clicks, views, etc); where, unlike ratings, you (a) don’t have negative feedback, and (b) the feedback you obtain can be used to measure the confidence you have that someone likes something, rather than their preference.
They also give some detailed descriptions of algorithms for this kind of data, ranging from neighborhood to latent factor models.

 

私は、この論文を見ることに、あなたは興味を持っているかもしれないと思います:
http://research.yahoo.com/pub/2433

それは、暗黙のデータ(クリック、視界などのような)に対処する方法の非常に完全な議論を含んでいます;
格付けと異なり、あなたが(a)ネガティブ・フィードバックを持たず、(b)得るフィードバックは、ユーザの好みではなく、誰かが何かを好きであることを測定するために使用することができます。
さらに、近隣から潜在している因子モデルまで、この種のデータ用アルゴリズムのいくつかの詳細な記述もあります。

 

回答4

It’s entirely reasonable to map these behaviors to some scalar values — maybe a page view is “0.1″, a video play is “0.3″ and a favorite is “1.0″. Then you can apply any technique that operates on rating values. Picking the right values is up to your domain and your intuition, though you could also use machine learning techniques to figure optimum weights even!

いくつかのスカラー値にこれらの行動を割り当てることは完全に合理的です
おそらく、ページビューは「0.1」です。ビデオ・プレーは「0.3」です。また、お気に入りは「1.0」です。
その後、値の評価上で作動するあらゆる技術を適用することができます。

さらに、あなたは最適の重量を計算するために機械学習技術を使用することができましたが、正しい値を取ることはあなたの領域とあなたの直観 さえあります!

 

回答5

One way would be to have separate matrices for each type of action.
You could interpolate the results from each to get your final output. Obviously “bought” would have a much higher weight than “clicked”… Instead of interpolation you could also use something like a backoff model.

1つの方法は各タイプのアクション用の個別のマトリックスを持つことでしょう。
最終産出物を得るために、各々の結果を設定します。
「買われた」は、明らかに「クリックされた」よりはるかに高い重量を持つだろう…
書き入れの代わりに、さらにbackoffモデルのようなものを使用することができました。

How does one determine similarity between people online? (Quora和訳)

2012年1月1日 日曜日

http://www.quora.com/How-does-one-determine-similarity-between-people-online

 

How does one determine similarity between people online?

どのようにオンラインのユーザ間の類似度を決定するか?

How do you quantify similarities between people using shopping sites, social networks, Q&A sites etc (e.g how do Netflix, Amazon, Paypal, Twitter, Linkedin, Facebook, Quora calculate user similarity/assign users into groups)

どのようにショッピングサイト、ソーシャルネットワーク、QAサイトのユーザ間の類似度を定量化するか。

 

回答1

 

Here are some educated guesses about what serves as a basis for their work:

(1) Use vector models. For each user, look at the text he wrote.

Build a tf.idf vector. See http://en.wikipedia.org/wiki/TF_IDF for details.

Then compute the cosine between any two users.

You can supplement this with fancier Techniques such as LSI.

If you want to implement something such as similarity measure based on text, you can look at the

org.apache.lucene.search.similar package in Lucene (open source).

(2) Networking sites such as Facebook might simply look at how many friends you have in common and compute something like the Jaccard index .

 

 

彼らの仕事の基礎について、いくつかの経験から推測は以下のとおりです。

(1)ベクトルモデルを使用してください。 ユーザーごとに、彼が書いたテキストをもとに。TF-IDFベクトルを構築します。

その後、任意の2つのユーザー間のコサインを計算します。

またLSIの等の凝ったテクニックこれを補完することができます。

このようなテキストに基づいて類似度として何かを実装する場合は、(オープンソースの)Luceneライブラリがあります。

(2)Facebookなどのネットワーキングサイトは、単にあなたが共通に持ってどのように多くの友人を見て、Jaccardインデックスのようなものを計算しているのかもしれない。

(関連キーワード: LSI / Jaccard Index )

 

 

回答2

 

A good place to start is: Programming Collective Intelligence

http://www.amazon.com/Programming-Collective-Intelligence-Building-Applications/dp/0596529325

Whole books have been written on this area so answering it in a few words is not give anywhere near a full answer.

But if using the collaborative filtering approach, then find how many actions (e.g. products purchased, likes, friends) two people have in common. But to make it work well you have assign weights to the actions in common. The correlation value between two people is the sum of the weights of the actions. But the tricky part is assigning good weights to the actions. The weight has to be relative the two people, the cluster of the two people and the whole population.

 

 

集合知プログラミングは入門には良い。

その領域についてこの本に書かれている。

しかし、協調フィルタリング手法を使用している場合は、その後二人が共通して持ってどのように多くのアクション(購入などの商品、好き、友人)を見つける。

しかしそれはあなたが共通のアクションに重みを割り当てるているうまく機能させるために。

二人の間の相関値は、アクションの重みの合計です。

しかし、トリッキーな部分はアクションに適切な重みを割り当てています。 重量は相対的な二人、二人のクラスタと全体の人口にする必要があります。

 

回答3

Recommendation mining is very useful to determine similarity between peoples using shopping sites, social networks and Q&A sites on the basis of their likes, choices and on-line behavior

Some of popular recommendation engine are

 

You can also find similarity between in text posted by authors in Q&A, social networks, blogs etc. For that you can try out following techniques

  • Jaccard Index
  • Simrank
  • Vector space model with Cosine Similarity
  • Sorensen similarity index
  • BM25 Okapi model

 

 

レコメンドマイニングは、ショッピングサイト、ソーシャルネットワーク、Q&Aを用いて人々の間の類似性を決定するために非常に便利です。

有名なレコマンドエンジンとしては以下があります。

また、Q&A、ソーシャルネットワーク、ブログ等での、投稿者間の類似性を見つけることができます。

そのためには、次の方法を試してみることができます

  • ジャッカード係数
  • Simrank
  • コサイン類似度によるベクトル空間モデル
  • Sorensen similarity index
  • BM25 Okapi model

(関連キーワード: Jaccard Index / Simrank / Vector space model with Cosine Similarity / Sorensen similarity index / BM25 Okapi model )

 

 

 

 関連するQuoraのQA

 

 

 

 

 

 

 

 

 

 

 

第7回データマイニング+WEB勉強会@東京で発表してきた

2010年9月27日 月曜日

こんにちは。2010/09/26(日)、第7回データマイニング+WEB勉強会@東京に参加してきました。

この勉強会の特徴について

双方向の議論が多く、参加者の多くの方が発言するのが大きな特徴です。またIT系以外の方が参加される異業種交流ができる貴重な勉強回の一つです。内容については「理論〜詳細な実装〜実務」と幅広いものとなってます。
開始時の自己紹介、終了時の振り返り、で少なくとも全員2回ずつ発言する必要がありますw
今回も会場を提供してくださったニフティ・エンジニアサポート様に感謝!また、次回の勉強会は11/14(日)開催予定です。

今回は発表しました

以下発表資料です。

はじめてでもわかるベイズ分類器 -基礎からMahout実装まで-


機会学習も統計も素人ですが、素人なりに勉強した結果と、MahoutというHadoop(またはElastic MapReduce)上で動作する分類器の使い方を解説しています。ベイズ分類器の学習・評価データにはWikipediaのデータを利用してます。

参加者をまとめたホワイトボード

恒例の参加者一覧です。

プレゼン内で紹介した本とRubyのサンプルコード

「この本持っている人います?」の質問に7割近くの人が手を挙げたのが印象的でした。この「集合知プログラミング」の6章では、Pythonによるナイーブベイズ分類器の実装を解説していますが、それを私が使い慣れているRubyで実装してみました。

集合知プログラミング

まず使い方から

# 分類器生成
n = NaiveBayes.new
# 学習
n.train('Nobody owns the water.','good')
n.train('the quick rabbit jumps fences','good')
n.train('buy pharmaceuticals now','bad')
n.train('make quick money at the online casino','bad')
n.train('the quick brown fox jumps','good')
# 推定
puts n.classify("quick rabbit",default="unknown")
puts n.classify("quick money",default="unknown")
# 閾値を与える
n.setthreshold("bad",3.0)
# 推定
puts n.classify("quick money",default="unknown")

分類器のコード

# 特徴抽出クラス
class GetWordFeature
  def get_feature(doc)
    words = doc.split(' ')
    words.map{|w| w.downcase}.select{|w| w.length < 20 && w.length > 2 }.uniq
  end
end
 
# 分類器の基底クラス
class Classifier
  def initialize(f)
    @fc,@cc,@feature = {},{},f
  end
 
  def incf(f,cat)
    @fc[f] ||= {}
    @fc[f][cat] ||= 0.0
    @fc[f][cat] = @fc[f][cat] + 1.0
  end
 
  def incc(cat)
    @cc[cat] ||= 0.0
    @cc[cat] = @cc[cat] + 1.0
  end
 
  def fcount(f,cat)
    @fc[f] ||= {}
    @fc[f][cat] ||= 0.0
    @fc[f][cat]
  end
 
  def catcount(cat)
    @cc[cat] ? @cc[cat].to_f : 0.0
  end
 
  def totalcount
    sum = 0
    @cc.each_value {|value| sum += value}
    return sum
  end
 
  def categories
    @cc.keys
  end
 
  # 条件付き確率 Pr(A|B)
  def fprob(f,cat)
    return 0 if catcount(cat) == 0 || fcount(f,cat) == nil
    fcount(f,cat) / catcount(cat)
  end
 
  # 重み付き確率
  def weightedprob(f, cat, weight=1.0, ap=0.5)
    # 通常の条件付き確率
    basicprob = fprob(f,cat)
    # この特徴がすべてのカテゴリ中に存在する確率
    totals = 0
    categories.each do |c|
      totals = totals + fcount(f,c) if fcount(f,c)
    end
    # 重み付けした平均計算
    ((weight*ap)+(totals*basicprob)) / (weight+totals)
  end
 
  def train(item, cat)
    features =  @feature.get_feature(item);
    features.each do |f|
      incf(f, cat)
    end
    incc(cat)
  end
end
 
# 単純ベイズ分類器
class NaiveBayes < Classifier
  def initialize
    super(GetWordFeature.new)
    @thresholds = {}
  end
 
  # P(B|A):アイテム全体の与えられたカテゴリでの確率を求める(掛け合わせる)
  def docprob(item,cat)
    features = @feature.get_feature(item)
    p = 1.0
    features.each do |f|
      ep = weightedprob(f,cat)
      p = p * ep
    end
    return p
  end
 
  def prob(item,cat)
    catprob = catcount(cat) / totalcount
    docprob = docprob(item,cat)
    return docprob * catprob
  end
 
  def setthreshold(cat,t)
    @thresholds[cat] = t
  end
 
  def getthreshold(cat)
    @thresholds[cat] || 1.0
  end
 
  def classify(item, default=nil)
    probs,max,best = {},0.0,nil
    categories.each do |c|
      probs[c] = prob(item,c)
      if probs[c] > max
        max = probs[c]
        best = c
      end
    end
    probs.each_key do |c|
      # (2番目に確率の高いもの * 閾値)と比較
      second = probs[c].to_f * getthreshold(best)
      return default if second > probs[best]
    end
    return best
  end
end

以上です!

第6回データマイニング+WEB勉強会@東京に参加してきた

2010年8月25日 水曜日

2010/08/22(日)、第6回データマイニング+WEB勉強会@東京に参加してきました。

ATND
http://atnd.org/events/7239

主催者@hamadakoichiさんによる勉強会まとめ(発表資料一覧/Togetter)
http://d.hatena.ne.jp/hamadakoichi/20100822/p1

@tyatsutaさんがまとめてくださった参加者一覧
http://d.hatena.ne.jp/yatsuta/20100824#1282636786

写真は会場提供してくださったニフティさん(大森 ベルポート)です。
今回の勉強会のテーマは「ソーシャル・広告・最適化祭り」ということもあって、
「ソーシャルアプリ業界」と「オンライン広告業界」からの参加者が多かったです。

この勉強会の特徴について

私はエンジニアで、昨今の技術勉強会ブームにのっている一人ですが、プロデューサ/マーケタ/企画の人向けの勉強会って、まだまだは少ないと感じていて、
(ノウハウやビジネスプランなど社外に出せるネタが少ないわけで、当然といえば当然なのですが)
そういう意味ではとても貴重な勉強会だったのではないでしょうか。

内容について

「広告」や「ソーシャルアプリ」はオープンなテクノロジが主流になりつつあることから、発表者や参加者の方は、公開ギリギリのかなり思い切った発表や質疑をしてくださっていたと思います。
ソーシャルアプリの運用の話が掘り下げられて行ったときは、正直ハラハラしました(笑)
資料については上記の@hamadakoichiさんのブログにまとまってます。
本当にありがとうございました!
そんな私はSIerという立場上、技術以外の話をすることができず大変申し訳ございませんw

懇親会のピザパーティも盛り上がりました

写真撮り忘れた。
立ち話ですが、両業界の共通点としてユーザーの反応がすぐに数字となって現れるという点があって、それって中の人にとってはドラッグみたいなもので、数字の恐怖や快感に一度浸かると、なかなかそこから抜けれないんじゃないかとか、そんな話をしたのが印象的でした。
また、お互いの業界への感心が深いことも感じました。
ソーシャルメディアのお仕事をしてる方が、広告エコシステムの話しをする一方で、広告エンジニアが、Zingaの指標値の話をするなど両者の交流を感じました。
皆さん、アンテナ貼ってるんすね。
そしてそれを横断するのが「データマイニング方法論」や「分散処理テクノロジー」であることであることは間違いなくて、私の勉強のモチベーションが上がったことは言うまでもありません。

最後に

今回、楽しみにしていた@mmlab_jp さんのプレゼンで印象に残った言葉で、
「周りに目を向けて、勘やバランス感覚を養い続けることの大切さ」
は、まさにこのような勉強会への参加を意味するんだと感じました。
発表者・参加者の皆さん、また会場提供してくださったニフティの皆さん
本当にありがとうございました。

次回の第7回勉強会は、9/26(日)の予定です!

第5回データマイニング+WEB勉強会@東京で発表してきた

2010年6月21日 月曜日

こんにちは。

6/20(日)、第5回データマイニング+WEB勉強会@東京に行ってきました。

http://atnd.org/events/5095

今回は、金融・出版・ウェブ・教育・製造の各業界から、マーケター ・アナリスト・コンサル・企画・エンジニア・学生の方がいらっしゃってました。

幅広い業界から参加者が集まるという点で、非常に珍しい勉強会の一つだと思います。

-

今回の私の発表資料を貼っておきます。

Facebookがトップページ最適化に利用しているEdgeRank(エッジランク)というアルゴリズムを身近なTwitter(ツイッター)に適用してみたよ、

っていうポップで軽い内容になってます。

ソーシャルグラフとEdgeRank


Twitterという身近なネタなので、多くの方に興味を持っていただいてよかったです。

発表中に見せたアプリのデモですが、イメージだけ貼っておきます。

このアプリはご覧のとおり、自分のフォローの中で人気(ふぁぼ、りぷ、RT)の高いツイートが選別されます。

クローラーを除いては、半日で作ったので、かなり適当なアプリですが、以外と使えるので、ちゃんとしたものに作り直してみようかと思ってます。

-

また、今回はニフティさんの会場提供を受けることができて、素晴らしい環境での開催となりました。

私も運営スタッフの一人だったのですが、ニフティさんスタッフの方に任せっぱなしでした。

素晴らしい運営本当にありがとうございました!

会場の写真はbob3さんが撮ってくださったものをどうぞ。

いつもありがとうございます。

http://f.hatena.ne.jp/bob3/TokyoWebmining%235/

それにしても大きいビルでした。

私がiPhoneで撮った、ベルポートビルの広い中庭(?)の写真も貼っておきます。

第4回 データマイニング+WEB 勉強会@東京で発表してきた

2010年5月17日 月曜日

2010/5/16(土)に、@hamadakoichiさん主催の第4回 データマイニング+WEB 勉強会@東京で「Hadoop入門」について発表してきました。

勉強会の概要

会場は恵比寿のSPSS株式会社。すごくきれいな建物でびっくりでした。

会場内の写真は、bob3さんのブログを。

次回、第5回データマイニング+WEB@東京勉強会は、2010/6/20(日)の予定です。

発表資料を公開します。

この資料で、社内勉強会も開催する予定です。

Hadoop入門とクラウド活用