JP5535787B2 - 分類装置、分類方法及び分類プログラム - Google Patents

Description

本発明は、複数のウェブサイトを分類する分類装置、分類方法及び分類プログラムに関する。

従来、インターネット上で公開されているウェブサイトの中には、オフラインの個人が設定した１又は複数のオンラインの個人により管理される個人ウェブサイトが存在する。
ここで、オフラインの個人とは、ネットワーク（インターネット）を利用する現実のユーザそれぞれをいい、ネットワーク上でオンラインの個人を管理している。オンラインの個人とは、ネットワークを通じて所定のサービス群の提供を受ける仮想のユーザをいい、オフラインの個人とオンラインの個人とは、１対１又は１対多の関係にある。

各オンラインの個人は、例えば、同じ学校の生徒であったり、同じ趣味を持つグループの一員であったり、オンラインの他者と一定の人間関係（同一の属性）を持っている。そのため、複数のオンラインの個人がそれぞれ管理している個人ウェブサイトの間は、リンクで参照されていることも多い。例えば、近年、特に中学生や高校生の間では、各人が複数の個人ウェブサイトを操り、それぞれのオンラインの個人で複数の個人ウェブサイトを作成し、自身のサイト間のみならず、他者とのサイト間で互いにリンクを設け、情報やメッセージの公開及び交換を行うことが多い。

ところで、このように相互にリンクが設けられているウェブサイトのリンク構造を解析する技術も提案されている。例えば、特許文献１では、リンク構造を解析してコミュニティの境界を判定することが示されている。

特開２００６−３３１０７０号公報

特許文献１の手法は、ウェブサイトのリンクを抽出し、リンク先のウェブサイトを再帰的に、リンクがなくなるまで収集するものであるため、リンクで紐付けられている全てのウェブサイトが同一のコミュニティとみなされる。

しかしながら、個人ウェブサイトは、管理者の属性が同一のグループ内に対してのみリンクを有しているとは限られず、ある確率で他のグループの個人ウェブサイトへのリンクを有する場合もある。また、この管理者の属性は、個人ウェブサイトを参照する第三者には不明、又は取得が難しい。したがって、特許文献１の手法のように、リンクの有無によりグループの境界を判定すると、グループ間にリンクの入出力がある場合には、個人ウェブサイトを管理者の属性ごとに分類することができなかった。

本発明は、複数の個人ウェブサイトを、管理者の未知の属性ごとに分類できる分類装置、分類方法及び分類プログラムを提供することを目的とする。

本発明では、以下のような解決手段を提供する。

（１）複数のウェブサイトを、当該ウェブサイトを管理している管理者の属性ごとに分類する分類装置であって、前記管理者が異なるウェブサイト間を結ぶリンクの入出力関係を示すリンク情報を記憶する記憶部と、前記管理者が同一の前記ウェブサイトの集合であるノードにおける当該管理者の属性値がある値となる確率、及び前記管理者の属性値の組み合わせに応じて前記リンクが生成される確率を未知の潜在パラメータとするリンク生成モデルにおいて、前記記憶部に記憶されているリンク情報を表す観測可能な確率変数に対して、最も尤度が高い観測不可能な確率変数である前記管理者の属性値の組み合わせを算出する分類部と、を備える分類装置。

このような構成によれば、分類装置は、管理者が異なる個人ウェブサイト間を結ぶリンクの入出力関係を観測し、ノード生成確率及びリンク生成確率を未知の潜在パラメータとするリンク生成モデルに対して適用することで、所定の推定処理により最も尤度が高い確率変数である管理者の属性値の組み合わせを算出できる。したがって、分類装置は、複数の個人ウェブサイトを、管理者の未知の属性ごとに分類できる。

（２）前記管理者の属性値が取りうる値の数の入力を受け付ける受付部をさらに備え、前記分類部は、前記受付部により受け付けた前記管理者の属性値が取りうる値の数に前記リンク生成モデルを限定し、前記観測不可能な確率変数である前記管理者の属性値の組み合わせを算出する（１）に記載の分類装置。

このような構成によれば、分類装置は、取りうる属性値の数の入力を受け付けて生成モデルを限定した上で推定処理を実行できる。したがって、分類装置は、推定対象のパラメータ数を低減し、高精度かつ高効率に個人ウェブサイトを分類できる。

（３）前記受付部は、前記観測不可能な確率変数の初期値をさらに受け付け、前記分類部は、前記受付部により受け付けた初期値を元に、前記潜在パラメータ及び前記観測不可能な確率変数を算出する逐次処理を繰り返し、収束値を算出する（２）に記載の分類装置。

このような構成によれば、分類装置は、属性値の初期値を受け付け、この初期値を元に推定値が収束するまで逐次処理を行う。したがって、例えば、いくつかのノードの属性値が判明している等、手がかりが与えられている場合に、推定値の収束までの演算回数の低減が期待できると共に、分類装置は、推定値が誤った局所解に収束するのを抑制できる。

