逐次クラスタリング装置とその方法及びプログラム
【課題】 クラスタリングによるＤＢＳＣＡＮアルゴリズムを逐次的に実行することができるようにする。
【解決手段】 クラスタ更新は、新しく追加された点ｐとその近傍の点のうち、新しくクラスタ核になる点があるかどうかを調べる処理と、クラスタ核になる点があった場合に新しいクラスタの生成、既存クラスタ間の統合を行う処理の２つの処理を行う。具体的には、逐次的に与えられる点ｐとそのε-近傍に含まれる点の集合を入力として与え（Ｓ２２）、ε-近傍に含まれる点の数がＮ以上かどうかを調べ（Ｓ２３）、Ｎ以上であった場合には、ｐはクラスタ核となるため、クラスタ更新部分処理１（Ｓ２４）に進み、ｐにクラスタ核マークを与え、新しいクラスタＩＤを発行して、点ｐにそのクラスタＩＤを与える。Ｎ以下の場合はｐはクラスタ核ではないため、クラスタ更新部分処理２（Ｓ２５）に進み、クラスタ核マークの付け替え処理を行う。
【解決手段】 クラスタ更新は、新しく追加された点ｐとその近傍の点のうち、新しくクラスタ核になる点があるかどうかを調べる処理と、クラスタ核になる点があった場合に新しいクラスタの生成、既存クラスタ間の統合を行う処理の２つの処理を行う。具体的には、逐次的に与えられる点ｐとそのε-近傍に含まれる点の集合を入力として与え（Ｓ２２）、ε-近傍に含まれる点の数がＮ以上かどうかを調べ（Ｓ２３）、Ｎ以上であった場合には、ｐはクラスタ核となるため、クラスタ更新部分処理１（Ｓ２４）に進み、ｐにクラスタ核マークを与え、新しいクラスタＩＤを発行して、点ｐにそのクラスタＩＤを与える。Ｎ以下の場合はｐはクラスタ核ではないため、クラスタ更新部分処理２（Ｓ２５）に進み、クラスタ核マークの付け替え処理を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えばＧＰＳ（Global Positioning System）等を利用することによって得られるユーザ位置情報から、当該ユーザが滞在している場所をリアルタイムに判定する処理に利用される逐次クラスタリング装置とその方法及びプログラムに関する。
【背景技術】
【０００２】
ＧＰＳ等を用いて一定時間間隔で取得されたユーザの位置を示す座標データ（以下、本明細書において点データと総称する）から、クラスタリングによってユーザが滞在した場所を抽出する処理が提案されている。このようなアルゴリズムのひとつとしてＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムが利用されており、効果をあげている。ＤＢＳＣＡＮアルゴリズムの特性として、ノイズを含むデータに強い、クラスタの形状に依存しないなどの点が挙げられる。
【０００３】
しかしながら、既存のＤＢＳＣＡＮアルゴリズムには、その逐次的な実行方法が示されていない。そのため、点データが逐次的に得られる状況で、得られた点データに対して常に最新のクラスタリング結果を得ようとした場合、新しく点データが得られるごとに、現在までに得られた全ての点データに対してクラスタリング処理を再実行しなければならない。この処理には計算コストがかかるため、リアルタイムで入力データが得られる状況でユーザの滞在地を知るような処理には不向きである。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", ACM KDD‘96
【非特許文献２】Brett Adams, Dinh Phung, and Svetha Venkatesh, "Extraction of Social Context and Application to Personal Multimedia Exploration", ACM MM'06
【発明の概要】
【発明が解決しようとする課題】
【０００５】
以上のように、既存のＤＢＳＣＡＮアルゴリズムには、その逐次的な実行方法が示されていないため、入力データが逐次的に得られる状況で、得られたデータに対して常に最新のクラスタリング結果を得る場合には、新しくデータが得られるごとに現在までに得られた全てのデータに対してクラスタリング処理を再実行しなければならない。
【０００６】
本発明は、上記の事情を鑑みてなされたもので、逐次的にデータが得られる状況でクラスタリングによるＤＢＳＣＡＮアルゴリズムを逐次的に実行する際の計算コストを削減することのできる逐次クラスタリング装置とその方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために本発明に係る逐次クラスタリング装置、逐次クラスタリング方法、逐次クラスタリングプログラムは以下のような態様の構成とする。
【０００８】
（１）新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムを実行する逐次クラスタリング装置であって、過去のクラスタリング処理されたクラスタ構造を蓄積しておき、前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新することとし、前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定する判定手段と、前記判定の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新する更新手段とを備える構成とする。
【０００９】
（２）新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムを実行する逐次クラスタリング方法であって、過去のクラスタリング処理されたクラスタ構造を蓄積しておき、前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新することとし、前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定し、前記判定の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新する構成とする。
【００１０】
（３）新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムをコンピュータに実行させるための逐次クラスタリングプログラムであって、過去のクラスタリング処理されたクラスタ構造を蓄積してする蓄積処理と、前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新する処理を備え、前記更新処理は、前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定し、前記判定処理の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新する構成とする。
【００１１】
すなわち、本発明に係る逐次クラスタリング装置、方法、プログラムでは、クラスタリングによるＤＢＳＣＡＮアルゴリズムを逐次的に実行する手法として、新たな点データが逐次的に得られる状況で、毎回それまでに得られた全ての点データを入力としてＤＢＳＣＡＮアルゴリズムを再実行するのではなく、前回の計算で得られたクラスタ結果を新たな点データに合わせて更新することで新しいクラスタを得るようにしている。この手法を用いることで、逐次的に点データが得られる状況でクラスタリングを実行する計算コストが削減される。
【００１２】
手法のポイントは、新たな点データが追加されるときに起こりうる変化として、(1)新しく追加された点がいずれかのクラスタに含まれる、(2)新しく追加された点がクラスタ核になる、(3)新しく追加された点の近傍の点がクラスタ核になる、(4)新しく追加された点がNOISE（雑音）になる、の４種類のみに限定されることに着目したことである。これらのうち既存のクラスタの構造の変化を引き起こす可能性があるのは(2)、(3)のみである。これらの変化が生じた場合、既存のクラスタの構造に対して、(a)新しいクラスタの出現、(b)既存のクラスタの拡張、(C)クラスタ間の結合、のいずれかが発生する可能性があるため、これらの変化の発生を調べる。いずれの処理も追加した点の近傍のみを調べることで行うことができるため、更新の範囲が局所的なものにすることができ、計算コストの削減になる。
【発明の効果】
【００１３】
本発明によれば、逐次的に点データが得られる状況でクラスタリングによるＤＢＳＣＡＮアルゴリズムを逐次的に実行する際の計算コストを削減することのできる逐次クラスタリング装置とその方法及びプログラムを提供することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明に係る逐次クラスタリング装置の一実施形態とするユーザ位置判定システムの全体構成を示すブロック図。
【図２】上記実施形態の位置データの例を示す図。
【図３】上記実施形態のクラスタデータの例を示す図。
【図４】上記実施形態のＩＤ変換テーブルの例を示す図。
【図５】上記実施形態において、装置全体の処理の流れを示すフローチャート。
【図６】図５の逐次クラスタリング処理の流れを示すフローチャート。
【図７】図６の近傍位置データ取得処理の流れを示すフローチャート。
【図８】図６のクラスタ更新処理の流れを示すフローチャート。
【図９】図７のクラスタ部分更新処理１の流れを示すフローチャート。
【図１０】図９のクラスタ部分更新処理１−１の流れを示すフローチャート。
【図１１】図７のクラスタ部分更新処理２の流れを示すフローチャート。
【図１２】図１１のクラスタ部分更新処理２−１の流れを示すフローチャート。
【発明を実施するための形態】
【００１５】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１６】
図1は本発明に係る逐次クラスタリング装置を利用したユーザ位置判定システムの全体構成を示すブロック図である。このシステムは、入力部１１、記録部１２、処理部１３、出力部１４から構成される。
【００１７】
入力部１１はＧＰＳ受信機等によって得られる位置情報を逐次入力するための位置情報逐次入力手段１１１を備える。この入力手段１１は、逐次的に与えられ、二次元の座標をもつ点として表される位置データを取り込んで、順次記録部１２の位置データ記録手段１２１に送信する。
【００１８】
記録部１２は位置データ記録手段１２１、クラスタリング結果記録手段１２２、クラスタＩＤ変換テーブル記録手段１２３を備える。
【００１９】
位置データ記録手段１２１は、入力部１１から送信される位置データを随時受け取って記録する。位置データは、図２に示す例のように、記録部１２に入力された順に付与される入力データＩＤをそれぞれの座標を対応付けた形式で保持される。一度記録されたデータが修正されることはない。
【００２０】
クラスタリング結果記録手段１２２は、位置データ記録手段１２１に記録されている位置データを処理部１３の逐次クラスタリング処理手段１３１に適用することによって得られた出力を格納する。クラスタリング結果記録手段１２２によって記録されるクラスタデータの例を図３に示す。
【００２１】
図３に示すクラスタデータでは、テーブルの１列目と２列目によって、各入力データＩＤに、それぞれの点がどのクラスタに属するかを示すクラスタＩＤを対応付けている。例えば、入力データＩＤ１と３が示す点が、同じクラスタ（クラスタＩＤ１）に属することを示している。一般にクラスタリングアルゴリズムとは、入力データに対してそれが属するクラスタを割り振るものである。ＤＢＳＣＡＮアルゴリズムに特有の概念として、入力された点の中にはいずれのクラスタにも属さないものもあり、そのような点にはNOIZEという特別なＩＤが与えられる。
【００２２】
図３のテーブルの３列目にはその点がクラスタ核かどうかを示すフラグが保持される。ここで、ある点がクラスタ核であるとは、「その点の座標を中心として、距離があるしきい値以内（以下、εとする）にＮ点以上の点が存在すること」と定義する。ここで、ある点ｐから距離ε以内にある点の集合を「点ｐのε-近傍」と定義する。クラスタ核はＤＢＳＣＡＮアルゴリズムにおいて中心となる概念である。ＤＢＳＣＡＮアルゴリズムはクラスタ核である点とその近傍、さらに近傍に別のクラスタ核が含まれるならば、さらにその近傍を…として、クラスタ核の近傍を一つのクラスタとしてクラスタリングを行う手法である（ＤＢＳＣＡＮの詳細については非特許文献１を参照）。
【００２３】
クラスタＩＤ変換テーブル記録手段１２３は、逐次クラスタリング処理を実行する過程で、異なるクラスタの統合が発生した場合に、それらのクラスタＩＤが同じクラスタを表すという情報を保管するためのものである。具体的には、図４に示すようなテーブルが保管されている。
【００２４】
図４のテーブルはもとのクラスタＩＤと、そのクラスタＩＤと同じクラスタを表すクラスタＩＤとの対応関係が保持されている。この例では、例えばクラスタＩＤ２をもつクラスタは、クラスタＩＤ３をもつクラスタと等しく、さらにクラスタＩＤ５をもつクラスタと等しいとされる。また、ある単一のクラスタに対して発行された複数のクラスタＩＤのうち、最後に発行されたものをそのクラスタの代表ＩＤとする。
【００２５】
クラスタＩＤは、１，２，３，…と順に発行されるものとすると、あるクラスタの代表ＩＤは、そのクラスタに対して発行されたクラスタＩＤのうち最大のものとなる。クラスタＩＤ変換テーブルには、常にあるＩＤからそれよりも大きなＩＤへの変換を登録するようにする。この結果として、任意のクラスタＩＤを入力として複数回テーブルを参照することで、対応するクラスタの代表ＩＤを知ることができる。図４のテーブルでは、クラスタＩＤ４に対応するクラスタの代表ＩＤはＩＤ７であるが、ＩＤ４でテーブルを検索してＩＤ６を獲得し、さらにＩＤ６で再度テーブルを検索することで代表ＩＤ７を得ることができる。
【００２６】
処理部１３は逐次クラスタリング処理手段１３１を備える。この逐次クラスタリング処理手段１３１は、位置データ記憶手段１２１から新しく与えられた入力と、クラスタリング結果記憶手段１２２から与えられたある時点でのクラスタリング結果を受け取り、入力が与えられた後のクラスタリング結果を出力する。
【００２７】
出力部１４はクラスタ出力手段１４１を備える。このクラスタ出力手段１４１は、記録部１３よりクラスタリング結果を受け取り、それを出力する。
【００２８】
上記システムの処理全体の処理の流れを、図５に示すフローチャートを参照して説明する。
【００２９】
処理開始が指示されると（ステップＳ１）、入力部１１から入力されるデータを待機し（ステップＳ２）、新しい入力があるまでは、ステップＳ３の判定によってステップＳ２に遷移して待機状態となる。新たに入力が得られたときにステップＳ４に遷移する。ステップＳ４では逐次クラスタリング処理を実行する。この処理のフローについては後述する。
【００３０】
ステップＳ５で逐次クラスタリング処理によって得られたクラスタリング結果を記録し、ステップＳ６でクラスタリング結果を出力部１４に記録する。ステップＳ７で引き続きデータが入力されるかどうかを判断し、入力されると判断されるならばデータ入力の待機状態（ステップＳ２）に戻る。ステップＳ７で入力はないと判断された場合には、一連の処理を終了する（ステップＳ８）。
【００３１】
次に、図５の全体処理フローのステップＳ４で用いられる逐次クラスタリング処理について、図６に示すフローチャートを参照して説明する。
【００３２】
処理開始が指示されると（ステップＳ１１）、ステップＳ１２，Ｓ１３で、新しく与えられた入力データおよび既にクラスタリングを行った結果をロードする。ここで、新しく入力されたデータをｐとする。ステップＳ１４で新しく入力されたデータｐを引数として、近傍位置データ取得処理を実行する。この近傍位置データ取得処理は、位置データ記録手段１２１に記録されている点のうち、点ｐのε-近傍に含まれる点を全て取得する処理である。詳細は後述する。ステップＳ１５で、ｐのクラスタＩＤの初期値としてNOIZEを与える。その後、ステップＳ１６でクラスタ更新処理を行って一連の処理を終了する（ステップＳ１７）。
【００３３】
上記ステップＳ１４の近傍位置データ取得処理について、図７に示すフローチャートを参照して説明する。
【００３４】
まず、処理開始が指示されると（ステップＳ１０１）、ステップＳ１０２で入力として与えられた点を受け取り、ステップＳ１０３で記録部１２に蓄積されている位置データを読み込む。ステップＳ１０４で、Ｓ１０３で読み込んだ位置データのうち、Ｓ１０２で入力として与えられた点のε-近傍に含まれる点を全て取得する。近傍の点の取得には、［非特許文献１］と同様に、予め点を空間データの高速な検索に適したデータ構造であるR - Treeという形式で、位置データ記録手段１２１によって記録しておくことによって、処理時間の削減を図る。ステップＳ１０５で取得した点を出力して一連の処理を終了する（ステップＳ１０６）。
【００３５】
上記クラスタ更新処理Ｓ１６について図８に示すフローチャートを参照して説明する。前述したように、クラスタ更新は新しく追加された点ｐとその近傍の点のうち、新しくクラスタ核になる点があるかどうかを調べる処理と、クラスタ核になる点があった場合に新しいクラスタの生成、既存クラスタ間の統合を行う処理の２つの処理を行うことで成される。図８の処理では、新しく追加した点ｐがクラスタ核となるかどうかを調べ、それぞれの場合に対して異なる処理を実行する。
【００３６】
まず、処理開始が指示されると（ステップＳ２１）、ステップＳ２２で点ｐとそのε-近傍に含まれる点の集合を入力として与える。そして、ステップＳ２３で、ε-近傍に含まれる点の数がＮ以上かどうかを調べる。Ｎ以上であった場合には、ｐはクラスタ核となるため、ステップＳ２４のクラスタ更新部分処理１に進む。Ｎ以下の場合はｐはクラスタ核ではないため、ステップＳ２５のクラスタ更新部分処理２に進む。分岐した先のＳ２４、Ｓ２５のどちらかの処理が終了したとき、一連の処理を終了する（ステップＳ２６）。
【００３７】
上記ステップＳ２４のクラスタ更新部分処理1について、図９に示すフローチャートを参照して説明する。この処理は、新しく入力された点ｐがクラスタ核であった場合の更新処理である。まず、処理開始が指示されると（ステップＳ３２）、ステップＳ３２で点ｐとpのε-近傍の点を入力する。ステップＳ３３でｐにクラスタ核マークを与え、ステップＳ３４で新しいクラスタＩＤを発行して、点ｐにそのクラスタＩＤを与える。新しいクラスタＩＤを発行することは、点ｐを中心とした新しいクラスタが形成されることを意味する。
【００３８】
ステップＳ３５〜Ｓ４０で、ｐのε-近傍に含まれる各点に対して順に更新を行う。ε-近傍に含まれるある点をｑとして、以下ｑの更新手順を説明する。更新の内容は、まずその点ｑが既にクラスタ核であるかどうかによって分岐する。すなわち、ステップＳ３６でｑがクラスタ核かどうかを判定し、クラスタ核だった場合にはステップＳ３７へ遷移し、そうでなかった場合はＳ３９へ遷移する。ステップＳ３７、Ｓ３８でＩＤ変換テーブルを用いて、ｑをクラスタ核とするクラスタとｐをクラスタ核とするクラスタとが等しいクラスタであることを登録している。具体的には、ステップＳ３７でｑが表すクラスタの代表ＩＤを獲得し、ステップＳ３８でクラスタＩＤ変換テーブルに、ｑの代表ＩＤからｐのクラスタＩＤへの変換を登録する。ｐのクラスタＩＤは今回の処理で新たに発行されたものなので、必ずｑの代表ＩＤよりも大きい。ｑがクラスタ核でなかった場合には、ステップＳ３９でクラスタ更新部分処理１−１に遷移する。ステップＳ３８またはＳ３９の処理が終了した場合には、ステップＳ４０でｐの近傍の点がまだあるか判断し、ある場合にはステップＳ３５に遷移し、ない場合には一連の処理を終了する（ステップＳ４１）。
【００３９】
上記ステップＳ３９のクラスタ更新部分処理１−１について、図１０に示すフローチャートを参照して説明する。このクラスタ更新部分処理１−１では、新たに追加した点pの近傍の点のうち、事前にクラスタ核でなかった点を対象として、その点が新たなクラスタ核になるかどうかを調べる。その後、新たなクラスタ核になった場合には、その周囲に結合するクラスタが存在するかどうかを調べる。クラスタ核にならなかった場合には、ｐと同じクラスタＩＤを与える。
【００４０】
まず、処理開始が指示されると（ステップＳ５１）、ステップＳ５２で、入力として更新対象の点であり、かつクラスタ核でない点ｑを入力として受け取る。ステップＳ５３で、近傍位置データ取得処理によって、点ｑのε-近傍の点を全て取得する。ステップＳ５４でε-近傍のサイズがしきい値を超えているかを調べる。しきい値を超えている場合にはｑが新たにクラスタ核となり、ステップＳ５５に遷移する。ステップＳ５５でｑをクラスタ核として登録し、そのクラスタＩＤとしてｐと同じクラスタＩＤを付与する。これは、ｐとｑの距離がε以下であるため、必ず同じクラスタとなるためである。
【００４１】
ステップＳ５６〜Ｓ６１で、ｑのε-近傍に含まれる各点について更新を行う。まず、ｑのε-近傍の点からｐのε-近傍でない点を１つ選択してｒとし（ステップＳ５６）、そのε-近傍に含まれる点ｒがクラスタ核であるか判定し（ステップＳ５７）、点ｒがクラスタ核であった場合、ｑとｒが表すクラスタが等しいことを登録する（ステップＳ５８，Ｓ５９）。点ｒがクラスタ核でなかった場合には、ｒにｐのクラスタＩＤを付与する（ステップＳ６０）。ここで、ステップＳ６１で近傍の点がまだ存在するかを判断し（ステップＳ６１）、存在する場合にはステップＳ５６に遷移し、存在しない場合には一連の処理を終了する（ステップＳ６３）。一方、ステップＳ５４でｑがクラスタ核にならなかった場合には、ｑはｐをクラスタ核とするクラスタと同じクラスタであるとして、ｐのクラスタＩＤをｑに与え（ステップＳ６２）、一連の処理を終了する（ステップＳ６３）。
【００４２】
次に、上記ステップＳ２５のクラスタ更新部分処理２について、図１１に示すフローチャートを参照して説明する。この処理は、図８のクラスタ更新処理のステップＳ２３で、追加された点がクラスタ核でないと判定されたときの処理に相当する。まず、処理開始が指示されると（ステップＳ７１）、ステップＳ７２で点ｐとそのε-近傍の点の集合を入力として受け取る。ステップＳ７３〜Ｓ７９でｐのε-近傍に含まれる各点に対して更新を行う。以下、ｑをε-近傍のひとつの点として説明する。ステップＳ７３でｑの更新対象マークを消したのち、ステップＳ７４でｑがクラスタ核かどうかを調べる。クラスタ核であったならばステップＳ７５に、そうでなければステップＳ７８に遷移する。
【００４３】
ステップＳ７５〜Ｓ７７では、クラスタｐのクラスタＩＤを付け替える処理を行う。まず、ステップＳ７５でｐとｑのクラスタＩＤが対応するクラスタの代表ＩＤを検索する。ステップＳ７６でそれらの代表ＩＤを比較し、ｑの代表ＩＤの方が大きいならば、ステップＳ７７に遷移してそのＩＤをｐに与える。ｑがクラスタ核でなかった場合、ステップＳ７８でクラスタ更新部分処理２-１を実行する。処理の引数として、ｑを与える。ステップＳ７７またはＳ７８の処理が終了した場合には、ステップＳ７９で更新対象がまだあるか判断し、更新対象がある場合にはステップＳ７３に遷移し、更新対象がない場合には一連の処理を終了する（ステップＳ８０）。
【００４４】
上記ステップＳ７８のクラスタ更新部分処理２-１について、図１２に示すフローチャートを参照して説明する。この処理は、クラスタ更新部分処理１-１と類似点が多いが、ｐがクラスタ核でないために処理が増えている。
【００４５】
まず、処理開始が指示されると（ステップＳ８１）、ステップＳ８２で更新対象の点ｑを入力として与える。ステップＳ８３でｑのε-近傍に含まれる点を取得する。ステップＳ８４で点ｑのε-近傍のサイズを調べ、ｑが新たにクラスタ核となったかどうかを判定する。クラスタ核となっている場合にはステップＳ８５に、そうでない場合にはステップＳ９２に遷移する。
【００４６】
ステップＳ８５では、クラスタ核と判定されたｑに対して新しく発行したクラスタＩＤを与える。ステップＳ８６〜Ｓ９３で、ｑのε-近傍に含まれる全ての点について順に更新を行う。ｒをｑのε一近傍の点として、以下に説明を行う。
【００４７】
まず、ステップＳ８１〜Ｓ８４までは図１０の処理１−１のステップＳ５１〜Ｓ５４と同じであるので省略する。ステップＳ８５では、ｑにクラスタ核マークと新しく発行したクラスタＩＤを与える。続いて、ステップＳ８６でｑのε-近傍の点を１つ選択し、選択した点をｒとする。この点ｒがクラスタ核かどうかを調べ（ステップＳ８７）、クラスタ核の場合はステップＳ８８に、そうでない場合にはステップＳ９０に進む。
【００４８】
ステップＳ８８、Ｓ８９で行う処理は、クラスタ更新部分処理１-１でのステップＳ５８、Ｓ５９で行う処理とほぼ同じであり、違いはＩＤの変換先がｐのＩＤからｑのＩＤになったことのみである。ステップＳ９０ではクラスタ核でないｒに対してｑと同じクラスタＩＤを与える。ステップＳ８９またはＳ９０の処理が終了した場合には、ステップＳ９１で更新対象がまだあるか判断し、更新対象がある場合にはステップＳ８６に遷移し、更新対象がない場合には一連の処理を終了する（ステップＳ９３）。
【００４９】
上記ステップＳ８４でｑのε-近傍のサイズがＮより小さい場合には、ステップＳ９２に遷移する。ステップＳ９２では、ｑがクラスタ核でなかった場合に、ｑにｐと同じクラスタＩＤを与える。その処理が終了した場合には一連の処理を終了する（ステップＳ９３）。
【００５０】
以上の処理を行うユーザ位置判定システムでは、本発明を適用することによって、ノイズに強いといったユーザの滞在地抽出に適した特性を持つＤＢＳＣＡＮアルゴリズムを、逐次的にデータが入力される状況で適用することが可能になる。その効果として、時間的遅れなくユーザがある滞在地に滞在したという情報を得ることができ、実時間でのコンテクストアウェアネスサービスの実現につなげることができる。
【００５１】
尚、この発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成を削除してもよい。さらに、異なる実施形態例に亘る構成要素を適宜組み合わせても良い。
【符号の説明】
【００５２】
１１…入力部、１１１…位置情報逐次入力手段、
１２…記録部、１２１…位置データ記録手段、１２２…クラスタリング結果記録手段、１２３…クラスタＩＤ変換テーブル記録手段、
１３…処理部、１３１…逐次クラスタリング処理手段、
１４…出力部、１４１…クラスタ出力手段。
【技術分野】
【０００１】
本発明は、例えばＧＰＳ（Global Positioning System）等を利用することによって得られるユーザ位置情報から、当該ユーザが滞在している場所をリアルタイムに判定する処理に利用される逐次クラスタリング装置とその方法及びプログラムに関する。
【背景技術】
【０００２】
ＧＰＳ等を用いて一定時間間隔で取得されたユーザの位置を示す座標データ（以下、本明細書において点データと総称する）から、クラスタリングによってユーザが滞在した場所を抽出する処理が提案されている。このようなアルゴリズムのひとつとしてＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムが利用されており、効果をあげている。ＤＢＳＣＡＮアルゴリズムの特性として、ノイズを含むデータに強い、クラスタの形状に依存しないなどの点が挙げられる。
【０００３】
しかしながら、既存のＤＢＳＣＡＮアルゴリズムには、その逐次的な実行方法が示されていない。そのため、点データが逐次的に得られる状況で、得られた点データに対して常に最新のクラスタリング結果を得ようとした場合、新しく点データが得られるごとに、現在までに得られた全ての点データに対してクラスタリング処理を再実行しなければならない。この処理には計算コストがかかるため、リアルタイムで入力データが得られる状況でユーザの滞在地を知るような処理には不向きである。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", ACM KDD‘96
【非特許文献２】Brett Adams, Dinh Phung, and Svetha Venkatesh, "Extraction of Social Context and Application to Personal Multimedia Exploration", ACM MM'06
【発明の概要】
【発明が解決しようとする課題】
【０００５】
以上のように、既存のＤＢＳＣＡＮアルゴリズムには、その逐次的な実行方法が示されていないため、入力データが逐次的に得られる状況で、得られたデータに対して常に最新のクラスタリング結果を得る場合には、新しくデータが得られるごとに現在までに得られた全てのデータに対してクラスタリング処理を再実行しなければならない。
【０００６】
本発明は、上記の事情を鑑みてなされたもので、逐次的にデータが得られる状況でクラスタリングによるＤＢＳＣＡＮアルゴリズムを逐次的に実行する際の計算コストを削減することのできる逐次クラスタリング装置とその方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために本発明に係る逐次クラスタリング装置、逐次クラスタリング方法、逐次クラスタリングプログラムは以下のような態様の構成とする。
【０００８】
（１）新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムを実行する逐次クラスタリング装置であって、過去のクラスタリング処理されたクラスタ構造を蓄積しておき、前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新することとし、前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定する判定手段と、前記判定の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新する更新手段とを備える構成とする。
【０００９】
（２）新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムを実行する逐次クラスタリング方法であって、過去のクラスタリング処理されたクラスタ構造を蓄積しておき、前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新することとし、前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定し、前記判定の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新する構成とする。
【００１０】
（３）新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムをコンピュータに実行させるための逐次クラスタリングプログラムであって、過去のクラスタリング処理されたクラスタ構造を蓄積してする蓄積処理と、前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新する処理を備え、前記更新処理は、前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定し、前記判定処理の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新する構成とする。
【００１１】
すなわち、本発明に係る逐次クラスタリング装置、方法、プログラムでは、クラスタリングによるＤＢＳＣＡＮアルゴリズムを逐次的に実行する手法として、新たな点データが逐次的に得られる状況で、毎回それまでに得られた全ての点データを入力としてＤＢＳＣＡＮアルゴリズムを再実行するのではなく、前回の計算で得られたクラスタ結果を新たな点データに合わせて更新することで新しいクラスタを得るようにしている。この手法を用いることで、逐次的に点データが得られる状況でクラスタリングを実行する計算コストが削減される。
【００１２】
手法のポイントは、新たな点データが追加されるときに起こりうる変化として、(1)新しく追加された点がいずれかのクラスタに含まれる、(2)新しく追加された点がクラスタ核になる、(3)新しく追加された点の近傍の点がクラスタ核になる、(4)新しく追加された点がNOISE（雑音）になる、の４種類のみに限定されることに着目したことである。これらのうち既存のクラスタの構造の変化を引き起こす可能性があるのは(2)、(3)のみである。これらの変化が生じた場合、既存のクラスタの構造に対して、(a)新しいクラスタの出現、(b)既存のクラスタの拡張、(C)クラスタ間の結合、のいずれかが発生する可能性があるため、これらの変化の発生を調べる。いずれの処理も追加した点の近傍のみを調べることで行うことができるため、更新の範囲が局所的なものにすることができ、計算コストの削減になる。
【発明の効果】
【００１３】
本発明によれば、逐次的に点データが得られる状況でクラスタリングによるＤＢＳＣＡＮアルゴリズムを逐次的に実行する際の計算コストを削減することのできる逐次クラスタリング装置とその方法及びプログラムを提供することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明に係る逐次クラスタリング装置の一実施形態とするユーザ位置判定システムの全体構成を示すブロック図。
【図２】上記実施形態の位置データの例を示す図。
【図３】上記実施形態のクラスタデータの例を示す図。
【図４】上記実施形態のＩＤ変換テーブルの例を示す図。
【図５】上記実施形態において、装置全体の処理の流れを示すフローチャート。
【図６】図５の逐次クラスタリング処理の流れを示すフローチャート。
【図７】図６の近傍位置データ取得処理の流れを示すフローチャート。
【図８】図６のクラスタ更新処理の流れを示すフローチャート。
【図９】図７のクラスタ部分更新処理１の流れを示すフローチャート。
【図１０】図９のクラスタ部分更新処理１−１の流れを示すフローチャート。
【図１１】図７のクラスタ部分更新処理２の流れを示すフローチャート。
【図１２】図１１のクラスタ部分更新処理２−１の流れを示すフローチャート。
【発明を実施するための形態】
【００１５】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１６】
図1は本発明に係る逐次クラスタリング装置を利用したユーザ位置判定システムの全体構成を示すブロック図である。このシステムは、入力部１１、記録部１２、処理部１３、出力部１４から構成される。
【００１７】
入力部１１はＧＰＳ受信機等によって得られる位置情報を逐次入力するための位置情報逐次入力手段１１１を備える。この入力手段１１は、逐次的に与えられ、二次元の座標をもつ点として表される位置データを取り込んで、順次記録部１２の位置データ記録手段１２１に送信する。
【００１８】
記録部１２は位置データ記録手段１２１、クラスタリング結果記録手段１２２、クラスタＩＤ変換テーブル記録手段１２３を備える。
【００１９】
位置データ記録手段１２１は、入力部１１から送信される位置データを随時受け取って記録する。位置データは、図２に示す例のように、記録部１２に入力された順に付与される入力データＩＤをそれぞれの座標を対応付けた形式で保持される。一度記録されたデータが修正されることはない。
【００２０】
クラスタリング結果記録手段１２２は、位置データ記録手段１２１に記録されている位置データを処理部１３の逐次クラスタリング処理手段１３１に適用することによって得られた出力を格納する。クラスタリング結果記録手段１２２によって記録されるクラスタデータの例を図３に示す。
【００２１】
図３に示すクラスタデータでは、テーブルの１列目と２列目によって、各入力データＩＤに、それぞれの点がどのクラスタに属するかを示すクラスタＩＤを対応付けている。例えば、入力データＩＤ１と３が示す点が、同じクラスタ（クラスタＩＤ１）に属することを示している。一般にクラスタリングアルゴリズムとは、入力データに対してそれが属するクラスタを割り振るものである。ＤＢＳＣＡＮアルゴリズムに特有の概念として、入力された点の中にはいずれのクラスタにも属さないものもあり、そのような点にはNOIZEという特別なＩＤが与えられる。
【００２２】
図３のテーブルの３列目にはその点がクラスタ核かどうかを示すフラグが保持される。ここで、ある点がクラスタ核であるとは、「その点の座標を中心として、距離があるしきい値以内（以下、εとする）にＮ点以上の点が存在すること」と定義する。ここで、ある点ｐから距離ε以内にある点の集合を「点ｐのε-近傍」と定義する。クラスタ核はＤＢＳＣＡＮアルゴリズムにおいて中心となる概念である。ＤＢＳＣＡＮアルゴリズムはクラスタ核である点とその近傍、さらに近傍に別のクラスタ核が含まれるならば、さらにその近傍を…として、クラスタ核の近傍を一つのクラスタとしてクラスタリングを行う手法である（ＤＢＳＣＡＮの詳細については非特許文献１を参照）。
【００２３】
クラスタＩＤ変換テーブル記録手段１２３は、逐次クラスタリング処理を実行する過程で、異なるクラスタの統合が発生した場合に、それらのクラスタＩＤが同じクラスタを表すという情報を保管するためのものである。具体的には、図４に示すようなテーブルが保管されている。
【００２４】
図４のテーブルはもとのクラスタＩＤと、そのクラスタＩＤと同じクラスタを表すクラスタＩＤとの対応関係が保持されている。この例では、例えばクラスタＩＤ２をもつクラスタは、クラスタＩＤ３をもつクラスタと等しく、さらにクラスタＩＤ５をもつクラスタと等しいとされる。また、ある単一のクラスタに対して発行された複数のクラスタＩＤのうち、最後に発行されたものをそのクラスタの代表ＩＤとする。
【００２５】
クラスタＩＤは、１，２，３，…と順に発行されるものとすると、あるクラスタの代表ＩＤは、そのクラスタに対して発行されたクラスタＩＤのうち最大のものとなる。クラスタＩＤ変換テーブルには、常にあるＩＤからそれよりも大きなＩＤへの変換を登録するようにする。この結果として、任意のクラスタＩＤを入力として複数回テーブルを参照することで、対応するクラスタの代表ＩＤを知ることができる。図４のテーブルでは、クラスタＩＤ４に対応するクラスタの代表ＩＤはＩＤ７であるが、ＩＤ４でテーブルを検索してＩＤ６を獲得し、さらにＩＤ６で再度テーブルを検索することで代表ＩＤ７を得ることができる。
【００２６】
処理部１３は逐次クラスタリング処理手段１３１を備える。この逐次クラスタリング処理手段１３１は、位置データ記憶手段１２１から新しく与えられた入力と、クラスタリング結果記憶手段１２２から与えられたある時点でのクラスタリング結果を受け取り、入力が与えられた後のクラスタリング結果を出力する。
【００２７】
出力部１４はクラスタ出力手段１４１を備える。このクラスタ出力手段１４１は、記録部１３よりクラスタリング結果を受け取り、それを出力する。
【００２８】
上記システムの処理全体の処理の流れを、図５に示すフローチャートを参照して説明する。
【００２９】
処理開始が指示されると（ステップＳ１）、入力部１１から入力されるデータを待機し（ステップＳ２）、新しい入力があるまでは、ステップＳ３の判定によってステップＳ２に遷移して待機状態となる。新たに入力が得られたときにステップＳ４に遷移する。ステップＳ４では逐次クラスタリング処理を実行する。この処理のフローについては後述する。
【００３０】
ステップＳ５で逐次クラスタリング処理によって得られたクラスタリング結果を記録し、ステップＳ６でクラスタリング結果を出力部１４に記録する。ステップＳ７で引き続きデータが入力されるかどうかを判断し、入力されると判断されるならばデータ入力の待機状態（ステップＳ２）に戻る。ステップＳ７で入力はないと判断された場合には、一連の処理を終了する（ステップＳ８）。
【００３１】
次に、図５の全体処理フローのステップＳ４で用いられる逐次クラスタリング処理について、図６に示すフローチャートを参照して説明する。
【００３２】
処理開始が指示されると（ステップＳ１１）、ステップＳ１２，Ｓ１３で、新しく与えられた入力データおよび既にクラスタリングを行った結果をロードする。ここで、新しく入力されたデータをｐとする。ステップＳ１４で新しく入力されたデータｐを引数として、近傍位置データ取得処理を実行する。この近傍位置データ取得処理は、位置データ記録手段１２１に記録されている点のうち、点ｐのε-近傍に含まれる点を全て取得する処理である。詳細は後述する。ステップＳ１５で、ｐのクラスタＩＤの初期値としてNOIZEを与える。その後、ステップＳ１６でクラスタ更新処理を行って一連の処理を終了する（ステップＳ１７）。
【００３３】
上記ステップＳ１４の近傍位置データ取得処理について、図７に示すフローチャートを参照して説明する。
【００３４】
まず、処理開始が指示されると（ステップＳ１０１）、ステップＳ１０２で入力として与えられた点を受け取り、ステップＳ１０３で記録部１２に蓄積されている位置データを読み込む。ステップＳ１０４で、Ｓ１０３で読み込んだ位置データのうち、Ｓ１０２で入力として与えられた点のε-近傍に含まれる点を全て取得する。近傍の点の取得には、［非特許文献１］と同様に、予め点を空間データの高速な検索に適したデータ構造であるR - Treeという形式で、位置データ記録手段１２１によって記録しておくことによって、処理時間の削減を図る。ステップＳ１０５で取得した点を出力して一連の処理を終了する（ステップＳ１０６）。
【００３５】
上記クラスタ更新処理Ｓ１６について図８に示すフローチャートを参照して説明する。前述したように、クラスタ更新は新しく追加された点ｐとその近傍の点のうち、新しくクラスタ核になる点があるかどうかを調べる処理と、クラスタ核になる点があった場合に新しいクラスタの生成、既存クラスタ間の統合を行う処理の２つの処理を行うことで成される。図８の処理では、新しく追加した点ｐがクラスタ核となるかどうかを調べ、それぞれの場合に対して異なる処理を実行する。
【００３６】
まず、処理開始が指示されると（ステップＳ２１）、ステップＳ２２で点ｐとそのε-近傍に含まれる点の集合を入力として与える。そして、ステップＳ２３で、ε-近傍に含まれる点の数がＮ以上かどうかを調べる。Ｎ以上であった場合には、ｐはクラスタ核となるため、ステップＳ２４のクラスタ更新部分処理１に進む。Ｎ以下の場合はｐはクラスタ核ではないため、ステップＳ２５のクラスタ更新部分処理２に進む。分岐した先のＳ２４、Ｓ２５のどちらかの処理が終了したとき、一連の処理を終了する（ステップＳ２６）。
【００３７】
上記ステップＳ２４のクラスタ更新部分処理1について、図９に示すフローチャートを参照して説明する。この処理は、新しく入力された点ｐがクラスタ核であった場合の更新処理である。まず、処理開始が指示されると（ステップＳ３２）、ステップＳ３２で点ｐとpのε-近傍の点を入力する。ステップＳ３３でｐにクラスタ核マークを与え、ステップＳ３４で新しいクラスタＩＤを発行して、点ｐにそのクラスタＩＤを与える。新しいクラスタＩＤを発行することは、点ｐを中心とした新しいクラスタが形成されることを意味する。
【００３８】
ステップＳ３５〜Ｓ４０で、ｐのε-近傍に含まれる各点に対して順に更新を行う。ε-近傍に含まれるある点をｑとして、以下ｑの更新手順を説明する。更新の内容は、まずその点ｑが既にクラスタ核であるかどうかによって分岐する。すなわち、ステップＳ３６でｑがクラスタ核かどうかを判定し、クラスタ核だった場合にはステップＳ３７へ遷移し、そうでなかった場合はＳ３９へ遷移する。ステップＳ３７、Ｓ３８でＩＤ変換テーブルを用いて、ｑをクラスタ核とするクラスタとｐをクラスタ核とするクラスタとが等しいクラスタであることを登録している。具体的には、ステップＳ３７でｑが表すクラスタの代表ＩＤを獲得し、ステップＳ３８でクラスタＩＤ変換テーブルに、ｑの代表ＩＤからｐのクラスタＩＤへの変換を登録する。ｐのクラスタＩＤは今回の処理で新たに発行されたものなので、必ずｑの代表ＩＤよりも大きい。ｑがクラスタ核でなかった場合には、ステップＳ３９でクラスタ更新部分処理１−１に遷移する。ステップＳ３８またはＳ３９の処理が終了した場合には、ステップＳ４０でｐの近傍の点がまだあるか判断し、ある場合にはステップＳ３５に遷移し、ない場合には一連の処理を終了する（ステップＳ４１）。
【００３９】
上記ステップＳ３９のクラスタ更新部分処理１−１について、図１０に示すフローチャートを参照して説明する。このクラスタ更新部分処理１−１では、新たに追加した点pの近傍の点のうち、事前にクラスタ核でなかった点を対象として、その点が新たなクラスタ核になるかどうかを調べる。その後、新たなクラスタ核になった場合には、その周囲に結合するクラスタが存在するかどうかを調べる。クラスタ核にならなかった場合には、ｐと同じクラスタＩＤを与える。
【００４０】
まず、処理開始が指示されると（ステップＳ５１）、ステップＳ５２で、入力として更新対象の点であり、かつクラスタ核でない点ｑを入力として受け取る。ステップＳ５３で、近傍位置データ取得処理によって、点ｑのε-近傍の点を全て取得する。ステップＳ５４でε-近傍のサイズがしきい値を超えているかを調べる。しきい値を超えている場合にはｑが新たにクラスタ核となり、ステップＳ５５に遷移する。ステップＳ５５でｑをクラスタ核として登録し、そのクラスタＩＤとしてｐと同じクラスタＩＤを付与する。これは、ｐとｑの距離がε以下であるため、必ず同じクラスタとなるためである。
【００４１】
ステップＳ５６〜Ｓ６１で、ｑのε-近傍に含まれる各点について更新を行う。まず、ｑのε-近傍の点からｐのε-近傍でない点を１つ選択してｒとし（ステップＳ５６）、そのε-近傍に含まれる点ｒがクラスタ核であるか判定し（ステップＳ５７）、点ｒがクラスタ核であった場合、ｑとｒが表すクラスタが等しいことを登録する（ステップＳ５８，Ｓ５９）。点ｒがクラスタ核でなかった場合には、ｒにｐのクラスタＩＤを付与する（ステップＳ６０）。ここで、ステップＳ６１で近傍の点がまだ存在するかを判断し（ステップＳ６１）、存在する場合にはステップＳ５６に遷移し、存在しない場合には一連の処理を終了する（ステップＳ６３）。一方、ステップＳ５４でｑがクラスタ核にならなかった場合には、ｑはｐをクラスタ核とするクラスタと同じクラスタであるとして、ｐのクラスタＩＤをｑに与え（ステップＳ６２）、一連の処理を終了する（ステップＳ６３）。
【００４２】
次に、上記ステップＳ２５のクラスタ更新部分処理２について、図１１に示すフローチャートを参照して説明する。この処理は、図８のクラスタ更新処理のステップＳ２３で、追加された点がクラスタ核でないと判定されたときの処理に相当する。まず、処理開始が指示されると（ステップＳ７１）、ステップＳ７２で点ｐとそのε-近傍の点の集合を入力として受け取る。ステップＳ７３〜Ｓ７９でｐのε-近傍に含まれる各点に対して更新を行う。以下、ｑをε-近傍のひとつの点として説明する。ステップＳ７３でｑの更新対象マークを消したのち、ステップＳ７４でｑがクラスタ核かどうかを調べる。クラスタ核であったならばステップＳ７５に、そうでなければステップＳ７８に遷移する。
【００４３】
ステップＳ７５〜Ｓ７７では、クラスタｐのクラスタＩＤを付け替える処理を行う。まず、ステップＳ７５でｐとｑのクラスタＩＤが対応するクラスタの代表ＩＤを検索する。ステップＳ７６でそれらの代表ＩＤを比較し、ｑの代表ＩＤの方が大きいならば、ステップＳ７７に遷移してそのＩＤをｐに与える。ｑがクラスタ核でなかった場合、ステップＳ７８でクラスタ更新部分処理２-１を実行する。処理の引数として、ｑを与える。ステップＳ７７またはＳ７８の処理が終了した場合には、ステップＳ７９で更新対象がまだあるか判断し、更新対象がある場合にはステップＳ７３に遷移し、更新対象がない場合には一連の処理を終了する（ステップＳ８０）。
【００４４】
上記ステップＳ７８のクラスタ更新部分処理２-１について、図１２に示すフローチャートを参照して説明する。この処理は、クラスタ更新部分処理１-１と類似点が多いが、ｐがクラスタ核でないために処理が増えている。
【００４５】
まず、処理開始が指示されると（ステップＳ８１）、ステップＳ８２で更新対象の点ｑを入力として与える。ステップＳ８３でｑのε-近傍に含まれる点を取得する。ステップＳ８４で点ｑのε-近傍のサイズを調べ、ｑが新たにクラスタ核となったかどうかを判定する。クラスタ核となっている場合にはステップＳ８５に、そうでない場合にはステップＳ９２に遷移する。
【００４６】
ステップＳ８５では、クラスタ核と判定されたｑに対して新しく発行したクラスタＩＤを与える。ステップＳ８６〜Ｓ９３で、ｑのε-近傍に含まれる全ての点について順に更新を行う。ｒをｑのε一近傍の点として、以下に説明を行う。
【００４７】
まず、ステップＳ８１〜Ｓ８４までは図１０の処理１−１のステップＳ５１〜Ｓ５４と同じであるので省略する。ステップＳ８５では、ｑにクラスタ核マークと新しく発行したクラスタＩＤを与える。続いて、ステップＳ８６でｑのε-近傍の点を１つ選択し、選択した点をｒとする。この点ｒがクラスタ核かどうかを調べ（ステップＳ８７）、クラスタ核の場合はステップＳ８８に、そうでない場合にはステップＳ９０に進む。
【００４８】
ステップＳ８８、Ｓ８９で行う処理は、クラスタ更新部分処理１-１でのステップＳ５８、Ｓ５９で行う処理とほぼ同じであり、違いはＩＤの変換先がｐのＩＤからｑのＩＤになったことのみである。ステップＳ９０ではクラスタ核でないｒに対してｑと同じクラスタＩＤを与える。ステップＳ８９またはＳ９０の処理が終了した場合には、ステップＳ９１で更新対象がまだあるか判断し、更新対象がある場合にはステップＳ８６に遷移し、更新対象がない場合には一連の処理を終了する（ステップＳ９３）。
【００４９】
上記ステップＳ８４でｑのε-近傍のサイズがＮより小さい場合には、ステップＳ９２に遷移する。ステップＳ９２では、ｑがクラスタ核でなかった場合に、ｑにｐと同じクラスタＩＤを与える。その処理が終了した場合には一連の処理を終了する（ステップＳ９３）。
【００５０】
以上の処理を行うユーザ位置判定システムでは、本発明を適用することによって、ノイズに強いといったユーザの滞在地抽出に適した特性を持つＤＢＳＣＡＮアルゴリズムを、逐次的にデータが入力される状況で適用することが可能になる。その効果として、時間的遅れなくユーザがある滞在地に滞在したという情報を得ることができ、実時間でのコンテクストアウェアネスサービスの実現につなげることができる。
【００５１】
尚、この発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成を削除してもよい。さらに、異なる実施形態例に亘る構成要素を適宜組み合わせても良い。
【符号の説明】
【００５２】
１１…入力部、１１１…位置情報逐次入力手段、
１２…記録部、１２１…位置データ記録手段、１２２…クラスタリング結果記録手段、１２３…クラスタＩＤ変換テーブル記録手段、
１３…処理部、１３１…逐次クラスタリング処理手段、
１４…出力部、１４１…クラスタ出力手段。
【特許請求の範囲】
【請求項１】
新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムを実行する逐次クラスタリング装置であって、
過去のクラスタリング処理されたクラスタ構造を蓄積しておき、前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新することとし、
前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定する判定手段と、
前記判定の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新する更新手段と
を備えることを特徴とする逐次クラスタリング装置。
【請求項２】
新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムを実行する逐次クラスタリング方法であって、
過去のクラスタリング処理されたクラスタ構造を蓄積しておき、前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新することとし、
前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定し、
前記判定の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新することを特徴とする逐次クラスタリング方法。
【請求項３】
新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムをコンピュータに実行させるための逐次クラスタリングプログラムであって、
過去のクラスタリング処理されたクラスタ構造を蓄積してする蓄積処理と、
前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新処理とを備え、
前記更新処理は、
前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定し、
前記判定処理の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新することを特徴とする逐次クラスタリングプログラム。
【請求項１】
新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムを実行する逐次クラスタリング装置であって、
過去のクラスタリング処理されたクラスタ構造を蓄積しておき、前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新することとし、
前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定する判定手段と、
前記判定の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新する更新手段と
を備えることを特徴とする逐次クラスタリング装置。
【請求項２】
新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムを実行する逐次クラスタリング方法であって、
過去のクラスタリング処理されたクラスタ構造を蓄積しておき、前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新することとし、
前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定し、
前記判定の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新することを特徴とする逐次クラスタリング方法。
【請求項３】
新たな点データが逐次得られる状況下で、前記新たな点データが入力される毎に、ある点データを核として一定の距離範囲にある近傍点データをクラスタ単位とするクラスタリング処理によるＤＢＳＣＡＮ（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムをコンピュータに実行させるための逐次クラスタリングプログラムであって、
過去のクラスタリング処理されたクラスタ構造を蓄積してする蓄積処理と、
前記新たな点データが入力されたとき、蓄積されている既存のクラスタ構造を新たな点データに合わせて更新処理とを備え、
前記更新処理は、
前記新たな点データが入力されるときに、前記新たな点データがクラスタの核になるか、前記新たな点データの近傍点データがクラスタ核になるかを判定し、
前記判定処理の結果に基づいて、前記既存のクラスタ構造に対して、前記新たな点データ及びその近傍点データについて、新しいクラスタの出現、既存のクラスタの拡張、クラスタ間の結合、のいずれかの変化の発生を判定し更新することを特徴とする逐次クラスタリングプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１０−１８６２５６（Ｐ２０１０−１８６２５６Ａ）
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【出願番号】特願２００９−２８９４５（Ｐ２００９−２８９４５）
【出願日】平成２１年２月１０日（２００９．２．１０）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ２００８年１１月６日 社団法人情報処理学会発行の「情報処理学会研究報告 情処研報 Ｖｏｌ．２００８，Ｎｏ．１１０」に発表
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【出願日】平成２１年２月１０日（２００９．２．１０）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ２００８年１１月６日 社団法人情報処理学会発行の「情報処理学会研究報告 情処研報 Ｖｏｌ．２００８，Ｎｏ．１１０」に発表
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]