双方向クラスタ分割装置、方法、及び、プログラム
【課題】多変量データと多変量データに対応したシーケンスデータとを、各変量間、及び、シーケンスデータ間で共通の特徴をもつクラスタに同時に分割することができる双方向クラスタ分割装置を提供する。
【解決手段】入力手段１１は、多変量データと多変量データに対応したシーケンスデータとを入力する。双方向クラスタリング手段１２は、多変量データとシーケンスデータとに対して双方向クラスタリングを行う。双方向クラスタリング手段１２は、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて、多変量データとシーケンスデータとを、複数のクラスタに分割する。
【解決手段】入力手段１１は、多変量データと多変量データに対応したシーケンスデータとを入力する。双方向クラスタリング手段１２は、多変量データとシーケンスデータとに対して双方向クラスタリングを行う。双方向クラスタリング手段１２は、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて、多変量データとシーケンスデータとを、複数のクラスタに分割する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、双方向クラスタ分割装置、方法、及び、プログラムに関し、更に詳しくは、多変量データの集合を、データ間で共通の特徴を持つクラスタに分割する双方向クラスタ分割装置、方法、及び、プログラムに関する。
【背景技術】
【０００２】
クラスタリング技術は、データの集合を、共通の特徴を持つクラスタに分割する技術である。多変量データは、あるデータ点が複数の変量から成るデータである。多変量データを変量ごとにクラスタリングする技術は、一方向のクラスタリングと呼ばれている。これに対し、複数の変量を同時にクラスタリングする技術は、双方向クラスタリング（Co-clustering）と呼ばれる。非特許文献１及び２は、双方向クラスタリングが記載された文献である。
【０００３】
双方向クラスタリングは、特に、自然言語処理の技術として開発されている。自然言語処理の分野では、双方向クラスタリングを、文章と単語とを同時にクラスタリングする際に使用している。双方向クラスタリングでは、文章と単語という多変量データを、文章と単語との共起情報を基に、文章と単語との各部分集合が共起関係になるクラスタにクラスタ分割を行う。
【０００４】
自然言語処理の分野で、双方向クラスタリングを用いずに文章と単語とをクラスタリングする場合には、文章と単語とを別々にクラスタリングする必要がある。文章のクラスタリングでは、各文章に含まれる単語の頻度を特徴として利用し、その特徴が同じ文章が同一クラスタに属するように、クラスタ分割を行う。単語のクラスタリングでは、各単語がどの文章に含まれているかを特徴として利用し、その特徴が同じ単語が同一クラスタに含まれるように、クラスタ分割を行う。
【０００５】
自然言語処理に一方向のクラスタリングを用いる場合、上記のように、文章は単語の特徴を用いてクラスタリングし、単語は文章の特徴を用いてクラスタリングする。このため、クラスタリング処理が冗長になる。また、文書でクラスタリングした結果と、単語でクラスタリングした結果とを組み合わせることで、文書と単語の双方のクラスタリングが実現できる。しかし、一方向のクラスタリングでは、文章と単語とを別々にクラスタリングするために、文章と単語との相関や、共起関係を適切にクラスタに組み込むことが困難である。これに対し、双方向のクラスタリングでは、文書と単語との相関や、共起関係をクラスタに組み込むことができる。
【０００６】
特許文献１は、顧客ごとの商品の購買履歴データから、クラスタを抽出する購買情報処理装置が記載された文献である。特許文献１の購買情報処理装置は、購買情報生成手段と、購買情報処理手段とから成る。購買情報生成手段は、購買履歴データにある顧客と商品とをそれぞれ、行及び列の一方の項目として当てはめる。購買情報生成手段は、顧客が購入した履歴がある商品の行列要素と、購入した履歴がない商品の行列要素とに、互いに異なる所定の指標値（０又は１）を付与して、行列テーブルを生成する。
【０００７】
購買情報処理手段は、行列テーブルについて、行ごとの指標値の総和に基づいて行を並び替えると共に、列ごとの指標値の総和に基づいて列を並び替える。購買情報処理手段は、指標値の総和を、昇順又は降順に並び変える。購買情報処理手段は、並び変え後、行列テーブル上の指標値の分布にて規定されるクラスタを抽出する。特許文献１では、このようなクラスタリングを行うことで、顧客情報のクラスタ抽出に要する計算量及び処理時間の低減が可能である。
【０００８】
特許文献２は、時系列データをクラスタリングする時系列データ処理装置が記載された文献である。時系列データは、処理日時などの時間情報、顧客特定情報、及び、商品特定情報を最低限含む。時系列データ処理装置は、時系列データを対象として、商品をその購買顧客が類似する複数のグループにクラスタリングする。時系列データ処理装置は、クラスタ内の任意の２つの商品（商品Ａ、Ｂ）に対して、２つの商品が同時に購入されている事例数、Ａが購入された後にＢが購入された事例数、Ｂが購入された後にＡが購入された事例数をカウントする。時系列データ処理装置は、カウンタした事例数から、２つの商品の順序関係を決定する。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００３−２４８７５０号公報
【特許文献２】特開平９−３０５５７１号公報
【非特許文献】
【００１０】
【非特許文献１】A Generalized Maximum Entropy Approach to Bregman Co-clustering and Matrix Approximation,A.Banerjee and I.Dhillon and J.Ghosh and S.Merugu and D.S.Modha,KDD2004
【非特許文献２】Fully Automatic Cross-associations,Deepayan Chakrabarti and Spiros Papadimitriou and Dharmendra S.Modha and Christos Faloutsos,KDD2004
【非特許文献３】Probabilistic Model-Based Clustering of Multivariate and Sequential Data,Padhraic Smyth,In Proceedings of Artificial Intelligence and Statistics,1999
【発明の概要】
【発明が解決しようとする課題】
【００１１】
情報化社会が進み、蓄積されたデータも膨大な量になっている。例えば、小売業では、ＰＯＳ（Point of Sales）データと呼ばれる多変量データが大量に蓄積されている。ＰＯＳデータは、どの顧客が、いつ、どこで、何を購入したかという情報を含む。蓄積されるデータは多変量データだけではなく、各データ点に順序情報が与えられたシーケンスデータも膨大に蓄積されている。シーケンスデータは、データ点に対応したデータであり、多変量データの２以上のキー（属性）に関連する情報が時系列に並んだデータである。多変量データのデータ点に対応してシーケンスデータがある場合、シーケンスデータも考慮した上で、クラスタリングを行うことが好ましいと考えられる。
【００１２】
しかし、非特許文献１及び２は、多変量データに対して双方向クラスタリングを行うのみであり、多変量データとシーケンスデータとを同時にクラスタリングすることはできない。特許文献１も、同様に、多変量データに対して双方向クラスタリングを行うのみで、シーケンスデータを考慮して双方向クラスタリングを行うことができない。また、特許文献２は、クラスタリング後に、同じクラスタに属する２つの商品について、時系列データから、どちらの商品が先に購入されたか、又は、同時に購入されたかを求めているに過ぎず、シーケンスデータを考慮したクラスタリングは行っていない。
【００１３】
ここで、非特許文献３には、多変量データとシーケンスデータとをクラスタに分割する技術が記載されている。しかし、非特許文献３におけるクラスタリングは、一方向クラスタリングである。従って、非特許文献３では、多変量データとシーケンスデータとを同時に双方向クラスタリングすることはできない。
【００１４】
本発明は、多変量データと多変量データに対応したシーケンスデータとを、各変量間、及び、シーケンスデータ間で共通の特徴をもつクラスタに同時に分割可能な双方向クラスタ分割装置、方法、及び、プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記目的を達成するために、本発明は、多変量データと多変量データに対応したシーケンスデータとを入力する入力手段と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割する双方向クラスタリング手段とを備える双方向クラスタ分割装置を提供する。
【００１６】
本発明は、多変量データと多変量データに対応したシーケンスデータとを入力するステップと、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割するステップとを有する双方向クラスタ分割方法を提供する。
【００１７】
本発明は、コンピュータに、多変量データと多変量データに対応したシーケンスデータとを入力する処理と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割する処理とを実行させるプログラムを提供する。
【００１８】
本発明は、ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付手段と、ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信手段と、前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成手段と、前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、前記双方向クラスタリング結果に基づいて、前記コンテンツ配信手段がコンテンツに付加すべき広告を決定する広告選択手段とを備える広告配信システムを提供する。
【００１９】
本発明は、ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付ステップと、ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信ステップと、前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成ステップと、前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、前記双方向クラスタリング結果に基づいて、前記コンテンツに付加すべき広告を決定する広告選択ステップとを有する広告配信方法を提供する。
【００２０】
本発明は、コンピュータに、ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付処理と、ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信処理と、前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成処理と、前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、前記双方向クラスタリング結果に基づいて、前記コンテンツに付加すべき広告を決定する広告選択処理とを実行させるプログラムを提供する。
【００２１】
本発明は、顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成手段と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成手段とを備える商品推薦システムを提供する。
【００２２】
本発明は、顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成ステップと、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成ステップとを有する商品推薦方法を提供する。
【００２３】
本発明は、コンピュータに、顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成処理と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成処理とを実行させるプログラムを提供する。
【００２４】
本発明は、車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成手段と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成手段とを備える故障予測システムを提供する。
【００２５】
本発明は、車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成ステップと、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成ステップとを有する故障予測方法を提供する。
【００２６】
本発明は、コンピュータに、車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成処理と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成処理とを実行させるプログラムを提供する。
【発明の効果】
【００２７】
本発明の双方向クラスタ分割装置、方法、及び、プログラムは、多変量データと多変量データに対応したシーケンスデータとを、各変量間、及び、シーケンスデータ間で共通の特徴をもつクラスタに同時に分割することができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の第１実施形態に係る双方向クラスタ分割装置を示すブロック図。
【図２】双方向クラスタ分割装置の動作手順を示すフローチャート。
【図３】入力データの一例を示す図。
【図４】入力データをテーブル形式（行列形式）で示す図。
【図５】初期クラスタリングの結果を示す図。
【図６】最終的に得られたクラスタリング結果を示す図。
【図７】（ａ）は、多変量データを示し、（ｂ）は、クラスタリング結果を示す図。
【図８】（ａ）は、シーケンスデータが付加された多変量データを示し、（ｂ）は、クラスタリング結果を示す図。
【図９】本発明の第２実施形態に係る広告配信システムを示すブロック図。
【図１０】ユーザ端末を示すブロック図。
【図１１】Ｗｅｂサーバを示すブロック図。
【図１２】双方向クラスタリング処理の手順を示すフローチャート。
【図１３】双方向クラスタリング手段の入力データを示す図。
【図１４】入力データをテーブル形式（行列形式）で示す図。
【図１５】双方向クラスタリング手段のクラスタリング結果を示す図。
【図１６】広告配信処理の手順を示すフローチャート。
【図１７】広告配信候補を示す図。
【図１８】Ｗｅｂ広告が付加されたＷｅｂページを示す図。
【図１９】本発明の第３実施形態に係る商品推薦システムを示す図。
【図２０】商品推薦の動作手順を示すフローチャート。
【図２１】双方向クラスタリング手段の入力データを示す図。
【図２２】双方向クラスタリング結果を示す図。
【図２３】推薦商品リストを示す図。
【図２４】本発明の第４実施形態に係る故障予測システムを示すブロック図。
【図２５】故障予測の動作手順を示すフローチャート。
【図２６】双方向クラスタリング手段の入力データを示す図。
【図２７】双方向クラスタリング結果を示す図。
【図２８】故障予測候補リストを示す図。
【図２９】本発明の双方向クラスタ分割装置の概略を示すブロック図。
【発明を実施するための形態】
【００２９】
以下、図面を参照し、本発明の実施の形態について詳細に説明する。図１は、本発明の第１実施形態に係る双方向クラスタ分割装置を示している。双方向クラスタ分割装置１００は、入力手段１０１、双方向クラスタリング手段１０２、クラスタ数算出手段１０３、及び、出力手段１０４を備える。双方向クラスタ分割装置１００内の各手段の機能は、コンピュータが所定のプログラムを読み込んで実行することで実現可能である。
【００３０】
入力手段１０１は、多変量データとシーケンスデータとを入力する。多変量データは、２以上の属性を変量とするデータである。シーケンスデータは、多変量データに対応したデータであり、多変量データの２以上のキー（属性）に関連する情報が時系列に並んだデータである。多変量データは、例えば、顧客と商品とを変量とし、顧客が商品を購入したか否かを示すデータとする。シーケンスデータは、例えば、顧客がある商品を購入したというデータ点に対応して、顧客がこれまでにその商品を購入したということに関する履歴を時系列で並べた履歴データとする。
【００３１】
双方向クラスタリング手段１０２は、入力データに対し双方向クラスタリングを行う。双方向クラスタリング手段１０２は、評価関数を用いて、多変量データを複数のクラスタに分割する。評価関数は、多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで、共通した特徴が多いか少ないかを表す関数である。双方向クラスタリング手段１０２は、例えば、評価関数が共通した特徴が多くなるほど値が小さくなる関数であるとすれば、クラスタごとに計算した評価関数の値の総和が小さくなるように、クラスタ分割を行う。出力手段１０４は、双方向クラスタリング結果を出力する。
【００３２】
クラスタ数算出手段１０３は、双方向クラスタリングにおけるクラスタ分割数を決定する。クラスタ数算出手段１０３は、初回のクラスタリングでは、クラスタ分割数として所定の初期値を出力する。双方向クラスタリング手段１０２は、初回のクラスタリングでは、入力データを、所定の初期値の数のクラスタに分割する。クラスタ数算出手段１０３は、双方向クラスタリング手段１０２がクラスタリングを行うと、評価関数の値に基づいて、クラスタ分割数を増加させるか否かを決定する。双方向クラスタリング手段１０２は、クラスタ数算出手段１０３がクラスタ分割数を増加させると、そのクラスタ分割数でクラスタ分割を再度行う。
【００３３】
図２は、動作手順を示している。入力手段１０１は、多変量データとシーケンスデータとを入力する（ステップＡ１）。図３は、入力データの一例を示している。この例では、多変量データは、誰がどの商品を買ったかを表すデータである。多変量データの変量は、「顧客」と、「商品」との２つである。多変量データの各データに対して、商品購入の曜日履歴のデータ（シーケンスデータ）が付加されている。シーケンスデータは、ｙｉｋで表現する。シーケンスデータｙｊｋは、顧客ｊが、過去に商品ｋを購入した曜日を時系列で並べたデータである。
【００３４】
なお、顧客が商品を購入したという情報は、所定の期間ごとに求めることができる。所定の期間は、例えば一月単位とする。図３では、顧客Ｂが商品２を購入したというデータが２つあるが、これは、顧客Ｂが商品２を購入した期間が異なるためである。例えば、２つの購入データのうちの一方は、顧客Ｂが商品２を先月購入したというデータに対応し、他方は、顧客Ｂが商品２を先々月購入したというデータに対応している。また、シーケンスデータｙ１２Ｂは、顧客Ｂが商品２を購入した先々月の購入曜日履歴を表し、ｙ２２Ｂは、顧客Ｂが商品２を購入した先々月の購入曜日履歴を表している。
【００３５】
図４は、入力データをテーブル形式（行列形式）で示している。図３に示す入力データを、行列で表すと、図４に示すようになる。入力データの行列を、Ｄで表す。行列Ｄの行は顧客を表し、列は商品を表す。行列Ｄの各要素は、０又は１の値を取る。０は商品を購入していないことを表し、１は商品を購入したことを表す。シーケンスデータは、顧客が商品を購入したことを表すデータ点に付加される。シーケンスデータは、１つのデータ点に対して１つとは限らず、１つのデータ点に複数のシーケンスデータが対応することもあり得る。
【００３６】
双方向クラスタリング手段１０２は、クラスタ数算出手段１０３から、多変量データの各変量について、クラスタ分割数を受け取る。双方向クラスタリング手段１０２は、例えば、変量が２つであるとき、クラスタ数算出手段１０３から、各変量のクラスタ分割数ｋ、ｌを受け取る。双方向クラスタリング手段１０２は、シーケンスデータを考慮しつつ、多変量データを双方向クラスタリングする（ステップＡ２）。双方向クラスタリング手段１０２は、多変量データをｋ×ｌのクラスタに分割する。双方向クラスタリング手段１０２は、例えば、クラスタ分割数の初期値として、ｋ＝２、ｌ＝２を受け取り、多変量データを４つのクラスタに分割する。
【００３７】
双方向クラスタリング手段１０２は、評価関数を用いてクラスタリングを行う。評価関数には、各クラスタに属するデータが共通した特徴を持っていない度合いを計算する関数を用いる。入力データを双方向クラスタリングしたとき、各クラスタに属するデータが共通した特徴を持つほど、評価関数の値は小さくなる。逆に、各クラスタに属するデータが共通した特徴を持たないほど、評価関数の値は大きくなる。双方向クラスタリング手段１０２は、評価関数を小さくするようなクラスタ分割を行う。
【００３８】
シーケンスデータを考慮した双方向クラスタリングで用いる評価関数について説明する。分割されたクラスタを、Ｄｉｊ（ｉ＝１〜ｋ、ｊ＝１〜ｋ）で表す。クラスタリングのコストは、下記式１で定義する。
【数１】
式１にて、Ｃ（Ｄｉｊ）は、評価関数を用いて計算されるクラスタＤｉｊのコストを表す。コストＴは、各クラスタＤｉｊのコストの総和である。
【００３９】
コストには、ＭＤＬ（Minimum Description Length）という基準を用いる。各クラスタのコストＣ（Ｄｉｊ）は、下記式２で定義する。
【数２】
ここで、ｕは、多変量データが取る値である。図４の例では、ｕは、０又は１を取る。ｎｕは、クラスタＤｉｊに属するｕの値の個数を表す。ｎ（Ｄｉｊ）は、クラスタに属するデータ点の数である。すなわち、
である。なお、式２において、ｎｕ（Ｄｉｊ）＝０のときは、
【数３】
と定義する。
【００４０】
式２で定義される関数が、評価関数に該当する。式２において、第１項は、クラスタＤｉｊに含まれる多変量データの類似度が高いほど値が小さくなり、第２項（コストＤＬ（ｙ（Ｄｉｊ）））は、クラスタＤｉｊに含まれるシーケンスデータの類似度合が高いほど値が小さくなる。コストＤＬ（ｙ（Ｄｉｊ））は、下記式３で定義する。
【数４】
ここで、｜Ｄｉｊ｜は、クラスタＤｉｊに属するシーケンスデータの総数を表す。ｍは、ｌｏｇの底である。＾θは、ｙ（Ｄｉｊ）をモデルで表すときのパラメータである。モデルには、シーケンスデータをモデル化する方法として広く利用されているＨＭＭ（Hidden Markov Model）やMarkov Model等の確率モデルを用いることができる。Ｒは、＾θに含まれるパラメータの数を表す。
【００４１】
コストＣ（Ｄｉｊ）は、クラスタＤｉｊに含まれる多変量データとシーケンスデータとの共通した特徴が多いか少ないかを表す。コストＣ（Ｄｉｊ）の値が小さいほど、共通した特徴が多く、値が大きいほど、共通した特徴が少ない。なお、クラスタＤｉｊの属する多変量データが全て同じ値のときは、式２における第１項の値は０となる。その場合、コストＣ（Ｄｉｊ）は、ＤＬ（ｙ（Ｄｉｊ））のみで決まる。例えば、図４で、ｕ＝１のデータ点のみで構成されるクラスタのコストは、クラスタに属するデータ点のシーケンスデータの類似度に応じた値のみで決まる。なお、ｕ＝０のデータ点のみで構成されるクラスタのコストは、シーケンスデータがないことから０となる。
【００４２】
クラスタ数算出手段１０３は、双方向クラスタリング手段１０２がクラスタ分割を行うと、クラスタ分割結果と評価関数とを用いて、クラスタ数を増加するか否かを決定する（ステップＡ３）。クラスタ数算出手段１０３は、例えば、式１で定義されるコストＴの値が所定のしきい値を上回るか否かを判断する。クラスタ数算出手段１０３は、コストＴの値がしきい値を上回るときは、クラスタ数を増加すると決定する。
【００４３】
クラスタ数算出手段１０３にて、クラスタ数を増加させるか否かの判断手法は、特に上記したものには限定されない。例えば、以下のように判断してもよい。クラスタＤｉｊに属する多変量データとシーケンスデータとのから、どれか１つのデータ点を取り除く。データ点を１つ取り除いたクラスタをＤ’ｉｊとする。クラスタ数算出手段１０３は、データ点を取り除く前後のコスト、Ｃ（Ｄｉｊ）とＣ（Ｄ’ｉｊ）を計算し、両者を比較する。クラスタ数算出手段１０３は、Ｃ（Ｄｉｊ）＞Ｃ（Ｄ’ｉｊ）となるデータ点が存在する場合は、クラスタ数を増加すると決定する。
【００４４】
クラスタ数算出手段１０３は、クラスタ数を増加させると決定すると、双方向クラスタリング手段１０２に、増加後のクラスタ数を通知する。クラスタ数算出手段１０３は、例えば、現在のクラスタ数をｋ、ｌとして、ｋ＋１とｌ、ｋとｌ＋１、又は、ｋ＋１とｌ＋１を、新たなクラスタ数として双方向クラスタリング手段１０２に通知する。その後、ステップＡ３からステップＡ２へ戻り、双方向クラスタリング手段１０２は、入力データを、通知されたクラスタ数にクラスタ分割する。ステップＡ２とステップＡ３とを繰り返し行うことで、適切な分割数のクラスタを得ることができる。
【００４５】
出力手段１０４は、ステップＡ３で、クラスタ数算出手段１０３がクラスタ数を増加させないと決定すると、双方向クラスタリング手段１０２が行った双方クラスタリングの結果を出力する（ステップＡ４）。出力手段１０４は、例えば、クラスタ分割で得られた各クラスタＤｉｊについて、各クラスタに属するデータ点の情報を、ディスプレイ等の出力装置に表示する。
【００４６】
図５は、初期クラスタリングの結果を示している。双方向クラスタリング手段１０２が、入力データ（図４）を初期クラスタ数（ｋ＝２、ｌ＝２）のクラスタに分割することで、図５に示す４つのクラスタＤ１１、Ｄ１２、Ｄ２１、Ｄ２２が得られる。各クラスタについて、コストを計算すると、
Ｃ（Ｄ１１）＝４ｌｏｇ（６／４）＋２ｌｏｇ（６／２）＋ＤＬ（ｙ１１Ａ、ｙ１２Ｂ、ｙ２２Ｂ）＝１．６６＋ＤＬ（ｙ１１Ａ、ｙ１２Ｂ、ｙ２２Ｂ）
Ｃ（Ｄ１２）＝５２ｌｏｇ（５４／５２）＋２ｌｏｇ（５４／２）＋ＤＬ（ｙ１５Ａ、ｙ１２８Ｂ）＝３．７２＋ＤＬ（ｙ１５Ａ、ｙ１２８Ｂ）
Ｃ（Ｄ２１）＝７ｌｏｇ（９／７）＋２ｌｏｇ（９／２）＋ＤＬ（ｙ１１Ｄ、ｙ１２Ｅ）＝２．０７＋ＤＬ（ｙ１１Ｄ、ｙ１２Ｅ）
Ｃ（Ｄ２２）＝７８ｌｏｇ（８１／７８）＋３ｌｏｇ（８１／３）＋ＤＬ（ｙ１５Ｄ、ｙ２２８Ｅ、ｙ１３０Ｃ）＝５．５７＋ＤＬ（ｙ１５Ｄ、ｙ２２８Ｅ、ｙ１３０Ｃ）
となる。全体のコストＴは、
Ｔ＝Ｃ（Ｄ１１）＋Ｃ（Ｄ１２）＋Ｃ（Ｄ２１）＋Ｃ（Ｄ２２）
＝１３．０２＋ＤＬ（ｙ１１Ａ、ｙ１２Ｂ、ｙ２２Ｂ）＋ＤＬ（ｙ１５Ａ、ｙ１２８Ｂ）＋ＤＬ（ｙ１１Ｄ、ｙ１２Ｅ）＋ＤＬ（ｙ１５Ｄ、ｙ２２８Ｅ、ｙ１３０Ｃ）
となる。
【００４７】
図６は、最終的に得られたクラスタリング結果を示している。ステップＡ２、Ａ３を繰り返し行うことで、「顧客」方向のクラスタ分割数は２に、「商品」方向のクラスタ分割数は３になり、最終的に、図６に示す６個のクラスタＤ１１〜Ｄ１３、Ｄ２１〜Ｄ２３が得られたとする。図６に示すＤ１１〜Ｄ１３、Ｄ２１〜Ｄ２３について、各クラスタのコストを計算すると、
Ｃ（Ｄ１１）＝１ｌｏｇ（４／１）＋３ｌｏｇ（４／３）＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ）＝０．９７７＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ）
Ｃ（Ｄ１２）＝０
Ｃ（Ｄ１３）＝０
Ｃ（Ｄ２１）＝０
Ｃ（Ｄ２２）＝３ｌｏｇ（９／３）＋６ｌｏｇ（９／６）＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）＝２．４８＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）
Ｃ（Ｄ２３）＝０
となる。全体のコストＴは、
Ｔ＝ΣＣ（Ｄｉｊ）＝３．４６＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ）＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）
となる。
【００４８】
図５に示すクラスタリング結果におけるコストＴと、図６に示すクラスタリング結果におけるコストＴとを比較すると、ＤＬの値（シーケンスデータの類似度）を除いて、評価関数の値が下がっていることが確認できる。すなわち、評価関数に基づいて双方向クラスタリングを行うことで、多変量データと多変量データに対応したシーケンスデータを、各変量間及びシーケンスデータ間で共通の特徴を持つクラスタに分割できる。なお、コストＴは、上記したものには限定されず、双方向クラスタリングに必要な他のコストを含んでいてもよい。
【００４９】
比較例として、シーケンスデータを考慮しない双方向クラスタリングを考える。多変量データとして、２変量データを考える。変量の１つは顧客で、もう１つは商品とする。図７（ａ）に、多変量データを示す。顧客は、Ａ、Ｂ、Ｃの値を取り、商品は１、２、３の値を取る。多変量データの値は、顧客が商品を購入したか否かを表す。例えば、顧客Ａが商品１を購入したとき、顧客Ａと商品１とに対応するデータ点の値は１となる。
【００５０】
図７（ａ）に示す多変量データに対して、顧客及び商品の双方向でクラスタリングを行うと、図７（ｂ）のクラスタリング結果が得られる。この場合、クラスタ分割数は４である。多変量データに対して双方向クラスタリングを行うことで、顧客Ａ、Ｃが、商品１、３を購入するというデータ点から成るクラスタと、顧客Ｂが商品２を購入するというデータ点から成るクラスタとが得られる。このクラスタリング結果から、顧客Ａ、Ｃが、商品１、３と共通した特徴を持ち、顧客Ｂは商品２と共通した特徴を持つことがわかる。
【００５１】
図８は、多変量データとシーケンスデータとを双方向クラスタリングする例を示している。図８（ａ）は、シーケンスデータが付加された多変量データを示している。シーケンスデータは、例えば、顧客が、過去に商品を購入した曜日を示すデータから成る。シーケンスデータは、顧客が商品を購入したことを示すデータ点、すなわち、値が１のデータ点に添付される。
【００５２】
図８（ａ）に示す多変量データを、顧客、商品のみでなく、シーケンスデータを考慮して双方向クラスタリングすると、図８（ｂ）に示すクラスタリング結果が得られる。この場合、クラスタ分割数は６となる。シーケンスデータも考慮して双方向クラスタリングを行うことで、顧客Ａ、Ｃが、商品１を購入するというデータ点から成るクラスタと、顧客Ａ、Ｃが商品３を購入するというデータ点から成るクラスタと、顧客Ｂが商品２を購入するというデータ点から成るクラスタとが得られる。
【００５３】
図８（ｂ）に示す双方向クラスタリング結果から、顧客Ａ、Ｃは、商品１を同じような購入曜日履歴で購入していることが読み取れる。また、顧客Ａ、Ｃは、商品３を同じような購入曜日履歴で購入していることが読み取れる。顧客Ａ、Ｃは、共に商品１及び商品３を購入しているものの、商品１と商品３とが同じクラスタに分類されなかったことから、商品１と商品３とでは、購入曜日履歴が異なるということを読み取ることができる。つまり、顧客Ａ、Ｃは、商品１を、商品３と同じような曜日間隔で購入していないことが読み取ることができる。商品２については、顧客Ｂが商品２を購入する曜日履歴は、商品１、３の購入曜日履歴とは異なっていることを読み取ることができる。
【００５４】
本実施形態では、双方向クラスタリング手段１０２は、多変量データとシーケンスデータとに対して双方向クラスタリングを行う。評価関数として、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用い、双方向クラスタリングを行うことで、多変量データと多変量データに対応したシーケンスデータとを、各変量間、及び、シーケンスデータ間でそれぞれ共通の特徴をもつクラスタに同時に分割することができる。
【００５５】
また、本実施形態では、双方向クラスタ分割装置１００は、クラスタ数算出手段１０３を有する。クラスタ数算出手段１０３は、評価関数に基づいてクラスタリング結果が適切であるか否かを判断し、よりよいクラスタリング結果を得るために、クラスタ分割数を増加させる。クラスタリングに際して、いくつのクラスタに分割すればよいかは、事前にわからないことが多い。本実施形態では、クラスタ数算出手段１０３が、動的にクラスタ数を決定することで、事前に、何個のクラスタに分割すればよいかがわからないときでも、多変量データを、適切な分割数で、クラスタ分割することができる。
【００５６】
図９は、本発明の第２実施形態に係る広告配信システムを示している。広告配信システムは、双方向クラスタ分割装置１００とＷｅｂサーバ３００とを有する。双方向クラスタ分割装置１００の構成は、図１に示す第１実施形態における双方向クラスタ分割装置の構成と同様である。Ｗｅｂサーバ３００は、ユーザ端末２００と、インターネット４００などのネットワークを介して接続している。ユーザ端末２００は、ユーザに対して、入出力等のインターフェースを提供する。ユーザ端末２００は、例えば、パーソナルコンピュータや携帯型の情報端末装置である。
【００５７】
広告配信システムは、ユーザがＷｅｂコンテンツをリクエストした際に、ユーザがリクエストしたコンテンツに広告を付け加えてユーザに配信する。広告は、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む。より具体的には、広告には、広告主が誘導したいサイトのリンクが含まれており、ユーザが広告をクリックすることで、ユーザが広告主などのサイトを訪問できるようになっている。広告主は、例えば、商品やサービスの詳細情報を掲載したＷｅｂページへのリンクを広告に含め、ユーザを、そのＷｅｂページに誘導する。
【００５８】
ここで、ユーザにコンテンツに付随して広告を配信しても、その広告がユーザの好みと異なれば、ユーザが広告をクリックする可能性は低く、ユーザを訪問させたいサイトに誘導することができる可能性が低くなる。広告主は、ユーザが広告をクリックしなければ、広告配信の効果を得ることが難しい。従って、広告配信システムでは、ユーザの好みに合致した広告を正確に予測することが重要になる。
【００５９】
Ｗｅｂサーバ３００は、双方向クラスタ分割装置１００に対し、多変量データ及びシーケンスデータを与える。双方向クラスタ分割装置１００は、多変量データと、シーケンスデータとに対して双方向クラスタリングを行う。Ｗｅｂサーバ３００は、双方向クラスタ分割装置１００から双方向クラスタリング結果を受け取る。Ｗｅｂサーバ３００は、双方向クラスタリング結果を用いて、Ｗｅｂコンテンツをリクエストしたユーザに、ユーザの好みに対応した広告を配信する。本実施形態は、協調フィルタリングやコラボレーティブフィルタリングという分野に当てはまる。
【００６０】
図１０は、ユーザ端末２００を示している。ユーザ端末２００は、コンテンツリクエスト手段２０１と、コンテンツ表示手段２０２とを有する。コンテンツリクエスト手段２０１は、ユーザが閲覧を希望するコンテンツを、Ｗｅｂサーバ３００にリクエストする。コンテンツ表示手段２０２は、Ｗｅｂサーバ３００から、ユーザがリクエストしたコンテンツを取得し、表示する。ユーザ端末２００内の各部の機能は、コンピュータが所定のプログラムに従って動作することで実現可能である。
【００６１】
コンテンツリクエスト手段２０１は、例えば、ユーザがスポーツのコンテンツを希望するときは、Ｗｅｂサーバ３００にスポーツのコンテンツをリクエストする。また、コンテンツリクエスト手段２０１は、ユーザが、コンテンツに付随して配信された広告をクリックすると、Ｗｅｂサーバ３００に、その広告に対応するコンテンツをリクエストする。
【００６２】
図１１は、Ｗｅｂサーバ３００を示している。Ｗｅｂサーバ３００は、コンテンツ配信手段３０１、ユーザリクエスト記憶部３０２、コンテンツ記憶部３０３、広告選択手段３０４、広告記憶部３０５、リクエスト受付手段３０６、クラスタリング制御手段３０７、出力装置３０８、入力装置３０９、及び、クラスタリング結果記憶部３１０を有する。Ｗｅｂサーバ３００内の各部の機能は、コンピュータが所定のプログラムに従って動作することで実現可能である。
【００６３】
リクエスト受付手段３０６は、ユーザからのリクエストを受け付ける。ユーザからのリクエストには、所望のＷｅｂページの取得を要求するリクエストと、Ｗｅｂ広告に対応するＷｅｂページの取得を要求するリクエストとがある。ユーザリクエスト記憶部３０２は、ユーザからのリクエストに関する情報を記憶する。リクエスト受付手段３０６は、例えば、ユーザ名、リクエストの内容、リクエストの時刻を、ユーザリクエスト記憶部３０２に記憶する。
【００６４】
コンテンツ記憶部３０３は、ユーザに配信すべきコンテンツを記憶する。広告記憶部３０５は、Ｗｅｂ広告を記憶する。コンテンツ配信手段３０１は、コンテンツ記憶部３０３から、ユーザがリクエストしたコンテンツを取得し、ユーザに配信する。その際、コンテンツ配信手段３０１は、コンテンツに広告記憶部３０５が記憶するＷｅｂ広告を付け加えて、ユーザにコンテンツを配信する。なお、コンテンツ配信手段３０１は、ユーザがリクエストしたコンテンツがコンテンツ記憶部３０３にない場合は、外部サーバにリクエストを転送してもよい。また、ユーザがリクエストしたコンテンツが広告に対応したＷｅｂページである場合、コンテンツ配信手段３０１は、コンテンツにＷｅｂ広告を付け加えなくてもよい。
【００６５】
クラスタリング制御手段３０７は、データ生成手段を兼ねている。クラスタリング制御手段３０７は、双方向クラスタ分割装置１００に与えるデータの生成と、双方向クラスタ分割装置１００が行う双方向クラスタリングの制御を行う。クラスタリング制御手段３０７は、例えば、Ｗｅｂサーバ３００への全アクセス回数が所定のしきい値を越えると、ユーザリクエスト記憶部３０２から、全ユーザの過去のコンテンツ訪問履歴を読み出す。クラスタリング制御手段３０７は、読み出した情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成する。ユーザは、広告をクリックすることで、広告主のコンテンツをリクエストするので、多変量データは、ユーザがどの広告をクリックしたかを示すデータを表していることになる。
【００６６】
また、クラスタリング制御手段３０７は、多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成する。以下では、ユーザが送信したリクエストを時系列で並べたデータを、コンテンツ訪問履歴とも呼ぶ。クラスタリング制御手段３０７は、どのユーザがどの広告をクリックしたかを示す多変量データと、広告をクリックするまでのコンテンツ訪問履歴（シーケンスデータ）とを、出力装置３０８に渡すと共に、双方向クラスタ分割装置１００に双方向クラスタリングを依頼する。
【００６７】
双方向クラスタ分割装置１００は、どのユーザがどの広告をクリックしたかを示す多変量データと、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とを、出力装置３０８を介して入力する。双方向クラスタ分割装置１００は、多変量データと、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とに対して、双方向クラスタリングを行う。双方向クラスタ分割装置１００は、双方向クラスタリング結果をＷｅｂサーバ３００に出力する。
【００６８】
入力装置３０９は、双方向クラスタ分割装置１００から、双方向クラスタリング結果を入力し、クラスタリング結果記憶部３１０に渡す。クラスタリング結果記憶部３１０は、入力装置３０９から受け取った双方向クラスタリング結果を記憶する。広告選択手段３０４は、クラスタリング結果記憶部３１０を参照し、双方向クラスタリング結果に基づいて、ユーザに配信すべきＷｅｂ広告を決定する。広告選択手段３０４は、広告記憶部３０５からＷｅｂ広告を読み出し、コンテンツ配信手段３０１に与える。
【００６９】
以下、動作手順を説明する。広告配信システムの動作は、大きく分けて、双方向クラスタリング処理と、双方向クラスタリング結果を用いた広告配信処理との２つある。図１２は、双方向クラスタリング処理の手順を示している。ユーザがコンテンツを要求すると、ユーザ端末２００のコンテンツリクエスト手段２０１は、Ｗｅｂサーバ３００に、コンテンツをリクエストする（ステップＢ１）。ユーザは、あらかじめ属性情報が判明しているユーザであり、Ｗｅｂサーバ３００は、どのユーザからのコンテンツリクエストであるかを判別可能であるとする。
【００７０】
Ｗｅｂサーバ３００のリクエスト受付手段３０６は、ユーザからのリクエストを受け付ける。リクエスト受付手段３０６は、ユーザ名、リクエストの内容、及び、時刻を、ユーザリクエスト記憶部に記憶する（ステップＢ２）。また、リクエスト受付手段３０６は、ユーザからのリクエストをコンテンツ配信手段３０１に渡す。
【００７１】
コンテンツ配信手段３０１は、コンテンツ記憶部３０３からリクエストに対応するコンテンツを読み出す。また、コンテンツ配信手段３０１は、広告選択手段３０４からＷｅｂ広告を受け取る。コンテンツ配信手段３０１は、コンテンツ記憶部３０３から読み出したコンテンツにＷｅｂ広告を付加して、ユーザ端末２００に送信する（ステップＢ３）。ユーザ端末２００のコンテンツ表示手段２０２は、受信したコンテンツを表示する（ステップＢ４）。
【００７２】
クラスタリング制御手段３０７は、Ｗｅｂサーバ３００への全アクセス回数が所定のしきい値を超えたか否かを判断する。クラスタリング制御手段３０７は、全アクセス回数がしきい値を超えたと判断すると、ユーザリクエスト記憶部３０２から、全ユーザの過去のコンテンツ訪問履歴を読み出す（ステップＢ５）。クラスタリング制御手段３０７は、読み出したコンテンツ訪問履歴に基づいて、どのユーザがどの広告をクリックしたかを示す多変量データと、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とを生成する。クラスタリング制御手段３０７は、生成した多変量データ、及び、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とを、双方向クラスタ分割装置１００に出力する（ステップＢ６）。
【００７３】
双方向クラスタ分割装置１００の双方向クラスタリング手段１０２（図１）は、入力手段１０１を介して、多変量データと、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とを入力する。双方向クラスタリング手段１０２は、多変量データと、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とに対し、双方向クラスタリングを行う（ステップＢ７）。双方向クラスタリングの手順は、図２に示す手順と同様である。
【００７４】
双方向クラスタリング手段１０２は、出力手段１０４を介して、Ｗｅｂサーバ３００に双方向クラスタリング結果を送信する（ステップＢ８）。Ｗｅｂサーバ３００の入力装置３０９は、双方向クラスタリング結果を受け取ると、受け取った双方向クラスタリング結果をクラスタリング結果記憶部３１０に記憶する。クラスタリング結果記憶部３１０は、双方向クラスタリング得結果を記憶する（ステップＢ９）。
【００７５】
図１３は、双方向クラスタリング手段１０２の入力データを示している。多変量データの変量は、「ユーザ」と、「Ｗｅｂ広告」との２つである。コンテンツ訪問履歴は、ユーザが広告をクリックするまでのリクエストを時系列で並べたシーケンスデータである。コンテンツ訪問履歴は、例えば、ユーザが広告をクリックしたその日に、ユーザが最初に送信したリクエストから、広告をクリックする直前のリクエストまでを時系列に並べたものである。或いは、コンテンツ訪問履歴は、ユーザが広告をクリックした時点から１０個前までのリクエストを時系列に並べたものでもよい。コンテンツ訪問履歴の定義は、特に上記したものに限定されるわけではない。
【００７６】
コンテンツ訪問履歴（シーケンスデータ）は、ｙｉｊｋで表す。ｙｉｊｋは、ユーザｋが広告ｊをクリックしたというデータ点に対応したシーケンスデータであり、ユーザｋが広告ｊをクリックするまでに送信したリクエストを時系列で並べたコンテンツ訪問履歴である。ｉは、ユーザが広告をクリックしたのが何回目であるかを表している。例えば、ｙ１ｊｋは、ユーザｋが広告ｊをクリックするのが１回目のときのコンテンツ訪問履歴を表し、ｙ２ｊｋは、ユーザｋが広告ｊをクリックするのが２回目のときのコンテンツ訪問履歴を表している。
【００７７】
図１４は、入力データをテーブル形式（行列形式）で示している。図１３に示す入力データを、行列で表すと、図１４に示すようになる。入力データの行列を、Ｄで表す。行列Ｄの行はユーザを表し、列はＷｅｂ広告を表す。行列Ｄの各要素は、０又は１の値を取る。０はユーザが広告をクリックしていないことを表し、１はユーザが広告をクリックしたことを表す。シーケンスデータは、１つのデータ点に対して１つとは限らず、１つのデータ点に複数のシーケンスデータが対応することもあり得る。
【００７８】
図１５は、双方向クラスタリング手段１０２のクラスタリング結果を示している。双方向クラスタリング手段１０２は、図１４に示す多変量データ及びシーケンスデータに対して双方向クラスタリングを行うことで、入力データを、図１５に示す６個のクラスタＤ１１〜Ｄ１３、Ｄ２１〜Ｄ２３に分割する。
【００７９】
図１５に示すＤ１１〜Ｄ１３、Ｄ２１〜Ｄ２３について、各クラスタのコストを計算すると、
Ｃ（Ｄ１１）＝１ｌｏｇ（４／１）＋３ｌｏｇ（４／３）＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ）＝０．９７７＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ）
Ｃ（Ｄ１２）＝０．０
Ｃ（Ｄ１３）＝０．０
Ｃ（Ｄ２１）＝０．０
Ｃ（Ｄ２２）＝３ｌｏｇ（９／３）＋６ｌｏｇ（９／６）＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）＝２．４８＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）
Ｃ（Ｄ２３）＝０．０
となる。全体のコストＴは、
Ｔ＝ΣＣ（Ｄｉｊ）＝３．４６＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ、ｙ１５Ｄ）＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）
となる。
【００８０】
続いて、双方向クラスタリング結果を用いた広告配信処理を説明する。図１６は、広告配信処理の手順を示している。ユーザ端末２００のコンテンツリクエスト手段２０１は、Ｗｅｂサーバ３００にコンテンツをリクエストする（ステップＣ１）。リクエスト受付手段３０６は、ユーザ端末２００からのリクエストを受け付ける。ユーザリクエスト記憶部３０２は、リクエスト受付手段３０６が受け付けたリクエストを記憶する（ステップＣ２）。
【００８１】
コンテンツ配信手段３０１は、リクエスト受付手段３０６からリクエストを受け取る。コンテンツ配信手段３０１は、リクエストを送信したユーザを識別する情報、例えばユーザ名を広告選択手段３０４に渡す（ステップＣ３）。広告選択手段３０４は、クラスタリング結果記憶部３１０から、ユーザが属するクラスタの情報を読み出す（ステップＣ４）。クラスタリング結果記憶部３１０は、ステップＣ４では、ユーザが所属するクラスタに所属するユーザのユーザ名と、所属クラスのユーザがクリックしたＷｅｂ広告を識別する情報とを読み出す。
【００８２】
広告選択手段３０４は、ステップＣ４で読み出した情報に基づいて、コンテンツをリクエストしたユーザに配信すべきＷｅｂ広告を決定する（ステップＣ５）。広告選択手段３０４は、同じクラスタに所属するユーザがクリックした広告を、ユーザに配信する広告の候補とし、その候補の中から、ユーザに配信する広告を決定する。広告選択手段３０４は、広告の決定では、他のユーザはクリックしたが、コンテンツをリクエストしたユーザがクリックしていない広告があるときは、その広告を、優先的に、ユーザに配信する広告として決定する。
【００８３】
図１７は、広告配信候補を示している。クラスタ分割結果として、図１５に示すクラスタ分割結果が得られているとき、各ユーザに配信すべき広告の候補は、図１７に示すようになる。図１７において、Ｗｅｂ広告配信候補の並び順は、優先順位が高い順とする。例えば、クラスタＤ１１を考える。図１５を参照すると、このクラスタに所属するユーザは、ユーザＡとユーザＤの二人である。また、ユーザＡは、広告１と広告５とをクリックし、ユーザＤは、広告１をクリックしている。
【００８４】
同じクラスタに所属するユーザは、Ｗｅｂ広告に関して好みが似通っていており、そのクラスタに属するＷｅｂ広告群に興味があると考えられる。また、双方向クラスタ分割装置１００は、どのＷｅｂページにアクセスしてから広告をクリックしたかというシーケンスデータも用いて双方向クラスタリングを行うので、同じクラスタに所属するユーザは、コンテンツ訪問履歴に関しても、共通した特徴が多く持つと考えられる。このため、コンテンツをリクエストしたユーザに対して、同じクラスタに所属するユーザのうちの少なくとも一人がクリックしたことがある広告を配信すれば、広告の配信を受けたユーザは、その広告をクリックすると予測できる。
【００８５】
クラスタＤ１１に所属するユーザは、広告１と広告５とをクリックしたことがあるので、ユーザＡとユーザＤとに配信する広告の候補は、広告１と広告５とする。ユーザＤは、広告５をクリックしたことがないので、広告選択手段３０４は、広告５の優先順位を広告１の優先順位よりも高くする。広告選択手段３０４は、優先順位に従って、広告５、広告１の順で、ユーザＤに配信すべき広告を決定する。ユーザＡは、広告１と広告５とをクリックしているので、特に優先順位はない。広告選択手段３０４は、ユーザＡに対しては、広告１と広告５との何れかを、ランダムに、ユーザＡに配信すべき広告として決定すればよい。
【００８６】
図１６に戻り、広告選択手段３０４は、配信する広告を決定すると、広告記憶部３０５からＷｅｂ広告を読み出し、コンテンツ配信手段３０１に与える。広告選択手段３０４は、決定したＷｅｂ広告を識別する情報をコンテンツ配信手段３０１に渡し、コンテンツ配信手段３０１が、広告記憶部３０５からＷｅｂコンテンツを読み出してもよい。
【００８７】
コンテンツ配信手段３０１は、コンテンツ記憶部３０３から、ユーザがリクエストしたコンテンツを読み出す（ステップＣ６）。コンテンツ配信手段３０１は、広告選択手段３０４が決定したＷｅｂ広告を、読み出したコンテンツに付け加える（ステップＣ７）。コンテンツ配信手段３０１は、Ｗｅｂ広告を付け加えたＷｅｂコンテンツを、ユーザ端末２００に送信する（ステップＣ８）。ユーザ端末２００のコンテンツ表示手段２０２は、コンテンツ配信手段３０１が送信した、Ｗｅｂ広告を含むＷｅｂコンテンツを表示する（ステップＣ９）。
【００８８】
図１８は、Ｗｅｂ広告が付加されたＷｅｂページを示している。コンテンツ配信手段３０１は、Ｗｅｂページ９０１内に、広告表示領域９０２を設け、その広告表示領域９０２内に、Ｗｅｂ広告を埋め込む。Ｗｅｂ広告の配信は、特にここで記載したものには限定されない。例えば、ＷｅｂコンテンツにＷｅｂ広告を埋め込まずに、Ｗｅｂコンテンツとは別に、Ｗｅｂ広告を配信する形でもよい。
【００８９】
本実施形態では、双方向クラスタ分割装置は、どのユーザがどのＷｅｂ広告をクリックしたかというデータを多変量データとし、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴をシーケンスデータとして、多変量データとシーケンスデータとに対し、双方向クラスタリングを行う。ユーザの特徴は、どのＷｅｂ広告をリクエストしたかという情報に加えて、どのようにＷｅｂ広告をクリックしたかという情報にも現れる。本実施形態では、多変量データとシーケンスデータとを同時に扱い、それらに対して双方向クラスタリングを行うので、ユーザの特徴や好みを、より正確に抽出できることが期待できる。また、そのような双方向クラスタリングを行った結果を用いて、ユーザに配信する広告を決定することで、ユーザが広告をクリックすることが期待できる。
【００９０】
図１９は、本発明の第３実施形態に係る商品推薦システムを示している。商品推薦システムは、サーバシステム６００を有する。サーバシステム６００は、双方向クラスタ分割装置１００と、データ生成手段６０１と、推薦商品リスト生成手段６０２と、クラスタリング結果記憶部６０３とを有する。サーバシステム６００は、クライアントシステム５０１〜５０３と、ネットワーク４０１を介して接続されている。クライアントシステム５０１〜５０３は、例えば、小売店に設置される売上管理システムである。サーバシステム６００は、小売店の情報を束ねる中央管理システムであり、データセンタなどに設置される。
【００９１】
クライアントシステム５０１〜５０３は、各店舗の売上情報を管理する。売上情報は、例えば、顧客名と、顧客が購入した商品名と、購入日時に関する情報とを含む。サーバシステム６００は、クライアントシステムからどの顧客がどの商品を購入したかを示すデータを含む顧客の購入情報を収集する。サーバシステム６００は、収集した情報を用いて双方向クラスタリングを行う。多変量データとしてこのような情報を用いる場合、双方向クラスタリング結果を、小売業のマーケティングなどに利用することができる。サーバシステム６００は、双方向クラスタリング結果を用いて、顧客に対して今後推薦する商品を決定する。サーバシステム６００は、推薦商品の情報を、各店舗のクライアントシステム５０１〜５０３に送信する。
【００９２】
データ生成手段６０１は、クライアントシステム５０１〜５０３から顧客の購入情報を収集する。データ生成手段６０１は、収集した顧客の購入情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成する。また、データ生成手段６０１は、多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータを生成する。ここでは、シーケンスデータは、顧客の商品購入曜日を時系列に並べた購入曜日履歴であるとする。
【００９３】
双方向クラスタ分割装置１００の構成は、図１に示す第１実施形態における双方向クラスタ分割装置の構成と同様である。双方向クラスタ分割装置１００は、データ生成手段６０１が生成した多変量データとシーケンスデータとに対して双方向クラスタリングを行う。双方向双方向クラスタ分割装置１００は、双方向クラスタリング結果を、クラスタリング結果記憶部６０３に記憶する。推薦商品リスト生成手段６０２は、クラスタリング結果記憶部６０３記憶するクラスタリング結果を用いて、顧客に推薦する商品のリストを生成する。
【００９４】
図２０は、動作手順を示している。クライアントシステム５０１〜５０３は、それぞれ、ネットワーク４０１を介して、サーバシステム６００に、顧客の購入情報を送信する（ステップＤ１）。サーバシステム６００は、各クライアントから、顧客の購入情報を受け取る。各クライアントがサーバシステム６００に顧客の購入情報を送信するタイミングは、クライアントごとに異なっていてもよい。
【００９５】
データ生成手段６０１は、どの顧客がどの商品を購入したかを示す多変量データと、顧客が商品を購入した曜日の履歴を示す購入曜日履歴とを生成する。データ生成手段６０１は、生成した多変量データと購入曜日履歴とを、双方向クラスタ分割装置１００に出力する（ステップＤ２）。
【００９６】
双方向クラスタ分割装置１００の双方向クラスタリング手段１０２（図１）は、入力手段１０１を介して、多変量データと、購入曜日履歴とを入力する。双方向クラスタリング手段１０２は、多変量データと、購入曜日履歴とに対し、双方向クラスタリングを行う（ステップＤ３）。双方向クラスタリングの手順は、図２に示す手順と同様である。双方向クラスタ分割装置１００は、双方向クラスタリング結果をクラスタリング結果記憶部６０３に送り、双方向クラスタリング結果を、クラスタリング結果記憶部６０３に記憶する（ステップＤ４）。
【００９７】
推薦商品リスト生成手段６０２は、双方向クラスタリング結果記憶部６０３から双方向クラスタリング結果を読み出し、顧客ごとの推薦商品リストを生成する（ステップＤ５）。推薦商品リスト生成手段６０２は、ステップＤ５では、クラスタごとに、そのクラスタに所属する顧客のうちの少なくとも一人が購入した商品を調べる。推薦商品リスト生成手段６０２は、顧客ごとに、当該顧客が所属するクラスタに所属する顧客のうちの少なくとも一人が購入した商品のうち、当該顧客が購入していない商品を、推薦商品リストに含める。
【００９８】
推薦商品リスト生成手段６０２は、推薦商品リストをクライアントシステム５０１〜５０３に送信する（ステップＤ６）。クライアントシステム５０１〜５０３は、各顧客に対する推薦商品リストを、サーバシステム６００から受信する（ステップＤ７）。
【００９９】
図２１は、双方向クラスタリング手段１０２の入力データを示している。多変量データの変量は、「顧客」と、「商品」との２つである。購入曜日履歴は、例えば１月単位で、顧客が商品を購入した曜日の履歴を時系列で並べたシーケンスデータである。図２２は、双方向クラスタリング結果を示している。双方向クラスタリング手段１０２が、図２１に示す入力データに対して双方向クラスタリングを行うことで、図２２に示す、２×３＝６つのクラスタが得られたとする。
【０１００】
図２３は、推薦商品リストを示している。クラスタ分割結果として、図２２に示すクラスタ分割結果が得られているとき、各顧客に推薦すべき商品のリスト（推薦商品候補）は、図２３に示すようになる。例えば、クラスタＤ１１を考える。図２２を参照すると、このクラスタに所属する顧客は、顧客Ａと顧客Ｄの二人である。また、顧客Ａは、商品１と商品５とを購入し、顧客Ｄは、商品１を購入している。
【０１０１】
本実施形態では、顧客、商品、購入曜日履歴に対して双方向クラスタリングを行っており、双方向クラスタリングを行うことで、同じ商品に興味があり、また、商品の購入曜日履歴も類似する顧客を、各クラスタに集めることができる。同じクラスタに所属する顧客は、購入商品に関して好みが似通っていており、また、商品を購入する曜日履歴も共通した特徴が多く含まれていると考えられる。従って、あるクラスタに属する商品に関連したお勧め商品を、そのクラスタに属する顧客に対してお勧めすると、顧客が商品を購入することが期待できる。
【０１０２】
推薦商品リスト生成手段６０２は、クラスタＤ１１に所属する顧客は、商品１と商品５とを購入しているので、顧客Ａと顧客Ｄとに推薦する商品を、商品１と商品５との中から選ぶ。顧客Ｄは、商品５を購入していないので、推薦商品リスト生成手段６０２は、顧客Ｄに推薦する商品を商品５と決定する。顧客Ａは、商品１と商品５とを既に購入しているので、推薦商品リスト生成手段６０２は、顧客Ａに推薦する商品はないと判断する。
【０１０３】
本実施形態では、双方向クラスタ分割装置１００は、どの顧客がどの商品を購入したかというデータを多変量データとし、顧客が商品を購入した曜日の履歴をシーケンスデータとして、多変量データとシーケンスデータとに対し、双方向クラスタリングを行う。顧客の特徴は、どの商品を購入したかという情報に加えて、どのような曜日履歴で商品を購入したかという情報にも現れる。本実施形態では、多変量データとシーケンスデータとを同時に扱い、それらに対して双方向クラスタリングを行うので、ユーザの特徴や好みを、より正確に抽出できることが期待できる。また、そのような双方向クラスタリングを行った結果を用いて、顧客に推薦する商品を決定することで、ユーザがその後購入することを期待できる商品を、推薦商品とすることができる。
【０１０４】
図２４は、本発明の第４実施形態に係る故障予測システムを示している。故障予測システムは、サーバシステム８００を有する。サーバシステム８００は、双方向クラスタ分割装置１００と、データ生成手段８０１と、故障予測候補リスト生成手段８０２と、クラスタリング結果記憶部８０３とを有する。サーバシステム８００は、クライアントシステム７０１〜７０３と、ネットワーク４０２を介して接続されている。クライアントシステム７０１〜７０３は、例えば、自動車販売店や修理工場に設置されている。サーバシステム８００は、中央管理システムであり、データセンタなどに設置される。
【０１０５】
クライアントシステム７０１〜７０３は、自動車の故障情報を管理する。故障情報は、車種と故障個所（故障部品）とを含む。例えば、各車種に対して、複数の地域で故障が起きており、クライアントシステム７０１〜７０３は、車種ごとに故障が起こった部品の故障履歴を蓄積しているとする。サーバシステム８００は、クライアントシステム７０１〜７０３から、故障情報を収集する。サーバシステム８００は、クライアントシステムから収集した情報を用いて、双方向クラスタリングを行う。サーバシステム８００は、双方向クラスタリング結果を用いて、故障予測を行い、予測結果をクライアントシステム７０１〜７０３に送信する。
【０１０６】
データ生成手段８０１は、クライアントシステム７０１〜７０３から車種ごとの故障情報を収集する。データ生成手段８０１は、収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に当該地域で故障が発生したか否かを示す多変量データを生成する。また、データ生成手段８０１は、多変量データに対応して、当該車種で故障が発生したことに関する履歴を時系列で並べたシーケンスデータを生成する。ここでは、シーケンスデータは、過去に故障が発生した部品を時系列に並べた故障部品履歴であるとする。
【０１０７】
双方向クラスタ分割装置１００の構成は、図１に示す第１実施形態における双方向クラスタ分割装置の構成と同様である。双方向クラスタ分割装置１００は、車種ごとの故障発生地域と、故障部品履歴とに対して双方向クラスタリングを行う。クラスタリング結果記憶部８０３は、双方向クラスタ分割装置１００のクラスタリング結果を記憶する。故障予測候補リスト生成手段８０２は、クラスタリング結果記憶部８０３が記憶するクラスタリング結果を用いて、車種と地域とに対して、今後故障が発生すると予測される部品のリストを生成する。
【０１０８】
図２５は、動作手順を示している。クライアントシステム７０１〜７０３は、それぞれ、ネットワーク４０２を介して、サーバシステム８００に、故障情報を送信する（ステップＥ１）。サーバシステム８００は、各クライアントから、故障情報を受け取る。クライアントシステム７０１〜７０３が管理する故障情報は地域が異なっており、サーバシステム８００は、どのクライアントから故障情報を受信したかに応じて、故障が発生した地域が判別可能であるとする。或いは、故障情報が地域に関する情報を含んでいてもよい。各クライアントがサーバシステム８００に故障情報を送信するタイミングは、クライアントごとに異なっていてもよい。
【０１０９】
データ生成手段８０１は、どの車種にどの地域で故障が発生しているかを示す多変量データと、当該車種で過去に故障が発生した部品の履歴を示す故障部品履歴とを生成する。データ生成手段８０１は、生成した多変量データと故障部品履歴とを、双方向クラスタ分割装置１００に出力する（ステップＥ２）。
【０１１０】
双方向クラスタ分割装置１００の双方向クラスタリング手段１０２（図１）は、入力手段１０１を介して、多変量データと、故障部品履歴とを入力する。双方向クラスタリング手段１０２は、多変量データと、故障部品履歴とに対し、双方向クラスタリングを行う（ステップＥ３）。双方向クラスタリングの手順は、図２に示す手順と同様である。双方向クラスタ分割装置１００は、双方向クラスタリング結果をクラスタリング結果記憶部８０３に送り、双方向クラスタリング結果を、クラスタリング結果記憶部８０３に記憶する（ステップＥ４）。
【０１１１】
故障予測候補リスト生成手段８０２は、双方向クラスタリング結果記憶部８０３から双方向クラスタリング結果を読み出し、車種ごとの故障予測候補リストを生成する（ステップＥ５）。故障予測候補リスト生成手段８０２は、ステップＥ５では、クラスタごとに、そのクラスタに所属する車種の少なくとも一つに故障が発生した地域を調べる。故障予測候補リスト生成手段８０２は、車種ごとに、当該車種が所属するクラスタに所属する車種のうちの少なくとも一つで故障が発生した地域のうち、当該顧客でまだ故障が発生していない地域を、故障予測候補リストに含める。
【０１１２】
故障予測候補リスト生成手段８０２は、故障予測候補リストをクライアントシステム７０１〜７０３に送信する（ステップＥ６）。クライアントシステム７０１〜７０３は、各顧客に対する故障予測候補リストを、サーバシステム８００から受信する（ステップＥ７）。
【０１１３】
図２６は、双方向クラスタリング手段１０２の入力データを示している。多変量データの変量は、「車種」と、「地域」との２つである。故障部品履歴は、例えば１年単位で、当該車種で故障が発生した部品の履歴を時系列で並べたシーケンスデータである。或いは、故障部品履歴は、故障発生以前に故障が発生した過去の故障部品を並べたものでもよい。図２７は、双方向クラスタリング結果を示している。双方向クラスタリング手段１０２が、図２６に示す入力データに対して双方向クラスタリングを行うことで、図２７に示す、２×３＝６つのクラスタが得られたとする。
【０１１４】
図２８は、故障予測候補リストを示している。クラスタ分割結果として、図２７に示すクラスタ分割結果が得られているとき、各車種に故障が発生すると予測される地域のリスト（故障発生地域候補）は、図２８に示すようになる。例えば、クラスタＤ１１を考える。図２７を参照すると、このクラスタに所属する車種は、車種Ａと車種Ｄの２つである。また、車種Ａは、地域１と地域５とで故障が発生しており、車種Ｄは、地域１で故障が発生している。
【０１１５】
本実施形態では、車種、地域、故障部品履歴に対して双方向クラスタリングを行っており、双方向クラスタリンを行うことで、同じ地域で故障が発生し、また、故障備品履歴も類似する車種を、各クラスタに集めることができる。同じクラスタに所属する車種は、故障発生地域が同じ傾向にあり、また、故障が発生した部品履歴も共通した特徴を多く含んでいると考えられる。従って、あるクラスタに属する車種は、今後、そのクラスタに所属する地域で故障が発生すると予測できる。
【０１１６】
故障予測候補リスト生成手段８０２は、クラスタＤ１１に所属する車種は、地域１と地域５とで故障が発生しているので、故障発生地域を、地域１と地域５との中から選ぶ。車種Ｄは、既に地域１で故障が発生しているので、故障予測候補リスト生成手段８０２は、車種Ｄで故障の発生が予測される地域を地域５と決定する。車種Ａは、既に地域１と地域５とで故障が発生しているので、故障予測候補リスト生成手段８０２は、車種Ａに今後故障が発生すると予測される地域はないと判断する。
【０１１７】
本実施形態では、双方向クラスタ分割装置１００は、どの地域でどの車種に故障が発生しているかというデータを多変量データとし、故障発生部品の履歴をシーケンスデータとして、多変量データとシーケンスデータとに対し、双方向クラスタリングを行う。多変量データとシーケンスデータとに対して双方向クラスタリングを行うことで、車種、地域、故障部品履歴に共通した特徴を持つクラスタに分割することができ、車種と地域で共通の特徴をもつクラスタを発見することができる。クラスタリング結果から、車種ごとに、今後、故障が発生すると予測される地域を予測することができる。サーバシステム８００から、故障発生が予測される地域のクライアントシステムに対してどの車種でどのような故障が発生する可能性が高いかを示す情報を送信することで、故障発生に備えることができる。また、故障原因を発見するための調査を早期に行うこともできる。
【０１１８】
ここで、双方向クラスタリングでは、通常、事前にクラスタ数を設定する必要がある。本実施形態で言えば、クラスタ数は、全体で発生している故障の数を表している。双方向クラスタリングで事前にクラスタ数を設定する場合、全体として故障が何個発生しているかが不明な状態でも、事前にクラスタ数を決めなければならない。言い換えれば、クラスタリングを行うことで、発生している故障の数を知りたいにもかかわらず、発生している故障の数を事前に決めなくてはならない。本実施形態では、双方向クラスタ分割装置１００がクラスタ数算出手段１０３（図１）を有しているので、事前にクラスタ数を決めておかなくても、適切な分割数でクラスタ分割を行うことができる。応用上、双方向クラスタリングでは、データを入力するだけで、適切な数でクラスタに分割したクラスタリング結果を出力することが重要である。
【０１１９】
なお、上記各実施形態では、多変量データの変量を２つとしているが、変量の数は２つには限定されない。また、多変量データ及びシーケンスデータとの組み合わせは、上記各実施形態で用いたものには限定されない。例えば、多変量データの変量として「顧客」、「商品」を用い、シーケンスデータとして「商品購入履歴」を用いてもよい。或いは、多変量データの変量として「顧客」、「会社名」を用い、シーケンスデータとして「転職履歴」を用いることや、多変量データの変量として「商品」、「Ｗｅｂページ」を用い、シーケンスデータとして「ｗｅｂページで各商品を紹介キャンペーンした日時の履歴」を用いてもよい。更には、多変量データの変量として「部品」、「部品製造会社」を用い、シーケンスデータとして、「部品製造会社が部品を配送した履歴」用いることも可能であり、また、多変量データの変量として「インターネットウィルス名」、「インターネットウィルスの感染が確認された地域」を用い、シーケンスデータとして「１日にウィルスに感染したと報告のあった数の履歴」を用いることもできる。
【０１２０】
図１では、双方向クラスタ分割装置１００はクラスタ数算出手段１０３を有しているが、クラスタ数算出手段１０３を持たない構成も可能である。その場合、双方向クラスタリング手段１０２は、事前に設定されたクラスタ分割数で、クラスタ分割を行えばよい。また、双方向クラスタリング手段１０２と、クラスタ数算出手段１０３とは、同一の装置が備えている必要はなく、双方向クラスタリング手段１０２と、クラスタ数算出手段１０３とを別の装置に分けて、クラスタリングの実行と、クラスタリング結果の評価とを、異なる装置で行ってもよい。
【０１２１】
上記各実施形態では、外部から、多変量データとシーケンスデータとを双方向クラスタ分割装置１００に入力する例を説明したが、多変量データとシーケンスデータとの生成は、双方向クラスタ分割装置１００内で行ってもよい。例えば、第２実施形態で、Ｗｅｂサーバ３００（図１１）のクラスタリング制御手段３０７は、多変量データとシーケンスデータとの生成を行わずに、ユーザリクエスト記憶部３０２から読み出した各ユーザのリクエスト履歴を、出力装置３０８を介して双方向クラスタ分割装置１００に出力する。双方向クラスタ分割装置１００には、データ生成手段を設けておく。双方向クラスタ分割装置１００は、クラスタリング制御手段３０７から入力した情報に基づいて、どのユーザがどのＷｅｂ広告をクリックしたかを示す多変量データと、Ｗｅｂ広告をクリックするまでのコンテンツ訪問履歴とを生成し、その後、双方向クラスタリングを実施してもよい。
【０１２２】
以上、本発明をその好適な実施形態に基づいて説明したが、本発明の双方向クラスタ分割装置、広告配信システム、商品推薦システム、故障予測システム、方法、及び、プログラムは、上記実施形態にのみ限定されるものではなく、上記実施形態の構成から種々の修正及び変更を施したものも、本発明の範囲に含まれる。
【０１２３】
最後に、本発明の概要について説明する。図２９は、本発明の双方向クラスタ分割装置の概略を示している。双方向クラスタ分割装置１０は、入力手段１１と双方向クラスタリング手段１２とを有する。入力手段１１は、変量データと多変量データに対応したシーケンスデータとを入力する。双方向クラスタリング手段１２は、多変量データとシーケンスデータとに対して双方向クラスタリングを行う。双方向クラスタリング手段１２は、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて、多変量データとシーケンスデータとを、複数のクラスタに分割する。
【０１２４】
本発明では、多変量データだけでなく、多変量データに対応したシーケンスデータも同時に双方向クラスタリングする。従って、各変量間、及び、シーケンスデータ間でそれぞれ共通の特徴を持つクラスタに同時に分割することができる。また、データの特徴は、多変量データだけでなく、多変量データに対応したシーケンスデータにも現れる。このため、多変量データとシーケンスデータとを同時に扱い、双方向クラスタリングを行うことで、より正確に、多変量データ間の特徴を抽出できるとことが期待できる。
【符号の説明】
【０１２５】
１０：双方向クラスタ分割装置
１１：入力手段
１２：双方向クラスタリング手段
１００：双方向クラスタ分割装置
１０１：入力手段
１０２：双方向クラスタリング手段
１０３：クラスタ数算出手段
１０４：出力手段
２００：ユーザ端末
２０１：コンテンツリクエスト手段
２０２：コンテンツ表示手段
３００：Ｗｅｂサーバ
３０１：コンテンツ配信手段
３０２：ユーザリクエスト記憶部
３０３：コンテンツ記憶部
３０４：広告選択手段
３０５：広告記憶部
３０６：リクエスト受付手段
３０７：クラスタリング制御手段
３０８：出力装置
３０９：入力装置
３１０：クラスタリング結果記憶部
４００：インターネット
４０１、４０２：ネットワーク
５０１〜５０３、７０１〜７０３：クライアントシステム
６００：サーバシステム
６０１：データ生成手段
６０２：推薦商品リスト生成手段
６０３：クラスタリング結果記憶部
８００：サーバシステム
８０１：データ生成手段
８０２：故障予測候補リスト生成手段
８０３：クラスタリング結果記憶部
【技術分野】
【０００１】
本発明は、双方向クラスタ分割装置、方法、及び、プログラムに関し、更に詳しくは、多変量データの集合を、データ間で共通の特徴を持つクラスタに分割する双方向クラスタ分割装置、方法、及び、プログラムに関する。
【背景技術】
【０００２】
クラスタリング技術は、データの集合を、共通の特徴を持つクラスタに分割する技術である。多変量データは、あるデータ点が複数の変量から成るデータである。多変量データを変量ごとにクラスタリングする技術は、一方向のクラスタリングと呼ばれている。これに対し、複数の変量を同時にクラスタリングする技術は、双方向クラスタリング（Co-clustering）と呼ばれる。非特許文献１及び２は、双方向クラスタリングが記載された文献である。
【０００３】
双方向クラスタリングは、特に、自然言語処理の技術として開発されている。自然言語処理の分野では、双方向クラスタリングを、文章と単語とを同時にクラスタリングする際に使用している。双方向クラスタリングでは、文章と単語という多変量データを、文章と単語との共起情報を基に、文章と単語との各部分集合が共起関係になるクラスタにクラスタ分割を行う。
【０００４】
自然言語処理の分野で、双方向クラスタリングを用いずに文章と単語とをクラスタリングする場合には、文章と単語とを別々にクラスタリングする必要がある。文章のクラスタリングでは、各文章に含まれる単語の頻度を特徴として利用し、その特徴が同じ文章が同一クラスタに属するように、クラスタ分割を行う。単語のクラスタリングでは、各単語がどの文章に含まれているかを特徴として利用し、その特徴が同じ単語が同一クラスタに含まれるように、クラスタ分割を行う。
【０００５】
自然言語処理に一方向のクラスタリングを用いる場合、上記のように、文章は単語の特徴を用いてクラスタリングし、単語は文章の特徴を用いてクラスタリングする。このため、クラスタリング処理が冗長になる。また、文書でクラスタリングした結果と、単語でクラスタリングした結果とを組み合わせることで、文書と単語の双方のクラスタリングが実現できる。しかし、一方向のクラスタリングでは、文章と単語とを別々にクラスタリングするために、文章と単語との相関や、共起関係を適切にクラスタに組み込むことが困難である。これに対し、双方向のクラスタリングでは、文書と単語との相関や、共起関係をクラスタに組み込むことができる。
【０００６】
特許文献１は、顧客ごとの商品の購買履歴データから、クラスタを抽出する購買情報処理装置が記載された文献である。特許文献１の購買情報処理装置は、購買情報生成手段と、購買情報処理手段とから成る。購買情報生成手段は、購買履歴データにある顧客と商品とをそれぞれ、行及び列の一方の項目として当てはめる。購買情報生成手段は、顧客が購入した履歴がある商品の行列要素と、購入した履歴がない商品の行列要素とに、互いに異なる所定の指標値（０又は１）を付与して、行列テーブルを生成する。
【０００７】
購買情報処理手段は、行列テーブルについて、行ごとの指標値の総和に基づいて行を並び替えると共に、列ごとの指標値の総和に基づいて列を並び替える。購買情報処理手段は、指標値の総和を、昇順又は降順に並び変える。購買情報処理手段は、並び変え後、行列テーブル上の指標値の分布にて規定されるクラスタを抽出する。特許文献１では、このようなクラスタリングを行うことで、顧客情報のクラスタ抽出に要する計算量及び処理時間の低減が可能である。
【０００８】
特許文献２は、時系列データをクラスタリングする時系列データ処理装置が記載された文献である。時系列データは、処理日時などの時間情報、顧客特定情報、及び、商品特定情報を最低限含む。時系列データ処理装置は、時系列データを対象として、商品をその購買顧客が類似する複数のグループにクラスタリングする。時系列データ処理装置は、クラスタ内の任意の２つの商品（商品Ａ、Ｂ）に対して、２つの商品が同時に購入されている事例数、Ａが購入された後にＢが購入された事例数、Ｂが購入された後にＡが購入された事例数をカウントする。時系列データ処理装置は、カウンタした事例数から、２つの商品の順序関係を決定する。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００３−２４８７５０号公報
【特許文献２】特開平９−３０５５７１号公報
【非特許文献】
【００１０】
【非特許文献１】A Generalized Maximum Entropy Approach to Bregman Co-clustering and Matrix Approximation,A.Banerjee and I.Dhillon and J.Ghosh and S.Merugu and D.S.Modha,KDD2004
【非特許文献２】Fully Automatic Cross-associations,Deepayan Chakrabarti and Spiros Papadimitriou and Dharmendra S.Modha and Christos Faloutsos,KDD2004
【非特許文献３】Probabilistic Model-Based Clustering of Multivariate and Sequential Data,Padhraic Smyth,In Proceedings of Artificial Intelligence and Statistics,1999
【発明の概要】
【発明が解決しようとする課題】
【００１１】
情報化社会が進み、蓄積されたデータも膨大な量になっている。例えば、小売業では、ＰＯＳ（Point of Sales）データと呼ばれる多変量データが大量に蓄積されている。ＰＯＳデータは、どの顧客が、いつ、どこで、何を購入したかという情報を含む。蓄積されるデータは多変量データだけではなく、各データ点に順序情報が与えられたシーケンスデータも膨大に蓄積されている。シーケンスデータは、データ点に対応したデータであり、多変量データの２以上のキー（属性）に関連する情報が時系列に並んだデータである。多変量データのデータ点に対応してシーケンスデータがある場合、シーケンスデータも考慮した上で、クラスタリングを行うことが好ましいと考えられる。
【００１２】
しかし、非特許文献１及び２は、多変量データに対して双方向クラスタリングを行うのみであり、多変量データとシーケンスデータとを同時にクラスタリングすることはできない。特許文献１も、同様に、多変量データに対して双方向クラスタリングを行うのみで、シーケンスデータを考慮して双方向クラスタリングを行うことができない。また、特許文献２は、クラスタリング後に、同じクラスタに属する２つの商品について、時系列データから、どちらの商品が先に購入されたか、又は、同時に購入されたかを求めているに過ぎず、シーケンスデータを考慮したクラスタリングは行っていない。
【００１３】
ここで、非特許文献３には、多変量データとシーケンスデータとをクラスタに分割する技術が記載されている。しかし、非特許文献３におけるクラスタリングは、一方向クラスタリングである。従って、非特許文献３では、多変量データとシーケンスデータとを同時に双方向クラスタリングすることはできない。
【００１４】
本発明は、多変量データと多変量データに対応したシーケンスデータとを、各変量間、及び、シーケンスデータ間で共通の特徴をもつクラスタに同時に分割可能な双方向クラスタ分割装置、方法、及び、プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記目的を達成するために、本発明は、多変量データと多変量データに対応したシーケンスデータとを入力する入力手段と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割する双方向クラスタリング手段とを備える双方向クラスタ分割装置を提供する。
【００１６】
本発明は、多変量データと多変量データに対応したシーケンスデータとを入力するステップと、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割するステップとを有する双方向クラスタ分割方法を提供する。
【００１７】
本発明は、コンピュータに、多変量データと多変量データに対応したシーケンスデータとを入力する処理と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割する処理とを実行させるプログラムを提供する。
【００１８】
本発明は、ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付手段と、ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信手段と、前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成手段と、前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、前記双方向クラスタリング結果に基づいて、前記コンテンツ配信手段がコンテンツに付加すべき広告を決定する広告選択手段とを備える広告配信システムを提供する。
【００１９】
本発明は、ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付ステップと、ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信ステップと、前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成ステップと、前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、前記双方向クラスタリング結果に基づいて、前記コンテンツに付加すべき広告を決定する広告選択ステップとを有する広告配信方法を提供する。
【００２０】
本発明は、コンピュータに、ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付処理と、ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信処理と、前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成処理と、前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、前記双方向クラスタリング結果に基づいて、前記コンテンツに付加すべき広告を決定する広告選択処理とを実行させるプログラムを提供する。
【００２１】
本発明は、顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成手段と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成手段とを備える商品推薦システムを提供する。
【００２２】
本発明は、顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成ステップと、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成ステップとを有する商品推薦方法を提供する。
【００２３】
本発明は、コンピュータに、顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成処理と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成処理とを実行させるプログラムを提供する。
【００２４】
本発明は、車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成手段と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成手段とを備える故障予測システムを提供する。
【００２５】
本発明は、車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成ステップと、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成ステップとを有する故障予測方法を提供する。
【００２６】
本発明は、コンピュータに、車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成処理と、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成処理とを実行させるプログラムを提供する。
【発明の効果】
【００２７】
本発明の双方向クラスタ分割装置、方法、及び、プログラムは、多変量データと多変量データに対応したシーケンスデータとを、各変量間、及び、シーケンスデータ間で共通の特徴をもつクラスタに同時に分割することができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の第１実施形態に係る双方向クラスタ分割装置を示すブロック図。
【図２】双方向クラスタ分割装置の動作手順を示すフローチャート。
【図３】入力データの一例を示す図。
【図４】入力データをテーブル形式（行列形式）で示す図。
【図５】初期クラスタリングの結果を示す図。
【図６】最終的に得られたクラスタリング結果を示す図。
【図７】（ａ）は、多変量データを示し、（ｂ）は、クラスタリング結果を示す図。
【図８】（ａ）は、シーケンスデータが付加された多変量データを示し、（ｂ）は、クラスタリング結果を示す図。
【図９】本発明の第２実施形態に係る広告配信システムを示すブロック図。
【図１０】ユーザ端末を示すブロック図。
【図１１】Ｗｅｂサーバを示すブロック図。
【図１２】双方向クラスタリング処理の手順を示すフローチャート。
【図１３】双方向クラスタリング手段の入力データを示す図。
【図１４】入力データをテーブル形式（行列形式）で示す図。
【図１５】双方向クラスタリング手段のクラスタリング結果を示す図。
【図１６】広告配信処理の手順を示すフローチャート。
【図１７】広告配信候補を示す図。
【図１８】Ｗｅｂ広告が付加されたＷｅｂページを示す図。
【図１９】本発明の第３実施形態に係る商品推薦システムを示す図。
【図２０】商品推薦の動作手順を示すフローチャート。
【図２１】双方向クラスタリング手段の入力データを示す図。
【図２２】双方向クラスタリング結果を示す図。
【図２３】推薦商品リストを示す図。
【図２４】本発明の第４実施形態に係る故障予測システムを示すブロック図。
【図２５】故障予測の動作手順を示すフローチャート。
【図２６】双方向クラスタリング手段の入力データを示す図。
【図２７】双方向クラスタリング結果を示す図。
【図２８】故障予測候補リストを示す図。
【図２９】本発明の双方向クラスタ分割装置の概略を示すブロック図。
【発明を実施するための形態】
【００２９】
以下、図面を参照し、本発明の実施の形態について詳細に説明する。図１は、本発明の第１実施形態に係る双方向クラスタ分割装置を示している。双方向クラスタ分割装置１００は、入力手段１０１、双方向クラスタリング手段１０２、クラスタ数算出手段１０３、及び、出力手段１０４を備える。双方向クラスタ分割装置１００内の各手段の機能は、コンピュータが所定のプログラムを読み込んで実行することで実現可能である。
【００３０】
入力手段１０１は、多変量データとシーケンスデータとを入力する。多変量データは、２以上の属性を変量とするデータである。シーケンスデータは、多変量データに対応したデータであり、多変量データの２以上のキー（属性）に関連する情報が時系列に並んだデータである。多変量データは、例えば、顧客と商品とを変量とし、顧客が商品を購入したか否かを示すデータとする。シーケンスデータは、例えば、顧客がある商品を購入したというデータ点に対応して、顧客がこれまでにその商品を購入したということに関する履歴を時系列で並べた履歴データとする。
【００３１】
双方向クラスタリング手段１０２は、入力データに対し双方向クラスタリングを行う。双方向クラスタリング手段１０２は、評価関数を用いて、多変量データを複数のクラスタに分割する。評価関数は、多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで、共通した特徴が多いか少ないかを表す関数である。双方向クラスタリング手段１０２は、例えば、評価関数が共通した特徴が多くなるほど値が小さくなる関数であるとすれば、クラスタごとに計算した評価関数の値の総和が小さくなるように、クラスタ分割を行う。出力手段１０４は、双方向クラスタリング結果を出力する。
【００３２】
クラスタ数算出手段１０３は、双方向クラスタリングにおけるクラスタ分割数を決定する。クラスタ数算出手段１０３は、初回のクラスタリングでは、クラスタ分割数として所定の初期値を出力する。双方向クラスタリング手段１０２は、初回のクラスタリングでは、入力データを、所定の初期値の数のクラスタに分割する。クラスタ数算出手段１０３は、双方向クラスタリング手段１０２がクラスタリングを行うと、評価関数の値に基づいて、クラスタ分割数を増加させるか否かを決定する。双方向クラスタリング手段１０２は、クラスタ数算出手段１０３がクラスタ分割数を増加させると、そのクラスタ分割数でクラスタ分割を再度行う。
【００３３】
図２は、動作手順を示している。入力手段１０１は、多変量データとシーケンスデータとを入力する（ステップＡ１）。図３は、入力データの一例を示している。この例では、多変量データは、誰がどの商品を買ったかを表すデータである。多変量データの変量は、「顧客」と、「商品」との２つである。多変量データの各データに対して、商品購入の曜日履歴のデータ（シーケンスデータ）が付加されている。シーケンスデータは、ｙｉｋで表現する。シーケンスデータｙｊｋは、顧客ｊが、過去に商品ｋを購入した曜日を時系列で並べたデータである。
【００３４】
なお、顧客が商品を購入したという情報は、所定の期間ごとに求めることができる。所定の期間は、例えば一月単位とする。図３では、顧客Ｂが商品２を購入したというデータが２つあるが、これは、顧客Ｂが商品２を購入した期間が異なるためである。例えば、２つの購入データのうちの一方は、顧客Ｂが商品２を先月購入したというデータに対応し、他方は、顧客Ｂが商品２を先々月購入したというデータに対応している。また、シーケンスデータｙ１２Ｂは、顧客Ｂが商品２を購入した先々月の購入曜日履歴を表し、ｙ２２Ｂは、顧客Ｂが商品２を購入した先々月の購入曜日履歴を表している。
【００３５】
図４は、入力データをテーブル形式（行列形式）で示している。図３に示す入力データを、行列で表すと、図４に示すようになる。入力データの行列を、Ｄで表す。行列Ｄの行は顧客を表し、列は商品を表す。行列Ｄの各要素は、０又は１の値を取る。０は商品を購入していないことを表し、１は商品を購入したことを表す。シーケンスデータは、顧客が商品を購入したことを表すデータ点に付加される。シーケンスデータは、１つのデータ点に対して１つとは限らず、１つのデータ点に複数のシーケンスデータが対応することもあり得る。
【００３６】
双方向クラスタリング手段１０２は、クラスタ数算出手段１０３から、多変量データの各変量について、クラスタ分割数を受け取る。双方向クラスタリング手段１０２は、例えば、変量が２つであるとき、クラスタ数算出手段１０３から、各変量のクラスタ分割数ｋ、ｌを受け取る。双方向クラスタリング手段１０２は、シーケンスデータを考慮しつつ、多変量データを双方向クラスタリングする（ステップＡ２）。双方向クラスタリング手段１０２は、多変量データをｋ×ｌのクラスタに分割する。双方向クラスタリング手段１０２は、例えば、クラスタ分割数の初期値として、ｋ＝２、ｌ＝２を受け取り、多変量データを４つのクラスタに分割する。
【００３７】
双方向クラスタリング手段１０２は、評価関数を用いてクラスタリングを行う。評価関数には、各クラスタに属するデータが共通した特徴を持っていない度合いを計算する関数を用いる。入力データを双方向クラスタリングしたとき、各クラスタに属するデータが共通した特徴を持つほど、評価関数の値は小さくなる。逆に、各クラスタに属するデータが共通した特徴を持たないほど、評価関数の値は大きくなる。双方向クラスタリング手段１０２は、評価関数を小さくするようなクラスタ分割を行う。
【００３８】
シーケンスデータを考慮した双方向クラスタリングで用いる評価関数について説明する。分割されたクラスタを、Ｄｉｊ（ｉ＝１〜ｋ、ｊ＝１〜ｋ）で表す。クラスタリングのコストは、下記式１で定義する。
【数１】
式１にて、Ｃ（Ｄｉｊ）は、評価関数を用いて計算されるクラスタＤｉｊのコストを表す。コストＴは、各クラスタＤｉｊのコストの総和である。
【００３９】
コストには、ＭＤＬ（Minimum Description Length）という基準を用いる。各クラスタのコストＣ（Ｄｉｊ）は、下記式２で定義する。
【数２】
ここで、ｕは、多変量データが取る値である。図４の例では、ｕは、０又は１を取る。ｎｕは、クラスタＤｉｊに属するｕの値の個数を表す。ｎ（Ｄｉｊ）は、クラスタに属するデータ点の数である。すなわち、
である。なお、式２において、ｎｕ（Ｄｉｊ）＝０のときは、
【数３】
と定義する。
【００４０】
式２で定義される関数が、評価関数に該当する。式２において、第１項は、クラスタＤｉｊに含まれる多変量データの類似度が高いほど値が小さくなり、第２項（コストＤＬ（ｙ（Ｄｉｊ）））は、クラスタＤｉｊに含まれるシーケンスデータの類似度合が高いほど値が小さくなる。コストＤＬ（ｙ（Ｄｉｊ））は、下記式３で定義する。
【数４】
ここで、｜Ｄｉｊ｜は、クラスタＤｉｊに属するシーケンスデータの総数を表す。ｍは、ｌｏｇの底である。＾θは、ｙ（Ｄｉｊ）をモデルで表すときのパラメータである。モデルには、シーケンスデータをモデル化する方法として広く利用されているＨＭＭ（Hidden Markov Model）やMarkov Model等の確率モデルを用いることができる。Ｒは、＾θに含まれるパラメータの数を表す。
【００４１】
コストＣ（Ｄｉｊ）は、クラスタＤｉｊに含まれる多変量データとシーケンスデータとの共通した特徴が多いか少ないかを表す。コストＣ（Ｄｉｊ）の値が小さいほど、共通した特徴が多く、値が大きいほど、共通した特徴が少ない。なお、クラスタＤｉｊの属する多変量データが全て同じ値のときは、式２における第１項の値は０となる。その場合、コストＣ（Ｄｉｊ）は、ＤＬ（ｙ（Ｄｉｊ））のみで決まる。例えば、図４で、ｕ＝１のデータ点のみで構成されるクラスタのコストは、クラスタに属するデータ点のシーケンスデータの類似度に応じた値のみで決まる。なお、ｕ＝０のデータ点のみで構成されるクラスタのコストは、シーケンスデータがないことから０となる。
【００４２】
クラスタ数算出手段１０３は、双方向クラスタリング手段１０２がクラスタ分割を行うと、クラスタ分割結果と評価関数とを用いて、クラスタ数を増加するか否かを決定する（ステップＡ３）。クラスタ数算出手段１０３は、例えば、式１で定義されるコストＴの値が所定のしきい値を上回るか否かを判断する。クラスタ数算出手段１０３は、コストＴの値がしきい値を上回るときは、クラスタ数を増加すると決定する。
【００４３】
クラスタ数算出手段１０３にて、クラスタ数を増加させるか否かの判断手法は、特に上記したものには限定されない。例えば、以下のように判断してもよい。クラスタＤｉｊに属する多変量データとシーケンスデータとのから、どれか１つのデータ点を取り除く。データ点を１つ取り除いたクラスタをＤ’ｉｊとする。クラスタ数算出手段１０３は、データ点を取り除く前後のコスト、Ｃ（Ｄｉｊ）とＣ（Ｄ’ｉｊ）を計算し、両者を比較する。クラスタ数算出手段１０３は、Ｃ（Ｄｉｊ）＞Ｃ（Ｄ’ｉｊ）となるデータ点が存在する場合は、クラスタ数を増加すると決定する。
【００４４】
クラスタ数算出手段１０３は、クラスタ数を増加させると決定すると、双方向クラスタリング手段１０２に、増加後のクラスタ数を通知する。クラスタ数算出手段１０３は、例えば、現在のクラスタ数をｋ、ｌとして、ｋ＋１とｌ、ｋとｌ＋１、又は、ｋ＋１とｌ＋１を、新たなクラスタ数として双方向クラスタリング手段１０２に通知する。その後、ステップＡ３からステップＡ２へ戻り、双方向クラスタリング手段１０２は、入力データを、通知されたクラスタ数にクラスタ分割する。ステップＡ２とステップＡ３とを繰り返し行うことで、適切な分割数のクラスタを得ることができる。
【００４５】
出力手段１０４は、ステップＡ３で、クラスタ数算出手段１０３がクラスタ数を増加させないと決定すると、双方向クラスタリング手段１０２が行った双方クラスタリングの結果を出力する（ステップＡ４）。出力手段１０４は、例えば、クラスタ分割で得られた各クラスタＤｉｊについて、各クラスタに属するデータ点の情報を、ディスプレイ等の出力装置に表示する。
【００４６】
図５は、初期クラスタリングの結果を示している。双方向クラスタリング手段１０２が、入力データ（図４）を初期クラスタ数（ｋ＝２、ｌ＝２）のクラスタに分割することで、図５に示す４つのクラスタＤ１１、Ｄ１２、Ｄ２１、Ｄ２２が得られる。各クラスタについて、コストを計算すると、
Ｃ（Ｄ１１）＝４ｌｏｇ（６／４）＋２ｌｏｇ（６／２）＋ＤＬ（ｙ１１Ａ、ｙ１２Ｂ、ｙ２２Ｂ）＝１．６６＋ＤＬ（ｙ１１Ａ、ｙ１２Ｂ、ｙ２２Ｂ）
Ｃ（Ｄ１２）＝５２ｌｏｇ（５４／５２）＋２ｌｏｇ（５４／２）＋ＤＬ（ｙ１５Ａ、ｙ１２８Ｂ）＝３．７２＋ＤＬ（ｙ１５Ａ、ｙ１２８Ｂ）
Ｃ（Ｄ２１）＝７ｌｏｇ（９／７）＋２ｌｏｇ（９／２）＋ＤＬ（ｙ１１Ｄ、ｙ１２Ｅ）＝２．０７＋ＤＬ（ｙ１１Ｄ、ｙ１２Ｅ）
Ｃ（Ｄ２２）＝７８ｌｏｇ（８１／７８）＋３ｌｏｇ（８１／３）＋ＤＬ（ｙ１５Ｄ、ｙ２２８Ｅ、ｙ１３０Ｃ）＝５．５７＋ＤＬ（ｙ１５Ｄ、ｙ２２８Ｅ、ｙ１３０Ｃ）
となる。全体のコストＴは、
Ｔ＝Ｃ（Ｄ１１）＋Ｃ（Ｄ１２）＋Ｃ（Ｄ２１）＋Ｃ（Ｄ２２）
＝１３．０２＋ＤＬ（ｙ１１Ａ、ｙ１２Ｂ、ｙ２２Ｂ）＋ＤＬ（ｙ１５Ａ、ｙ１２８Ｂ）＋ＤＬ（ｙ１１Ｄ、ｙ１２Ｅ）＋ＤＬ（ｙ１５Ｄ、ｙ２２８Ｅ、ｙ１３０Ｃ）
となる。
【００４７】
図６は、最終的に得られたクラスタリング結果を示している。ステップＡ２、Ａ３を繰り返し行うことで、「顧客」方向のクラスタ分割数は２に、「商品」方向のクラスタ分割数は３になり、最終的に、図６に示す６個のクラスタＤ１１〜Ｄ１３、Ｄ２１〜Ｄ２３が得られたとする。図６に示すＤ１１〜Ｄ１３、Ｄ２１〜Ｄ２３について、各クラスタのコストを計算すると、
Ｃ（Ｄ１１）＝１ｌｏｇ（４／１）＋３ｌｏｇ（４／３）＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ）＝０．９７７＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ）
Ｃ（Ｄ１２）＝０
Ｃ（Ｄ１３）＝０
Ｃ（Ｄ２１）＝０
Ｃ（Ｄ２２）＝３ｌｏｇ（９／３）＋６ｌｏｇ（９／６）＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）＝２．４８＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）
Ｃ（Ｄ２３）＝０
となる。全体のコストＴは、
Ｔ＝ΣＣ（Ｄｉｊ）＝３．４６＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ）＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）
となる。
【００４８】
図５に示すクラスタリング結果におけるコストＴと、図６に示すクラスタリング結果におけるコストＴとを比較すると、ＤＬの値（シーケンスデータの類似度）を除いて、評価関数の値が下がっていることが確認できる。すなわち、評価関数に基づいて双方向クラスタリングを行うことで、多変量データと多変量データに対応したシーケンスデータを、各変量間及びシーケンスデータ間で共通の特徴を持つクラスタに分割できる。なお、コストＴは、上記したものには限定されず、双方向クラスタリングに必要な他のコストを含んでいてもよい。
【００４９】
比較例として、シーケンスデータを考慮しない双方向クラスタリングを考える。多変量データとして、２変量データを考える。変量の１つは顧客で、もう１つは商品とする。図７（ａ）に、多変量データを示す。顧客は、Ａ、Ｂ、Ｃの値を取り、商品は１、２、３の値を取る。多変量データの値は、顧客が商品を購入したか否かを表す。例えば、顧客Ａが商品１を購入したとき、顧客Ａと商品１とに対応するデータ点の値は１となる。
【００５０】
図７（ａ）に示す多変量データに対して、顧客及び商品の双方向でクラスタリングを行うと、図７（ｂ）のクラスタリング結果が得られる。この場合、クラスタ分割数は４である。多変量データに対して双方向クラスタリングを行うことで、顧客Ａ、Ｃが、商品１、３を購入するというデータ点から成るクラスタと、顧客Ｂが商品２を購入するというデータ点から成るクラスタとが得られる。このクラスタリング結果から、顧客Ａ、Ｃが、商品１、３と共通した特徴を持ち、顧客Ｂは商品２と共通した特徴を持つことがわかる。
【００５１】
図８は、多変量データとシーケンスデータとを双方向クラスタリングする例を示している。図８（ａ）は、シーケンスデータが付加された多変量データを示している。シーケンスデータは、例えば、顧客が、過去に商品を購入した曜日を示すデータから成る。シーケンスデータは、顧客が商品を購入したことを示すデータ点、すなわち、値が１のデータ点に添付される。
【００５２】
図８（ａ）に示す多変量データを、顧客、商品のみでなく、シーケンスデータを考慮して双方向クラスタリングすると、図８（ｂ）に示すクラスタリング結果が得られる。この場合、クラスタ分割数は６となる。シーケンスデータも考慮して双方向クラスタリングを行うことで、顧客Ａ、Ｃが、商品１を購入するというデータ点から成るクラスタと、顧客Ａ、Ｃが商品３を購入するというデータ点から成るクラスタと、顧客Ｂが商品２を購入するというデータ点から成るクラスタとが得られる。
【００５３】
図８（ｂ）に示す双方向クラスタリング結果から、顧客Ａ、Ｃは、商品１を同じような購入曜日履歴で購入していることが読み取れる。また、顧客Ａ、Ｃは、商品３を同じような購入曜日履歴で購入していることが読み取れる。顧客Ａ、Ｃは、共に商品１及び商品３を購入しているものの、商品１と商品３とが同じクラスタに分類されなかったことから、商品１と商品３とでは、購入曜日履歴が異なるということを読み取ることができる。つまり、顧客Ａ、Ｃは、商品１を、商品３と同じような曜日間隔で購入していないことが読み取ることができる。商品２については、顧客Ｂが商品２を購入する曜日履歴は、商品１、３の購入曜日履歴とは異なっていることを読み取ることができる。
【００５４】
本実施形態では、双方向クラスタリング手段１０２は、多変量データとシーケンスデータとに対して双方向クラスタリングを行う。評価関数として、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用い、双方向クラスタリングを行うことで、多変量データと多変量データに対応したシーケンスデータとを、各変量間、及び、シーケンスデータ間でそれぞれ共通の特徴をもつクラスタに同時に分割することができる。
【００５５】
また、本実施形態では、双方向クラスタ分割装置１００は、クラスタ数算出手段１０３を有する。クラスタ数算出手段１０３は、評価関数に基づいてクラスタリング結果が適切であるか否かを判断し、よりよいクラスタリング結果を得るために、クラスタ分割数を増加させる。クラスタリングに際して、いくつのクラスタに分割すればよいかは、事前にわからないことが多い。本実施形態では、クラスタ数算出手段１０３が、動的にクラスタ数を決定することで、事前に、何個のクラスタに分割すればよいかがわからないときでも、多変量データを、適切な分割数で、クラスタ分割することができる。
【００５６】
図９は、本発明の第２実施形態に係る広告配信システムを示している。広告配信システムは、双方向クラスタ分割装置１００とＷｅｂサーバ３００とを有する。双方向クラスタ分割装置１００の構成は、図１に示す第１実施形態における双方向クラスタ分割装置の構成と同様である。Ｗｅｂサーバ３００は、ユーザ端末２００と、インターネット４００などのネットワークを介して接続している。ユーザ端末２００は、ユーザに対して、入出力等のインターフェースを提供する。ユーザ端末２００は、例えば、パーソナルコンピュータや携帯型の情報端末装置である。
【００５７】
広告配信システムは、ユーザがＷｅｂコンテンツをリクエストした際に、ユーザがリクエストしたコンテンツに広告を付け加えてユーザに配信する。広告は、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む。より具体的には、広告には、広告主が誘導したいサイトのリンクが含まれており、ユーザが広告をクリックすることで、ユーザが広告主などのサイトを訪問できるようになっている。広告主は、例えば、商品やサービスの詳細情報を掲載したＷｅｂページへのリンクを広告に含め、ユーザを、そのＷｅｂページに誘導する。
【００５８】
ここで、ユーザにコンテンツに付随して広告を配信しても、その広告がユーザの好みと異なれば、ユーザが広告をクリックする可能性は低く、ユーザを訪問させたいサイトに誘導することができる可能性が低くなる。広告主は、ユーザが広告をクリックしなければ、広告配信の効果を得ることが難しい。従って、広告配信システムでは、ユーザの好みに合致した広告を正確に予測することが重要になる。
【００５９】
Ｗｅｂサーバ３００は、双方向クラスタ分割装置１００に対し、多変量データ及びシーケンスデータを与える。双方向クラスタ分割装置１００は、多変量データと、シーケンスデータとに対して双方向クラスタリングを行う。Ｗｅｂサーバ３００は、双方向クラスタ分割装置１００から双方向クラスタリング結果を受け取る。Ｗｅｂサーバ３００は、双方向クラスタリング結果を用いて、Ｗｅｂコンテンツをリクエストしたユーザに、ユーザの好みに対応した広告を配信する。本実施形態は、協調フィルタリングやコラボレーティブフィルタリングという分野に当てはまる。
【００６０】
図１０は、ユーザ端末２００を示している。ユーザ端末２００は、コンテンツリクエスト手段２０１と、コンテンツ表示手段２０２とを有する。コンテンツリクエスト手段２０１は、ユーザが閲覧を希望するコンテンツを、Ｗｅｂサーバ３００にリクエストする。コンテンツ表示手段２０２は、Ｗｅｂサーバ３００から、ユーザがリクエストしたコンテンツを取得し、表示する。ユーザ端末２００内の各部の機能は、コンピュータが所定のプログラムに従って動作することで実現可能である。
【００６１】
コンテンツリクエスト手段２０１は、例えば、ユーザがスポーツのコンテンツを希望するときは、Ｗｅｂサーバ３００にスポーツのコンテンツをリクエストする。また、コンテンツリクエスト手段２０１は、ユーザが、コンテンツに付随して配信された広告をクリックすると、Ｗｅｂサーバ３００に、その広告に対応するコンテンツをリクエストする。
【００６２】
図１１は、Ｗｅｂサーバ３００を示している。Ｗｅｂサーバ３００は、コンテンツ配信手段３０１、ユーザリクエスト記憶部３０２、コンテンツ記憶部３０３、広告選択手段３０４、広告記憶部３０５、リクエスト受付手段３０６、クラスタリング制御手段３０７、出力装置３０８、入力装置３０９、及び、クラスタリング結果記憶部３１０を有する。Ｗｅｂサーバ３００内の各部の機能は、コンピュータが所定のプログラムに従って動作することで実現可能である。
【００６３】
リクエスト受付手段３０６は、ユーザからのリクエストを受け付ける。ユーザからのリクエストには、所望のＷｅｂページの取得を要求するリクエストと、Ｗｅｂ広告に対応するＷｅｂページの取得を要求するリクエストとがある。ユーザリクエスト記憶部３０２は、ユーザからのリクエストに関する情報を記憶する。リクエスト受付手段３０６は、例えば、ユーザ名、リクエストの内容、リクエストの時刻を、ユーザリクエスト記憶部３０２に記憶する。
【００６４】
コンテンツ記憶部３０３は、ユーザに配信すべきコンテンツを記憶する。広告記憶部３０５は、Ｗｅｂ広告を記憶する。コンテンツ配信手段３０１は、コンテンツ記憶部３０３から、ユーザがリクエストしたコンテンツを取得し、ユーザに配信する。その際、コンテンツ配信手段３０１は、コンテンツに広告記憶部３０５が記憶するＷｅｂ広告を付け加えて、ユーザにコンテンツを配信する。なお、コンテンツ配信手段３０１は、ユーザがリクエストしたコンテンツがコンテンツ記憶部３０３にない場合は、外部サーバにリクエストを転送してもよい。また、ユーザがリクエストしたコンテンツが広告に対応したＷｅｂページである場合、コンテンツ配信手段３０１は、コンテンツにＷｅｂ広告を付け加えなくてもよい。
【００６５】
クラスタリング制御手段３０７は、データ生成手段を兼ねている。クラスタリング制御手段３０７は、双方向クラスタ分割装置１００に与えるデータの生成と、双方向クラスタ分割装置１００が行う双方向クラスタリングの制御を行う。クラスタリング制御手段３０７は、例えば、Ｗｅｂサーバ３００への全アクセス回数が所定のしきい値を越えると、ユーザリクエスト記憶部３０２から、全ユーザの過去のコンテンツ訪問履歴を読み出す。クラスタリング制御手段３０７は、読み出した情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成する。ユーザは、広告をクリックすることで、広告主のコンテンツをリクエストするので、多変量データは、ユーザがどの広告をクリックしたかを示すデータを表していることになる。
【００６６】
また、クラスタリング制御手段３０７は、多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成する。以下では、ユーザが送信したリクエストを時系列で並べたデータを、コンテンツ訪問履歴とも呼ぶ。クラスタリング制御手段３０７は、どのユーザがどの広告をクリックしたかを示す多変量データと、広告をクリックするまでのコンテンツ訪問履歴（シーケンスデータ）とを、出力装置３０８に渡すと共に、双方向クラスタ分割装置１００に双方向クラスタリングを依頼する。
【００６７】
双方向クラスタ分割装置１００は、どのユーザがどの広告をクリックしたかを示す多変量データと、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とを、出力装置３０８を介して入力する。双方向クラスタ分割装置１００は、多変量データと、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とに対して、双方向クラスタリングを行う。双方向クラスタ分割装置１００は、双方向クラスタリング結果をＷｅｂサーバ３００に出力する。
【００６８】
入力装置３０９は、双方向クラスタ分割装置１００から、双方向クラスタリング結果を入力し、クラスタリング結果記憶部３１０に渡す。クラスタリング結果記憶部３１０は、入力装置３０９から受け取った双方向クラスタリング結果を記憶する。広告選択手段３０４は、クラスタリング結果記憶部３１０を参照し、双方向クラスタリング結果に基づいて、ユーザに配信すべきＷｅｂ広告を決定する。広告選択手段３０４は、広告記憶部３０５からＷｅｂ広告を読み出し、コンテンツ配信手段３０１に与える。
【００６９】
以下、動作手順を説明する。広告配信システムの動作は、大きく分けて、双方向クラスタリング処理と、双方向クラスタリング結果を用いた広告配信処理との２つある。図１２は、双方向クラスタリング処理の手順を示している。ユーザがコンテンツを要求すると、ユーザ端末２００のコンテンツリクエスト手段２０１は、Ｗｅｂサーバ３００に、コンテンツをリクエストする（ステップＢ１）。ユーザは、あらかじめ属性情報が判明しているユーザであり、Ｗｅｂサーバ３００は、どのユーザからのコンテンツリクエストであるかを判別可能であるとする。
【００７０】
Ｗｅｂサーバ３００のリクエスト受付手段３０６は、ユーザからのリクエストを受け付ける。リクエスト受付手段３０６は、ユーザ名、リクエストの内容、及び、時刻を、ユーザリクエスト記憶部に記憶する（ステップＢ２）。また、リクエスト受付手段３０６は、ユーザからのリクエストをコンテンツ配信手段３０１に渡す。
【００７１】
コンテンツ配信手段３０１は、コンテンツ記憶部３０３からリクエストに対応するコンテンツを読み出す。また、コンテンツ配信手段３０１は、広告選択手段３０４からＷｅｂ広告を受け取る。コンテンツ配信手段３０１は、コンテンツ記憶部３０３から読み出したコンテンツにＷｅｂ広告を付加して、ユーザ端末２００に送信する（ステップＢ３）。ユーザ端末２００のコンテンツ表示手段２０２は、受信したコンテンツを表示する（ステップＢ４）。
【００７２】
クラスタリング制御手段３０７は、Ｗｅｂサーバ３００への全アクセス回数が所定のしきい値を超えたか否かを判断する。クラスタリング制御手段３０７は、全アクセス回数がしきい値を超えたと判断すると、ユーザリクエスト記憶部３０２から、全ユーザの過去のコンテンツ訪問履歴を読み出す（ステップＢ５）。クラスタリング制御手段３０７は、読み出したコンテンツ訪問履歴に基づいて、どのユーザがどの広告をクリックしたかを示す多変量データと、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とを生成する。クラスタリング制御手段３０７は、生成した多変量データ、及び、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とを、双方向クラスタ分割装置１００に出力する（ステップＢ６）。
【００７３】
双方向クラスタ分割装置１００の双方向クラスタリング手段１０２（図１）は、入力手段１０１を介して、多変量データと、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とを入力する。双方向クラスタリング手段１０２は、多変量データと、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴とに対し、双方向クラスタリングを行う（ステップＢ７）。双方向クラスタリングの手順は、図２に示す手順と同様である。
【００７４】
双方向クラスタリング手段１０２は、出力手段１０４を介して、Ｗｅｂサーバ３００に双方向クラスタリング結果を送信する（ステップＢ８）。Ｗｅｂサーバ３００の入力装置３０９は、双方向クラスタリング結果を受け取ると、受け取った双方向クラスタリング結果をクラスタリング結果記憶部３１０に記憶する。クラスタリング結果記憶部３１０は、双方向クラスタリング得結果を記憶する（ステップＢ９）。
【００７５】
図１３は、双方向クラスタリング手段１０２の入力データを示している。多変量データの変量は、「ユーザ」と、「Ｗｅｂ広告」との２つである。コンテンツ訪問履歴は、ユーザが広告をクリックするまでのリクエストを時系列で並べたシーケンスデータである。コンテンツ訪問履歴は、例えば、ユーザが広告をクリックしたその日に、ユーザが最初に送信したリクエストから、広告をクリックする直前のリクエストまでを時系列に並べたものである。或いは、コンテンツ訪問履歴は、ユーザが広告をクリックした時点から１０個前までのリクエストを時系列に並べたものでもよい。コンテンツ訪問履歴の定義は、特に上記したものに限定されるわけではない。
【００７６】
コンテンツ訪問履歴（シーケンスデータ）は、ｙｉｊｋで表す。ｙｉｊｋは、ユーザｋが広告ｊをクリックしたというデータ点に対応したシーケンスデータであり、ユーザｋが広告ｊをクリックするまでに送信したリクエストを時系列で並べたコンテンツ訪問履歴である。ｉは、ユーザが広告をクリックしたのが何回目であるかを表している。例えば、ｙ１ｊｋは、ユーザｋが広告ｊをクリックするのが１回目のときのコンテンツ訪問履歴を表し、ｙ２ｊｋは、ユーザｋが広告ｊをクリックするのが２回目のときのコンテンツ訪問履歴を表している。
【００７７】
図１４は、入力データをテーブル形式（行列形式）で示している。図１３に示す入力データを、行列で表すと、図１４に示すようになる。入力データの行列を、Ｄで表す。行列Ｄの行はユーザを表し、列はＷｅｂ広告を表す。行列Ｄの各要素は、０又は１の値を取る。０はユーザが広告をクリックしていないことを表し、１はユーザが広告をクリックしたことを表す。シーケンスデータは、１つのデータ点に対して１つとは限らず、１つのデータ点に複数のシーケンスデータが対応することもあり得る。
【００７８】
図１５は、双方向クラスタリング手段１０２のクラスタリング結果を示している。双方向クラスタリング手段１０２は、図１４に示す多変量データ及びシーケンスデータに対して双方向クラスタリングを行うことで、入力データを、図１５に示す６個のクラスタＤ１１〜Ｄ１３、Ｄ２１〜Ｄ２３に分割する。
【００７９】
図１５に示すＤ１１〜Ｄ１３、Ｄ２１〜Ｄ２３について、各クラスタのコストを計算すると、
Ｃ（Ｄ１１）＝１ｌｏｇ（４／１）＋３ｌｏｇ（４／３）＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ）＝０．９７７＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ）
Ｃ（Ｄ１２）＝０．０
Ｃ（Ｄ１３）＝０．０
Ｃ（Ｄ２１）＝０．０
Ｃ（Ｄ２２）＝３ｌｏｇ（９／３）＋６ｌｏｇ（９／６）＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）＝２．４８＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）
Ｃ（Ｄ２３）＝０．０
となる。全体のコストＴは、
Ｔ＝ΣＣ（Ｄｉｊ）＝３．４６＋ＤＬ（ｙ１１Ａ、ｙ１５Ａ、ｙ１１Ｄ、ｙ１５Ｄ）＋ＤＬ（ｙ１２Ｂ、ｙ２２Ｂ、ｙ１２８Ｂ、ｙ１２Ｅ、ｙ２２８Ｅ、ｙ１２Ｃ、ｙ１３０Ｃ）
となる。
【００８０】
続いて、双方向クラスタリング結果を用いた広告配信処理を説明する。図１６は、広告配信処理の手順を示している。ユーザ端末２００のコンテンツリクエスト手段２０１は、Ｗｅｂサーバ３００にコンテンツをリクエストする（ステップＣ１）。リクエスト受付手段３０６は、ユーザ端末２００からのリクエストを受け付ける。ユーザリクエスト記憶部３０２は、リクエスト受付手段３０６が受け付けたリクエストを記憶する（ステップＣ２）。
【００８１】
コンテンツ配信手段３０１は、リクエスト受付手段３０６からリクエストを受け取る。コンテンツ配信手段３０１は、リクエストを送信したユーザを識別する情報、例えばユーザ名を広告選択手段３０４に渡す（ステップＣ３）。広告選択手段３０４は、クラスタリング結果記憶部３１０から、ユーザが属するクラスタの情報を読み出す（ステップＣ４）。クラスタリング結果記憶部３１０は、ステップＣ４では、ユーザが所属するクラスタに所属するユーザのユーザ名と、所属クラスのユーザがクリックしたＷｅｂ広告を識別する情報とを読み出す。
【００８２】
広告選択手段３０４は、ステップＣ４で読み出した情報に基づいて、コンテンツをリクエストしたユーザに配信すべきＷｅｂ広告を決定する（ステップＣ５）。広告選択手段３０４は、同じクラスタに所属するユーザがクリックした広告を、ユーザに配信する広告の候補とし、その候補の中から、ユーザに配信する広告を決定する。広告選択手段３０４は、広告の決定では、他のユーザはクリックしたが、コンテンツをリクエストしたユーザがクリックしていない広告があるときは、その広告を、優先的に、ユーザに配信する広告として決定する。
【００８３】
図１７は、広告配信候補を示している。クラスタ分割結果として、図１５に示すクラスタ分割結果が得られているとき、各ユーザに配信すべき広告の候補は、図１７に示すようになる。図１７において、Ｗｅｂ広告配信候補の並び順は、優先順位が高い順とする。例えば、クラスタＤ１１を考える。図１５を参照すると、このクラスタに所属するユーザは、ユーザＡとユーザＤの二人である。また、ユーザＡは、広告１と広告５とをクリックし、ユーザＤは、広告１をクリックしている。
【００８４】
同じクラスタに所属するユーザは、Ｗｅｂ広告に関して好みが似通っていており、そのクラスタに属するＷｅｂ広告群に興味があると考えられる。また、双方向クラスタ分割装置１００は、どのＷｅｂページにアクセスしてから広告をクリックしたかというシーケンスデータも用いて双方向クラスタリングを行うので、同じクラスタに所属するユーザは、コンテンツ訪問履歴に関しても、共通した特徴が多く持つと考えられる。このため、コンテンツをリクエストしたユーザに対して、同じクラスタに所属するユーザのうちの少なくとも一人がクリックしたことがある広告を配信すれば、広告の配信を受けたユーザは、その広告をクリックすると予測できる。
【００８５】
クラスタＤ１１に所属するユーザは、広告１と広告５とをクリックしたことがあるので、ユーザＡとユーザＤとに配信する広告の候補は、広告１と広告５とする。ユーザＤは、広告５をクリックしたことがないので、広告選択手段３０４は、広告５の優先順位を広告１の優先順位よりも高くする。広告選択手段３０４は、優先順位に従って、広告５、広告１の順で、ユーザＤに配信すべき広告を決定する。ユーザＡは、広告１と広告５とをクリックしているので、特に優先順位はない。広告選択手段３０４は、ユーザＡに対しては、広告１と広告５との何れかを、ランダムに、ユーザＡに配信すべき広告として決定すればよい。
【００８６】
図１６に戻り、広告選択手段３０４は、配信する広告を決定すると、広告記憶部３０５からＷｅｂ広告を読み出し、コンテンツ配信手段３０１に与える。広告選択手段３０４は、決定したＷｅｂ広告を識別する情報をコンテンツ配信手段３０１に渡し、コンテンツ配信手段３０１が、広告記憶部３０５からＷｅｂコンテンツを読み出してもよい。
【００８７】
コンテンツ配信手段３０１は、コンテンツ記憶部３０３から、ユーザがリクエストしたコンテンツを読み出す（ステップＣ６）。コンテンツ配信手段３０１は、広告選択手段３０４が決定したＷｅｂ広告を、読み出したコンテンツに付け加える（ステップＣ７）。コンテンツ配信手段３０１は、Ｗｅｂ広告を付け加えたＷｅｂコンテンツを、ユーザ端末２００に送信する（ステップＣ８）。ユーザ端末２００のコンテンツ表示手段２０２は、コンテンツ配信手段３０１が送信した、Ｗｅｂ広告を含むＷｅｂコンテンツを表示する（ステップＣ９）。
【００８８】
図１８は、Ｗｅｂ広告が付加されたＷｅｂページを示している。コンテンツ配信手段３０１は、Ｗｅｂページ９０１内に、広告表示領域９０２を設け、その広告表示領域９０２内に、Ｗｅｂ広告を埋め込む。Ｗｅｂ広告の配信は、特にここで記載したものには限定されない。例えば、ＷｅｂコンテンツにＷｅｂ広告を埋め込まずに、Ｗｅｂコンテンツとは別に、Ｗｅｂ広告を配信する形でもよい。
【００８９】
本実施形態では、双方向クラスタ分割装置は、どのユーザがどのＷｅｂ広告をクリックしたかというデータを多変量データとし、ユーザがＷｅｂ広告をクリックするまでのコンテンツ訪問履歴をシーケンスデータとして、多変量データとシーケンスデータとに対し、双方向クラスタリングを行う。ユーザの特徴は、どのＷｅｂ広告をリクエストしたかという情報に加えて、どのようにＷｅｂ広告をクリックしたかという情報にも現れる。本実施形態では、多変量データとシーケンスデータとを同時に扱い、それらに対して双方向クラスタリングを行うので、ユーザの特徴や好みを、より正確に抽出できることが期待できる。また、そのような双方向クラスタリングを行った結果を用いて、ユーザに配信する広告を決定することで、ユーザが広告をクリックすることが期待できる。
【００９０】
図１９は、本発明の第３実施形態に係る商品推薦システムを示している。商品推薦システムは、サーバシステム６００を有する。サーバシステム６００は、双方向クラスタ分割装置１００と、データ生成手段６０１と、推薦商品リスト生成手段６０２と、クラスタリング結果記憶部６０３とを有する。サーバシステム６００は、クライアントシステム５０１〜５０３と、ネットワーク４０１を介して接続されている。クライアントシステム５０１〜５０３は、例えば、小売店に設置される売上管理システムである。サーバシステム６００は、小売店の情報を束ねる中央管理システムであり、データセンタなどに設置される。
【００９１】
クライアントシステム５０１〜５０３は、各店舗の売上情報を管理する。売上情報は、例えば、顧客名と、顧客が購入した商品名と、購入日時に関する情報とを含む。サーバシステム６００は、クライアントシステムからどの顧客がどの商品を購入したかを示すデータを含む顧客の購入情報を収集する。サーバシステム６００は、収集した情報を用いて双方向クラスタリングを行う。多変量データとしてこのような情報を用いる場合、双方向クラスタリング結果を、小売業のマーケティングなどに利用することができる。サーバシステム６００は、双方向クラスタリング結果を用いて、顧客に対して今後推薦する商品を決定する。サーバシステム６００は、推薦商品の情報を、各店舗のクライアントシステム５０１〜５０３に送信する。
【００９２】
データ生成手段６０１は、クライアントシステム５０１〜５０３から顧客の購入情報を収集する。データ生成手段６０１は、収集した顧客の購入情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成する。また、データ生成手段６０１は、多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータを生成する。ここでは、シーケンスデータは、顧客の商品購入曜日を時系列に並べた購入曜日履歴であるとする。
【００９３】
双方向クラスタ分割装置１００の構成は、図１に示す第１実施形態における双方向クラスタ分割装置の構成と同様である。双方向クラスタ分割装置１００は、データ生成手段６０１が生成した多変量データとシーケンスデータとに対して双方向クラスタリングを行う。双方向双方向クラスタ分割装置１００は、双方向クラスタリング結果を、クラスタリング結果記憶部６０３に記憶する。推薦商品リスト生成手段６０２は、クラスタリング結果記憶部６０３記憶するクラスタリング結果を用いて、顧客に推薦する商品のリストを生成する。
【００９４】
図２０は、動作手順を示している。クライアントシステム５０１〜５０３は、それぞれ、ネットワーク４０１を介して、サーバシステム６００に、顧客の購入情報を送信する（ステップＤ１）。サーバシステム６００は、各クライアントから、顧客の購入情報を受け取る。各クライアントがサーバシステム６００に顧客の購入情報を送信するタイミングは、クライアントごとに異なっていてもよい。
【００９５】
データ生成手段６０１は、どの顧客がどの商品を購入したかを示す多変量データと、顧客が商品を購入した曜日の履歴を示す購入曜日履歴とを生成する。データ生成手段６０１は、生成した多変量データと購入曜日履歴とを、双方向クラスタ分割装置１００に出力する（ステップＤ２）。
【００９６】
双方向クラスタ分割装置１００の双方向クラスタリング手段１０２（図１）は、入力手段１０１を介して、多変量データと、購入曜日履歴とを入力する。双方向クラスタリング手段１０２は、多変量データと、購入曜日履歴とに対し、双方向クラスタリングを行う（ステップＤ３）。双方向クラスタリングの手順は、図２に示す手順と同様である。双方向クラスタ分割装置１００は、双方向クラスタリング結果をクラスタリング結果記憶部６０３に送り、双方向クラスタリング結果を、クラスタリング結果記憶部６０３に記憶する（ステップＤ４）。
【００９７】
推薦商品リスト生成手段６０２は、双方向クラスタリング結果記憶部６０３から双方向クラスタリング結果を読み出し、顧客ごとの推薦商品リストを生成する（ステップＤ５）。推薦商品リスト生成手段６０２は、ステップＤ５では、クラスタごとに、そのクラスタに所属する顧客のうちの少なくとも一人が購入した商品を調べる。推薦商品リスト生成手段６０２は、顧客ごとに、当該顧客が所属するクラスタに所属する顧客のうちの少なくとも一人が購入した商品のうち、当該顧客が購入していない商品を、推薦商品リストに含める。
【００９８】
推薦商品リスト生成手段６０２は、推薦商品リストをクライアントシステム５０１〜５０３に送信する（ステップＤ６）。クライアントシステム５０１〜５０３は、各顧客に対する推薦商品リストを、サーバシステム６００から受信する（ステップＤ７）。
【００９９】
図２１は、双方向クラスタリング手段１０２の入力データを示している。多変量データの変量は、「顧客」と、「商品」との２つである。購入曜日履歴は、例えば１月単位で、顧客が商品を購入した曜日の履歴を時系列で並べたシーケンスデータである。図２２は、双方向クラスタリング結果を示している。双方向クラスタリング手段１０２が、図２１に示す入力データに対して双方向クラスタリングを行うことで、図２２に示す、２×３＝６つのクラスタが得られたとする。
【０１００】
図２３は、推薦商品リストを示している。クラスタ分割結果として、図２２に示すクラスタ分割結果が得られているとき、各顧客に推薦すべき商品のリスト（推薦商品候補）は、図２３に示すようになる。例えば、クラスタＤ１１を考える。図２２を参照すると、このクラスタに所属する顧客は、顧客Ａと顧客Ｄの二人である。また、顧客Ａは、商品１と商品５とを購入し、顧客Ｄは、商品１を購入している。
【０１０１】
本実施形態では、顧客、商品、購入曜日履歴に対して双方向クラスタリングを行っており、双方向クラスタリングを行うことで、同じ商品に興味があり、また、商品の購入曜日履歴も類似する顧客を、各クラスタに集めることができる。同じクラスタに所属する顧客は、購入商品に関して好みが似通っていており、また、商品を購入する曜日履歴も共通した特徴が多く含まれていると考えられる。従って、あるクラスタに属する商品に関連したお勧め商品を、そのクラスタに属する顧客に対してお勧めすると、顧客が商品を購入することが期待できる。
【０１０２】
推薦商品リスト生成手段６０２は、クラスタＤ１１に所属する顧客は、商品１と商品５とを購入しているので、顧客Ａと顧客Ｄとに推薦する商品を、商品１と商品５との中から選ぶ。顧客Ｄは、商品５を購入していないので、推薦商品リスト生成手段６０２は、顧客Ｄに推薦する商品を商品５と決定する。顧客Ａは、商品１と商品５とを既に購入しているので、推薦商品リスト生成手段６０２は、顧客Ａに推薦する商品はないと判断する。
【０１０３】
本実施形態では、双方向クラスタ分割装置１００は、どの顧客がどの商品を購入したかというデータを多変量データとし、顧客が商品を購入した曜日の履歴をシーケンスデータとして、多変量データとシーケンスデータとに対し、双方向クラスタリングを行う。顧客の特徴は、どの商品を購入したかという情報に加えて、どのような曜日履歴で商品を購入したかという情報にも現れる。本実施形態では、多変量データとシーケンスデータとを同時に扱い、それらに対して双方向クラスタリングを行うので、ユーザの特徴や好みを、より正確に抽出できることが期待できる。また、そのような双方向クラスタリングを行った結果を用いて、顧客に推薦する商品を決定することで、ユーザがその後購入することを期待できる商品を、推薦商品とすることができる。
【０１０４】
図２４は、本発明の第４実施形態に係る故障予測システムを示している。故障予測システムは、サーバシステム８００を有する。サーバシステム８００は、双方向クラスタ分割装置１００と、データ生成手段８０１と、故障予測候補リスト生成手段８０２と、クラスタリング結果記憶部８０３とを有する。サーバシステム８００は、クライアントシステム７０１〜７０３と、ネットワーク４０２を介して接続されている。クライアントシステム７０１〜７０３は、例えば、自動車販売店や修理工場に設置されている。サーバシステム８００は、中央管理システムであり、データセンタなどに設置される。
【０１０５】
クライアントシステム７０１〜７０３は、自動車の故障情報を管理する。故障情報は、車種と故障個所（故障部品）とを含む。例えば、各車種に対して、複数の地域で故障が起きており、クライアントシステム７０１〜７０３は、車種ごとに故障が起こった部品の故障履歴を蓄積しているとする。サーバシステム８００は、クライアントシステム７０１〜７０３から、故障情報を収集する。サーバシステム８００は、クライアントシステムから収集した情報を用いて、双方向クラスタリングを行う。サーバシステム８００は、双方向クラスタリング結果を用いて、故障予測を行い、予測結果をクライアントシステム７０１〜７０３に送信する。
【０１０６】
データ生成手段８０１は、クライアントシステム７０１〜７０３から車種ごとの故障情報を収集する。データ生成手段８０１は、収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に当該地域で故障が発生したか否かを示す多変量データを生成する。また、データ生成手段８０１は、多変量データに対応して、当該車種で故障が発生したことに関する履歴を時系列で並べたシーケンスデータを生成する。ここでは、シーケンスデータは、過去に故障が発生した部品を時系列に並べた故障部品履歴であるとする。
【０１０７】
双方向クラスタ分割装置１００の構成は、図１に示す第１実施形態における双方向クラスタ分割装置の構成と同様である。双方向クラスタ分割装置１００は、車種ごとの故障発生地域と、故障部品履歴とに対して双方向クラスタリングを行う。クラスタリング結果記憶部８０３は、双方向クラスタ分割装置１００のクラスタリング結果を記憶する。故障予測候補リスト生成手段８０２は、クラスタリング結果記憶部８０３が記憶するクラスタリング結果を用いて、車種と地域とに対して、今後故障が発生すると予測される部品のリストを生成する。
【０１０８】
図２５は、動作手順を示している。クライアントシステム７０１〜７０３は、それぞれ、ネットワーク４０２を介して、サーバシステム８００に、故障情報を送信する（ステップＥ１）。サーバシステム８００は、各クライアントから、故障情報を受け取る。クライアントシステム７０１〜７０３が管理する故障情報は地域が異なっており、サーバシステム８００は、どのクライアントから故障情報を受信したかに応じて、故障が発生した地域が判別可能であるとする。或いは、故障情報が地域に関する情報を含んでいてもよい。各クライアントがサーバシステム８００に故障情報を送信するタイミングは、クライアントごとに異なっていてもよい。
【０１０９】
データ生成手段８０１は、どの車種にどの地域で故障が発生しているかを示す多変量データと、当該車種で過去に故障が発生した部品の履歴を示す故障部品履歴とを生成する。データ生成手段８０１は、生成した多変量データと故障部品履歴とを、双方向クラスタ分割装置１００に出力する（ステップＥ２）。
【０１１０】
双方向クラスタ分割装置１００の双方向クラスタリング手段１０２（図１）は、入力手段１０１を介して、多変量データと、故障部品履歴とを入力する。双方向クラスタリング手段１０２は、多変量データと、故障部品履歴とに対し、双方向クラスタリングを行う（ステップＥ３）。双方向クラスタリングの手順は、図２に示す手順と同様である。双方向クラスタ分割装置１００は、双方向クラスタリング結果をクラスタリング結果記憶部８０３に送り、双方向クラスタリング結果を、クラスタリング結果記憶部８０３に記憶する（ステップＥ４）。
【０１１１】
故障予測候補リスト生成手段８０２は、双方向クラスタリング結果記憶部８０３から双方向クラスタリング結果を読み出し、車種ごとの故障予測候補リストを生成する（ステップＥ５）。故障予測候補リスト生成手段８０２は、ステップＥ５では、クラスタごとに、そのクラスタに所属する車種の少なくとも一つに故障が発生した地域を調べる。故障予測候補リスト生成手段８０２は、車種ごとに、当該車種が所属するクラスタに所属する車種のうちの少なくとも一つで故障が発生した地域のうち、当該顧客でまだ故障が発生していない地域を、故障予測候補リストに含める。
【０１１２】
故障予測候補リスト生成手段８０２は、故障予測候補リストをクライアントシステム７０１〜７０３に送信する（ステップＥ６）。クライアントシステム７０１〜７０３は、各顧客に対する故障予測候補リストを、サーバシステム８００から受信する（ステップＥ７）。
【０１１３】
図２６は、双方向クラスタリング手段１０２の入力データを示している。多変量データの変量は、「車種」と、「地域」との２つである。故障部品履歴は、例えば１年単位で、当該車種で故障が発生した部品の履歴を時系列で並べたシーケンスデータである。或いは、故障部品履歴は、故障発生以前に故障が発生した過去の故障部品を並べたものでもよい。図２７は、双方向クラスタリング結果を示している。双方向クラスタリング手段１０２が、図２６に示す入力データに対して双方向クラスタリングを行うことで、図２７に示す、２×３＝６つのクラスタが得られたとする。
【０１１４】
図２８は、故障予測候補リストを示している。クラスタ分割結果として、図２７に示すクラスタ分割結果が得られているとき、各車種に故障が発生すると予測される地域のリスト（故障発生地域候補）は、図２８に示すようになる。例えば、クラスタＤ１１を考える。図２７を参照すると、このクラスタに所属する車種は、車種Ａと車種Ｄの２つである。また、車種Ａは、地域１と地域５とで故障が発生しており、車種Ｄは、地域１で故障が発生している。
【０１１５】
本実施形態では、車種、地域、故障部品履歴に対して双方向クラスタリングを行っており、双方向クラスタリンを行うことで、同じ地域で故障が発生し、また、故障備品履歴も類似する車種を、各クラスタに集めることができる。同じクラスタに所属する車種は、故障発生地域が同じ傾向にあり、また、故障が発生した部品履歴も共通した特徴を多く含んでいると考えられる。従って、あるクラスタに属する車種は、今後、そのクラスタに所属する地域で故障が発生すると予測できる。
【０１１６】
故障予測候補リスト生成手段８０２は、クラスタＤ１１に所属する車種は、地域１と地域５とで故障が発生しているので、故障発生地域を、地域１と地域５との中から選ぶ。車種Ｄは、既に地域１で故障が発生しているので、故障予測候補リスト生成手段８０２は、車種Ｄで故障の発生が予測される地域を地域５と決定する。車種Ａは、既に地域１と地域５とで故障が発生しているので、故障予測候補リスト生成手段８０２は、車種Ａに今後故障が発生すると予測される地域はないと判断する。
【０１１７】
本実施形態では、双方向クラスタ分割装置１００は、どの地域でどの車種に故障が発生しているかというデータを多変量データとし、故障発生部品の履歴をシーケンスデータとして、多変量データとシーケンスデータとに対し、双方向クラスタリングを行う。多変量データとシーケンスデータとに対して双方向クラスタリングを行うことで、車種、地域、故障部品履歴に共通した特徴を持つクラスタに分割することができ、車種と地域で共通の特徴をもつクラスタを発見することができる。クラスタリング結果から、車種ごとに、今後、故障が発生すると予測される地域を予測することができる。サーバシステム８００から、故障発生が予測される地域のクライアントシステムに対してどの車種でどのような故障が発生する可能性が高いかを示す情報を送信することで、故障発生に備えることができる。また、故障原因を発見するための調査を早期に行うこともできる。
【０１１８】
ここで、双方向クラスタリングでは、通常、事前にクラスタ数を設定する必要がある。本実施形態で言えば、クラスタ数は、全体で発生している故障の数を表している。双方向クラスタリングで事前にクラスタ数を設定する場合、全体として故障が何個発生しているかが不明な状態でも、事前にクラスタ数を決めなければならない。言い換えれば、クラスタリングを行うことで、発生している故障の数を知りたいにもかかわらず、発生している故障の数を事前に決めなくてはならない。本実施形態では、双方向クラスタ分割装置１００がクラスタ数算出手段１０３（図１）を有しているので、事前にクラスタ数を決めておかなくても、適切な分割数でクラスタ分割を行うことができる。応用上、双方向クラスタリングでは、データを入力するだけで、適切な数でクラスタに分割したクラスタリング結果を出力することが重要である。
【０１１９】
なお、上記各実施形態では、多変量データの変量を２つとしているが、変量の数は２つには限定されない。また、多変量データ及びシーケンスデータとの組み合わせは、上記各実施形態で用いたものには限定されない。例えば、多変量データの変量として「顧客」、「商品」を用い、シーケンスデータとして「商品購入履歴」を用いてもよい。或いは、多変量データの変量として「顧客」、「会社名」を用い、シーケンスデータとして「転職履歴」を用いることや、多変量データの変量として「商品」、「Ｗｅｂページ」を用い、シーケンスデータとして「ｗｅｂページで各商品を紹介キャンペーンした日時の履歴」を用いてもよい。更には、多変量データの変量として「部品」、「部品製造会社」を用い、シーケンスデータとして、「部品製造会社が部品を配送した履歴」用いることも可能であり、また、多変量データの変量として「インターネットウィルス名」、「インターネットウィルスの感染が確認された地域」を用い、シーケンスデータとして「１日にウィルスに感染したと報告のあった数の履歴」を用いることもできる。
【０１２０】
図１では、双方向クラスタ分割装置１００はクラスタ数算出手段１０３を有しているが、クラスタ数算出手段１０３を持たない構成も可能である。その場合、双方向クラスタリング手段１０２は、事前に設定されたクラスタ分割数で、クラスタ分割を行えばよい。また、双方向クラスタリング手段１０２と、クラスタ数算出手段１０３とは、同一の装置が備えている必要はなく、双方向クラスタリング手段１０２と、クラスタ数算出手段１０３とを別の装置に分けて、クラスタリングの実行と、クラスタリング結果の評価とを、異なる装置で行ってもよい。
【０１２１】
上記各実施形態では、外部から、多変量データとシーケンスデータとを双方向クラスタ分割装置１００に入力する例を説明したが、多変量データとシーケンスデータとの生成は、双方向クラスタ分割装置１００内で行ってもよい。例えば、第２実施形態で、Ｗｅｂサーバ３００（図１１）のクラスタリング制御手段３０７は、多変量データとシーケンスデータとの生成を行わずに、ユーザリクエスト記憶部３０２から読み出した各ユーザのリクエスト履歴を、出力装置３０８を介して双方向クラスタ分割装置１００に出力する。双方向クラスタ分割装置１００には、データ生成手段を設けておく。双方向クラスタ分割装置１００は、クラスタリング制御手段３０７から入力した情報に基づいて、どのユーザがどのＷｅｂ広告をクリックしたかを示す多変量データと、Ｗｅｂ広告をクリックするまでのコンテンツ訪問履歴とを生成し、その後、双方向クラスタリングを実施してもよい。
【０１２２】
以上、本発明をその好適な実施形態に基づいて説明したが、本発明の双方向クラスタ分割装置、広告配信システム、商品推薦システム、故障予測システム、方法、及び、プログラムは、上記実施形態にのみ限定されるものではなく、上記実施形態の構成から種々の修正及び変更を施したものも、本発明の範囲に含まれる。
【０１２３】
最後に、本発明の概要について説明する。図２９は、本発明の双方向クラスタ分割装置の概略を示している。双方向クラスタ分割装置１０は、入力手段１１と双方向クラスタリング手段１２とを有する。入力手段１１は、変量データと多変量データに対応したシーケンスデータとを入力する。双方向クラスタリング手段１２は、多変量データとシーケンスデータとに対して双方向クラスタリングを行う。双方向クラスタリング手段１２は、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて、多変量データとシーケンスデータとを、複数のクラスタに分割する。
【０１２４】
本発明では、多変量データだけでなく、多変量データに対応したシーケンスデータも同時に双方向クラスタリングする。従って、各変量間、及び、シーケンスデータ間でそれぞれ共通の特徴を持つクラスタに同時に分割することができる。また、データの特徴は、多変量データだけでなく、多変量データに対応したシーケンスデータにも現れる。このため、多変量データとシーケンスデータとを同時に扱い、双方向クラスタリングを行うことで、より正確に、多変量データ間の特徴を抽出できるとことが期待できる。
【符号の説明】
【０１２５】
１０：双方向クラスタ分割装置
１１：入力手段
１２：双方向クラスタリング手段
１００：双方向クラスタ分割装置
１０１：入力手段
１０２：双方向クラスタリング手段
１０３：クラスタ数算出手段
１０４：出力手段
２００：ユーザ端末
２０１：コンテンツリクエスト手段
２０２：コンテンツ表示手段
３００：Ｗｅｂサーバ
３０１：コンテンツ配信手段
３０２：ユーザリクエスト記憶部
３０３：コンテンツ記憶部
３０４：広告選択手段
３０５：広告記憶部
３０６：リクエスト受付手段
３０７：クラスタリング制御手段
３０８：出力装置
３０９：入力装置
３１０：クラスタリング結果記憶部
４００：インターネット
４０１、４０２：ネットワーク
５０１〜５０３、７０１〜７０３：クライアントシステム
６００：サーバシステム
６０１：データ生成手段
６０２：推薦商品リスト生成手段
６０３：クラスタリング結果記憶部
８００：サーバシステム
８０１：データ生成手段
８０２：故障予測候補リスト生成手段
８０３：クラスタリング結果記憶部
【特許請求の範囲】
【請求項１】
多変量データと多変量データに対応したシーケンスデータとを入力する入力手段と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割する双方向クラスタリング手段とを備える双方向クラスタ分割装置。
【請求項２】
前記評価関数が、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多くなるほど値が小さくなる関数であり、前記双方向クラスタリング手段は、クラスタごとに評価関数の値を計算し、クラスタごとの評価関数の値の総和が小さくなるように、クラスタ分割を行う、請求項１に記載の双方向クラスタ分割装置。
【請求項３】
前記双方向クラスタリング手段がクラスタ分割を行った後に、前記評価関数の値に基づいて、双方向クラスタリング手段が行う双方向クラスタリングのクラスタ分割数を決定するクラスタ数算出手段を更に備える、請求項１又は２に記載の双方向クラスタ分割装置。
【請求項４】
前記双方向クラスタリング手段は、前記クラスタ数算出手段がクラスタ分割数を増加させると、前記クラスタ数算出手段が決定したクラスタ分割数でクラスタ分割を行い、請求項３に記載の双方向クラスタ分割装置。
【請求項５】
ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付手段と、
ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信手段と、
前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成手段と、
前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、
前記双方向クラスタリング結果に基づいて、前記コンテンツ配信手段がコンテンツに付加すべき広告を決定する広告選択手段とを備える広告配信システム。
【請求項６】
顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成手段と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、
前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成手段とを備える商品推薦システム。
【請求項７】
車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成手段と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、
前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成手段とを備える故障予測システム。
【請求項８】
コンピュータに、多変量データと多変量データに対応したシーケンスデータとを入力するステップと、
コンピュータが、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割するステップとを有する双方向クラスタ分割方法。
【請求項９】
前記評価関数が、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多くなるほど値が小さくなる関数であり、コンピュータは、前記双方向クラスタリングを行うステップでは、クラスタごとに評価関数の値を計算し、クラスタごとの評価関数の値の総和が小さくなるように、クラスタ分割を行う、請求項８に記載の双方向クラスタ分割方法。
【請求項１０】
前記双方向クラスタリングを行うステップに後続して、コンピュータが、前記評価関数の値に基づいて、双方向クラスタリングのクラスタ分割数を決定するステップを更に有する、請求項８又は９に記載の双方向クラスタ分割方法。
【請求項１１】
コンピュータは、前記クラスタ分割数を決定するステップで、現在のクラスタ分割数よりもクラスタ分割数を増加させると決定すると、前記決定したクラスタ分割数で更に双方向クラスタリングを行う、請求項１０に記載の双方向クラスタ分割方法。
【請求項１２】
コンピュータが、ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付ステップと、
コンピュータが、ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信ステップと、
コンピュータが、前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成ステップと、
コンピュータが、前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、
コンピュータが、前記双方向クラスタリング結果に基づいて、前記コンテンツに付加すべき広告を決定する広告選択ステップとを有する広告配信方法。
【請求項１３】
コンピュータが、顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成ステップと、
コンピュータが、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、
コンピュータが、前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成ステップとを有する商品推薦方法。
【請求項１４】
コンピュータが、車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成ステップと、
コンピュータが、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、
コンピュータが、前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成ステップとを有する故障予測方法。
【請求項１５】
コンピュータに、
多変量データと多変量データに対応したシーケンスデータとを入力する処理と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割する処理とを実行させるプログラム。
【請求項１６】
前記評価関数が、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多くなるほど値が小さくなる関数であり、前記双方向クラスタリングを行う処理では、クラスタごとに評価関数の値を計算し、クラスタごとの評価関数の値の総和が小さくなるように、クラスタ分割を行う、請求項１５に記載のプログラム。
【請求項１７】
前記双方向クラスタリングを行う処理に後続して、コンピュータに、前記評価関数の値に基づいて、双方向クラスタリングのクラスタ分割数を決定する処理を更に実行させる、請求項１５又は１６に記載のプログラム。
【請求項１８】
前記クラスタ分割数を決定する処理で、現在のクラスタ分割数よりもクラスタ分割数を増加させると決定すると、前記決定したクラスタ分割数で更に双方向クラスタリングを実行させる、請求項１７に記載のプログラム。
【請求項１９】
コンピュータに、
ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付処理と、
ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信処理と、
前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成処理と、
前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、
前記双方向クラスタリング結果に基づいて、前記コンテンツに付加すべき広告を決定する広告選択処理とを実行させるプログラム。
【請求項２０】
コンピュータに、
顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成処理と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、
前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成処理とを実行させるプログラム。
【請求項２１】
コンピュータに、
車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成処理と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、
前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成処理とを実行させるプログラム。
【請求項１】
多変量データと多変量データに対応したシーケンスデータとを入力する入力手段と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割する双方向クラスタリング手段とを備える双方向クラスタ分割装置。
【請求項２】
前記評価関数が、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多くなるほど値が小さくなる関数であり、前記双方向クラスタリング手段は、クラスタごとに評価関数の値を計算し、クラスタごとの評価関数の値の総和が小さくなるように、クラスタ分割を行う、請求項１に記載の双方向クラスタ分割装置。
【請求項３】
前記双方向クラスタリング手段がクラスタ分割を行った後に、前記評価関数の値に基づいて、双方向クラスタリング手段が行う双方向クラスタリングのクラスタ分割数を決定するクラスタ数算出手段を更に備える、請求項１又は２に記載の双方向クラスタ分割装置。
【請求項４】
前記双方向クラスタリング手段は、前記クラスタ数算出手段がクラスタ分割数を増加させると、前記クラスタ数算出手段が決定したクラスタ分割数でクラスタ分割を行い、請求項３に記載の双方向クラスタ分割装置。
【請求項５】
ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付手段と、
ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信手段と、
前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成手段と、
前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、
前記双方向クラスタリング結果に基づいて、前記コンテンツ配信手段がコンテンツに付加すべき広告を決定する広告選択手段とを備える広告配信システム。
【請求項６】
顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成手段と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、
前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成手段とを備える商品推薦システム。
【請求項７】
車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成手段と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング手段と、
前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成手段とを備える故障予測システム。
【請求項８】
コンピュータに、多変量データと多変量データに対応したシーケンスデータとを入力するステップと、
コンピュータが、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割するステップとを有する双方向クラスタ分割方法。
【請求項９】
前記評価関数が、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多くなるほど値が小さくなる関数であり、コンピュータは、前記双方向クラスタリングを行うステップでは、クラスタごとに評価関数の値を計算し、クラスタごとの評価関数の値の総和が小さくなるように、クラスタ分割を行う、請求項８に記載の双方向クラスタ分割方法。
【請求項１０】
前記双方向クラスタリングを行うステップに後続して、コンピュータが、前記評価関数の値に基づいて、双方向クラスタリングのクラスタ分割数を決定するステップを更に有する、請求項８又は９に記載の双方向クラスタ分割方法。
【請求項１１】
コンピュータは、前記クラスタ分割数を決定するステップで、現在のクラスタ分割数よりもクラスタ分割数を増加させると決定すると、前記決定したクラスタ分割数で更に双方向クラスタリングを行う、請求項１０に記載の双方向クラスタ分割方法。
【請求項１２】
コンピュータが、ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付ステップと、
コンピュータが、ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信ステップと、
コンピュータが、前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成ステップと、
コンピュータが、前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、
コンピュータが、前記双方向クラスタリング結果に基づいて、前記コンテンツに付加すべき広告を決定する広告選択ステップとを有する広告配信方法。
【請求項１３】
コンピュータが、顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成ステップと、
コンピュータが、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、
コンピュータが、前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成ステップとを有する商品推薦方法。
【請求項１４】
コンピュータが、車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成ステップと、
コンピュータが、前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリングステップと、
コンピュータが、前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成ステップとを有する故障予測方法。
【請求項１５】
コンピュータに、
多変量データと多変量データに対応したシーケンスデータとを入力する処理と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割する処理とを実行させるプログラム。
【請求項１６】
前記評価関数が、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多くなるほど値が小さくなる関数であり、前記双方向クラスタリングを行う処理では、クラスタごとに評価関数の値を計算し、クラスタごとの評価関数の値の総和が小さくなるように、クラスタ分割を行う、請求項１５に記載のプログラム。
【請求項１７】
前記双方向クラスタリングを行う処理に後続して、コンピュータに、前記評価関数の値に基づいて、双方向クラスタリングのクラスタ分割数を決定する処理を更に実行させる、請求項１５又は１６に記載のプログラム。
【請求項１８】
前記クラスタ分割数を決定する処理で、現在のクラスタ分割数よりもクラスタ分割数を増加させると決定すると、前記決定したクラスタ分割数で更に双方向クラスタリングを実行させる、請求項１７に記載のプログラム。
【請求項１９】
コンピュータに、
ユーザからのコンテンツへのリクエストを受け付け、リクエストを送信したユーザとリクエストしたコンテンツとをユーザリクエスト記憶部に記憶するリクエスト受付処理と、
ユーザがリクエストしたコンテンツに、ユーザに広告主のコンテンツをリクエストさせるための仕組みを含む広告を付加して送信するコンテンツ配信処理と、
前記ユーザリクエスト記憶部に記憶された情報に基づいて、ユーザと広告とを変量とし、ユーザが広告から広告主のコンテンツをリクエストしたか否かを示す多変量データを生成すると共に、前記多変量データ対応して、ユーザが広告主のコンテンツをリクエストするまでに送信したリクエストを時系列で並べたシーケンスデータを生成するデータ生成処理と、
前記多変量データと前記シーケンスデータとに対して双方向クラスタリングを行い、前記多変量データを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、
前記双方向クラスタリング結果に基づいて、前記コンテンツに付加すべき広告を決定する広告選択処理とを実行させるプログラム。
【請求項２０】
コンピュータに、
顧客が商品を購入したという情報を含む売上情報を収集し、該収集した売上情報に基づいて、顧客と商品とを変量とし、顧客が商品を購入したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、顧客が商品を購入したことに関する履歴を時系列で並べたシーケンスデータとを生成するデータ生成処理と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、
前記双方向クラスタリング結果に基づいて、顧客に推薦する商品を決定する推薦商品リスト生成処理とを実行させるプログラム。
【請求項２１】
コンピュータに、
車両の車種と故障個所とを含む故障情報を収集し、該収集した故障情報に基づいて、車種と地域とを変量とし、当該車種に対し当該地域で故障が発生したか否かを示す多変量データを生成すると共に、前記多変量データに対応して、当該車種で過去に発生した故障個所の履歴を時系列で並べたシーケンスデータを生成するデータ生成処理と、
前記多変量データとシーケンスデータとに対して双方向クラスタリングを行い、前記多変量データと前記シーケンスデータとを、クラスタに含まれる各変量間とシーケンスデータ間とのそれぞれで共通した特徴が多いか少ないかを表す評価関数を用いて複数のクラスタに分割し、双方向クラスタリング結果を出力する双方向クラスタリング処理と、
前記双方向クラスタリング結果に基づいて、車種に対して故障の発生が予測される地域を推測する故障予測候補リスト生成処理とを実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【公開番号】特開２０１１−１１３１０４（Ｐ２０１１−１１３１０４Ａ）
【公開日】平成２３年６月９日（２０１１．６．９）
【国際特許分類】
【出願番号】特願２００９−２６５９２８（Ｐ２００９−２６５９２８）
【出願日】平成２１年１１月２４日（２００９．１１．２４）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２３年６月９日（２０１１．６．９）
【国際特許分類】
【出願日】平成２１年１１月２４日（２００９．１１．２４）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]