（４）前記記憶部は、前記リンク情報の一部として、リンク元のウェブサイトの種別をさらに記憶し、前記リンク生成モデルにおいて、前記リンクが生成される確率は、前記種別ごとに定義され、前記観測可能な確率変数は、前記種別に応じた要素値が定義される（１）から（３）のいずれかに記載の分類装置。

このような構成によれば、分類装置は、リンク生成モデルにおいて、リンク元の個人ウェブサイトの種別ごとに、リンクが生成される確率と、隣接行列の要素値とを定義する。したがって、分類装置は、リンクの入出力関係を詳細に区別できるので、推定結果の精度の向上が期待できる。

（５）前記種別は、前記ウェブサイトの利用形態を表す所定数のいずれかであって、当該ウェブサイトのＵＲＬに基づいて分類される（４）に記載の分類装置。

このような構成によれば、分類装置は、リンク元のウェブサイトの利用形態を表す種別を、ウェブサイトのＵＲＬに基づいて分類できるので、リンク情報を容易に取得できる。

（６）前記分類部は、前記観測可能な確率変数の各要素値に対して、前記種別に応じた重み付けを行う（４）又は（５）に記載の分類装置。

このような構成によれば、分類装置は、リンク情報を表す観測可能な確率変数の各要素値に対して、リンク元のウェブサイトの利用形態を表す種別に応じた重み付けを行うので、リンク情報が効果的に用いられて推定精度を向上できる可能性がある。

（７）前記記憶部は、前記リンク情報の一部として、前記リンクの発生日時をさらに記憶し、前記分類部は、前記リンクの発生日時に応じて前記観測可能な確率変数の各要素値を決定する（１）から（６）のいずれかに記載の分類装置。

このような構成によれば、分類装置は、リンクの発生日時に応じて、リンク情報を表す観測可能な確率変数の各要素値を決定するので、リンク生成モデルに適合する有用なリンク情報が効果的に用いられて推定精度を向上できる可能性がある。

（８）複数のウェブサイトを、当該ウェブサイトを管理している管理者の属性ごとにコンピュータが分類する分類方法であって、前記管理者が異なるウェブサイト間を結ぶリンクの入出力関係を示すリンク情報を記憶する記憶ステップと、前記管理者が同一の前記ウェブサイトの集合であるノードにおける当該管理者の属性値がある値となる確率、及び前記管理者の属性値の組み合わせに応じて前記リンクが生成される確率を未知の潜在パラメータとするリンク生成モデルにおいて、前記記憶ステップにおいて記憶されているリンク情報を表す観測可能な確率変数に対して、最も尤度が高い観測不可能な確率変数である前記管理者の属性値の組み合わせを算出する分類ステップと、を含む分類方法。

このような構成によれば、分類方法をコンピュータが実行することにより、（１）と同様の効果が期待できる。

（９）複数のウェブサイトを、当該ウェブサイトを管理している管理者の属性ごとに分類させる分類プログラムであって、前記管理者が異なるウェブサイト間を結ぶリンクの入出力関係を示すリンク情報を記憶する記憶ステップと、前記管理者が同一の前記ウェブサイトの集合であるノードにおける当該管理者の属性値がある値となる確率、及び前記管理者の属性値の組み合わせに応じて前記リンクが生成される確率を未知の潜在パラメータとするリンク生成モデルにおいて、前記記憶ステップにおいて記憶されているリンク情報を表す観測可能な確率変数に対して、最も尤度が高い観測不可能な確率変数である前記管理者の属性値の組み合わせを算出する分類ステップと、をコンピュータに実行させる分類プログラム。

このような構成によれば、分類プログラムをコンピュータに実行させることにより、（１）と同様の効果が期待できる。

本発明によれば、複数の個人ウェブサイトを、管理者の未知の属性ごとに分類できる。

本発明の実施形態に係る個人ウェブサイトと、その管理者との関係を示す図である。 本発明の実施形態に係る分類装置によりオンラインＩＤが割り当てられた結果を示す概要図である。 本発明の実施形態に係る分類装置により個人ウェブサイトが属性値ごとに分類された結果を示す概要図である。 本発明の実施形態に係る分類装置の機能構成を示すブロック図である。 本発明の実施形態に係る個人ウェブサイトテーブルを示す図である。 本発明の実施形態に係るサイト間リレーションテーブルを示す図である。 本発明の実施形態に係る管理者属性テーブルを示す図である。 本発明の実施形態に係るリンク情報の一例を示す図である。 本発明の実施形態に係るリンク生成モデルを示す図である。 本発明の実施形態に係る分類処理を示すフローチャートである。 本発明の実施形態に係るパラメータの推定処理を示すフローチャートである。

