グラフにおけるリンク構造を利用したノードの自動クラスタリング
【課題】グラフにおけるリンク構造を利用したノードの自動クラスタリングすることで、既存の検索エンジンにおいては容易にたどり着かない情報へ到達可能にする。
【解決手段】探索のクエリーに対し、グラフにおけるリンク構造を利用したノードの自動クラスタリングを行い、求めようとする情報により近い情報であるクラスタ選択画面を表示し、利用者が必要とするクラスタを選択し、利用者に負荷をかけることなく、既存の検索エンジンにおいては容易にたどり着かない情報に到達する。
【解決手段】探索のクエリーに対し、グラフにおけるリンク構造を利用したノードの自動クラスタリングを行い、求めようとする情報により近い情報であるクラスタ選択画面を表示し、利用者が必要とするクラスタを選択し、利用者に負荷をかけることなく、既存の検索エンジンにおいては容易にたどり着かない情報に到達する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、WEB内のホームページに対するテキスト検索において、その異なるノードに対し、リンク構造を利用して、自動的にクラスタリングを行い、クラスタリングの結果から各クラスの共通の情報を提示し、画面に表示することで、ユーザーが求めたいクラスを選択し、順位付けることで、目的に容易に到達しうるすることを特徴とする検索エンジン。
【背景技術】
【０００２】
WEBの中で、検索エンジンは、キーワード入力のみで、必要な情報を入手できる利点があるので、パソコン、携帯を問わず全世界的に実用に共されている。
また、この検索エンジンを運営する会社には、従来のメディアの広告宣伝とは全く異なる形での、多大の広告宣伝費がもたらせられるという、ビジネスモデルとなっている。
既存の検索エンジンにあっては、何十万件の情報がヒットし、この大半が使用不可能な情報となっている。また、時流に合ったものを検索するには問題ないが、マイナーな情報は埋もれてしまうという、問題点を容易に指摘できる。
【０００３】
この問題点は、既存の検索エンジンにおいては、多くのホームページの中の検索テキストに一致するものを拾い出し、そのページへのリンク関係を基準にしてページランクを求めることで表示の順番を決めている。
【０００４】
例を挙げるならば、英語の「Apple」または「アップル」で検索すると、PCに関わるホームページが数百表示され、その後に果物の「りんご」に関するホームページが表示される。これは、ホームページを作る人はPCに意識があり、リンクを張るからである。ところが人によっては、果物の「りんご」だけでなく、りんごで作る「酒」や「酢」であったり、ビートルズの「アップル・レコード」、ニュートンの「万有引力の法則」、アダムとイブの「エデンの園」であるかもしれない。ところが既存の検索エンジンにおいては、このキーワードのままで、これらの情報にたどり着くことはない。ここで、PC以外の情報は、「Apple」のキーワードでクラスタリングし、「PCですか？」「果物ですか？」を選択することにより、浮上させることが可能となる。果物のAppleに関するホームページは何百番目かに始めて現れるので、ユーザーはそこまで待つほど気が長くないので、途中であきらめてしまうか、他のキーワードと組合せて色々と試みることになる。アップルコンピュータを知らない人にとっては（知らない人は居ないと思うが）訳の分からない情報が画面に表示される。このような問題を解決する。
図１はこの方法による手順を示す説明図である。
【０００５】
この改善策として、ホームページ同士の、間接的リンクも含め、リンク構造を考慮し、クラスタリングを行う。リンク構造においては、あるホームページから他のホームページにリンクを張るとき、あるホームページをノードと呼びそのリンクを含め、位相幾何学のグラフ理論においてはグラフという。ある初期負荷をグラフに与え、次々と負荷を伝搬させ、その蓄積と通過を累積しながらホットスポットを見つけ出し、ある閾値以上の候補集合からカットセットを構成していくものである。
図２はこのアルゴリズムを示す説明図である。
【特許文献１】なし
【非特許文献１】なし
【発明の開示】
【発明が解決しようとする課題】
【０００６】
解決しようとする問題点は、既存の検索エンジンにおいては、検索結果の表示順序(順位付け)に問題があり、多種多様なユーザーの要求に対応できていない点である。
【課題を解決するための手段】
【０００７】
本発明は、グラフにおけるリンク構造を利用したノードの自動クラスタリングすることにより、既存の検索エンジンにおいては容易にたどり着けない情報を提示させうることを最も主要な特徴とする。
【発明の効果】
【０００８】
本発明の検索エンジンは、自動クラスタリングすることにより、利用者に負荷をかけることなく、既存の検索エンジンにおいては容易にたどり着けない情報に到達できるという利点がある。
【発明を実施するための最良の形態】
【０００９】
検索クエリー「Apple」が発せられたとき、例えば「PCですか？」「果物ですか？」といった選択画面を表示させることにより、利用者に負担をかけることなく実現した。
【実施例１】
【００１０】
図１は、本発明の実施例の手順図である。検索クエリーに対して得られたノードのリンク関係を調べ、クラスタリングを行い、クエリー「Apple」に対する意味グループが複数あることをユーザーに気付かせ、ユーザーが探しているものを選択させることで早く目的に到達しうる。
【００１１】
一度行ったクラスタリングの結果は保存しておくこともでき、同一のクエリーに対しては、以前に行ったクラスタ結果の選択画面を表示することにより、高速化を図ることも可能である。また、ユーザーの好みに合うように自動的にカスタマイズすることも可能である。
【実施例２】
【００１２】
図２の実施例は、クラスタリングを行うアルゴリズムの概念図である。ある初期負荷をグラフに与え、次々と負荷を伝搬させ、その蓄積と通過を累積しながらホットスポットを見つけ出し、ある閾値以上の候補集合からカットセットを構成していくことを示す。ここで言うカットセットとは一般にグラフ理論で使われるより広義の意味で使われており、グラフGから非連結なグラフを得るために除去しなければならない最小限のエッジ集合として定義される
【産業上の利用可能性】
【００１３】
クラスタリングの採用は、テキストデータに限定された既存の検索エンジンに対し、画像音声を含むマルチメディア検索の用途にも適用できる。
【図面の簡単な説明】
【００１４】
【図１】検索エンジンの実施手順を示す説明図である。（実施例１）
【図２】クラスタリングのアルゴリズムを示す説明図である。（実施例２）
【符号の説明】
【００１５】
１ 検索クエリー発行
２ 検索エンジン
３ クラスタリング
４ クラスタ選択
５ 検索結果表示
６ クラスタリングのアルゴリズム
【技術分野】
【０００１】
本発明は、WEB内のホームページに対するテキスト検索において、その異なるノードに対し、リンク構造を利用して、自動的にクラスタリングを行い、クラスタリングの結果から各クラスの共通の情報を提示し、画面に表示することで、ユーザーが求めたいクラスを選択し、順位付けることで、目的に容易に到達しうるすることを特徴とする検索エンジン。
【背景技術】
【０００２】
WEBの中で、検索エンジンは、キーワード入力のみで、必要な情報を入手できる利点があるので、パソコン、携帯を問わず全世界的に実用に共されている。
また、この検索エンジンを運営する会社には、従来のメディアの広告宣伝とは全く異なる形での、多大の広告宣伝費がもたらせられるという、ビジネスモデルとなっている。
既存の検索エンジンにあっては、何十万件の情報がヒットし、この大半が使用不可能な情報となっている。また、時流に合ったものを検索するには問題ないが、マイナーな情報は埋もれてしまうという、問題点を容易に指摘できる。
【０００３】
この問題点は、既存の検索エンジンにおいては、多くのホームページの中の検索テキストに一致するものを拾い出し、そのページへのリンク関係を基準にしてページランクを求めることで表示の順番を決めている。
【０００４】
例を挙げるならば、英語の「Apple」または「アップル」で検索すると、PCに関わるホームページが数百表示され、その後に果物の「りんご」に関するホームページが表示される。これは、ホームページを作る人はPCに意識があり、リンクを張るからである。ところが人によっては、果物の「りんご」だけでなく、りんごで作る「酒」や「酢」であったり、ビートルズの「アップル・レコード」、ニュートンの「万有引力の法則」、アダムとイブの「エデンの園」であるかもしれない。ところが既存の検索エンジンにおいては、このキーワードのままで、これらの情報にたどり着くことはない。ここで、PC以外の情報は、「Apple」のキーワードでクラスタリングし、「PCですか？」「果物ですか？」を選択することにより、浮上させることが可能となる。果物のAppleに関するホームページは何百番目かに始めて現れるので、ユーザーはそこまで待つほど気が長くないので、途中であきらめてしまうか、他のキーワードと組合せて色々と試みることになる。アップルコンピュータを知らない人にとっては（知らない人は居ないと思うが）訳の分からない情報が画面に表示される。このような問題を解決する。
図１はこの方法による手順を示す説明図である。
【０００５】
この改善策として、ホームページ同士の、間接的リンクも含め、リンク構造を考慮し、クラスタリングを行う。リンク構造においては、あるホームページから他のホームページにリンクを張るとき、あるホームページをノードと呼びそのリンクを含め、位相幾何学のグラフ理論においてはグラフという。ある初期負荷をグラフに与え、次々と負荷を伝搬させ、その蓄積と通過を累積しながらホットスポットを見つけ出し、ある閾値以上の候補集合からカットセットを構成していくものである。
図２はこのアルゴリズムを示す説明図である。
【特許文献１】なし
【非特許文献１】なし
【発明の開示】
【発明が解決しようとする課題】
【０００６】
解決しようとする問題点は、既存の検索エンジンにおいては、検索結果の表示順序(順位付け)に問題があり、多種多様なユーザーの要求に対応できていない点である。
【課題を解決するための手段】
【０００７】
本発明は、グラフにおけるリンク構造を利用したノードの自動クラスタリングすることにより、既存の検索エンジンにおいては容易にたどり着けない情報を提示させうることを最も主要な特徴とする。
【発明の効果】
【０００８】
本発明の検索エンジンは、自動クラスタリングすることにより、利用者に負荷をかけることなく、既存の検索エンジンにおいては容易にたどり着けない情報に到達できるという利点がある。
【発明を実施するための最良の形態】
【０００９】
検索クエリー「Apple」が発せられたとき、例えば「PCですか？」「果物ですか？」といった選択画面を表示させることにより、利用者に負担をかけることなく実現した。
【実施例１】
【００１０】
図１は、本発明の実施例の手順図である。検索クエリーに対して得られたノードのリンク関係を調べ、クラスタリングを行い、クエリー「Apple」に対する意味グループが複数あることをユーザーに気付かせ、ユーザーが探しているものを選択させることで早く目的に到達しうる。
【００１１】
一度行ったクラスタリングの結果は保存しておくこともでき、同一のクエリーに対しては、以前に行ったクラスタ結果の選択画面を表示することにより、高速化を図ることも可能である。また、ユーザーの好みに合うように自動的にカスタマイズすることも可能である。
【実施例２】
【００１２】
図２の実施例は、クラスタリングを行うアルゴリズムの概念図である。ある初期負荷をグラフに与え、次々と負荷を伝搬させ、その蓄積と通過を累積しながらホットスポットを見つけ出し、ある閾値以上の候補集合からカットセットを構成していくことを示す。ここで言うカットセットとは一般にグラフ理論で使われるより広義の意味で使われており、グラフGから非連結なグラフを得るために除去しなければならない最小限のエッジ集合として定義される
【産業上の利用可能性】
【００１３】
クラスタリングの採用は、テキストデータに限定された既存の検索エンジンに対し、画像音声を含むマルチメディア検索の用途にも適用できる。
【図面の簡単な説明】
【００１４】
【図１】検索エンジンの実施手順を示す説明図である。（実施例１）
【図２】クラスタリングのアルゴリズムを示す説明図である。（実施例２）
【符号の説明】
【００１５】
１ 検索クエリー発行
２ 検索エンジン
３ クラスタリング
４ クラスタ選択
５ 検索結果表示
６ クラスタリングのアルゴリズム
【特許請求の範囲】
【請求項１】
WEB内のホームページ（グラフ理論と対応させるために以下ノードと呼ぶ）に対するテキスト検索において、その異なるノードに対し、リンク構造を利用して、自動的にクラスタリングを行い、求めようとする情報により近い情報に絞り込み、目的に容易に到達しうる検索エンジンを構築するためのノードのクラスタリング法。
【請求項１】
WEB内のホームページ（グラフ理論と対応させるために以下ノードと呼ぶ）に対するテキスト検索において、その異なるノードに対し、リンク構造を利用して、自動的にクラスタリングを行い、求めようとする情報により近い情報に絞り込み、目的に容易に到達しうる検索エンジンを構築するためのノードのクラスタリング法。
【図１】
【図２】
【図２】
【公開番号】特開２０１０−１９１９０２（Ｐ２０１０−１９１９０２Ａ）
【公開日】平成２２年９月２日（２０１０．９．２）
【国際特許分類】
【出願番号】特願２００９−３８３２５（Ｐ２００９−３８３２５）
【出願日】平成２１年２月２０日（２００９．２．２０）
【出願人】（５００２９３７４４）朝日エンジニアリング株式会社 (9)
【出願人】（５０６１２２３２７）公立大学法人大阪市立大学 (122)
【Ｆターム（参考）】
【公開日】平成２２年９月２日（２０１０．９．２）
【国際特許分類】
【出願日】平成２１年２月２０日（２００９．２．２０）
【出願人】（５００２９３７４４）朝日エンジニアリング株式会社 (9)
【出願人】（５０６１２２３２７）公立大学法人大阪市立大学 (122)
【Ｆターム（参考）】
[ Back to top ]