/var/log/messages

Jul 9, 2018 - 6 minute read - Comments - recommendation

Recommendation

以下のドキュメント確認しつつ機械翻訳なナニを作成したので控えを。

Recommendation

グラフデータベースのより一般的な使用例の1つは、推奨システムの開発であり、これを行うための簡単なアプローチは、コラボレーションフィルタリングによるものです。 コラボレーティブフィルタリングは、ある人が別の人と意見を共有する場合、他の問題に関して同様の趣味を持つ可能性が高いと想定しています。 このような考え方を念頭に置いて、特定の人物について、彼らの意見が何であるかを予測することが可能です。

簡単な例として、「購入」エッジによって接続された「人」と「製品」の頂点を含むグラフを考えてみましょう。 次のスクリプトは、その基本スキーマを使用してグラフのデータを生成します。

gremlin> g.addV("person").property("name","alice").
           addV("person").property("name","bob").
           addV("person").property("name","jon").
           addV("person").property("name","jack").
           addV("person").property("name","jill")iterate()
gremlin> (1..10).each {
           g.addV("product").property("name","product #${it}").iterate()
         }; []
gremlin> (3..7).each {
           g.V().has("person","name","alice").as("p").
             V().has("product","name","product #${it}").addE("bought").from("p").iterate()
         }; []
gremlin> (1..5).each {
           g.V().has("person","name","bob").as("p").
             V().has("product","name","product #${it}").addE("bought").from("p").iterate()
         }; []
gremlin> (6..10).each {
           g.V().has("person","name","jon").as("p").
             V().has("product","name","product #${it}").addE("bought").from("p").iterate()
         }; []
gremlin> 1.step(10, 2) {
           g.V().has("person","name","jack").as("p").
             V().has("product","name","product #${it}").addE("bought").from("p").iterate()
         }; []
gremlin> 2.step(10, 2) {
           g.V().has("person","name","jill").as("p").
             V().has("product","name","product #${it}").addE("bought").from("p").iterate()
         }; []

The first step to making a recommendation to “alice” using collaborative filtering is to understand what she bought:

gremlin> g.V().has('name','alice').out('bought').values('name')
==>product #5
==>product #6
==>product #7
==>product #3
==>product #4

他の状態が以下。