以下、本発明の実施形態の一例について説明する。
本実施形態に係る分類装置１００は、オンラインの個人が管理する個人ウェブサイトを、このオンラインの個人の属性（例えば、学校等）ごとに分類する装置である。なお、分類装置１００は、サーバ装置やＰＣ（Ｐｅｒｓｏｎａｌ Ｃｏｍｐｕｔｅｒ）等、様々な情報処理装置（コンピュータ）であってよい。

図１は、本実施形態に係る個人ウェブサイトと、その管理者との関係を示す図である。
現実の人物であるオフラインの個人は、ネットワーク（インターネット）上で、１又は複数のオンラインの個人を管理している管理者である。また、オンラインの個人は、１又は複数の個人ウェブサイトを管理している管理者である。

ここで、個人ウェブサイトとは、オンラインの個人が、自身に関する情報を公開したり、オンラインの他者とメッセージを交換したりするためのウェブサイトをいう。例えば、以下の種別（タイプ）の個人ウェブサイトがそれぞれ複数のサービスプロバイダにより提供されている。

プロフ（プロフィール）・・・個人のプロフィールを公開できるサイト
ゲスブ（ゲストブック）・・・訪問者が履歴としてコメントを投稿できるサイト
リアル（リアルタイム）・・・個人の現況を短い文章で投稿できるサイト
ブログ・・・日々更新される日記を公開できるサイト
Ｍｙリンク・・・他者の個人ウェブサイトへのリンクを掲載できるサイト
ホムペ（ホームページ）・・・個人用のサイト

オンラインの個人は、上記の複数のタイプの個人ウェブサイトを、サービスプロバイダごとに異なるアカウントで作成しているため、同一のＩＤによる紐付け（名寄せ）ができていないことが多い。例えば、「オンラインＩＤ（ＯｎＩＤ）＝１」であるオンラインの個人は、「プロフ１」及び「ゲスブ１」を管理している。これらの個人ウェブサイトは、「ＯｎＩＤ＝１」の情報を有しておらず、異なるアカウントＩＤ（１及び２）で管理されている。

分類装置１００は、まず、後述のＩＤ割当処理により、管理者であるオンラインの個人が同一である個人ウェブサイトに対して、同一のオンラインＩＤ（ＯｎＩＤ）を割り当て、複数の個人ウェブサイトをオンラインの個人ごとに分類する。
図２は、本実施形態に係る分類装置１００によりオンラインＩＤが割り当てられた結果を示す概要図である。

以下、本実施形態がＩＤの割り当ての対象とする個人ウェブサイトは、サイトの利用形態を表す上記の６種類のタイプに分類され、さらに、各タイプは、次の３種類のクラス（クラスＡ、クラスＢ及びクラスＣ）に分類される。なお、これらのクラス及びタイプは、個人ウェブサイトのＵＲＬから判別できるものとする。

クラスＡ（プロフ、ホムペ）・・・オンラインの個人が他者と識別するために作成する個人ウェブサイト
クラスＢ（ゲスブ、Ｍｙリンク）・・・オンラインの個人がクラスＡのサイトに付随して作成する個人ウェブサイト
クラスＣ（リアル、ブログ）・・・オンラインの個人が他者と識別するために単体で、又はクラスＡのサイトに付随して作成する個人ウェブサイト

次に、分類装置１００は、後述の分類処理により、オンラインの個人のそれぞれに対して属性値（例えば、所属する学校を区別する値）を算出し、個人ウェブサイトを属性値ごとに分類する。
図３は、本実施形態に係る分類装置１００により個人ウェブサイトが属性値ごとに分類された結果を示す概要図である。

以下、分類に用いるオンラインの個人の属性を、所属する学校として説明する。なお、この属性を示す属性値は、学校を区別する値であって、学校を特定するものではない。例えば、「○○中学校」と「△△中学校」とを区別する属性値が「１」又は「２」であるとき、「１」が「○○中学校」であるか「△△中学校」であるかは特定されない。

分類処理の結果、個人ウェブサイトの管理者であるオンラインの個人が属性値ごとに分類される。そして、少なくとも一部の個人ウェブサイトについて、そのコンテンツに基づいて属性（例えば、○○中学校）が特定されると、同一の属性値を持つオンラインの個人及び個人ウェブサイトの属性（○○中学校）が特定される。

図４は、本実施形態に係る分類装置１００の機能構成を示すブロック図である。
分類装置１００は、制御部１０と、記憶部２０と、通信部３０と、入力部４０と、出力部５０とを備える。

制御部１０は、分類装置１００の全体を制御する部分であり、記憶部２０に記憶された各種プログラムを適宜読み出して実行することにより、上記のハードウェアと協働し、本実施形態における各種機能を実現している。制御部１０は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）であってよい。なお、制御部１０が備える各部の機能は後述する。

