(57)【要約】  本発明は、目標ルートを若干のルートポイントからなるルートポイント集合として特徴付けて類似度距離行列を構築し、二つのルートポイント集合間毎の類似度を比較してから、類似度距離行列、距離しきい値ε及び密度しきい値ＭｉｎＰｔｓに基づいて密度クラスタリングによりルートポイント集合からなるクラスタを反復的に計算し、最後に、各クラスタのルートセットの最頻値を目標ホットルートとして出力する、密度クラスタリングに基づくホットルートの分析方法を開示した。本発明は、（１）目標ルートポイント集合の類似度の比較方法が提供されることと、（２）密度しきい値ＭｉｎＰｔｓの選択には一定の柔軟性やロバスト性があることと、（３）計算コストが低く、工学的な方法で実現されることという利点がある。【選択図】図１
2021514090.tif 000002
【特許請求の範囲】
【請求項１】
目標ルートを若干のルートポイントからなるルートポイント集合として特徴付けて類似度距離行列を構築するステップ１と、
二つのルートポイント集合間毎の類似度を比較してから、類似度距離行列、距離しきい値ε及び密度しきい値ＭｉｎＰｔｓに基づいてルートポイント集合から中核ルートセットをマイニングし、さらに、中核ルートセットに対する直接密度到達可能の関係に応じて、密度クラスタリングにより中核ルートセットがクラスタ化したクラスタを反復的に生成するステップ２と、
各クラスタのルートポイント集合の最頻値を目標ホットルートとして出力するステップ３と、
を含むことを特徴とする密度クラスタリングに基づくホットルートの分析方法。
【請求項２】
ステップ１はステップ１−１〜ステップ１−３を含み、
ステップ１−１では、ｎ個の目標ルートに対応するｎ個のルートポイント集合を収集したとし、ルートポイント集合毎は一つの目標ルートに対応し、ルートポイント集合中の要素毎は対応する目標ルート中の一つのルートポイントとなり、そして、ｉ個目のルートポイント集合Ｐｉとｊ個目のルートポイント集合Ｐｊとの間のＪａｃｃａｒｄ距離JaccardDist(Pi,Pj)は以下のように定義され、
【数２５】
2021514090.tif 000035
ステップ１−２では、ルートポイント集合をソートし、つまり、集合の大きさに関しては大きい順に、かつ索引値に関しては小さい順にｎ個のルートポイント集合をソートしてＰ１、Ｐ２、…、Ｐｎと記し、ただし、｜Ｐ１｜≧｜Ｐ２｜≧…≧｜Ｐｎ｜が満たされており、
ステップ１−３では、類似度距離行列を初期化し、つまり、距離しきい値εを設定し、初期化した類似度距離行列ＤｉｓｔＡｒｒａｙはＮ／Ａとなり、その行列の大きさがｎ×ｎであり、即ち、行列の行数と列数がいずれもｎであることを特徴とする、請求項１に記載の方法。
【請求項３】
ステップ１−３では、距離しきい値εはすべてのルートポイント集合の最近傍距離の平均値として値が取られ、即ち、
【数２６】
2021514090.tif 000036
とすることを特徴とする、請求項２に記載の方法。
【請求項４】
ステップ２はステップ２−１〜ステップ２−１１を含み、
ステップ２−１では、現在集合の索引を設定し、つまり、現在ルートポイント集合の索引をｓ＝１と設定し、
ステップ２−２では、比較待ち集合の索引を設定し、つまり、比較待ちルートポイント集合の索引をｔ＝ｓ＋１と設定し、
ステップ２−３では、比較待ち集合の索引を判断し、つまり、比較待ちルートポイント集合の索引を判断し、ｔ≦ｎかつ｜Ｐｔ｜／｜Ｐｓ｜≧１−εが満たされていないと、ステップ２−４へ進み、満たされていると、ステップ２−６を実行し、
ステップ２−４では、現在集合の索引を更新し、つまり、現在集合の索引値をｓ＝ｓ＋１と更新し、
ステップ２−５では、現在集合の索引を判断し、ｓ≧ｎが満たされていると、ステップ２−８へ進み、でないと、ステップ２−２へ戻り、
ステップ２−６では、類似度距離を計算し、つまり、現在集合の索引と比較待ち集合の索引に対応する二つのルートポイント集合間のＪａｃｃａｒｄ距離ＪａｃｃａｒｄＤｉｓｔ（Ｐｓ，Ｐｔ）を計算し、ＪａｃｃａｒｄＤｉｓｔ（Ｐｓ，Ｐｔ）≦εが満たされていると、類似度行列中の対応するセルの値を更新し、
DistArray[s,t] = JaccardDist(Ps,Pt)              （３）
DistArray[s,t]は類似度距離行列ＤｉｓｔＡｒｒａｙのｓ行目かつｔ列目の値を表し、
ステップ２−７では、比較待ち集合の索引をｔ＝ｔ＋１と更新し、ステップ２−３へ戻り、
ステップ２−８では、ルートポイント近傍の大きさを計算し、つまり、任意のルートポイント集合Ｐをセットし、ルートポイント集合Ｐとの類似度距離が距離しきい値ε以内にあるその他のルートポイント集合のすべてを当該ルートポイント集合Ｐのε近傍と定義してＮε（Ｐ）と記し、
Ｎε（Ｐ）＝｛Ｑ｜ＪａｃｃａｒｄＤｉｓｔ（Ｐ，Ｑ）≦ε＆＆Ｑ≠Ｐ｝                （４）
ただし、Ｑは任意のルートポイント集合Ｑを表し、式（４）に従って各ルートポイント集合Ｐｉのε近傍の大きさを計算して｜Ｎε（Ｐｉ）｜と記し、
ステップ２−９では、中核ルートセットを構築し、つまり、密度しきい値ＭｉｎＰｔｓを設定し、ε近傍の大きさがＭｉｎＰｔｓより小さくないルートポイント集合を中核ルートセットとして定義し、即ち、中核ルートセットＣｏｒｅＰはいずれも下式を満たし、
｜Ｎε（ＣｏｒｅＰ）｜≧ＭｉｎＰｔｓ                  （５）
ステップ２−１０では、密度に基づく反復クラスタ化を行い、つまり、各中核ルートセットをそれぞれ初期クラスタとしながら距離しきい値εと密度しきい値ＭｉｎＰｔｓをセットし、二つの中核ルートセットＣｏｒｅＰとＣｏｒｅＱは下式を満たすと、
ＣｏｒｅＱ∈Ｎε（ＣｏｒｅＰ）                 （６）
中核ルートセットＣｏｒｅＱは中核ルートセットＣｏｒｅＰから直接密度到達可能なものと称され、以下のように表されるものとなり、
【数２７】
2021514090.tif 000037
長さが零ではない一つの中核ルートセットチェーンの存在により、中核ルートセットＣｏｒｅＱと中核ルートセットＣｏｒｅＰは下記の条件（ａ）と（ｂ）を満たすものとなると、
【数２８】
2021514090.tif 000038
中核ルートセットＣｏｒｅＱは中核ルートセットＣｏｒｅＰから「間接密度到達可能」なものと称され、以下のように表されるものとなり、
【数２９】
2021514090.tif 000039
一つの中核ルートセットＣｏｒｅＯの存在により、中核ルートセットＣｏｒｅＰとＣｏｒｅＱはそれぞれ中核ルートセットＣｏｒｅＯから直接又は間接密度到達可能なもの、即ち、下記の条件（ｃ）と（ｄ）を満たすものとなると、
【数３０】
2021514090.tif 000040
中核ルートセットＣｏｒｅＰとＣｏｒｅＱは密度連結しているものと称され、
そして、距離しきい値εと密度しきい値ＭｉｎＰｔｓに基づいて、密度クラスタリングにより反復的にクラスタ化を行い、直接密度到達可能な、間接密度到達可能な及び密度連結している中核ルートセットをクラスタ化させて生成したクラスタの数はｕと記され、
ステップ２−１１では、ルートセットの最頻値を計算し、つまり、ｕ個のクラスタＣ１，Ｃ２，……，Ｃｕ中の、ｋ’個の中核ルートセットであるＣｋ＝｛ＣｏｒｅＰ１，ＣｏｒｅＰ２，……，ＣｏｒｅＰｋ’｝を含む各クラスタＣｋのそれぞれについてルートセットの最頻値Ｍｏｄｅｋを計算し、ＣｏｒｅＰｋ’はｋ’個目の中核ルートセットを表し、ただし、１≦ｋ≦ｕであり、Ｃｋはｋ個目のクラスタを表すことを特徴とする、請求項３に記載の方法。
【請求項５】
ステップ２−１０は、
距離しきい値εと密度しきい値ＭｉｎＰｔｓをセットし、いずれかの中核ルートセットＣｏｒｅＰから開始するように、中核ルートセットＣｏｒｅＰから直接密度到達可能な中核ルートセットのすべてを、全部の中核ルートセットが処理されたまでクラスタ化させることを含み、具体的には、ステップ２−１０−１〜ステップ２−１０−３を含み、
ステップ２−１０−１では、未処理の中核ルートセットがあるか否かを判断し、あれば、ステップ２−１０−２へ進み、なければ、ステップ２−１０−３へ進み、
ステップ２−１０−２では、未処理のいずれかの中核ルートセットＣｏｒｅＰについて、中核ルートセットＣｏｒｅＰから直接密度到達可能な中核ルートセットのすべてをクラスタ化させ、ステップ２−１０−１へ戻り、
ステップ２−１０−３では、クラスタ化した中核ルートセットのすべてを同一のクラスタとして出力し、クラスタの数はｕと記されることを特徴とする、請求項４に記載の方法。
【請求項６】
ステップ２−１１では、下式に従ってクラスタＣｋのルートセットの最頻値Ｍｏｄｅｋを計算し、
【数３１】
2021514090.tif 000041
ただし、Ｐはルートポイント集合を表し、ＣｏｒｅＰｑはクラスタＣｋ中のｑ個目の中核ルートセットを表し、ルートセットの最頻値ＭｏｄｅｋはクラスタＣｋ中のすべての中核ルートセットとのＪａｃｃａｒｄ距離の和が最小となる場合に対応するルートポイント集合を表すことを特徴とする、請求項５に記載の方法。
【請求項７】
ステップ２−１１はステップ２−１１−１〜ステップ２−１１−３を含み、
ステップ２−１１−１では、交叉集合係数と合併集合係数を計算し、つまり、ｋ’個の中核ルートセットであるＣｋ＝｛ＣｏｒｅＰ１，ＣｏｒｅＰ２，……，ＣｏｒｅＰｋ’｝を含むクラスタＣｋをセットし、最初にクラスタＣｋに含まれるルートポイント辞書Ωｋを計算し、
Ωｋ＝∪１≦ｑ≦ｋ’ＣｏｒｅＰｑ
即ち、ルートポイント辞書はクラスタＣｋ中のすべての中核ルートセットの合併集合であり、続いて、下式に示されるように、ルートポイント辞書中の各ルートポイントｐｒについて、クラスタＣｋの各中核ルートセットＣｏｒｅＰｑにおいてのルートポイントｐｒの交叉集合係数αｒｑと合併集合係数βｒｑを計算し、
【数３２】
2021514090.tif 000042
ステップ２−１１−２では、交叉集合係数と合併集合係数に基づいてルートポイントと中核ルートセットとのＪａｃｃａｒｄ距離を計算し、ルートポイント集合Ｐ＝｛ｐｒ｝と各中核ルートセットＣｏｒｅＰｑとのＪａｃｃａｒｄ距離は以下のように簡略化され、
【数３３】
2021514090.tif 000043
ステップ２−１１−３では、交叉集合係数と合併集合係数に基づいてルートポイント集合の最頻値を計算し、即ち、
【数３４】
2021514090.tif 000044
とすることを特徴とする、請求項６に記載の方法。
【請求項８】
ステップ３は、Ｍｏｄｅｋをｋ個目のクラスタＣｋのホットルートとして出力することを含むことを特徴とする、請求項７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目標ルートの分析・マイニングの分野に関し、特に密度クラスタリングに基づくホットルートの分析方法に関する。
【背景技術】
【０００２】
よく知られているように、現在では目標ルートに関する計測によるデータ量はますます大きくなっており、人力のみにより分析し処理すれば、即時かつ正確に目標ルートのパターンをまとめることが難しいため、リアルタイム性に対する要求の高い決断に対する補助を即時に支援することができない。従来の目標ルートの分析・予測技術では、目標位置についてデータを計測するが、キーとなるルートポイントに基づいて分析を行っていないものが多いため、高レベルのルート特徴に着目して多粒度の目標ルートモードを抽出できず、計算コストが高くなっていた。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明は、従来技術の問題点に対して、密度クラスタリングに基づくホットルートの分析方法を提供することを目的とする。
【課題を解決するための手段】
【０００４】
この密度クラスタリングに基づくホットルートの分析方法は、
目標ルートを若干のルートポイントからなるルートポイント集合として特徴付けて類似度距離行列を構築するステップ１と、
二つのルートポイント集合間毎の類似度を比較してから、類似度距離行列、距離しきい値ε及び密度しきい値ＭｉｎＰｔｓに基づいてルートポイント集合から中核ルートセットをマイニングし、さらに、中核ルートセットに対する「直接密度到達可能」の関係に応じて、密度クラスタリングにより中核ルートセットがクラスタ化したクラスタを反復的に生成するステップ２と、
各クラスタのルートポイント集合の最頻値を目標ホットルートとして出力するステップ３と、
を含む。
【０００５】
従来による密度クラスタリング中の類似度距離行列に比べて、ステップ１中の行列の行や列は一定次元数のベクトルに代えて、不定長のルートポイント集合に対応するものとなる。ステップ１はステップ１−１〜ステップ１−３を含む。
【０００６】
ステップ１−１では、ｎ個の目標ルートに対応するｎ個のルートポイント集合を収集したとし、ルートポイント集合毎は一つの目標ルートに対応し、ルートポイント集合中の要素毎は対応する目標ルート中の一つのルートポイントとなり、そして、ｉ個目のルートポイント集合Ｐｉとｊ個目のルートポイント集合Ｐｊとの間のＪａｃｃａｒｄ距離JaccardDist(Pi,Pj) は以下のように定義され、
【数１】
2021514090.tif 000003
ステップ１−２では、ルートポイント集合をソートし、つまり、集合の大きさに関しては大きい順に、かつ索引値に関しては小さい順にｎ個のルートポイント集合をソートしてＰ１、Ｐ２、…、Ｐｎと記し、ただし、|Ｐ１|≧|Ｐ２|≧…≧|Ｐｎ|が満たされており、
ステップ１−３では、類似度距離行列を初期化し、つまり、０＜ε＜１の範囲から値を取るように距離しきい値εを設定し、一般には、ルートポイント集合の最近傍距離の平均値として値を取ることができ、即ち、
【数２】
2021514090.tif 000004
初期化した類似度距離行列ＤｉｓｔＡｒｒａｙはＮ／Ａとなり、その行列の大きさがｎ×ｎであり、即ち、行列の行数と列数がいずれもｎであり、類似度距離行列はポリラインに関して対称なものであるため、上三角部分のみを残すようにする。
【０００７】
ステップ２では、ルートポイント集合の大きさと距離しきい値εに基づく類似度比較策（ステップ２−３）を創造的に提案し、二つのルートポイント集合間毎の類似度比較による計算コストは大きく省かれ、また、集合値類似度距離の計算のもとにルートポイント集合に特化した「ε近傍」、「中核ルートセット」、「直接密度到達可能」、「間接密度到達可能」、「密度連結」という概念（ステップ２−８、２−９）をさらに創造的に提案しており、それにより、従来による一定次元数のベクトルに対する密度クラスタリングの規則を集合値データにまで拡張させるようになる。ステップ２はステップ２−１〜ステップ２−１１を含む。
【０００８】
ステップ２−１では、現在集合の索引を設定し、つまり、現在ルートポイント集合の索引をｓ＝１と設定し、
ステップ２−２では、比較待ち集合の索引を設定し、つまり、比較待ちルートポイント集合の索引をｔ＝ｓ＋１と設定し、
ステップ２−３では、比較待ち集合の索引を判断し、つまり、比較待ちルートポイント集合の索引を判断し、ｔ≦ｎかつ|Ｐｔ|／|Ｐｓ|≧１−εが満たされていないと、ステップ２−４へ進み、満たされていると、ステップ２−６を実行し、
ステップ２−４では、現在集合の索引を更新し、つまり、現在集合の索引値をｓ＝ｓ＋１と更新し、
ステップ２−５では、現在集合の索引を判断し、ｓ≧ｎが満たされていると、ステップ２−８へ進み、でないと、ステップ２−２へ戻り、
ステップ２−６では、類似度距離を計算し、つまり、現在集合の索引と比較待ち集合の索引に対応する二つのルートポイント集合間のＪａｃｃａｒｄ距離ＪａｃｃａｒｄＤｉｓｔ（Ｐｓ，Ｐｔ）を計算し、ＪａｃｃａｒｄＤｉｓｔ（Ｐｓ，Ｐｔ）≦εが満たされていると、類似度行列中の対応するセルの値を更新し、
DistArray[s,t] = JaccardDist(Ps,Pt)              （３）
DistArray[s,t]は、類似度距離行列ＤｉｓｔＡｒｒａｙのｓ行目かつｔ列目の値を表し、
ステップ２−７では、比較待ち集合の索引をｔ＝ｔ＋１と更新し、ステップ２−３へ戻り、
ステップ２−８では、ルートポイント近傍の大きさを計算し、つまり、任意のルートポイント集合Ｐをセットし、ルートポイント集合Ｐとの類似度距離が距離しきい値ε以内にあるその他のルートポイント集合のすべてを当該ルートポイント集合Ｐのε近傍と定義してＮε（Ｐ）と記し、
Ｎε（Ｐ）＝｛Ｑ｜ＪａｃｃａｒｄＤｉｓｔ（Ｐ，Ｑ）≦ε＆＆Ｑ≠Ｐ｝
（４）
ただし、Ｑは任意のルートポイント集合Ｑを表し、式（４）に従って各ルートポイント集合Ｐｉのε近傍の大きさを計算して｜Ｎε（Ｐｉ）｜と記し、
ステップ２−９では、中核ルートセットを構築し、つまり、密度しきい値ＭｉｎＰｔｓを設定し、ε近傍の大きさがＭｉｎＰｔｓより小さくないルートポイント集合を中核ルートセットとして定義し、その値が１よりも大きいか等しいかつｎよりも小さい自然数とされ、一般には、
【数３】
2021514090.tif 000005
として値を取ってもよく、即ち、中核ルートセットＣｏｒｅＰはいずれも下式を満たし、
｜Ｎε（ＣｏｒｅＰ）｜≧ＭｉｎＰｔｓ                  （５）
ステップ２−１０では、密度に基づく反復クラスタ化を行い、つまり、各中核ルートセットをそれぞれ初期クラスタとしながら距離しきい値εと密度しきい値ＭｉｎＰｔｓをセットし、二つの中核ルートセットＣｏｒｅＰとＣｏｒｅＱは下式を満たすと、
ＣｏｒｅＱ∈Ｎε（ＣｏｒｅＰ）                 （６）
中核ルートセットＣｏｒｅＱは中核ルートセットＣｏｒｅＰから「直接密度到達可能」なものと称され、以下のように表されるものとなり、
【数４】
2021514090.tif 000006
長さが零ではない一つの中核ルートセットチェーンの存在により、中核ルートセットＣｏｒｅＱと中核ルートセットＣｏｒｅＰは下記の条件（ａ）と（ｂ）を満たすものとなると、
【数５】
2021514090.tif 000007
中核ルートセットＣｏｒｅＱは中核ルートセットＣｏｒｅＰから「間接密度到達可能」なものと称され、以下のように表されるものとなり、
【数６】
2021514090.tif 000008
また、一つの中核ルートセットＣｏｒｅＯの存在により、中核ルートセットＣｏｒｅＰとＣｏｒｅＱはそれぞれ中核ルートセットＣｏｒｅＯから直接又は間接密度到達可能なもの、即ち、下記の条件（ｃ）と（ｄ）を満たすものとなると、
【数７】
2021514090.tif 000009
中核ルートセットＣｏｒｅＰとＣｏｒｅＱは「密度連結」しているものと称され、
そして、距離しきい値εと密度しきい値ＭｉｎＰｔｓに基づいて、密度クラスタリングにより反復的にクラスタ化を行い、直接密度到達可能な、間接密度到達可能な及び密度連結している中核ルートセットをクラスタ化させて生成したクラスタの数はｕと記され、
ステップ２−１１では、ルートセットの最頻値を計算し、つまり、ｕ個のクラスタＣ１，Ｃ２，……，Ｃｕ中の、ｋ’個の中核ルートセットであるＣｋ＝｛ＣｏｒｅＰ１，ＣｏｒｅＰ２，……，ＣｏｒｅＰｋ’｝を含む各クラスタＣｋのそれぞれについてルートセットの最頻値Ｍｏｄｅｋを計算し、ＣｏｒｅＰｋ’はｋ’個目の中核ルートセットを表し、ただし、１≦ｋ≦ｕであり、Ｃｋはｋ個目のクラスタを表す。
【０００９】
ステップ２−１０は、
距離しきい値εと密度しきい値ＭｉｎＰｔｓをセットし、いずれかの中核ルートセットＣｏｒｅＰから開始するように、中核ルートセットＣｏｒｅＰから直接密度到達可能な中核ルートセットのすべてを、全部の中核ルートセットが処理されたまでクラスタ化させることを含み、具体的には、ステップ２−１０−１〜ステップ２−１０−３を含む。
【００１０】
ステップ２−１０−１では、未処理の中核ルートセットがあるか否かを判断し、あれば、ステップ２−１０−２へ進み、なければ、ステップ２−１０−３へ進み、
ステップ２−１０−２では、未処理のいずれかの中核ルートセットＣｏｒｅＰについて、中核ルートセットＣｏｒｅＰから直接密度到達可能な中核ルートセットのすべてをクラスタ化させ、ステップ２−１０−１へ戻り、
ステップ２−１０−３では、クラスタ化した中核ルートセットのすべてを同一のクラスタとして出力し、クラスタの数はｕと記される。
【００１１】
ステップ２−１０−３では、同一のクラスタＣにおいて、二つの中核ルートセット間毎の関係は必ず直接密度到達可能なもの、間接密度到達可能なもの又は密度連結しているものの一つに属し、以下、具体的に証明する。
【００１２】
現在クラスタＣ中の二つの中核ルートセット間毎を直接密度到達可能なもの、間接密度到達可能なもの又は密度連結しているものとし、中核ルートセットＣｏｒｅＯから直接密度到達可能な中核ルートセットＣｏｒｅＱを一つ新たにクラスタ化させ、即ち、
【数８】
2021514090.tif 000010
としようとする場合、クラスタＣに既存している任意の中核ルートセットＣｏｒｅＰと新たに追加される中核ルートセットＣｏｒｅＱは下記四つの関係となり得る。
【００１３】
１．中核ルートセットＣｏｒｅＰは中核ルートセットＣｏｒｅＯそのものである場合、
【数９】
2021514090.tif 000011
であり、中核ルートセットＣｏｒｅＱは中核ルートセットＣｏｒｅＰから直接密度到達可能となる。
【００１４】
２．中核ルートセットＣｏｒｅＰは中核ルートセットＣｏｒｅＯから直接密度到達可能な又は間接密度到達可能なものである場合、
【数１０】
2021514090.tif 000012
中核ルートセットＣｏｒｅＰとＣｏｒｅＱは中核ルートセットＣｏｒｅＯを介して密度連結している。
【００１５】
３．中核ルートセットＣｏｒｅＯは中核ルートセットＣｏｒｅＰから直接密度到達可能な又は間接密度到達可能なものである場合、即ち、
【数１１】
2021514090.tif 000013
中核ルートセットＣｏｒｅＱは中核ルートセットＣｏｒｅＰから間接密度到達可能となる。
【００１６】
４．中核ルートセットＣｏｒｅＯと中核ルートセットＣｏｒｅＰは密度連結している場合、即ち、ある中核ルートセットＣｏｒｅＲの存在により
【数１２】
2021514090.tif 000014
そのため、中核ルートセットＣｏｒｅＰと中核ルートセットＣｏｒｅＱも中核ルートセットＣｏｒｅＲを介して密度連結している。
【００１７】
以上から分かるように、新たにクラスタ化した中核ルートセットＣｏｒｅＱとクラスタに既存している中核ルートセットとの間はやはり直接密度到達可能、間接密度到達可能又は密度連結という関係を満たしている。
【００１８】
ステップ２−１１では、下式に従ってクラスタＣｋのルートセットの最頻値Ｍｏｄｅｋを計算し、
【数１３】
2021514090.tif 000015
ただし、Ｐはルートポイント集合を表し、ＣｏｒｅＰｑはクラスタＣｋ中のｑ個目の中核ルートセットを表し、ルートセットの最頻値ＭｏｄｅｋはクラスタＣｋ中のすべての中核ルートセットとのＪａｃｃａｒｄ距離の和が最小となる場合に対応するルートポイント集合を表す。
【００１９】
ステップ２−１１はステップ２−１１−１〜ステップ２−１１−３を含む。
【００２０】
ステップ２−１１−１では、交叉集合係数と合併集合係数を計算し、つまり、ｋ’個の中核ルートセットであるＣｋ＝｛ＣｏｒｅＰ１，ＣｏｒｅＰ２，……，ＣｏｒｅＰｋ’｝を含むクラスタＣｋをセットし、最初にクラスタＣｋに含まれるルートポイント辞書Ωｋを計算し、
Ωｋ＝∪１≦ｑ≦ｋ’ＣｏｒｅＰｑ
即ち、ルートポイント辞書はクラスタＣｋ中のすべての中核ルートセットの合併集合であり、続いて、下式に示されるように、ルートポイント辞書中の各ルートポイントｐｒについて、クラスタＣｋの各中核ルートセットＣｏｒｅＰｑにおいてのルートポイントｐｒの交叉集合係数αｒｑと合併集合係数βｒｑを計算し、
【数１４】
2021514090.tif 000016
ステップ２−１１−２では、交叉集合係数と合併集合係数に基づいてルートポイントと中核ルートセットとのＪａｃｃａｒｄ距離を計算し、交叉集合係数と合併集合係数によれば、ルートポイント集合Ｐ＝｛ｐｒ｝と各中核ルートセットＣｏｒｅＰｑとのＪａｃｃａｒｄ距離は以下のように簡略化されることが可能になり、
【数１５】
2021514090.tif 000017
ステップ２−１１−３では、交叉集合係数と合併集合係数に基づいてルートポイント集合の最頻値を計算し、
【数１６】
2021514090.tif 000018
ステップ３は、Ｍｏｄｅｋをｋ個目のクラスタＣｋのホットルートとして出力することを含む。
【００２１】
距離しきい値εはルートポイント集合間の類似度を比較するためのものであり、二つのルートポイント集合間毎のＪａｃｃａｒｄ距離は区間［０，１］の範囲において値を取るため、距離しきい値εは同様に区間［０，１］の範囲において値を取るようになる。
【００２２】
二つのルートポイント集合間のＪａｃｃａｒｄ距離は上限条件である
【数１７】
2021514090.tif 000019
【００２３】
従来による密度クラスタリング方法は一定次元数のベクトルデータのみに適合し、不定長のルートポイント集合データには適合していなかった。本発明はルートポイント集合に特化した「中核ルートセット」及びその「直接密度到達可能」、「間接密度到達可能」、「密度連結」という概念を創造的に提案し、それにより、一定次元数のベクトルのみに適合した従来による密度クラスタリング方法は不定長のルートポイント集合データへまで拡張応用されるようになる。本発明は交叉集合係数と合併集合係数に基づくホットルートのマイニング方法をさらに提案し、ホットルートの分析能力は効果的に向上している。
【発明の効果】
【００２４】
本発明によれば、（１）目標ルートポイント集合の類似度の比較方法が提供されることと、（２）密度しきい値ＭｉｎＰｔｓの選択には一定の柔軟性やロバスト性があることと、（３）計算コストが低く、工学的な方法で実現されることとなる。本発明に採用されるルートポイント集合に基づく分析・マイニング方法によれば、ルートポイント順序が簡略化され、同じルートポイントを有する計測データをクラスタ化させることに役立ち、計算コストが大きく低減され、計算効率の向上を図ることができる。
【００２５】
以下、図面と具体的な実施形態に合わせて本発明をさらに具体的に説明し、本発明による上記の又は他の利点はより明らかになろう。
【図面の簡単な説明】
【００２６】
【図１】本発明に係るフローチャートである。
【発明を実施するための形態】
【００２７】
以下、図面及び実施例に合わせて本発明をさらに説明する。
【００２８】
本発明によれば、目標ルートを若干のルートポイントからなるルートポイント集合として特徴付けて類似度距離行列を構築し、二つのルートポイント集合間毎の類似度を比較してから、類似度距離行列、距離しきい値ε及び密度しきい値ＭｉｎＰｔｓに基づいて密度クラスタリングによりルートポイント集合のクラスタを反復的に計算し、最後に、各クラスタのルートセットの最頻値を目標ホットルートとして出力する。
【００２９】
図１に示されるように、具体的には、本発明の方法はステップ（１）〜ステップ（１３）を含む。
【００３０】
ｎ個の目標ルートに対応するｎ個のルートポイント集合を収集したことを仮定し、ルートポイント集合毎は一つの目標ルートに対応し、ルートポイント集合中の要素毎は対応する目標ルート中の一つのルートポイントとなり、そして、二つのルートポイント集合ＰｉとＰｊとの間毎のＪａｃｃａｒｄ距離は以下のように定義され、
【数１８】
2021514090.tif 000020
ステップ（１）では、ルートポイント集合をソートし、つまり、集合の大きさに関しては大きい順に、かつ索引値に関しては小さい順にｎ個のルートポイント集合をソートしてＰ１、Ｐ２、…、Ｐｎと記し、ただし、｜Ｐ１｜≧｜Ｐ２｜≧…≧｜Ｐｎ｜が満たされており、
ステップ（２）では、類似度距離行列を初期化し、つまり、０＜ε＜１の範囲から値を取るように距離しきい値εを設定し、初期化した類似度距離行列ＤｉｓｔＡｒｒａｙはＮ／Ａとなり、その行列の大きさがｎ×ｎであり、即ち、行列の行数と列数がいずれもｎであり、類似度距離行列はポリラインに関して対称なものであるため、上三角部分のみを残すようにし、
ステップ（３）では、現在集合の索引を設定し、つまり、現在ルートポイント集合の索引をｓ＝１と設定し、
ステップ（４）では、比較待ち集合の索引を設定し、つまり、比較待ちルートポイント集合の索引をｔ＝ｓ＋１と設定し、
ステップ（５）では、比較待ち集合の索引を判断し、つまり、比較待ちルートポイント集合の索引を判断し、ｔ≦ｎかつ｜Ｐｔ｜／｜Ｐｓ｜≧１−εが満たされていない場合、ステップ（６）へ進み、満たされている場合、ステップ（８）へ進み、
ステップ（６）では、現在集合の索引を更新し、つまり、現在集合の索引値をｓ＝ｓ＋１と更新し、
ステップ（７）では、現在集合の索引を判断し、ｓ≧ｎが満たされている場合、ステップ（１０）へ進み、満たされていない場合、ステップ（４）へ戻り、
ステップ（８）では、類似度距離を計算し、つまり、現在集合の索引と比較待ち集合の索引に対応する二つのルートポイント集合間のＪａｃｃａｒｄ距離を計算し、ＪａｃｃａｒｄＤｉｓｔ（Ｐｓ，Ｐｔ）≦εが満たされていると、類似度行列中の対応するセルの値を更新し、
DistArray[s,t] = JaccardDist(Ps,Pt)              （２）
ステップ（９）では、比較待ち集合の索引をｔ＝ｔ＋１と更新し、ステップ（５）へ戻り、
ステップ（１０）では、ルートポイント近傍の大きさを計算し、つまり、任意のルートポイント集合Ｐをセットし、ルートポイント集合Ｐとの類似度距離が距離しきい値ε以内にあるその他のルートポイント集合のすべてを当該ルートポイント集合Ｐのε近傍と定義してＮε（Ｐ）と記し、
Ｎε（Ｐ）＝｛Ｑ｜ＪａｃｃａｒｄＤｉｓｔ（Ｐ，Ｑ）≦ε＆＆Ｑ≠Ｐ｝
（３）
各ルートポイント集合Ｐｉの近傍の大きさを計算して|Ｎε（Ｐｉ）|と記し、
ステップ（１１）では、中核ルートセットを構築し、つまり、密度しきい値ＭｉｎＰｔｓを設定し、ε近傍の大きさがＭｉｎＰｔｓより小さくないルートポイント集合を中核ルートセットとして定義し、即ち、中核ルートセットＣｏｒｅＰはいずれも下式を満たし、
｜Ｎε（ＣｏｒｅＰ）｜≧ＭｉｎＰｔｓ                  （４）
ステップ（１２）では、密度に基づく反復クラスタ化を行い、つまり、各中核ルートセットをそれぞれ初期クラスタとしながら距離しきい値εと密度しきい値ＭｉｎＰｔｓをセットし、二つの中核ルートセットＣｏｒｅＰとＣｏｒｅＱは下式を満たすと、
ＣｏｒｅＱ∈Ｎε（ＣｏｒｅＰ）                 （５）
中核ルートセットＣｏｒｅＱは中核ルートセットＣｏｒｅＰから「直接密度到達可能」なものと称されて、
【数１９】
2021514090.tif 000021
として表され、長さが零ではない一つの中核ルートセットチェーンの存在により、中核ルートセットＣｏｒｅＱと中核ルートセットＣｏｒｅＰは下記の条件（ａ）と（ｂ）を満たすものとなると、
【数２０】
2021514090.tif 000022
中核ルートセットＣｏｒｅＱは中核ルートセットＣｏｒｅＰから「間接密度到達可能」なものと称されて、
【数２１】
2021514090.tif 000023
として表され、また、一つの中核ルートセットＣｏｒｅＯの存在により、中核ルートセットＣｏｒｅＰとＣｏｒｅＱはそれぞれ中核ルートセットＣｏｒｅＯから直接又は間接密度到達可能なものとなると、即ち、下記の条件が満たされていると、
【数２２】
2021514090.tif 000024
中核ルートセットＣｏｒｅＰとＣｏｒｅＱは「密度連結」しているものと称され、そして、距離しきい値εと密度しきい値ＭｉｎＰｔｓに基づいて、密度クラスタリングにより反復的にクラスタ化を行い、直接密度到達可能な、間接密度到達可能な及び密度連結している中核ルートセットをクラスタ化させて生成したクラスタの数はｕと記され、
ステップ（１３）では、ルートセットの最頻値を計算し、つまり、ｕ個のクラスタＣ１，Ｃ２，……，Ｃｕ中の、ｋ’個の中核ルートセットであるＣｋ＝｛ＣｏｒｅＰ１，ＣｏｒｅＰ２，……，ＣｏｒｅＰｋ’｝を含む各クラスタＣｋのそれぞれについてルートセットの最頻値Ｍｏｄｅｋを計算し、
【数２３】
2021514090.tif 000025
ただし、１≦ｋ≦ｕであり、Ｃｋはｋ個目のクラスタを表し，ＣｏｒｅＰｊはｊ個目の中核ルートセットを表し、ＭｏｄｅｋをクラスタＣｋのホットルートとして出力する。
【００３１】
本発明の方法によれば、目標位置に対する計測が不正確である場合の目標ルートの分析能力を高めることができ、目標位置に対する計測の冗長性の低減に役立ち、空間粒度の柔軟性を増加させ、目標ルートの分析をより良好に完成可能となる。以下、一実例に従って本発明による密度クラスタリングに基づくホットルートの分析方法を説明する。
【００３２】
本実施例では、ある都市の道路交通管理においてタクシの軌跡情報から高頻度の目標ルートをｎ＝５個収集しており、それらは５個のルートポイント集合に対応し、ルートポイント集合中の要素毎は当該ルート中の一つのルートポイントに対応し、距離しきい値εに０．３が取られ、密度しきい値ＭｉｎＰｔｓに１が取られ、そして、密度クラスタリングに基づくホットルートの分析ステップは以下の様になる。
【００３３】
ステップ１では、ルートポイント集合をソートし、つまり、ルートポイント集合の大きさに関しては大きい順に、かつ索引値に関しては小さい順にＰ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５としてソートする。詳細は表１に示す。
【表１】
2021514090.tif 000026
ステップ２では、類似度距離行列を初期化し、つまり、距離しきい値εに０．３が取られ、初期化した類似度距離行列ＤｉｓｔＡｒｒａｙはＮ／Ａとなり、行列の大きさが５×５であり、類似度距離行列はポリラインに関して対称なものであるため、上三角部分のみを残す。詳細は表２に示す。
【表２】
2021514090.tif 000027
ステップ３では、現在集合の索引を設定し、つまり、現在ルートポイント集合の索引をｓ＝１と設定し、
ステップ４では、比較待ち集合の索引を設定し、つまり、比較待ちルートポイント集合の索引をｔ＝ｓ＋１＝２と設定し、
ステップ５では、比較待ち集合の索引を判断し、「ｔ≦ｎかつ｜Ｐｔ｜／｜Ｐｓ｜＝０．７５＞１−ε＝０．７」が満たされていると、ステップ８へ進み、
ステップ８では、類似度距離を計算し、ルートポイント集合Ｐ１とＰ２との間のＪａｃｃａｒｄ距離は０．２５として計算され、距離しきい値ε＝０．３よりも小さいものであるから、類似度行列ＤｉｓｔＡｒｒａｙを更新する。詳細は表３に示す。
【表３】
2021514090.tif 000028
ステップ９では、比較待ち集合の索引を更新し、つまり、比較待ちレーダ放射源の索引をｔ＝ｔ＋１＝３と更新し、ステップ５へ戻り、
ステップ５では、比較待ち集合の索引を判断し、「ｔ≦ｎかつ｜Ｐｔ｜／｜Ｐｓ｜＝０．７５＞１−ε」が満たされていると、ステップ８へ進み、
ステップ８では、類似度距離を計算し、つまり、ルートポイント集合Ｐ１とＰ３との間のＪａｃｃａｒｄ距離を計算して、類似度行列ＤｉｓｔＡｒｒａｙを更新する。詳細は表４に示す。
【表４】
2021514090.tif 000029
ステップ９では、比較待ち集合の索引を更新し、つまり、比較待ちレーダ放射源の索引をｔ＝ｔ＋１＝４と更新し、ステップ５へ戻り、
ステップ５では、比較待ち集合の索引を判断し、比較待ち目標索引値は「｜Ｐｔ｜／｜Ｐｓ｜＝０．５≧１−ε」を満たしていないと判断され、ステップ６へ進み、
ステップ６では、現在集合の索引を更新し、つまり、現在集合の索引値をｓ＝ｓ＋１＝２と更新し、
ステップ７では、現在集合の索引を判断し、現在集合の索引はｓ＜ｎとして判断され、ステップ４へ戻り、
ステップ４では、比較待ち集合の索引を設定し、つまり、比較待ち集合の索引をｔ＝ｓ＋１＝３と設定し、
ステップ５では、比較待ち集合の索引を判断し、比較待ち目標索引値はｔ＝３として判断され、「ｔ＜ｎかつ｜Ｐｔ｜／｜Ｐｓ｜＝１≧１−ε」が満たされており、ステップ８へ進み、
ステップ８では、類似度距離を計算し、つまり、ルートポイント集合Ｐ２とＰ３との間のＪａｃｃａｒｄ距離を計算して、類似度行列ＤｉｓｔＡｒｒａｙを更新する。詳細は表５に示す。
【表５】
2021514090.tif 000030
ステップ９では、比較待ち集合の索引を更新し、つまり、比較待ちレーダ放射源の索引をｔ＝ｔ＋１＝４と更新し、ステップ５へ戻り、
ステップ５では、比較待ち集合の索引を判断し、比較待ち目標索引値はｔ＝４として判断され、「｜Ｐｔ｜／｜Ｐｓ｜＝０．６６７≧１−ε」が満たされておらず、ステップ６へ進み、
ステップ６では、現在集合の索引を更新し、つまり、現在集合の索引値をｓ＝ｓ＋１＝３と更新し、
ステップ７では、現在集合の索引を判断し、現在集合の索引はｓ＜ｎとして判断され、ステップ４へ戻り、
ステップ４では、比較待ち集合の索引を設定し、つまり、比較待ちルートポイント集合の索引をｔ＝ｓ＋１＝４と設定し、
ステップ５では、比較待ち集合の索引を判断し、比較待ち目標索引値はｔ＝４として判断され、「｜Ｐｔ｜／｜Ｐｓ｜≧１−ε」が満たされておらず、ステップ６へ進み、
ステップ６では、現在集合の索引を更新し、つまり、現在集合の索引値をｓ＝ｓ＋１＝４と更新し、
ステップ７では、現在集合の索引を判断し、現在集合の索引はｓ＜ｎとして判断され、ステップ４へ戻り、
ステップ４では、比較待ち集合の索引を設定し、つまり、比較待ちルートポイント集合の索引をｔ＝ｓ＋１＝５と設定し、
ステップ５では、比較待ち集合の索引を判断し、比較待ちルートポイント集合の索引は「ｔ＝５≦ｎかつ｜Ｐｔ｜／｜Ｐｓ｜＝１≧１−ε」を満たしていると判断され、ステップ８へ進み、
ステップ８では、類似度距離を計算し、ルートポイント集合Ｐ４とＰ５との間のＪａｃｃａｒｄ距離は零として計算され、ＪａｃｃａｒｄＤｉｓｔ（Ｐ４，Ｐ５）≦０．３が満たされており、類似度行列ＤｉｓｔＡｒｒａｙを更新する。詳細は表６に示す。
【表６】
2021514090.tif 000031
ステップ９では、比較待ち集合の索引を更新し、つまり、比較待ちレーダ放射源の索引をｔ＝ｔ＋１＝６と更新し、ステップ５へ戻り、
ステップ５では、比較待ち集合の索引を判断し、比較待ち目標索引値はｔ＝６として判断され、「ｔ≦ｎ」が満たされておらず、ステップ６へ進み、
ステップ６では、現在集合の索引を更新し、つまり、現在集合の索引値をｓ＝ｓ＋１＝５と更新し、
ステップ７では、現在集合の索引を判断し、現在集合の索引はｓ＝ｎとして判断され、ステップ１０へ進み、
ステップ１０では、ルートポイント近傍の大きさを計算し、つまり、各ルートポイント集合Ｐｉのε近傍の大きさ｜Ｎε（Ｐｉ）｜を計算する。詳細は表７に示す。
【表７】
2021514090.tif 000032
ステップ１１では、中核ルートセットを構築し、つまり、ε近傍の大きさがＭｉｎＰｔｓより小さくないルートポイント集合を中核ルートセットとし、その値が１よりも大きいか等しいかつｎよりも小さい自然数とされ、一般には、
【数２４】
2021514090.tif 000033
として値を取ってもよく、Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５はいずれも中核ルートセットであり、
ステップ１２では、密度に基づく反復クラスタ化を行い、初期クラスタはそれぞれ｛Ｐ１｝，｛Ｐ２｝，｛Ｐ３｝，｛Ｐ４｝及び｛Ｐ５｝の５個であり、反復クラスタ化を経て最終的に生成されたクラスタはｕ＝２個でＣ１＝｛Ｐ１，Ｐ２，Ｐ３｝及びＣ２＝｛Ｐ４，Ｐ５｝となり、クラスタＣ１においては、Ｐ１，Ｐ２，Ｐ３の両者毎は直接密度到達可能なものであり、クラスタＣ２においては、Ｐ４とＰ５も直接密度到達可能なものであり、
ステップ１３では、ルートセットの最頻値を計算し、クラスタ毎についてそのすべての中核ルート集合からなる中核セットを構築してＣ１＝｛Ｐ１，Ｐ２，Ｐ３｝とＣ２＝｛Ｐ４，Ｐ５｝が得られ、そしてそれらの最頻値をそれぞれ計算してＭｏｄｅ１＝｛ａ，ｂ，ｃ｝，Ｍｏｄｅ２＝｛ｅ，ｆ｝が得られ、Ｍｏｄｅ１を例として、その交叉集合係数と合併集合係数は表８に示される。
【表８】
2021514090.tif 000034
【００３４】
都市の道路交通管理においては、マイニングされたホットルート｛ａ，ｂ，ｃ｝と｛ｅ，ｆ｝について対応する道路や信号機を強化することで、円滑な交通を保証し、交通流量を制御することが可能になる。本発明の研究成果によれば、目標位置に対する計測が不正確である場合の目標ルートの分析能力の向上や、目標位置に対する計測の冗長性の低減に役立ち、空間粒度の柔軟性を増加させ、目標ルートの分析をより良好に完成可能となる。
【００３５】
本発明は中国国家自然科学基金委員会からの経済的援助（Ｎｏ．６１７７１１７７）を受けて研究したものである。
【００３６】
本発明は密度クラスタリングに基づくホットルートの分析方法を提供するが、その具体的な実現方法や手段が多く、上記は本発明の好ましい実施形態に過ぎず、当業者にとっては、本発明の原理から逸脱することなく若干の改良や変更を行うこともでき、それらも本発明の保護範囲にあるものと見なすべきであることは了解されたい。本実施例において明らかにされていない各構成部分はいずれも従来技術により実現可能なものである。
【図１】
2021514090.tif 000045
【国際調査報告】
2021514090.tif 000046
2021514090.tif 000047
2021514090.tif 000048
2021514090.tif 000049