gremlin> g.V(13).out('bought').valueMap()
==>{name=[product #3]}
==>{name=[product #4]}
==>{name=[product #5]}
==>{name=[product #6]}
==>{name=[product #7]}
gremlin> g.V(15).out('bought').valueMap()
==>{name=[product #1]}
==>{name=[product #2]}
==>{name=[product #3]}
==>{name=[product #4]}
==>{name=[product #5]}
gremlin> g.V(17).out('bought').valueMap()
==>{name=[product #6]}
==>{name=[product #7]}
==>{name=[product #8]}
==>{name=[product #9]}
==>{name=[product #10]}
gremlin> g.V(19).out('bought').valueMap()
==>{name=[product #1]}
==>{name=[product #3]}
==>{name=[product #5]}
==>{name=[product #7]}
==>{name=[product #9]}
gremlin> g.V(21).out('bought').valueMap()
==>{name=[product #4]}
==>{name=[product #6]}
==>{name=[product #8]}
==>{name=[product #2]}

以下の図は、上記の例では、「alice」と「product#5」の間を横切ったエッジの1つを示しています。 明らかに、購入された他の製品「alice」は類似した関係を持ちますが、この図とそれに続くものはその製品の周りに集中します。

recommendation alice 1

The next step is to determine who else purchased those products:

gremlin> g.V().has('name','alice').out('bought').in('bought').dedup().values('name')
==>bob
==>alice
==>jack
==>jill
==>jon

上記の結果に「アリス」があることは注目に値する。 彼女は本当にリストから除外されるべきです。なぜなら、興味が自分自身以外の個人が購入したものであるからです。

gremlin> g.V().has('name','alice').as('her').
......1>                out('bought').
......2>                in('bought').where(neq('her')).
......3>                dedup().values('name')
==>bob
==>jack
==>jill
==>jon

The following diagram shows “alice” and those others who purchased “product #5”.

recommendation alice 2

The knowledge of the people who bought the same things as “alice” can then be used to find the set of products that they bought:

gremlin> g.V().has('name','alice').as('her').
......1>                out('bought').
......2>                in('bought').where(neq('her')).
......3>                out('bought').
......4>                dedup().values('name')
==>product #1
==>product #2
==>product #3
==>product #4
==>product #5
==>product #7
==>product #9
==>product #6
==>product #8
==>product #10

recommendation alice 3

このセットの製品は推奨の基礎となる可能性がありますが、「アリス」はすでにこれらの製品の一部を購入している可能性があり、自分が既に所有している製品の推奨事項を彼女に告知しない方がよいでしょう。 購入した商品は次のように除外することができます:

g.V().has('name','alice').as('her').
......1>                out('bought').aggregate('self').
......2>                in('bought').where(neq('her')).
......3>                out('bought').where(without('self')).
......4>                dedup().values('name')
==>product #1
==>product #2
==>product #9
==>product #8
==>product #10

recommendation alice 4

The final step would be to group the remaining products (instead of dedup() which was mostly done for demonstration purposes) to form a ranking: 最後のステップは、デモンストレーションの目的で主に行われたdedup()の代わりに、残りの製品をグループ化してランキングを作成することです。

gremlin> g.V().has('person','name','alice').as('her'). //1\
               out('bought').aggregate('self'). //2\
               in('bought').where(neq('her')). //3\
               out('bought').where(without('self')). //4\
               groupCount().
               order(local).
                 by(values, decr) //5\
==>[v[10]:6,v[26]:5,v[12]:5,v[24]:4,v[28]:2]
  1. Find “alice” who is the person for whom the product recommendation is being made.
  2. Traverse to the products that “alice” bought and gather them for later use in the traversal.
  3. Traverse to the “person” vertices who bought the products that “alice” bought and exclude “alice” herself from that list.
  4. Given those people who bought similar products to “alice”, find the products that they bought and exclude those that she already bought.
  5. Group the products and count the number of times they were purchased by others to come up with a ranking of products to recommend to “alice”.

  6. 製品の推薦が行われている人である「アリス」を探します。

  7. “alice”が購入した製品をトラバースし、後でそのトラバーサルで使用するために収集します。

  8. 「アリス」が購入した商品を購入した「人」の頂点に移動し、そのリストから「アリス」自身を除外します。

  9. 同様の商品を「アリス」に購入した人には、購入した商品を見つけ、すでに購入した商品を除外します。

  10. 製品をグループ化し、他のユーザーが購入した回数を数えて、「alice」に推奨する製品のランキングを提示します。 g.V().has(‘person’,‘name’,‘alice’).as(‘her’).out(‘bought’).aggregate(‘self’).in(‘bought’).where(neq(‘her’)).out(‘bought’).where(without(‘self’)).groupCount().order(local).by(values, decr)

前の例はすでに「基本的」として記述されており、明らかに推奨の品質をさらに向上させるために利用できるデータ(商品の評価、購入時間など)を考慮に入れることができます。 (前のデータセットを拡張することなく)推奨されるものの品質を向上させる1つの選択肢は、最も一般的な購入セットを有する「アリス」に対する推奨を構成する人の頂点を選択することである。

前のコードの例に戻って、少なくとも1つの製品が共通している個人を示すストリップダウン表現を検討してください。

gremlin> g.V().has("person","name","alice").as("alice").
               out("bought").aggregate("self").
               in("bought").where(neq("alice")).dedup()
==>v[2]
==>v[6]
==>v[8]
==>v[4]

Next, do some grouping to find count how many products they have in common: 次にいくつかのグループ分けをして、どれだけ多くの製品が共通しているかを調べます。

gremlin> g.V().has("person","name","alice").as("alice").
               out("bought").aggregate("self").
               in("bought").where(neq("alice")).dedup().
               group().
                 by().by(out("bought").
               where(within("self")).count())
==>[v[2]:3,v[4]:2,v[6]:3,v[8]:2]

The above output shows that the best that can be expected is three common products. The traversal needs to be aware of that maximum: 上記の結果から、期待できる最善のものは3つの一般的な製品であることが示されています。 トラバーサルはその最大値に注意する必要があります:

gremlin> g.V().has("person","name","alice").as("alice").
               out("bought").aggregate("self").
               in("bought").where(neq("alice")).dedup().
               group().
                 by().by(out("bought").
               where(within("self")).count()).
               select(values).
               order(local).
                 by(decr).limit(local, 1)
==>3

With the maximum value available, it can be used to chose those “person” vertices that have the three products in common: 使用可能な最大値を使用して、3つの製品が共通する「人」の頂点を選択することができます。

gremlin> g.V().has("person","name","alice").as("alice").
               out("bought").aggregate("self").
               in("bought").where(neq("alice")).dedup().
               group().
                 by().by(out("bought").
               where(within("self")).count()).as("g").
               select(values).
               order(local).
                 by(decr).limit(local, 1).as("m").
               select("g").unfold().
               where(select(values).as("m")).select(keys)
==>v[2]
==>v[6]

Now that there is a list of “person” vertices to base the recommendation on, traverse to the products that they purchased: これで、推薦のベースとなる「人」の頂点のリストが得られ、購入した製品をトラバースすることができました。

gremlin> g.V().has("person","name","alice").as("alice").
               out("bought").aggregate("self").
               in("bought").where(neq("alice")).dedup().
               group().
                 by().by(out("bought").
               where(within("self")).count()).as("g").
               select(values).
               order(local).
                 by(decr).limit(local, 1).as("m").
               select("g").unfold().
               where(select(values).as("m")).select(keys).
               out("bought").where(without("self"))
==>v[10]
==>v[12]
==>v[26]
==>v[10]

The above output shows that one product is held in common making it the top recommendation: 上記の結果は、1つの製品が共通に保持されていることを示しています。

gremlin> g.V().has("person","name","alice").as("alice").
               out("bought").aggregate("self").
               in("bought").where(neq("alice")).dedup().
               group().
                 by().by(out("bought").
               where(within("self")).count()).as("g").
               select(values).
               order(local).
                 by(decr).limit(local, 1).as("m").
               select("g").unfold().
               where(select(values).as("m")).select(keys).
               out("bought").where(without("self")).
               groupCount().
               order(local).
                 by(values, decr).
                 by(select(keys).values("name")).
               unfold().select(keys).values("name")
==>product #1
==>product #2
==>product #9

In considering the practical applications of this recipe, it is worth revisiting the earlier “basic” version of the recommendation algorithm: このレシピの実際のアプリケーションを検討する際には、以前の「推奨」アルゴリズムの「基本」バージョンを再度検討する価値があります。

gremlin> g.V().has('person','name','alice').as('her').
               out('bought').aggregate('self').
               in('bought').where(neq('her')).
               out('bought').where(without('self')).
               groupCount().
               order(local).
                 by(values, decr)
==>[v[10]:6,v[26]:5,v[12]:5,v[24]:4,v[28]:2]

上記のトラバーサルは、接続されたすべてのデータに基づいて項目の完全なランキングを実行します。 トラバースされているパスの数に応じて時間がかかる操作になる可能性があります。 結局のところ、推奨は、推奨の「かなり良い」近似を提供するために、すべてのデータの完全な知識を持つ必要はありません。 そのため、トラバーサルに追加の制限を設けて、より少ないデータを調べることで、より迅速により良い結果を得ることができます。

Gremlinは、coin()、sample()、およびtimeLimit() のような制限に役立ついくつかのステップを提供しています。 たとえば、トラバーサルサンプルに1秒以下のデータをサンプリングさせるには、以前の「基本的な」推奨を次のように変更できます。

gremlin> g.V().has('person','name','alice').as('her').
               out('bought').aggregate('self').
               in('bought').where(neq('her')).
               out('bought').where(without('self')).timeLimit(1000).
               groupCount().
               order(local).
                 by(values, decr)
==>[v[10]:6,v[26]:5,v[12]:5,v[24]:4,v[28]:2]

サンプリング方法を使用する際には、グラフ内のエッジの自然順序付けが推奨の理想的なサンプルを生成しない可能性があることを考慮することが重要です。 たとえば、エッジが最も古いものから最初に返された場合、推薦は最も理想的ではない最も古いデータに基づいて行われます。 任意のトラバーサルと同様に、トラバースされるグラフの性質と、目的の結果を適切に達成するための基礎となるグラフデータベースの動作を理解することが重要です。

Tinkerpop Gremlin Aggregate Gremlin Client Initialize

comments powered by Disqus