記憶部２０は、ハードウェア群を分類装置１００として機能させるための各種プログラム、及び各種データ等の記憶領域であり、ハードディスク（ＨＤＤ）であってよい。具体的には、記憶部２０には、本実施形態の各種機能を実現させるため制御部１０に実行させるプログラム（分類プログラム）が記憶される。

さらに、記憶部２０は、サイト保存ＤＢ２１と、個人ウェブサイトＤＢ２２とを備える。サイト保存ＤＢ２１は、プログラムにて取得される個人ウェブサイトのページデータを記憶する。また、個人ウェブサイトＤＢ２２は、プログラムにて作成又は編集される後述の個人ウェブサイトテーブル、サイト間リレーションテーブル及び管理者属性テーブルを記憶する。

通信部３０は、分類装置１００が他の装置と情報を送受信する場合のネットワーク・アダプタであり、ネットワーク（インターネット）を介して個人ウェブサイトを提供しているサーバ２００にアクセスし、ページデータを取得して制御部１０へ提供する。

入力部４０は、分類装置１００に対する利用者からの指示入力を受け付けるインタフェース装置である。入力部４０は、例えば、キーボード、マウス及びタッチパネル等により構成される。

出力部５０は、利用者にデータの入力を受け付ける画面を表示したり、分類装置１００による処理結果の画面を表示したりするディスプレイ装置を含む。さらに、出力部５０は、ブラウン管表示装置（ＣＲＴ）や液晶表示装置（ＬＣＤ）等のディスプレイ装置の他、プリンタ等の各種出力装置を含んでよい。

次に、制御部１０の機能を詳述する。
制御部１０は、収集処理を実行する収集部１１と、ＩＤ割当処理を実行するＩＤ割当部１２と、分類処理を実行する分類部１３と、受付部１４とを備える。各部は、分類プログラムを実行することにより実現される機能ブロックである。

収集部１１は、収集処理を開始すると、個人ウェブサイトに含まれるリンクを抽出し、さらにこのリンクの参照先である別の個人ウェブサイトのページデータを取得する。そして、収集部１１は、サイト保存ＤＢ２１にページデータを記憶すると共に、複数の個人ウェブサイトのリスト（個人ウェブサイトテーブル）、及び複数の個人ウェブサイト間におけるリンクの入出力関係を示したリンク情報のリスト（サイト間リレーションテーブル）にそれぞれデータ追加し、個人ウェブサイトＤＢ２２を更新する。

具体的には、収集部１１は、まず、収集処理の元になるルートの個人ウェブサイトのＵＲＬと、このルートの個人ウェブサイトから他の個人ウェブサイトへのリンクを幾つ辿るかを示すリンクホップ数の指定を受け付ける。なお、リンクホップ数は、個人ウェブサイト間を結ぶハイパーリンク（ＨＴＭＬにおける＜Ａ＞リンク）の数をいい、個人ウェブサイト内を遷移するハイパーリンクは数えない。

次に、収集部１１は、インターネットにアクセスし、ルートの個人ウェブサイトのページデータをサイト保存ＤＢ２１に記憶する。さらに、このルートの個人ウェブサイトのＵＲＬを、個人ウェブサイトテーブルに追加する。

また、収集部１１は、個人ウェブサイトからリンクを取得し、リンク先が個人ウェブサイトでないものを除いて、リンク元のＵＲＬとリンク先のＵＲＬとの組み合わせをサイト間リレーションテーブルに追加する。

さらに、収集部１１は、リンク先のＵＲＬから取得した個人ウェブサイトのページデータをサイト保存ＤＢ２１に、このＵＲＬを個人ウェブサイトテーブルにそれぞれ記憶する。そして、収集部１１は、指定されたリンクホップ数まで、全てのＵＲＬが個人ウェブサイトテーブルに記憶されると収集処理を終了する。また、収集部１１は、個人ウェブサイトテーブルに記憶されているＵＲＬが指定されたリンクホップ数に達していない場合には、リンクの取得、サイト間リレーションテーブルの更新、ページデータの記憶及び個人ウェブサイトテーブルの更新を繰り返す。

図５は、本実施形態に係る個人ウェブサイトテーブルを示す図である。
個人ウェブサイトテーブルは、収集ＩＤ、ルートＵＲＬ、リンク元ＵＲＬ、個人ウェブサイトＵＲＬ、個人ウェブサイトのタイプ、個人ウェブサイトのクラス、ローカルＵＲＬ、リンクホップ数、オンラインＩＤ（ＯｎＩＤ）、取得日及び取得時刻を記憶する。

ここで、収集ＩＤは、上記の収集処理ごとに付与される識別番号である。また、ローカルＵＲＬは、サイト保存ＤＢ２１内における対象のページデータの記憶場所を示すＵＲＬである。ＯｎＩＤは、後述の割当処理によって割り当てられるオンラインの個人、すなわち個人ウェブサイトの管理者を識別するＩＤである。

