(57)【要約】【課題】ユーザの行動履歴に応じた適切な選択肢を提示することができるようにする。【解決手段】選択確率計算部３８が、特定ユーザの行動履歴データに基づいて、特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算する。初期クラスタリング部４０が、複数のアイテムｊの各々について抽出された特徴量に基づいて、複数のアイテムｊを複数のクラスｋにクラスタリングする。情報量最大化クラスタリング部４２が、クラスタリング結果に基づいて、選択確率から特定ユーザがクラスｋを選択する確率を表すクラス確率を算出し、クラスｋに対するクラス確率が大きいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を小さくし、クラスｋに対するクラス確率が小さいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングする。【選択図】図１
2016103107.tif 000002
【特許請求の範囲】
【請求項１】
特定ユーザが各アイテムｊに対して所定の行動をとった行動履歴データに基づいて、前記特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算する選択確率計算手段と、
複数のアイテムｊの各々について抽出された特徴量に基づいて、複数のアイテムｊを複数のクラスｋにクラスタリングする第１のクラスタリング手段と、
前記第１のクラスタリング手段によって計算されたクラスタリング結果に基づいて、複数のクラスｋの各々について、前記選択確率計算手段によって計算された、前記クラスｋに属する前記アイテムｊの各々に対しての前記選択確率から、前記特定ユーザが前記クラスｋを選択する確率を表すクラス確率を算出し、前記複数のアイテムｊの各々から抽出された特徴量に基づいて、前記クラスｋに対する前記クラス確率が大きいほど、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を小さくし、前記クラスｋに対する前記クラス確率が小さいほど、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングする第２のクラスタリング手段と、
を含むクラスタリング装置。
【請求項２】
前記第２のクラスタリング手段は、前記第１のクラスタリング手段によって計算されたクラスタリング結果に基づいて、複数のクラスｋの各々について、前記クラス確率を算出し、前記複数のアイテムｊの各々から抽出された特徴量に基づいて、前記クラスｋに対する前記クラス確率が前記クラス確率の平均値より大きい場合に、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を小さくし、前記クラスｋに対する前記クラス確率が前記クラス確率の平均値以下の場合に、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングする請求項１に記載のクラスタリング装置。
【請求項３】
前記第２のクラスタリング手段は、前記特定ユーザが前記クラスｋを選択する確率を表すクラス確率の標準偏差が、予め定められた閾値以下になるまで、複数のアイテムｊを複数のクラスｋにクラスタリングすることを繰り返す
請求項１又は請求項２に記載のクラスタリング装置。
【請求項４】
複数のユーザｉの各々が各アイテムｊに対して所定の行動をとった行動履歴データに基づいて、複数のユーザｉの各々が各アイテムｊに対して所定の行動をとった度合いを表すレートを要素にもつレート行列を生成するレート行列生成手段と、
前記レート行列生成手段によって生成されたレート行列に基づいて、前記レート行列のうち、前記特定ユーザについての０である要素のレートを推定し、前記レート行列生成手段によって生成された前記レート行列を更新するフィルタリング手段とを更に含み、
前記選択確率計算手段は、前記フィルタリング手段によって更新された前記レート行列に基づいて、前記特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算する
請求項１〜請求項３の何れか１項に記載のクラスタリング装置。
【請求項５】
前記第２のクラスタリング手段によって計算されたクラスタリング結果と、前記レート行列生成手段によって生成されたレート行列とに基づいて、複数のユーザｉの各々が各クラスｋに属するアイテムに対して所定の行動をとる度合いを表すレートを要素にもつ第２レート行列を生成し、
前記生成された第２レート行列に基づいて、前記第２レート行列のうち、前記特定ユーザについての０である要素のレートを推定し、前記第２レート行列を更新する第２のフィルタリング手段を更に含む
請求項４に記載のクラスタリング装置。
【請求項６】
前記アイテムは、商品であって、前記所定の行動は、商品の閲覧、購入、又は評価である請求項１〜請求項５の何れか１項に記載のクラスタリング装置。
【請求項７】
前記アイテムは、場所であって、前記所定の行動は、場所への訪問又は場所の評価である請求項１〜請求項５の何れか１項に記載のクラスタリング装置。
【請求項８】
請求項５〜請求項７の何れか１項に記載のクラスタリング装置によって計算された前記第２レート行列において、前記特定ユーザについてのレートが高い順に並び替えられたクラスの情報を取得する通信手段と、
前記通信手段によって取得されたクラスの情報を提示する提示手段と、
を含む情報端末。
【請求項９】
請求項４〜請求項７の何れか１項に記載のクラスタリング装置と、
請求項８に記載の情報端末とを含む情報提示システム。
【請求項１０】
コンピュータを、
特定ユーザが各アイテムｊに対して所定の行動をとった行動履歴データに基づいて、前記特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算する選択確率計算手段、
複数のアイテムｊの各々について抽出された特徴量に基づいて、複数のアイテムｊを複数のクラスｋにクラスタリングする第１のクラスタリング手段、及び
前記第１のクラスタリング手段によって計算されたクラスタリング結果に基づいて、複数のクラスｋの各々について、前記選択確率計算手段によって計算された、前記クラスｋに属する前記アイテムｊの各々に対しての前記選択確率から、前記特定ユーザが前記クラスｋを選択する確率を表すクラス確率を算出し、前記複数のアイテムｊの各々から抽出された特徴量に基づいて、前記クラスｋに対する前記クラス確率が大きいほど、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を小さくし、前記クラスｋに対する前記クラス確率が小さいほど、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングする第２のクラスタリング手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置、情報端末、情報提示システム、及びプログラムに関する。
【背景技術】
【０００２】
従来より、ユーザが検索のために入力したクエリに基づいて、ユーザの検索意図を推測し、クエリの意味に追従し、話題となっているドキュメントをレコメンドするサーバが知られている（例えば、特許文献１を参照。）。
【０００３】
また、協調フィルタリングによる処理に基づいて、特定ユーザと似ているユーザが選んだアイテムを推薦するinteractiveレコメンドに関する技術が知られている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−１１８０２１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、従来の技術では、特定ユーザに対するレコメンドの精度を高くすると粒度が粗くなり、レコメンドの粒度を細かくすると精度が低くなるため、精度と粒度とのトレードオフが発生し、適切な選択肢をユーザに提示することができない、という問題があった。
【０００６】
本発明は、上記の事情に鑑みてなされたもので、ユーザの行動履歴に応じた適切な選択肢を提示することができるクラスタリング装置、情報端末、情報提示システム、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、第１の発明のクラスタリング装置は、特定ユーザが各アイテムｊに対して所定の行動をとった行動履歴データに基づいて、前記特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算する選択確率計算手段と、複数のアイテムｊの各々について抽出された特徴量に基づいて、複数のアイテムｊを複数のクラスｋにクラスタリングする第１のクラスタリング手段と、前記第１のクラスタリング手段によって計算されたクラスタリング結果に基づいて、複数のクラスｋの各々について、前記選択確率計算手段によって計算された、前記クラスｋに属する前記アイテムｊの各々に対しての前記選択確率から、前記特定ユーザが前記クラスｋを選択する確率を表すクラス確率を算出し、前記複数のアイテムｊの各々から抽出された特徴量に基づいて、前記クラスｋに対する前記クラス確率が大きいほど、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を小さくし、前記クラスｋに対する前記クラス確率が小さいほど、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングする第２のクラスタリング手段と、を含んで構成されている。
【０００８】
第２の発明に係るプログラムは、コンピュータを、特定ユーザが各アイテムｊに対して所定の行動をとった行動履歴データに基づいて、前記特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算する選択確率計算手段、複数のアイテムｊの各々について抽出された特徴量に基づいて、複数のアイテムｊを複数のクラスｋにクラスタリングする第１のクラスタリング手段、及び前記第１のクラスタリング手段によって計算されたクラスタリング結果に基づいて、複数のクラスｋの各々について、前記選択確率計算手段によって計算された、前記クラスｋに属する前記アイテムｊの各々に対しての前記選択確率から、前記特定ユーザが前記クラスｋを選択する確率を表すクラス確率を算出し、前記複数のアイテムｊの各々から抽出された特徴量に基づいて、前記クラスｋに対する前記クラス確率が大きいほど、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を小さくし、前記クラスｋに対する前記クラス確率が小さいほど、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングする第２のクラスタリング手段として機能させるためのプログラムである。
【０００９】
第１の発明及び第２の発明によれば、選択確率計算手段によって、特定ユーザが各アイテムｊに対して所定の行動をとった行動履歴データに基づいて、特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算する。
【００１０】
そして、第１のクラスタリング手段によって、複数のアイテムｊの各々について抽出された特徴量に基づいて、複数のアイテムｊを複数のクラスｋにクラスタリングする。
【００１１】
そして、第２のクラスタリング手段によって、第１のクラスタリング手段によって計算されたクラスタリング結果に基づいて、複数のクラスｋの各々について、選択確率計算手段によって計算された、クラスｋに属するアイテムｊの各々に対しての選択確率から、特定ユーザがクラスｋを選択する確率を表すクラス確率を算出し、複数のアイテムｊの各々から抽出された特徴量に基づいて、クラスｋに対するクラス確率が大きいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を小さくし、クラスｋに対するクラス確率が小さいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングする。
【００１２】
このように、特定ユーザの行動履歴データに基づいて、特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算し、複数のアイテムｊを複数のクラスｋにクラスタリングしたクラスタリング結果に基づいて、複数のクラスｋの各々について、特定ユーザがクラスｋを選択する確率を表すクラス確率を算出し、クラスｋに対するクラス確率が大きいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を小さくし、クラスｋに対するクラス確率が小さいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングすることにより、ユーザの行動履歴に応じた適切な選択肢を提示することができる。
【００１３】
第１の発明及び第２の発明の前記第２のクラスタリング手段は、前記第１のクラスタリング手段によって計算されたクラスタリング結果に基づいて、複数のクラスｋの各々について、前記クラス確率を算出し、前記複数のアイテムｊの各々から抽出された特徴量に基づいて、前記クラスｋに対する前記クラス確率が前記クラス確率の平均値より大きい場合に、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を小さくし、前記クラスｋに対する前記クラス確率が前記クラス確率の平均値以下の場合に、前記クラスｋに属する前記アイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングするようにすることができる。
【００１４】
第１の発明及び第２の発明の前記第２のクラスタリング手段は、前記特定ユーザが前記クラスｋを選択する確率を表すクラス確率の標準偏差が、予め定められた閾値以下になるまで、複数のアイテムｊを複数のクラスｋにクラスタリングすることを繰り返すようにすることができる。
【００１５】
第１の発明及び第２の発明は、複数のユーザｉの各々が各アイテムｊに対して所定の行動をとった行動履歴データに基づいて、複数のユーザｉの各々が各アイテムｊに対して所定の行動をとった度合いを表すレートを要素にもつレート行列を生成するレート行列生成手段と、前記レート行列生成手段によって生成されたレート行列に基づいて、前記レート行列のうち、前記特定ユーザについての０である要素のレートを推定し、前記レート行列生成手段によって生成された前記レート行列を更新するフィルタリング手段とを更に含み、前記選択確率計算手段は、前記フィルタリング手段によって更新された前記レート行列に基づいて、前記特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算するようにすることができる。
【００１６】
第１の発明及び第２の発明は、前記第２のクラスタリング手段によって計算されたクラスタリング結果と、前記レート行列生成手段によって生成されたレート行列とに基づいて、複数のユーザｉの各々が各クラスｋに属するアイテムに対して所定の行動をとる度合いを表すレートを要素にもつ第２レート行列を生成し、前記生成された第２レート行列に基づいて、前記第２レート行列のうち、前記特定ユーザについての０である要素のレートを推定し、前記第２レート行列を更新する第２のフィルタリング手段を更に含むようにすることができる。
【００１７】
また、前記アイテムは、商品であって、前記所定の行動は、商品の閲覧、購入、又は評価であるようにすることができる。
【００１８】
また、前記アイテムは、場所であって、前記所定の行動は、場所への訪問又は場所の評価であるようにすることができる。
【００１９】
第３の発明に係る情報端末は、第１の発明のクラスタリング装置によって計算された前記第２レート行列において、前記特定ユーザについてのレートが高い順に並び替えられたクラスの情報を取得する通信手段と、前記通信手段によって取得されたクラスの情報を提示する提示手段と、を含んで構成されている。
【００２０】
第４の発明に係る情報提示システムは、第１の発明のクラスタリング装置と、第３の発明の情報端末とを含んで構成されている。
【００２１】
なお、本発明のプログラムを記憶する記憶媒体は、特に限定されず、ハードディスクであってもよいし、ＲＯＭであってもよい。また、ＣＤ−ＲＯＭやＤＶＤディスク、光磁気ディスクやＩＣカードであってもよい。更にまた、該プログラムを、ネットワークに接続されたサーバ等からダウンロードするようにしてもよい。
【発明の効果】
【００２２】
以上説明したように、本発明のクラスタリング装置、情報端末、情報提示システム、及びプログラムによれば、特定ユーザの行動履歴データに基づいて、特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算し、複数のアイテムｊを複数のクラスｋにクラスタリングしたクラスタリング結果に基づいて、複数のクラスｋの各々について、特定ユーザがクラスｋを選択する確率を表すクラス確率を算出し、クラスｋに対するクラス確率が大きいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を小さくし、クラスｋに対するクラス確率が小さいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングすることにより、ユーザの行動履歴に応じた適切な選択肢を提示することができる、という効果が得られる。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施の形態に係る情報提示システムの機能的構成を示すブロック図である。
【図２】レート行列の一例を示す図である。
【図３】情報端末に表示される画面の一例と当該画面の選択肢数との関係を説明するための図である。
【図４】本発明の実施の形態におけるクラスタリング処理ルーチンの内容を示すフローチャートである。
【図５】本発明の実施の形態における初期クラスタリング処理ルーチンの内容を示すフローチャートである。
【図６】本発明の実施の形態における情報量最大化クラスタリング処理ルーチンの内容を示すフローチャートである。
【図７】情報端末に表示される画面の階層を説明するための図である。
【図８】複数のユーザの各アイテムに対する評価行動の概念図を示す図である。
【発明を実施するための形態】
【００２４】
＜概要＞
本発明の実施の形態では、ユーザの行動履歴データに基づいて、ユーザが各アイテムに対してとる行動についての情報量が大きくなるように、複数のアイテムをクラスタリングする。具体的には、本実施の形態では、ユーザの興味のあるアイテム群については細かくクラスを生成し、ユーザの興味のないアイテム群は粗くクラスを生成し、クラスに対応する選択肢を提示することにより、少ない選択操作でユーザにマッチしたアイテムを決定することができる。
【００２５】
以下、図面を参照して本発明の実施の形態を詳細に説明する。本実施の形態では、ユーザの行動履歴データに基づいて複数のアイテムをクラスタリングし、当該ユーザに対してクラスタリング結果に応じた情報を提示する情報提示システムに本発明を適用した場合を例に説明する。
【００２６】
＜情報提示システムのシステム構成＞
図１に示すように、本発明の実施の形態に係る情報提示システム１０は、複数の情報端末１２と、複数の情報端末１２から送信された情報を受信して、情報端末１２を持つ複数のユーザの行動履歴データを取得し、複数のユーザの各々に対して情報を提供するサーバ１４とを備えている。複数の情報端末１２とサーバ１４とは、インターネットなどのネットワーク１６を介して接続されている。なお、サーバ１４は、クラスタリング装置の一例である。
【００２７】
情報端末１２は、ユーザによって入力された行先としての訪問場所の情報を受け付ける入力部２０と、入力部２０によって受け付けた訪問場所の情報に対応するアイテムＩＤをユーザＩＤと共にサーバ１４へ逐次送信すると共に、ユーザＩＤを含む選択肢提示要求をサーバ１４へ送信し、選択肢の一覧を受信する通信部２２と、受信した選択肢の一覧をユーザに提示する提示部２４とを備えている。なお、提示部２４によってユーザへ提示される選択肢の数は予め定められている。またユーザＩＤは、情報端末１２に予め設定されている。なお、本実施の形態では、アイテムが、特定の場所を表すＰＯＩ（Point of Interest）である場合を例に説明する。また、本実施の形態では、情報端末１２が、車両に搭載されたカーナビゲーションシステムである場合を例に説明する。
【００２８】
サーバ１４は、ＣＰＵ、後述するクラスタリング処理ルーチンを実現するためのプログラム等を記憶したＲＯＭ、データを一時的に記憶するＲＡＭ、記憶手段としてのメモリ、ネットワークインタフェース等を含むサーバで構成されており、機能的には、通信部３０、行動履歴データベース３２、レート行列生成部３４、協調フィルタリング部３６、選択確率計算部３８、初期クラスタリング部４０、情報量最大化クラスタリング部４２、及び最適粒度協調フィルタリング部４４を含んだ構成で表すことができる。協調フィルタリング部３６は、フィルタリング手段の一例であり、初期クラスタリング部４０は、第１のクラスタリング手段の一例であり、情報量最大化クラスタリング部４２は、第２のクラスタリング手段の一例であり、最適粒度協調フィルタリング部４４は、第２のフィルタリング手段の一例である。
【００２９】
通信部３０は、情報端末１２から送信されたユーザＩＤ及びアイテムＩＤを受信し、行動履歴データベース３２に格納するように制御する。通信部３０は、情報端末１２から送信された選択肢提示要求を受信すると、レート行列生成部３４へ出力し、最適粒度協調フィルタリング部４４により出力されたクラスタリング結果に応じた選択肢を、当該情報端末１２へ送信する。
【００３０】
行動履歴データベース３２には、通信部３０によって受信したユーザＩＤ及びアイテムＩＤを蓄積し、ユーザＩＤ毎に、アイテムＩＤに対応するアイテムを訪問した回数を表す行動履歴データを記憶する。
【００３１】
レート行列生成部３４は、通信部３０によって選択肢提示要求を受信すると、ユーザＩＤ毎の行動履歴データを、行動履歴データベース３２から読み込む。そして、レート行列生成部３４は、複数のユーザｉの各々が各アイテムｊを訪問した行動履歴データに基づいて、複数のユーザｉの各々が各アイテムｊを訪問する度合いを表すレートを要素にもつレート行列を生成する。具体的には、レート行列生成部３４は、行動履歴データベース３２から読み込んだ複数の行動履歴データから、図２（Ａ）に示されるようなレート行列を生成する。本実施の形態では、アイテムが場所であって、所定の行動は当該場所への訪問であり、レートが訪問回数を表す。なお、レート行列の各要素のうち、該当する行動履歴データのない要素は０となる。
【００３２】
協調フィルタリング部３６は、レート行列生成部３４によって生成されたレート行列に基づいて、レート行列のうち、選択肢提示要求を送信した特定ユーザについての０である要素のレートを推定し、レート行列生成部３４によって生成されたレート行列を更新する。具体的には、協調フィルタリング部３６は、例えば参考文献（Koren，“Matrix Factorization Techniques For Recommender Systems”，2009）に記載の手法を用いて、図２（Ｂ）に示されるように、レート行列生成部３４によって生成されたレート行列のデータ欠損要素（０要素）を推定し、補完する。
【００３３】
選択確率計算部３８は、協調フィルタリング部３６によって更新されたレート行列に基づいて、選択肢提示要求を送信した特定ユーザが各アイテムｊを訪問する確率を表す選択確率を計算する。具体的には、選択確率計算部３８は、協調フィルタリング部３６によって欠損補完されたレート行列の値に基づいて、選択肢提示要求を送信した特定ユーザｉのアイテムｊの選択確率を以下の式（１）に従って推定する。
【００３４】
【数１】
2016103107.tif 000003
【００３５】
初期クラスタリング部４０は、複数のアイテムｊの各々について抽出された特徴量に基づいて、複数のアイテムｊを複数のクラスｋにクラスタリングする。具体的には、初期クラスタリング部４０は、例えばＫ−ｍｅａｎｓアルゴリズムや、ＥＭアルゴリズム等（例えば、参考文献（Ｃ.Ｍ.ビショップ著、元田他４名監訳、「パターン認識と機械学習」、シュプリンガー・ジャパン、２０１２)を参照。）のクラスタリングアルゴリズムを用いて、各アイテムｊについて得られるアイテムの特徴量に基づいて、複数のアイテムｊをＫ個のクラスにクラスタリングする。なお、クラスの数Ｋは予め定められており、本実施の形態では、クラスの数Ｋは情報端末１２によってユーザへ提示される選択肢の数Ｍよりも大きい値であるとする。また、アイテムの特徴量としては、アイテムが表す場所のジャンル情報などを用い、例えば、「ラーメン屋」「床屋」等のジャンル情報が挙げられる。また、協調フィルタリング部３６によって得られたレート行列のユーザ毎のレートベクトルも特徴量として用いることができる。
【００３６】
本実施の形態では、混合ガウス分布とＥＭアルゴリズムとを用いてクラスタリングする場合を例に説明する。初期クラスタリング部４０によるクラスタリングによって、アイテムｊのクラスｋの負担率ｒｊｋと、クラスｋの平均μｋと、クラスｋの標準偏差ｓｋと、混合ガウス分布の混合係数πｋとが算出される。
【００３７】
まず、初期クラスタリング部４０は、複数のクラスｋの各々について、当該クラスｋの平均μｋ、分散ｓｋ２、及び混合係数πｋを初期化する。ここで、初期化の方法としては、平均μｋ、分散ｓｋ２、及び混合係数πｋをランダムな値に設定するか、又は任意の定数を設定する。
【００３８】
次に、初期クラスタリング部４０は、ＥＭアルゴリズムのＥステップにおいて、以下の式（２）に従って、複数のクラスｋの各々について、各アイテムｊに対し、アイテムｊのクラスｋの負担率ｒｊｋを更新する。
【００３９】
【数２】
2016103107.tif 000004
【００４０】
なお、上記式（２）における、ｘｊはアイテムｊの特徴量ベクトルを表し、Ｎ（ｘｊ｜μｋ、ｓｋ２）は、平均μｋ、標準偏差ｓｋの正規分布を表し、πｋは後述する式（６）において計算される混合係数を表す。
【００４１】
次に、初期クラスタリング部４０は、ＥＭアルゴリズムのＭステップにおいて、以下の式（３）〜（６）に従って、複数のクラスｋの各々について、当該クラスｋの平均μｋ、分散ｓｋ２、及び混合係数πｋを更新する。
【００４２】
【数３】
2016103107.tif 000005
【００４３】
なお、上記式（３）〜（６）における、Ｎｋは、クラスｋに属するアイテムｊの数を表し、Ｎはアイテムの総数を表す。
【００４４】
そして、初期クラスタリング部４０は、上記Ｅステップ及びＭステップを、収束するまで繰り返す。
【００４５】
情報量最大化クラスタリング部４２は、初期クラスタリング部４０によって計算されたクラスタリング結果に基づいて、複数のクラスｋの各々について、選択確率計算部３８によって計算された、クラスｋに属するアイテムｊの各々に対しての選択確率から、特定ユーザがクラスｋを選択する確率を表すクラス確率を算出する。
【００４６】
そして、情報量最大化クラスタリング部４２は、複数のクラスｋの各々について、複数のアイテムｊの各々から抽出された特徴量に基づいて、クラスｋに対するクラス確率が大きいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を小さくし、クラスｋに対するクラス確率が大きいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングする。
【００４７】
具体的には、情報量最大化クラスタリング部４２は、複数のクラスｋの各々について、クラスｋに属するアイテムｊの各々に対しての選択確率から、特定ユーザがクラスｋを選択する確率を表すクラス確率を算出し、クラス確率の平均値を算出する。そして、情報量最大化クラスタリング部４２は、複数のクラスｋの各々について、複数のアイテムｊの各々から抽出された特徴量に基づいて、クラスｋに対するクラス確率がクラス確率の平均値より大きい場合に、クラスｋに属するアイテムの各々の特徴量の標準偏差を小さくし、クラスｋに対するクラス確率がクラス確率の平均値以下の場合に、クラスｋに属するアイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングする。
【００４８】
まず、情報量最大化クラスタリング部４２は、初期クラスタリング部４０によって計算されたクラスタリング結果をクラスの初期値とする。そして、情報量最大化クラスタリング部４２は、特定ユーザがクラスｋを選択する確率を表すクラス確率の標準偏差が、予め定められた閾値以下になるまで、複数のアイテムｊを複数のクラスｋにクラスタリングすることを繰り返す。具体的には、情報量最大化クラスタリング部４２は、以下の（Ａ）〜（Ｄ）の処理を繰り返す。
【００４９】
（Ａ）情報量最大化クラスタリング部４２は、選択確率計算部３８によって計算された、クラスｋに属するアイテムｊの各々に対しての選択確率から、特定ユーザについての各クラスｋのクラス確率ｐｉｋを以下の式（７）に従って計算する。ｒｊｋは初期クラスタリングによって得られるクラス負担率、又は後述する（Ｃ）で前回更新されたクラス負担率を示す。また、情報量最大化クラスタリング部４２は、クラス確率の平均値を算出する。
【００５０】
【数４】
2016103107.tif 000006
【００５１】
（Ｂ）次に、情報量最大化クラスタリング部４２は、クラス確率が平均値より大きいクラスの標準偏差を小さく（ｍ倍）し、クラス確率が平均値以下のクラスの標準偏差を大きく（１／ｍ倍）する。なお、ｍは予め定められた１未満の定数である。
【００５２】
（Ｃ）次に、情報量最大化クラスタリング部４２は、ＥＭアルゴリズムのＭステップにおいて、上記式（２）に従って、複数のクラスｋの各々について、各アイテムｊに対し、アイテムｊのクラスｋの負担率ｒｊｋを更新する。
【００５３】
（Ｄ）次に、情報量最大化クラスタリング部４２は、ＥＭアルゴリズムのＭステップにおいて、上記式（３）、（４）、及び（６）に従って、複数のクラスｋの各々について、当該クラスｋの平均μｋ、及び混合係数πｋを更新する。
【００５４】
そして、情報量最大化クラスタリング部４２は、以下の式（８）に従って計算される、クラス確率の標準偏差ｓが、予め定められた閾値以下であるか否かを判定する。クラス確率の標準偏差ｓが、予め定められた閾値より大きい場合には、（Ａ）〜（Ｄ）の処理を繰り返す。一方、クラス確率の標準偏差ｓが、予め定められた閾値以下である場合には、クラスタリングの処理を終了する。
【００５５】
【数５】
2016103107.tif 000007
【００５６】
情報量最大化クラスタリング部４２によるクラスタリング処理によって、以下の式（９）の情報量が大きくなるように、各アイテムがクラスタリングされる。
【００５７】
【数６】
2016103107.tif 000008
【００５８】
最適粒度協調フィルタリング部４４は、情報量最大化クラスタリング部４２によって計算されたクラスタリング結果と、レート行列生成部３４によって生成されたレート行列とに基づいて、複数のユーザｉの各々が各クラスｋに属するアイテムを訪問する度合いを表すレートを要素にもつ第２レート行列を生成する。
そして、最適粒度協調フィルタリング部４４は、生成された第２レート行列に基づいて、第２レート行列のうち、選択肢提示要求を送信した特定ユーザについての０である要素のレートを推定し、第２レート行列を更新する。具体的には、最適粒度協調フィルタリング部４４は、情報量最大化クラスタリング部４２によって計算されたクラスタリング結果の各クラスを使って、図２（Ｃ）に示されるような第２レート行列を生成する。本実施の形態では、アイテムが場所に対応するため、レートは、クラスに属する各アイテムの訪問回数の合計となる。
また、最適粒度協調フィルタリング部４４は、協調フィルタリング部３６と同様に上記図２（Ｂ）に示されるように、生成された第２レート行列に対し協調フィルタリングを行い、第２レート行列を更新する。
【００５９】
また、最適粒度協調フィルタリング部４４は、協調フィルタリングによって更新された第２レート行列から、レート行列生成部３４によって受け付けた選択肢提示要求に含まれるユーザＩＤに対応する特定ユーザについて、当該特定ユーザの各クラスに対する第２レートの値が高い順に、クラスの各々を並び替え、並び替えられたクラスの各々を示す選択肢の一覧を、通信部３０により情報端末１２へ送信する。例えば、選択肢の数Ｍが５であって、クラスの数Ｋが１０である場合、最適粒度協調フィルタリング部４４は、特定ユーザの各クラスに対する第２レートの値が高い順に、クラスの各々を並び替え、並び替えられた上位５個のクラスの各々を示す選択肢の一覧を、通信部３０により情報端末１２へ送信する。
【００６０】
情報端末１２の通信部２２は、通信部３０により送信された選択肢の一覧を取得する。
【００６１】
情報端末１２の提示部２４は、通信部２２によって取得された選択肢の一覧を提示する。図３に提示部２４によって提示される選択肢の一覧の一例を示す。図３（Ａ）に示されるように、情報端末１２には、例えば「和食」「中華」「洋食」「遊ぶ・泊まる」「買う・見る」が各選択肢として提示される。図３（Ｂ）に示されるように、サーバ１４によって計算されたクラスタリング結果は、上記図３（Ａ）の選択肢として対応付けられる。そして、上記図３（Ａ）に示されるように、特定ユーザの興味の有りそうな箇所については細かくクラスタリングされ、特定ユーザの興味の無さそうな箇所は粗くクラスタリングされた結果が表示される。
なお、各クラスに対応する選択肢の名称は、例えば当該クラスに属する各アイテムのジャンル情報に基づいて決定される。また、各クラスに対応する選択肢の名称は、当該クラスに属する各アイテムの名称から決定してもよい。
【００６２】
＜情報提示システムの作用＞
次に、情報提示システム１０の作用について説明する。
【００６３】
まず、複数の情報端末１２が、逐次、ユーザＩＤ及びアイテムＩＤを、サーバ１４へ送信し、サーバ１４は、受信したユーザＩＤ及びアイテムＩＤを、行動履歴データベース３２に蓄積する。
【００６４】
また、情報端末１２が、ユーザＩＤを含む選択肢提示要求を、サーバ１４へ送信したときに、サーバ１４は図４に示すクラスタリング処理ルーチンを実行する。
【００６５】
まず、ステップＳ１００において、レート行列生成部３４によって、行動履歴データベース３２から、受信した選択肢提示要求に含まれるユーザＩＤに対応する行動履歴データを含む行動履歴データ集合を取得する。
【００６６】
次のステップＳ１０２において、レート行列生成部３４によって、上記ステップＳ１００で取得した行動履歴データ集合に基づいて、複数のユーザｉの各々が各アイテムｊを訪問する度合いを表すレートを要素にもつレート行列を生成する。
【００６７】
そして、ステップＳ１０４において、協調フィルタリング部３６によって、上記ステップＳ１０２で生成されたレート行列に基づいて、レート行列のうち、選択肢提示要求を送信した特定ユーザについての０である要素のレートを推定し、上記ステップＳ１０２で生成されたレート行列を更新する。
【００６８】
ステップＳ１０６において、選択確率計算部３８によって、上記ステップＳ１０４で更新されたレート行列に基づいて、選択肢提示要求を送信した特定ユーザが各アイテムｊを訪問する確率を表す選択確率を計算する。
【００６９】
そして、ステップＳ１０８において、初期クラスタリング部４０によって、複数のアイテムｊの各々について抽出された特徴量に基づいて、複数のアイテムｊを複数のクラスｋにクラスタリングする。ステップＳ１０８は、図５に示す初期クラスタリング処理ルーチンによって実現される。
【００７０】
＜初期クラスタリング処理ルーチン＞
まず、ステップＳ２００において、複数のアイテムｊの各々について抽出された特徴量を取得する。
【００７１】
ステップＳ２０２において、複数のクラスｋの各々について、当該クラスｋの平均μｋ、分散ｓｋ２、及び混合係数πｋを初期化する。
【００７２】
ステップＳ２０４において、ＥＭアルゴリズムのＥステップにおいて、上記ステップＳ２０２で初期化された各値、又は後述するステップＳ２０６で前回更新された各値に基づいて、上記式（２）に従って、複数のクラスｋの各々について、各アイテムｊに対し、アイテムｊのクラスｋの負担率ｒｊｋを更新する。
【００７３】
ステップＳ２０６において、ＥＭアルゴリズムのＭステップにおいて、上記ステップＳ２０４で更新された負担率ｒｊｋと、上記ステップＳ２０２で初期化された各値、又は本ステップＳ２０６で前回更新された各値に基づいて、上記式（３）〜（６）に従って、複数のクラスｋの各々について、当該クラスｋの平均μｋ、分散ｓｋ２、及び混合係数πｋを更新する。
【００７４】
ステップＳ２０８において、上記ステップＳ２０４及び上記ステップＳ２０６の更新処理が収束したか否かを判定する。更新処理が収束したと判定した場合には、ステップＳ２１０へ進む。一方、更新処理が収束したと判定した場合には、ステップＳ２０４へ戻る。
【００７５】
ステップＳ２１０において、上記ステップＳ２０４で更新されたクラスｋの各々についての各アイテムｊに対するクラスｋの負担率ｒｊｋと、上記ステップＳ２０６で更新された、クラスｋの各々についての、平均μｋ、分散ｓｋ２、及び混合係数πｋと、各クラスｋに属するアイテムｊの各々の情報とをクラスタリング結果として出力して、初期クラスタリング処理ルーチンを終了する。
【００７６】
次に、クラスタリング処理ルーチンに戻り、ステップＳ１１０において、情報量最大化クラスタリング部４２によって、上記ステップＳ１０８で計算されたクラスタリング結果に基づいて、複数のクラスｋの各々について、上記ステップＳ１０６で計算された、クラスｋに属するアイテムｊの各々に対しての選択確率から、特定ユーザがクラスｋを選択する確率を表すクラス確率を算出する。
【００７７】
そして、ステップＳ１１０において、情報量最大化クラスタリング部４２によって、複数のクラスｋの各々について、複数のアイテムｊの各々から抽出された特徴量に基づいて、クラスｋに対するクラス確率が平均値より大きい場合に、クラスｋに属するアイテムの各々の特徴量の標準偏差を小さくし、クラスｋに対するクラス確率が平均値以下である場合に、クラスｋに属するアイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングする。ステップＳ１１０は、図６に示す情報量最大化クラスタリング処理ルーチンによって実現される。
【００７８】
＜情報量最大化クラスタリング処理ルーチン＞
まず、ステップＳ３００において、上記ステップＳ１０８で計算されたクラスタリング結果を取得する。
【００７９】
ステップＳ３０２において、上記ステップＳ３００で取得されたクラスタリング結果を、各クラスｋの初期値として設定する。
【００８０】
ステップＳ３０４において、選択確率計算部３８によって計算された、クラスｋに属するアイテムｊの各々に対しての選択確率に基づいて、特定ユーザについてのクラス確率ｐｉｋを上記式（７）に従って計算する。また、情報量最大化クラスタリング部４２によって、クラス確率の平均値を算出する。
【００８１】
ステップＳ３０６において、各クラスｋについて、上記ステップＳ３０４で計算されたクラス確率ｐｉｋと平均値とに基づいて、クラス確率が平均値より大きいクラスの標準偏差ｓｋを小さく（ｍ倍）する。
【００８２】
ステップＳ３０８において、各クラスｋについて、上記ステップＳ３０４で計算されたクラス確率ｐｉｋと平均値とに基づいて、クラス確率が平均値以下のクラスの標準偏差ｓｋを大きく（１／ｍ倍）する。
【００８３】
ステップＳ３１０において、ＥＭアルゴリズムのＭステップにおいて、上記ステップＳ３０６及びＳ３０８で更新された各クラスｋの標準偏差ｓｋと、上記ステップＳ３０２で設定された初期値又は後述するステップＳ３１２で前回更新された各値とに基づいて、複数のクラスｋの各々について、各アイテムｊに対し、アイテムｊのクラスｋの負担率ｒｊｋを更新する。
【００８４】
ステップＳ３１２において、ＥＭアルゴリズムのＭステップにおいて、上記ステップＳ３１０で更新されたクラスｋの負担率ｒｊｋと、上記ステップＳ３０６及びＳ３０８で更新された各クラスｋの標準偏差ｓｋと、上記ステップＳ３０２で設定された初期値又は本ステップＳ３１２で前回更新された各値とに基づいて、上記式（３）、（４）、及び（６）に従って、複数のクラスｋの各々について、当該クラスｋの平均μｋ、及び混合係数πｋを更新する。
【００８５】
ステップＳ３１４において、上記式（８）に従って計算される、クラス確率の標準偏差ｓが、予め定められた閾値以下であるか否かを判定する。クラス確率の標準偏差ｓが予め定められた閾値より大きい場合には、ステップＳ３０４へ戻る。一方、クラス確率の標準偏差ｓが予め定められた閾値以下である場合には、ステップＳ３１６へ進む。
【００８６】
ステップＳ３１６において、上記ステップＳ３１０で更新されたクラスｋの各々についての各アイテムｊに対するクラスｋの負担率ｒｊｋと、上記ステップＳ３１２で更新された、クラスｋの各々についての、平均μｋ及び混合係数πｋと、各クラスｋに属するアイテムｊの各々の情報とをクラスタリング結果として出力して、情報量最大化クラスタリング処理ルーチンを終了する。
【００８７】
次に、クラスタリング処理ルーチンに戻り、最適粒度協調フィルタリング部４４によって、ステップＳ１１２において、上記ステップＳ１１０で出力されたクラスタリング結果と、上記ステップＳ１０２で生成されたレート行列とに基づいて、複数のユーザｉの各々が各クラスｋに属するアイテムを訪問する度合いを表すレートを要素にもつ第２レート行列を生成する。
【００８８】
ステップＳ１１４において、最適粒度協調フィルタリング部４４によって、上記ステップＳ１１２で生成された第２レート行列に基づいて、第２レート行列のうち、選択肢提示要求を送信した特定ユーザについての０である要素のレートを推定し、第２レート行列を更新する。
【００８９】
ステップＳ１１６において、最適粒度協調フィルタリング部４４によって、上記ステップＳ１１４で更新された第２レート行列から、上記で受け付けた選択肢提示要求に含まれるユーザＩＤに対応する特定ユーザについて、当該特定ユーザの各クラスに対する第２レートの値が大きい順に、クラスの各々を並び替え、並び替えられたクラスの各々を示す選択肢の一覧を結果として出力する。
【００９０】
そして、ステップＳ１１８において、通信部３０によって、上記ステップＳ１１６で出力された選択肢の一覧を情報端末１２へ送信する。
【００９１】
情報端末１２の通信部２２は、サーバ１４より送信された選択肢の一覧を受け付け、提示部２４へ出力する。そして、提示部２４は、通信部２２により出力された選択肢の一覧を提示する。
【００９２】
図７に、情報端末１２の提示部２４によって提示される選択肢の階層を説明するための図を示す。図７（Ａ）に示されるように、情報端末１２の提示部２４によって提示される選択肢の一覧は、ユーザの興味の無さそうな箇所は粗く表示され、ユーザの興味の有りそうな箇所は細かく表示される。また、図７（Ａ）に示されるように、選択肢は階層構造となっている。例えば、ユーザが選択肢「和食」を選択すると、「和食」に属する選択肢の一覧が更に表示される。
【００９３】
上記図７（Ａ）に示されるような階層構造を実現するために、ユーザが選択肢を選択すると、情報端末１２は、選択された選択肢の情報をサーバ１４へ送信し、サーバ１４が情報端末１２によって送信された選択肢の情報を受信すると、上記クラスタリング処理ルーチンが実行される。そして、サーバ１４によって、図７（Ｂ）に示されるように、ユーザによって選択された選択肢に対応するクラスに属するアイテムの集合に対して更にクラスタリングが行われ、再度、サーバ１４が、クラスタリングの結果に応じた選択肢の一覧を情報端末１２へ送信し、一段下層の選択肢の一覧が提示部２４によって提示される。なお、ユーザが選択肢を選択する毎に、情報端末１２は当該選択肢の情報をサーバ１４へ送信し、サーバ１４によってクラスタリング処理ルーチンが実行される。
【００９４】
以上説明したように、本発明の実施の形態に係る情報提示システムによれば、特定ユーザの行動履歴データに基づいて、特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算し、複数のアイテムｊを複数のクラスｋにクラスタリングしたクラスタリング結果に基づいて、複数のクラスｋの各々について、特定ユーザがクラスｋを選択する確率を表すクラス確率を算出し、複数のアイテムｊの各々から抽出された特徴量に基づいて、クラスｋに対するクラス確率が大きいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を小さくし、クラスｋに対するクラス確率が小さいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングすることにより、ユーザの行動履歴に応じた適切な選択肢を提示することができる。
【００９５】
また、複数のアイテムｊの各々から抽出された特徴量に基づいて、クラスｋに対するクラス確率が大きいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を小さくし、クラスｋに対するクラス確率が小さいほど、クラスｋに属するアイテムの各々の特徴量の標準偏差を大きくするように、複数のアイテムｊを複数のクラスｋにクラスタリングすることにより、情報量が大きくなるように、複数のアイテムをクラスタリングすることができる。
【００９６】
また、ユーザの行動から得られる情報量を最大化するように、ユーザの興味のある部分は細かく、興味のない部分は粗くなるよう選択肢を設計可能であるため、情報端末に対する最小の操作回数で、ユーザの希望するアイテムを特定することができる。
【００９７】
なお、上記実施の形態では、情報端末を車両等の移動体に搭載した形態を想定しているが、歩行者が情報端末を携帯している形態としてもよい。
【００９８】
また、上記実施の形態では、アイテムが場所を表し、所定の行動は当該場所への訪問である場合を例に説明したがこれに限定されるものではない。例えば、図８に示されるように、アイテムが商品であって、所定の行動が評価であっても良い。図８では、サムアップのマークが良評価を表し、サムダウンのマークが悪評価を表す。
【００９９】
また、アイテムが商品であって、所定の行動が商品の閲覧又は購入であっても良い。例えば、商品の一例として映画が挙げられ、商品が映画である場合の特徴量としては、当該映画の撮影年度、監督、ジャンル情報等を特徴量として用いることができる。
【０１００】
また、アイテムが場所であって、所定の行動が場所の評価であってもよい。
【０１０１】
また、上記実施の形態では、レート行列生成部３４が、複数のユーザｉの各々が各アイテムｊに対して所定の行動をとった行動履歴データに基づいて、複数のユーザｉの各々が各アイテムｊに対して所定の行動をとった度合いを表すレートを要素にもつレート行列を生成し、協調フィルタリング部３６が、生成されたレート行列に基づいて、レート行列のうち、特定ユーザについての０である要素のレートを推定し、生成されたレート行列を更新する場合を例に説明したがこれに限定されるものではない。例えば、レート行列を生成せずに、特定ユーザが各アイテムｊに対して所定の行動をとった行動履歴データに基づいて、特定ユーザが各アイテムｊに対して所定の行動をとる確率を表す選択確率を計算するようにしてもよい。
【０１０２】
また、上記実施の形態では、選択肢の一覧が階層構造である場合に、ユーザが選択肢を選択する毎に、情報端末１２は当該選択肢の情報をサーバ１４へ送信し、サーバ１４によってクラスタリング処理ルーチンが実行される場合を例に説明したがこれに限定されるものではない。例えば、選択肢の一覧が階層構造である場合には、階層毎のクラスタリングをサーバ１４によって予め実行しておき、情報端末１２はサーバ１４によって実行されたクラスタリング結果に基づく選択肢の階層構造を予め取得し、ユーザによって選択肢が選択される毎に、下層の選択肢を提示してもよい。
【０１０３】
また、サーバ１４によるクラスタリング結果を用いて、ユーザに選択肢を提示する場合を例に説明したが、これに限定されるものではなく、クラスタリング結果を用いて、選択肢を提示する以外の処理を行ってもよい。
【０１０４】
また、クラスタリング処理を実行する装置が、サーバ１４として実装される場合を例に説明したが、これに限定されるものではなく、情報端末上に、クラスタリング処理を実行する装置が実装されるようにしてもよい。
【符号の説明】
【０１０５】
１０   情報提示システム
１２   情報端末
１４   サーバ
１６   ネットワーク
２０   入力部
２２，３０  通信部
２４   提示部
３２   行動履歴データベース
３４   レート行列生成部
３６   協調フィルタリング部
３８   選択確率計算部
４０   初期クラスタリング部
４２   情報量最大化クラスタリング部
４４   最適粒度協調フィルタリング部
【図１】
2016103107.tif 000009
【図４】
2016103107.tif 000010
【図５】
2016103107.tif 000011
【図６】
2016103107.tif 000012
【図２】
2016103107.tif 000013
【図３】
2016103107.tif 000014
【図７】
2016103107.tif 000015
【図８】
2016103107.tif 000016