(57)【特許請求の範囲】
【請求項１】
オブジェクトと属性を同時にクラスタリングする共クラスタリング装置において、
オブジェクトと属性間のリンク関係と、全ての属性とリンクを持つ例外オブジェクトとから拡張エッジ行列を生成する拡張エッジ行列生成手段と、
前記生成された拡張エッジ行列を、各オブジェクトが含む属性数および各属性が属するオブジェクト数の差異の影響を防ぐことができるように正規化して正規化拡張エッジ行列を求める正規化手段と、
前記求められた正規化拡張エッジ行列を固有空間に変換する固有空間変換手段と、
前記固有空間変換手段によって固有空間に配置されたオブジェクトからクラスタを生成するオブジェクトクラスタリング手段と、
前記固有空間変換手段によって固有空間に配置された属性をオブジェクトのクラスタに分類する属性分類手段と、を有し、
前記属性分類手段は、前記オブジェクトクラスタリング手段によって得られたクラスタに適し、一つのクラスタに強く対応する属性を前記得られたクラスタに分類し、前記オブジェクトクラスタリング手段によって得られたクラスタに適さず、複数のクラスタに対応する属性を例外クラスタに分類することを特徴とする共クラスタリング装置。
【請求項２】
前記拡張エッジ行列生成手段により生成された拡張エッジ行列に対して、指定した２つのオブジェクトをできるだけ同じクラスタに配置するオブジェクト内の制約、指定した２つの属性をできるだけ同じクラスタに配置する属性内の制約、および、指定した属性とオブジェクトをできるだけ同じクラスタに配置するオブジェクト属性間の制約を加えて拡張エッジ行列を生成する制約導入手段を有したことを特徴とする請求項１に記載の共クラスタリング装置。
【請求項３】
オブジェクトと属性を同時にクラスタリングする共クラスタリング方法において、
拡張エッジ行列生成手段が、オブジェクトと属性間のリンク関係と、全ての属性とリンクを持つ例外オブジェクトとから拡張エッジ行列を生成する拡張エッジ行列生成ステップと、
正規化手段が、前記生成された拡張エッジ行列を、各オブジェクトが含む属性数および各属性が属するオブジェクト数の差異の影響を防ぐことができるように正規化して正規化拡張エッジ行列を求める正規化ステップと、
固有空間変換手段が、前記求められた正規化拡張エッジ行列を固有空間に変換する固有空間変換ステップと、
オブジェクトクラスタリング手段が、前記固有空間変換手段によって固有空間に配置されたオブジェクトからクラスタを生成するオブジェクトクラスタリングステップと、
属性分類手段が、前記固有空間変換手段によって固有空間に配置された属性をオブジェクトのクラスタに分類する属性分類ステップと、を有し、
前記属性分類ステップは、前記オブジェクトクラスタリング手段によって得られたクラスタに適し、一つのクラスタに強く対応する属性を前記得られたクラスタに分類し、前記オブジェクトクラスタリング手段によって得られたクラスタに適さず、複数のクラスタに対応する属性を例外クラスタに分類することを特徴とする共クラスタリング方法。
【請求項４】
制約導入手段が、前記拡張エッジ行列生成ステップにより生成された拡張エッジ行列に対して、指定した２つのオブジェクトをできるだけ同じクラスタに配置するオブジェクト内の制約、指定した２つの属性をできるだけ同じクラスタに配置する属性内の制約、および、指定した属性とオブジェクトをできるだけ同じクラスタに配置するオブジェクト属性間の制約を加えて拡張エッジ行列を生成する制約導入ステップを有したことを特徴とする請求項３に記載の共クラスタリング方法。
【請求項５】
コンピュータを請求項１又は２に記載の各手段として機能させる共クラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データクラスタリングに関し、特に、文書群とそれらが含む単語群や購入者と購入履歴、または、ユーザーと閲覧Ｗｅｂページなど、オブジェクトと属性を同時にクラスタリングする共クラスタリングに関する。
【背景技術】
【０００２】
従来、共クラスタリング方法として、例えば、非特許文献１に示す手法が提案されていた。非特許文献１の手法は、式（１）の形式のエッジ行列を用いて、オブジェクトと属性を指定したクラスタ数ｋにクラスタリングする。共クラスタリングはオブジェクトと属性を同時にクラスタリングし、その結果を分類や検索、推薦等に利用する。
【０００３】
【数１】
0005618967.tif 000002
【０００４】
文書群とそれらが含む単語群の場合は、文書をオブジェクト、単語を属性として、Ｅijは文書ｊが単語ｉを含むかどうかを示す。
【０００５】
非特許文献１の手順を図７のＡｌｇｏｒｉｔｈｍ  ３に示す。その中で用いられるｋ−ｍｅａｎｓクラスタリングは非特許文献２に開示されており、ｋ−ｍｅａｎｓ法の手順を図８のＡｌｇｏｒｉｔｈｍ  ４に示す。これらＡｌｇｏｒｉｔｈｍ  ３、４を用いて、下記の表１のデータ１をｋ＝３にクラスタリングした例を以下に説明する。
【０００６】
【表１】
0005618967.tif 000003
【０００７】
表１において、ｗ１の行、ｄ１の列が１であるのは、文書ｄ１が単語ｗ１を含むことを示している。
【０００８】
まず、式（２）〜（４）において行列Ａを計算する。
【０００９】
【数２】
0005618967.tif 000004
【００１０】
次に、Ａを特異値分解する。Ｕ，Ｓ，Ｖは式（５）〜（７）となる。
【００１１】
【数３】
0005618967.tif 000005
【００１２】
次に式（８）、（９）においてＺを計算する。
【００１３】
【数４】
0005618967.tif 000006
【００１４】
次にＺをｋ−ｍｅａｎｓクラスタリングする。クラスタ中心とクラスタインデクスは表２、表３となる。
【００１５】
これをクラスタ毎に整理すると表４となる。
【００１６】
【表２】
0005618967.tif 000007
【００１７】
【表３】
0005618967.tif 000008
【００１８】
【表４】
0005618967.tif 000009
【００１９】
表４では、文書とそこに含まれる単語が同一のクラスタにまとめられている。
【００２０】
また、非特許文献３は、非特許文献１の手法に、オブジェクト内の制約（指定した２つのオブジェクトをできるだけ同じクラスタに配置する）、属性内の制約（指定した２つの属性をできるだけ同じクラスタに配置する）、オブジェクト属性間の制約（指定した属性とオブジェクトをできるだけ同じクラスタに配置する）といった制約を導入した手法である。
【００２１】
非特許文献３では、前記オブジェクト内の制約ＣCC，属性内の制約Ｃrr，属性オブジェクト間の制約ＣrCを式（１０）〜（１２）の形式で入力する。
【００２２】
【数５】
0005618967.tif 000010
【００２３】
非特許文献３の手順を図９のＡｌｇｏｒｉｔｈｍ  ５に示す。ここで、表５のデータ３を制約なしでｋ＝２で共クラスタリングすると、表６のようにｄ１とｄ２が同じクラスタになる。
【００２４】
【表５】
0005618967.tif 000011
【００２５】
【表６】
0005618967.tif 000012
【００２６】
これに対し、文書ｄ２とｄ３を同じクラスタに配置する制約（下記の式（１３）〜（１６））を加え、前記Ａｌｇｏｒｉｔｈｍ  ５を用いてクラスタリングすると、表７のように制約通りｄ２とｄ３が同じクラスタになる。
【００２７】
【数６】
0005618967.tif 000013
【００２８】
【表７】
0005618967.tif 000014
【先行技術文献】
【非特許文献】
【００２９】
【非特許文献１】Ｉ．Ｓ．Ｄｈｉｌｌｏｎ，“Ｃｏ−ｃｌｕｓｔｅｒｉｎｇ  ｄｏｃｕｍｅｎｔｓ  ａｎｄ  ｗｏｒｄｓ  Ｕｓｉｎｇ  Ｂｉｐａｒｔｉｔｅ  Ｓｐｅｃｔｒａｌ  Ｇｒａｐｈ  Ｐａｒｔｉｔｉｏｎｇ”，ＫＤＤ−２００１（Ｔｈｅ  Ｓｅｖｅｎｔｈ  ＡＣＭ  ＳＩＧＫＤＤ  ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｆｅｒｅｎｃｅ  ｏｎ  Ｋｎｏｗｌｅｄｇｅ  Ｄｉｓｃｏｖｅｒｙ  ａｎｄ  Ｄａｔａ  Ｍｉｎｉｎｇ），ｐｐ．２６９−２７４
【非特許文献２】Ｃ．Ｍ．ビショップ，「パターン認識と機械学習  下」，シュプリンガー・ジャパン株式会社，ｐｐ．１４０−１４２
【非特許文献３】Ｘ．Ｓｈｉ，Ｗ．Ｆａｎ  ａｎｄ  Ｐ．Ｓ．Ｙｕ，“Ｅｆｆｉｃｉｅｎｔ  Ｓｅｍｉ−ｓｕｐｅｒｖｉｓｅｄ  Ｓｐｅｃｔｒａｌ  Ｃｏ−ｃｌｕｓｔｅｒｉｎｇ  ｗｉｔｈ  Ｃｏｎｓｔｒａｉｎｔｓ”，２０１０  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  Ｄａｔａ  Ｍｉｎｉｎｇ，ｐｐ．１０４３−１０４８
【発明の概要】
【発明が解決しようとする課題】
【００３０】
上述した非特許文献１の共クラスタリング手法では、全ての属性をいずれかのクラスタに振り分けるため、得られたクラスタに適さない属性がクラスタリング結果に含まれるという問題があった。
【００３１】
表８のデータ２をｋ＝３にクラスタリングした結果を表９に示す。
【００３２】
【表８】
0005618967.tif 000015
【００３３】
【表９】
0005618967.tif 000016
【００３４】
この例では、文書ｄ１、ｄ２に共通に含まれるｗ８が文書ｄ１を含みｄ２を含まないクラスタ０に割当てられている。また、文書ｄ１、ｄ２、ｄ３に共通に含まれるｗ１０が文書ｄ３を含みｄ１、ｄ２を含まないクラスタ１に割当てられている。
【００３５】
このように、異なるクラスタに属する文書に共通して含まれる単語もどこかのクラスタに振り分けられてしまう。クラスタに含まれる文書をそのクラスタに含まれる単語でタグ付けしたり、クラスタを分類・検索するためにそのクラスタに含まれる単語で特徴付けたりする場合、得られたクラスタに適さない単語は除外することが望ましい。
【００３６】
クラスタ０に単語ｗ７やｗ８をタグとして付けるのは、他のクラスタにもその単語を含む文書があるので好ましくない。
【００３７】
また、非特許文献３の例で制約付の結果を示す表７でも、単語ｗ２、ｗ３がクラスタ１に振り分けられているが、クラスタ０にもその単語を含む文書が有るので好ましくない。
【００３８】
本発明は、上記問題を解決するものであり、その目的は、得られたクラスタに適した（一つのクラスタに強く対応する様な）属性をクラスタに分類し、得られたクラスタに適さない（複数のクラスタに対応する様な）属性を例外クラスタに分類することができる共クラスタリング装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００３９】
上記課題を解決する本発明の共クラスタリング装置は、オブジェクトと属性を同時にクラスタリングする共クラスタリング装置において、オブジェクトと属性間のリンク関係と、全ての属性とリンクを持つ例外オブジェクトとから拡張エッジ行列を生成する拡張エッジ行列生成手段と、前記生成された拡張エッジ行列を、各オブジェクトが含む属性数および各属性が属するオブジェクト数の差異の影響を防ぐことができるように正規化して正規化拡張エッジ行列を求める正規化手段と、前記求められた正規化拡張エッジ行列を固有空間に変換する固有空間変換手段と、前記固有空間変換手段によって固有空間に配置されたオブジェクトからクラスタを生成するオブジェクトクラスタリング手段と、前記固有空間変換手段によって固有空間に配置された属性をオブジェクトのクラスタに分類する属性分類手段と、を有し、前記属性分類手段は、前記オブジェクトクラスタリング手段によって得られたクラスタに適し、一つのクラスタに強く対応する属性を前記得られたクラスタに分類し、前記オブジェクトクラスタリング手段によって得られたクラスタに適さず、複数のクラスタに対応する属性を例外クラスタに分類することを特徴としている。
【００４０】
また、前記拡張エッジ行列生成手段により生成された拡張エッジ行列に対して、指定した２つのオブジェクトをできるだけ同じクラスタに配置するオブジェクト内の制約、指定した２つの属性をできるだけ同じクラスタに配置する属性内の制約、および、指定した属性とオブジェクトをできるだけ同じクラスタに配置するオブジェクト属性間の制約を加えて拡張エッジ行列を生成する制約導入手段を有したことを特徴としている。
【発明の効果】
【００４１】
本発明によれば、得られたクラスタに適し、一つのクラスタに強く対応する属性を前記得られたクラスタに分類し、得られたクラスタに適さず、複数のクラスタに対応する属性を例外クラスタに分類することができ、適切なクラスタリングを行なうことが可能となる。
【図面の簡単な説明】
【００４２】
【図１】本発明の共クラスタリング装置の第１の実施形態（請求項１）の構成を示すブロック図。
【図２】本発明の共クラスタリング方法の第１の実施形態（請求項３）のフローチャート。
【図３】本発明の共クラスタリング方法の第１の実施形態（請求項３）における共クラスタリング手順を示す説明図。
【図４】本発明の共クラスタリング装置の第２の実施形態（請求項２）の構成を示すブロック図。
【図５】本発明の共クラスタリング方法の第２の実施形態（請求項４）のフローチャート。
【図６】本発明の共クラスタリング方法の第２の実施形態（請求項４）における共クラスタリング手順を示す説明図。
【図７】従来の非特許文献１のＡｌｇｏｒｉｔｈｍ  ３の手順を示す説明図。
【図８】従来の非特許文献２のＡｌｇｏｒｉｔｈｍ  ４の手順を示す説明図。
【図９】従来の非特許文献３のＡｌｇｏｒｉｔｈｍ  ５の手順を示す説明図。
【発明を実施するための形態】
【００４３】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。図１は本発明の共クラスタリング装置の第１の実施形態（請求項１）の構成を示すブロック図、図２は本発明の共クラスタリング方法の第１の実施形態（請求項３）のフローチャート、図３は本発明の共クラスタリング方法の第１の実施形態（請求項３）における共クラスタリング手順、図４は本発明の共クラスタリング装置の第２の実施形態（請求項２）の構成を示すブロック図、図５は本発明の共クラスタリング方法の第２の実施形態（請求項４）のフローチャート、図６は本発明の共クラスタリング方法の第２の実施形態（請求項４）における共クラスタリング手順を各々示している。
【００４４】
第１の実施形態を示す図１において、１０１はネットワーク又はファイルなどからエッジ行列Ｅ、クラスタ数ｋなどのデータを入力するデータ入力部である。
【００４５】
１０２は、前記エッジ行列Ｅに、全ての属性とリンクを持つ例外オブジェクトを追加することによって、オブジェクトと属性間のリンク関係だけでなく全ての属性とリンクを持つ例外オブジェクトから拡張エッジ行列Ｅ´を生成する、拡張エッジ行列生成手段としての拡張エッジ行列生成部である。
【００４６】
１０３は、各オブジェクトが含む属性数や各属性が属するオブジェクト数の差異の影響を防ぐため、前記拡張エッジ行列Ｅ´を正規化して正規化拡張エッジ行列を求める正規化手段としての正規化部である。
【００４７】
１０４は、前記正規化拡張エッジ行列を特異値分解して固有空間に変換する固有空間変換手段としての固有空間変換部である。
【００４８】
１０５は、前記固有空間変換部１０４によって固有空間に配置されたオブジェクトからクラスタを生成するオブジェクトクラスタリング手段としてのオブジェクトクラスタリング部である。
【００４９】
１０６は、前記固有空間変換部１０４によって固有空間に配置された属性をオブジェクトのクラスタに分類する属性分類手段としての属性分類部である。この属性分類部１０６は、前記オブジェクトクラスタリング部１０５によって得られたクラスタに適し、一つのクラスタに強く対応する属性を前記得られたクラスタに分類し、前記オブジェクトクラスタリング部１０５によって得られたクラスタに適さず、複数のクラスタに対応する属性を例外クラスタに分類する。
【００５０】
１０７は、ネットワーク又はファイルに属性分類部１０６のクラスタリング結果を出力する結果出力部である。
【００５１】
また、第２の実施形態を示す図４において、図１と同一部分は同一符号をもって示している。図４において図１と異なる点は、前記拡張エッジ行列生成部１０２により生成された拡張エッジ行列に対して、指定した２つのオブジェクトをできるだけ同じクラスタに配置するオブジェクト内の制約、指定した２つの属性をできるだけ同じクラスタに配置する属性内の制約、および、指定した属性とオブジェクトをできるだけ同じクラスタに配置するオブジェクト属性間の制約を加えて拡張エッジ行列を生成する制約導入手段としての制約導入部２００をさらに有していることにあり、その他の部分は図１と同一に構成されている。
【００５２】
上記の第１および第２の実施形態の共クラスタリング装置は、例えばコンピュータにより構成され、通常のコンピュータのハードウェアリソース、例えばＲＯＭ，ＲＡＭ，ＣＰＵ、入力装置、出力装置、通信インターフェース、ハードディスク、記録媒体およびその駆動装置を備えている。
【００５３】
このハードウェアリソースとソフトウェアリソース（ＯＳ、アプリケーションなど）との協働の結果、共クラスタリング装置は、図１、図４に示すように、データ入力部１０１、拡張エッジ行列生成部１０２、正規化部１０３、固有空間変換部１０４、オブジェクトクラスタリング部１０５、属性分類部１０６、結果出力部１０７、制約導入部２００を実装する。
【００５４】
図１の共クラスタリング装置の各部は、図２のフローチャートに示す各処理を行なって、図３に示すＡｌｇｏｒｉｔｈｍ  １（請求項３の共クラスタリング手順）を実行する。
【００５５】
図４の共クラスタリング装置の各部は、図５のフローチャートに示す各処理を行なって、図６に示すＡｌｇｏｒｉｔｈｍ  ２（請求項４の共クラスタリング手順）を実行する。
【００５６】
次に本発明の第１、第２の実施形態の具体的構成を説明する。データ入力部１０１は、ネットワーク又はファイルなどから、エッジ行列Ｅおよびクラスタ数ｋを入力する（図２、図５のステップＳ１０１）。制約がある場合は、オブジェクト内の制約ＣCC，属性内の制約Ｃrr，属性オブジェクト間の制約ＣrCおよびδ（クラスタリング精度を決めるパラメータ）も入力する（図５のステップＳ１０１）。
【００５７】
拡張エッジ行列生成部１０２は、エッジ行列Ｅに全ての属性とリンクを持つ例外オブジェクトを追加して、拡張エッジ行列Ｅ´を生成する（図２のステップＳ１０２、図５のステップＳ１０２ａ）。
【００５８】
すなわち、
【００５９】
【数７】
0005618967.tif 000017
【００６０】
ここで、ｍはエッジ行列Ｅの行数である。
【００６１】
図４の制約導入部２００は、式（１８）〜（２０）のＤ1，Ｄ2，Ｅ″を計算する（図５のステップＳ１０２ｂ）。
【００６２】
【数８】
0005618967.tif 000018
【００６３】
ここで、
【００６４】
【数９】
0005618967.tif 000019
【００６５】
正規化部１０３は、各オブジェクトが含む属性数や各属性が属するオブジェクト数の差異を吸収するため、拡張エッジ行列を正規化する（図２、図５のステップＳ１０３）。
【００６６】
すなわち、図１の正規化部１０３では、図３のＡｌｇｏｒｉｔｈｍ  １に示すように、
【００６７】
【数１０】
0005618967.tif 000020
【００６８】
を計算し、図４の正規化部１０３では、図６のＡｌｇｏｒｉｔｈｍ  ２に示すように、
【００６９】
【数１１】
0005618967.tif 000021
【００７０】
を計算する。
【００７１】
固有空間変換部１０４は、正規化された拡張エッジ行列Ａを特異値分解して固有空間に変換する（図２、図５のステップＳ１０４）。すなわち、
【００７２】
【数１２】
0005618967.tif 000022
【００７３】
オブジェクトクラスタリング部１０５は、右特異ベクトルＶからオブジェクトベクトルＹを計算する（図２、図５のステップＳ１０５）。
【００７４】
【数１３】
0005618967.tif 000023
【００７５】
オブジェクトベクトルＹ＝（ｙ(1)，…，ｙ(n+1)）Tから例外オブジェクト、すなわちｎ＋１番目の行ベクトルを除き、この元オブジェクトベクトルＹo＝（ｙ1，…，ｖn）Tをｋ−ｍｅａｎｓクラスタリングする。この結果のクラスタ中心をｃ0，…，ｃk-1，クラスタインデクスをｇobjとする。
【００７６】
属性分類部１０６は、ｋ個のクラスタ中心に例外オブジェクトベクトルを追加して、拡張クラスタ中心Ｃ´を作成する。
【００７７】
Ｃ´＝（ｃ0，…，ｃk-1，ｙn+1）T        （３５）
次に、属性ベクトルＸを式（３６）のように計算する。
【００７８】
【数１４】
0005618967.tif 000024
【００７９】
そして、ｍ個の属性ベクトルＸ＝（ｘ1，…，ｘm）Tの行ベクトルを拡張クラスタ中心の一番近いものに分類する（図２、図５のステップＳ１０６）。
【００８０】
【数１５】
0005618967.tif 000025
【００８１】
ここで、‖・‖はユークリッドノルム。
【００８２】
結果出力部１０７は、ネットワーク又はファイルなどに、クラスタリング結果ｇattr，および，ｇobjを出力する（図２、図５のステップＳ１０７）。
【実施例１】
【００８３】
ここでは、本発明の第１の実施形態（図１〜図３）に係る実施例１を説明する。
【００８４】
データ入力部１０１は、表８（文書ｄ１〜ｄ３をオブジェクトとし、単語ｗ１〜ｗ１０を属性とするデータ２）に示す行列Ｅおよびクラスタ数ｋ＝３を入力する。
【００８５】
拡張エッジ行列生成部１０２は、式（３８）のように拡張エッジ行列Ｅ´を生成する。
【００８６】
【数１６】
0005618967.tif 000026
【００８７】
正規化部１０３は、正規化拡張エッジ行列Ａを式（３９）〜（４１）のように計算する。
【００８８】
【数１７】
0005618967.tif 000027
【００８９】
固有空間変換部１０４は、正規化拡張エッジ行列Ａを式（４２）〜（４４）のように特異値分解する。
【００９０】
【数１８】
0005618967.tif 000028
【００９１】
オブジェクトクラスタリング部１０５は、式（４５）、（４６）のようにオブジェクトベクトルＹを計算する。
【００９２】
【数１９】
0005618967.tif 000029
【００９３】
そして、例外オブジェクトを除いた元オブジェクトベクトルＹoをｋ−ｍｅａｎｓクラスタリングする。結果は表１０、表１１となる。
【００９４】
【表１０】
0005618967.tif 000030
【００９５】
【表１１】
0005618967.tif 000031
【００９６】
属性分類部１０６は、表１０のクラスタ中心に例外オブジェクトを追加した拡張クラスタ中心Ｃ´を作成する（表１２）。
【００９７】
【表１２】
0005618967.tif 000032
【００９８】
次に、式（４７）の属性ベクトルを計算する。
【００９９】
【数２０】
0005618967.tif 000033
【０１００】
そして、Ｘの行ベクトルを一番近い拡張クラスタ中心に割当てる。結果は表１３となる。
【０１０１】
【表１３】
0005618967.tif 000034
【０１０２】
結果出力部１０７は、表１１のｇobjおよび表１３のｇattrを出力する。
【０１０３】
この結果をクラスタ毎に整理すると表１４となる。
【０１０４】
【表１４】
0005618967.tif 000035
【０１０５】
表１４によれば、異なるクラスタの文書に含まれる単語ｗ７、ｗ８、ｗ９、ｗ１０が例外クラスタに分類されていることが分かる。
【実施例２】
【０１０６】
ここでは、本発明の第２の実施形態（図４〜図６）に係る実施例２を説明する。
【０１０７】
データ入力部１０１は、表５（文書ｄ１〜ｄ３をオブジェクトとし、単語ｗ１〜ｗ５を属性とするデータ３）に示す行列Ｅ、クラスタ数ｋ＝２及び式（１０）〜（１６）の制約条件を入力する。
【０１０８】
拡張エッジ行列生成部１０２は、式（４８）のように拡張エッジ行列Ｅ´を生成する。
【０１０９】
【数２１】
0005618967.tif 000036
【０１１０】
制約導入部２００は、式（４９）〜（５１）のようにＤ1、Ｄ2，Ｅ″を計算する。
【０１１１】
【数２２】
0005618967.tif 000037
【０１１２】
正規化部１０３は、式（５２）の正規化拡張エッジ行列Ａを計算する。
【０１１３】
【数２３】
0005618967.tif 000038
【０１１４】
固有空間変換部１０４は、正規化拡張エッジ行列Ａを式（５３）〜（５５）のように特異値分解する。
【０１１５】
【数２４】
0005618967.tif 000039
【０１１６】
オブジェクトクラスタリング部１０５は、式（５６）、（５７）のようにオブジェクトベクトルＹを計算する。
【０１１７】
【数２５】
0005618967.tif 000040
【０１１８】
そして、例外オブジェクトを除いた元オブジェクトベクトルＹoをｋ−ｍｅａｎｓクラスタリングする。結果は表１５、表１６となる。
【０１１９】
【表１５】
0005618967.tif 000041
【０１２０】
【表１６】
0005618967.tif 000042
【０１２１】
属性分類部１０６は、クラスタ中心に例外オブジェクトを追加した拡張クラスタ中心Ｃ´を表１７のように作成する。
【０１２２】
【表１７】
0005618967.tif 000043
【０１２３】
次に、式（５８）の属性ベクトルを計算する。
【０１２４】
【数２６】
0005618967.tif 000044
【０１２５】
そして、Ｘの行ベクトルを一番近い拡張クラスタ中心に割当てる。結果は表１８となる。
【０１２６】
【表１８】
0005618967.tif 000045
【０１２７】
結果出力部１０７は、表１６のｇobjおよび表１８のｇattrを出力する。
【０１２８】
この結果をクラスタ毎に整理すると表１９となる。
【０１２９】
【表１９】
0005618967.tif 000046
【０１３０】
表１９によれば、異なるクラスタの文書に含まれる単語ｗ２、ｗ３が例外クラスタに分類されていることが分かる。
【０１３１】
また、本実施形態の共クラスタリング装置における各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態の共クラスタリング方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばＦＤ（Ｆｌｏｐｐｙ（登録商標）  Ｄｉｓｋ）や、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ）−ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＨＤＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【符号の説明】
【０１３２】
１０１…データ入力部
１０２…拡張エッジ行列生成部
１０３…正規化部
１０４…固有空間変換部
１０５…オブジェクトクラスタリング部
１０６…属性分類部
１０７…結果出力部
２００…制約導入部
【図１】
0005618967.tif 000047
【図２】
0005618967.tif 000048
【図３】
0005618967.tif 000049
【図４】
0005618967.tif 000050
【図５】
0005618967.tif 000051
【図６】
0005618967.tif 000052
【図７】
0005618967.tif 000053
【図８】
0005618967.tif 000054
【図９】
0005618967.tif 000055