図６は、本実施形態に係るサイト間リレーションテーブルを示す図である。
サイト間リレーションテーブルは、リンク元の個人ウェブサイトの情報（ＵＲＬ、ＯｎＩＤ、個人ウェブサイトのタイプ、個人ウェブサイトのクラス）、リンク先の個人ウェブサイトの情報（ＵＲＬ、ＯｎＩＤ、個人ウェブサイトのタイプ、個人ウェブサイトのクラス）及びリンク発生時期情報（収集ＩＤ、日付、時刻）を記憶する。

なお、リンクの発生日付及び時刻は、リンクを含む記事の書き込み日時であることが好ましい。この書き込み日時が取得できない場合は、個人ウェブサイトの作成日時や、個人ウェブサイトの収集日時で代用してもよい。

ＩＤ割当部１２は、割当処理により、複数の個人ウェブサイトのそれぞれに対して、オンラインの個人を識別するＯｎＩＤを割り当て、個人ウェブサイトテーブル及びサイト間リレーションテーブルを更新する。具体的には、ＩＤ割当部１２は、複数の個人ウェブサイトのそれぞれが分類されているクラス、及びサイト間リレーションテーブルのリンク情報により示されているリンクの入出力関係の構造に基づいて、予め設定されている制約に従って、複数の個人ウェブサイトのそれぞれに対して、オンラインの個人を識別するＯｎＩＤを割り当てることとしてよい。

ここで、予め設定されている制約とは、リンク元及びリンク先の関係にある個人ウェブサイトを管理するオンラインの個人の同異に関するクラスごとの制約である。個人ウェブサイトは、利用形態の違いにより特有のリンク構造を有している場合が多いため、リンク構造に関して各クラスに特有の制約を規定した。
なお、割当処理の詳細は、本発明者らによる先の特許出願（特願２０１０−１０８２４２号明細書）に示されている。

また、ＩＤ割当部１２は、この割当処理の結果として生成された全てのＯｎＩＤを、管理者属性テーブルに記憶する。

図７は、本実施形態に係る管理者属性テーブルを示す図である。
管理者属性テーブルは、ＯｎＩＤ及び管理者の属性値を記憶する。管理者の属性値は、分類部１３の分類処理により算出され、ＯｎＩＤに対応付けて記憶される。

分類部１３は、サイト間リレーションテーブルに記憶されている情報のうち、管理者が異なる、すなわちＯｎＩＤが異なる個人ウェブサイト間を結ぶリンクの入出力関係を示すリンク情報に基づいて、分類処理により管理者の属性値の組み合わせを算出する。

ここで、リンク情報は、リンク元の個人ウェブサイトのタイプによって区別される。以下、本実施形態では、分類部１３は、上述のタイプのうち「ゲスブ」と「Ｍｙリンク」がリンク元となっているリンク情報を用い、それぞれを区別する。

図８は、本実施形態に係るリンク情報の一例を示す図である。
「ＯｎＩＤ＝１」の管理者が管理している「ゲスブ」がリンク元である場合、このリンクは、「ＯｎＩＤ＝２」の管理者が自身の個人ウェブサイトへ誘導するために書き込んだものである。一方、「ＯｎＩＤ＝１」の管理者が管理している「Ｍｙリンク」がリンク元である場合、このリンクは、「ＯｎＩＤ＝１」の管理者が「ＯｎＩＤ＝２」の管理者が管理している個人ウェブサイトへ誘導するために書き込んだものである。
このように、個人ウェブサイトのタイプごとに利用形態は異なるため、分類部１３は、これらのリンクをタイプごとに区別して分類処理を実行する。

また、本実施形態では、分類部１３は、リンクの発生日時に応じて、このリンク情報を利用するか否かを判断する。例えば、平日と休日（日曜日、祝日、夏休み等）とではリンクの発生確率等の傾向が異なるため、分類部１３は、発生日時が平日のリンク情報を利用して分類処理を実行する。

受付部１４は、個人ウェブサイトの管理者の属性値が取りうる値の数の入力を、入力部４０、通信部３０等を介して利用者から受け付ける。また、受付部１４は、分類部１３により算出される前の属性値の初期値を、同様に入力部４０、通信部３０等を介して利用者から受け付けてもよい。

以下、分類部１３による分類処理について詳述する。
分類処理では、管理者が同一の個人ウェブサイトの集合であるノードにおける管理者の属性値がある値となる確率（ノード生成確率）、及びノード間の属性値の組み合わせに応じてリンクが生成される確率（リンク生成確率）を未知の潜在パラメータとするリンク生成モデルを用いる。

図９は、本実施形態に係るリンク生成モデルを示す図である。
このリンク生成モデルは、管理者（ＯｎＩＤ）が同一の個人ウェブサイトの集合をノードとし、ノード間がリンクで結ばれた有向グラフにおいて成立する。
以下、７つのノードが２つの属性値（１：○○中学校、２：△△中学校）のいずれかを持つとして説明する。

リンク生成モデルでは、潜在パラメータであるノード生成確率θに従って、属性値ベクトルｘの各要素（ノードの属性値）が確率的に決定される。また、この属性値ベクトルｘと、潜在パラメータであるリンク生成確率ηとに従って、有向グラフの構成を表す隣接行列ｙの各要素が確率的に決定される。

例えば、属性値ベクトルｘの要素ｘ_ｉは、属性値ごとのノード生成確率（θ_１及びθ_２）に従って、いずれかの値に決定される。また、隣接行列ｙのｉ行ｊ列の要素は、第ｉノードの属性値ｋ及び第ｊノードの属性値ｈと、これらの属性値の組み合わせに対する各種リンク種別ごとのリンク生成確率η_ａ（ｋ，ｈ）とに従って、いずれかの値に決定される。

ここで、属性値ベクトルｘは、以下のように定義される。

なお、本実施形態では、「Ｃ＝｛１，２｝、ｃ＝｜Ｃ｜＝２」として説明する。

また、隣接行列ｙは、以下のように定義される。

なお、本実施形態では、αによりリンク元のタイプ（ゲスブとＭｙリンク）ごとにリンクの有無（有：１、無：０）を示し、「α＝（ゲスブからのリンクの有無，Ｍｙリンクからのリンクの有無）」と表現する。

また、記号πは、ｙ_ｉｊ＝（ａ_ｔ，ａ_ｖ）におけるａ_ｔとａ_ｖとの入れ替えを示す（例えば、π（［（１，０），（０，０）］）＝（［（０，０），（１，０）］））。

分類部１３は、このリンク生成モデルにおいて、ベイジアン推定（例えば、「Ｋ．Ｎｏｗｉｃｋｉ ａｎｄ Ｔ．Ａ．Ｂ．Ｓｎｉｊｄｅｒｓ， “Ｅｓｔｉｍａｔｉｎ ａｎｄ ｐｒｅｄｉｃｔｉｏｎ ｆｏｒ ｓｔｏｃｈａｓｔｉｃ ｂｌｏｃｋｓｔｒｕｃｔｕｒｅｓ，” ＪＡＳＡ９６（４５５）， ２００１」を参照）を用いて属性値ベクトルｘを算出する。

ここで、Ｃ及びＡは固定であり、ｘ_ｉはＣのいずれかの値をとり、ｙ_ｉｊはＡのいずれかの値をとる。また、（ｙ，ｘ）は確率変数であり、ｙはｘに依存している。分類部１３は、観測可能なｙから、観測不可能なｘを算出する。

リンク生成モデルにおいて、リンク生成の条件付き確率は、

のように、接続する２つのノードの属性値のみに依存している。
ここで、あるｋ，ｈ∈Ｃに対して与えられる配列

は、以下の式を満たす。

すなわち、リンク生成モデルは、隣接行列ｙの各要素（リンクの状態）が接続する２つのノードの属性値のみに依存して決定されるＰａｉｒ−ｄｅｐｅｎｄｅｎｔ ｓｔｏｃｈａｓｔｉｃ ｂｌｏｃｋｍｏｄｅｌに当てはまる。したがって、隣接行列ｙの条件付き確率分布Ｐは、

で示される。ただし、Ａ_１をＡ_１０とＡ_１１とに分離する分け方は任意であり、例えば、

となる。また、Ｉ｛｝は、｛｝内が真のとき１、偽のとき０となる関数である。

図１０は、本実施形態に係る分類部１３における分類処理を示すフローチャートである。

ステップＳ１では、分類部１３は、管理者属性テーブル（図７）から管理者のＩＤ（ＯｎＩＤ）のリストを取得する。さらに、分類部１３は、サイト間リレーションテーブル（図６）からリンク情報を抽出するための条件として、受付部１４を介して、リンク元の個人ウェブサイトのタイプ及びリンクの発生時期の指定を受け付ける。また、分類部１３は、受付部１４を介して、管理者の属性値の取りうる数（例えば、「○○中学校」と「△△中学校」に分類する場合は「２」）を受け付ける。

ステップＳ２では、分類部１３は、リンク生成モデルにおけるパラメータ（ｘ、ｙ、θ、η）を生成する。

ステップＳ３では、分類部１３は、属性値ベクトルｘの初期値を生成する。この初期値は、受付部１４を介して利用者から受け付けてもよいし、分類部１３が所定のルールに従って自動で生成してもよい。

ステップＳ４では、分類部１３は、ステップＳ１で受け付けた条件に従って、サイト間リレーションテーブルからリンク情報を抽出し、隣接行列ｙを取得する。

ステップＳ５では、分類部１３は、ベイジアン推定におけるＧｉｂｂｓ ｓａｍｐｌｉｎｇの手法を用いて、ステップＳ４で取得した隣接行列ｙから、他のパラメータ（ｘ、θ、η）を推定し、分類結果として属性値ベクトルｘを出力する。

図１１は、本実施形態に係るパラメータの推定処理を示すフローチャートである。本処理は、分類処理（図１０）のステップＳ５に相当し、分類部１３は、Ｇｉｂｂｓ ｓａｍｐｌｉｎｇの手法を用いて、観測された確率変数である隣接行列ｙから、最も尤度が高い観測不可能な確率変数である属性値ベクトルｘを推定する。

具体的には、分類部１３は、観測したｙから、ｙを条件とするｘの確率分布関数と、ｙを条件とするθ及びηの確率密度関数とを最大化するｘ、θ、ηを、以下のステップ１１〜ステップ１３を繰り返すことにより算出する。なお、分類部１３は、ｘ、θ及びηを一度に推定するのではなく、逐次推定を行う。また、推定したい１つの変数に対し、他の変数は既知として推定する。
ここで、推定対象の確率変数ｘ、θ及びηの確率分布関数と確率密度関数は、

と定義され、確率事象Ｘ＝ｘの初期値は、ステップＳ３（図１０）において設定されている。

ステップＳ１１では、分類部１３は、属性値ベクトルｘのｐ回目の推定値（又は初期値）及び隣接行列ｙに基づいて、確率密度関数の期待値を、θ及びηのｐ＋１回目の推定値として算出する。

ここで、確率密度関数は、

と定義される。なお、Ｔ_ｋ及びＥ_ａは、経験的に以下の値とする。

また、ディリクレ（Ｄｉｒｉｃｈｌｅｔ）分布及びその変数θの期待値は、

である。

ステップＳ１２では、分類部１３は、いずれかのノードの属性値ｘ_ｉのｐ＋１回目の推定値として、他のノードの属性値の推定値（又は初期値）と、θ及びηの推定値と、隣接行列とに基づいて、確率分布関数が最大となる値を算出する。

ここで、確率分布関数は、

と定義される。

なお、分類部１３は、ステップＳ１２において、１〜ｎの各ノードの属性値を順に推定し、ｉ番目の属性値ｘ_ｉのｐ＋１回目の推定処理には、ｉ−１番目までの属性値のｐ＋１回目の推定値と、ｉ＋１番目以降の属性値のｐ回目の推定値が用いられる。

ステップＳ１３では、分類部１３は、Ｘ、θ及びηが収束したか否かを判定する。分類部１３は、この判定がＹＥＳの場合、分類結果として属性値ベクトルｘを出力し、判定がＮＯの場合、ステップＳ１１に戻って、推定処理を繰り返す。

＜実施例＞
以下、推定処理の数値例を示す。
まず、分類部１３は、以下のパラメータを生成する。

次に、分類部１３は、属性値ベクトルｘの初期値として、例えば、

を設定し、観測された隣接行列ｙ（図９参照）に基づいて、逐次推定を開始する。

ノード生成確率θの１回目の推定値は、

の期待値として、

と算出される。

また、リンク生成確率ηの１回目の推定値は、

の期待値として、

と算出される。

そして、１番目のノードの属性値ｘ_１の１回目の推定値は、確率分布関数Ｐにおいて、「ｉ＝１」としたときにＰが最大となる値（ｋ）である。ｋ＝１の場合とｋ＝２の場合とで、確率分布関数Ｐは、それぞれ、

と求められるので、値が最大となるｋとして、推定値「ｘ_１ ^（１）＝１」が算出される。
同様に、２番目〜７番目のノードの属性値も推定値が算出され、θ、η及びｘが収束するまで、逐次推定が繰り返される。

以上のように、本実施形態によれば、分類装置１００は、管理者が異なる個人ウェブサイト間を結ぶリンクの入出力関係を観測し、リンク生成モデルに対してベイジアン推定の手法を適用することにより、観測不可能な確率変数である管理者の属性値の組み合わせを算出できる。したがって、分類装置１００は、複数の個人ウェブサイトを、管理者の未知の属性ごとに分類できる。

また、分類装置１００は、取りうる属性値の数の入力を受け付けて推定処理を実行したので、推定対象のパラメータ数が低減され、高精度かつ高効率に個人ウェブサイトを分類できる。

また、分類装置１００は、属性値の初期値を受け付け、この初期値を元に推定値が収束するまで逐次処理を行った。したがって、例えば、いくつかのノードの属性値が判明している等、手がかりが与えられている場合に、推定値の収束までの演算回数の低減が期待できると共に、推定値が誤った局所解に収束するのを抑制できる。

また、分類装置１００は、リンク生成モデルにおいて、リンク元の個人ウェブサイトの種別（タイプ）ごとに、リンクが生成される確率と、隣接行列の要素値とを定義した。したがって、分類装置１００は、リンクの入出力関係を詳細に区別できるので、推定結果の精度の向上が期待できる。さらに、この種別は、個人ウェブサイトのＵＲＬに基づいて分類されるので、容易に取得できる。

以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。

分類装置１００は、取りうる管理者の属性値の数が指定された上で、属性値を推定したが、これには限られない。取りうる数が指定されない場合であっても、この数をさらに推定対象の変数とすることで、推定処理が可能である。

また、分類装置１００は、リンク元の個人ウェブサイトのタイプごとに隣接行列の要素値を定義したが、さらに、各要素値に対してリンク元のタイプや、リンクの発生日時に応じた所定の重み付けを行ってもよい。このことにより、リンク情報が効果的に用いられて推定精度を向上できる可能性がある。

１０ 制御部
１１ 収集部
１２ ＩＤ割当部
１３ 分類部
１４ 受付部
２０ 記憶部
２１ サイト保存ＤＢ
２２ 個人ウェブサイトＤＢ
３０ 通信部
４０ 入力部
５０ 出力部
１００ 分類装置

Claims (9)

1. 複数のウェブサイトを、当該ウェブサイトを管理している管理者の属性ごとに分類する分類装置であって、
   前記管理者が異なるウェブサイト間を結ぶリンクの入出力関係を示すリンク情報を記憶する記憶部と、
   前記管理者が同一の前記ウェブサイトの集合であるノードにおける当該管理者の属性値がある値となる確率、及び前記管理者の属性値の組み合わせに応じて前記リンクが生成される確率を未知の潜在パラメータとするリンク生成モデルにおいて、前記記憶部に記憶されているリンク情報を表す観測可能な確率変数に対して、最も尤度が高い観測不可能な確率変数である前記管理者の属性値の組み合わせを算出する分類部と、を備える分類装置。
2. 前記管理者の属性値が取りうる値の数の入力を受け付ける受付部をさらに備え、
   前記分類部は、前記受付部により受け付けた前記管理者の属性値が取りうる値の数に前記リンク生成モデルを限定し、前記観測不可能な確率変数である前記管理者の属性値の組み合わせを算出する請求項１に記載の分類装置。
3. 前記受付部は、前記観測不可能な確率変数の初期値をさらに受け付け、
   前記分類部は、前記受付部により受け付けた初期値を元に、前記潜在パラメータ及び前記観測不可能な確率変数を算出する逐次処理を繰り返し、収束値を算出する請求項２に記載の分類装置。
4. 前記記憶部は、前記リンク情報の一部として、リンク元のウェブサイトの種別をさらに記憶し、
   前記リンク生成モデルにおいて、前記リンクが生成される確率は、前記種別ごとに定義され、前記観測可能な確率変数は、前記種別に応じた要素値が定義される請求項１から請求項３のいずれかに記載の分類装置。
5. 前記種別は、前記ウェブサイトの利用形態を表す所定数のいずれかであって、当該ウェブサイトのＵＲＬに基づいて分類される請求項４に記載の分類装置。
6. 前記分類部は、前記観測可能な確率変数の各要素値に対して、前記種別に応じた重み付けを行う請求項４又は請求項５に記載の分類装置。
7. 前記記憶部は、前記リンク情報の一部として、前記リンクの発生日時をさらに記憶し、
   前記分類部は、前記リンクの発生日時に応じて前記観測可能な確率変数の各要素値を決定する請求項１から請求項６のいずれかに記載の分類装置。
8. 複数のウェブサイトを、当該ウェブサイトを管理している管理者の属性ごとにコンピュータが分類する分類方法であって、当該コンピュータの制御部が、
   前記管理者が異なるウェブサイト間を結ぶリンクの入出力関係を示すリンク情報を記憶部から読み出し、
   前記管理者が同一の前記ウェブサイトの集合であるノードにおける当該管理者の属性値がある値となる確率、及び前記管理者の属性値の組み合わせに応じて前記リンクが生成される確率を未知の潜在パラメータとするリンク生成モデルにおいて、前記リンク情報を表す観測可能な確率変数に対して、最も尤度が高い観測不可能な確率変数である前記管理者の属性値の組み合わせを算出する分類方法。
9. コンピュータに、複数のウェブサイトを、当該ウェブサイトを管理している管理者の属性ごとに分類させるための分類プログラムであって、当該コンピュータの制御部に、
   前記管理者が異なるウェブサイト間を結ぶリンクの入出力関係を示すリンク情報を記憶部から読み出させ、
   前記管理者が同一の前記ウェブサイトの集合であるノードにおける当該管理者の属性値がある値となる確率、及び前記管理者の属性値の組み合わせに応じて前記リンクが生成される確率を未知の潜在パラメータとするリンク生成モデルにおいて、前記リンク情報を表す観測可能な確率変数に対して、最も尤度が高い観測不可能な確率変数である前記管理者の属性値の組み合わせを算出させるための分類プログラム。

Images