(57)【特許請求の範囲】
【請求項１】
時系列的に生じる複数のデータをクラスタリングする時系列データの分類装置において、
クラスタリング条件を利用者の指定に基づき、各クラスタのクラスタリングの精度を表わすパラメータMaxDiameterを、クラスタＣｎｅａｒｅｓｔの中心値centerｎｅａｒｅｓｔが大きいほど大きな値に、クラスタＣｎｅａｒｅｓｔの中心値centerｎｅａｒｅｓｔが小さいほど小さな値となる関数として設定するクラスタリング条件設定手段と、
被クラスタリングデータをどのクラスタに含めるか最も近いクラスタを探すクラスタ検索手段と、
被クラスタリングデータについてクラスタリングのための評価尺度を計算する計算手段と、
前記計算手段の結果と前記クラスタリング条件設定手段の条件に基づきクラスタ分けを決定する判定手段と
から構成されることを特徴とする時系列データの分類装置。
【請求項２】
時系列的に生じる複数のデータをクラスタリングする時系列データの分類装置において、
クラスタリング条件を利用者の指定に基づき、各クラスタのクラスタリングの精度を表わすパラメータMaxDiameterを、クラスタＣｎｅａｒｅｓｔの中心値centerｎｅａｒｅｓｔの一次関数（ただし、傾きの係数は正）として設定するクラスタリング条件設定手段と、
被クラスタリングデータをどのクラスタに含めるか最も近いクラスタを探すクラスタ検索手段と、
被クラスタリングデータについてクラスタリングのための評価尺度を計算する計算手段と、
前記計算手段の結果と前記クラスタリング条件設定手段の条件に基づきクラスタ分けを決定する判定手段と
から構成されることを特徴とする時系列データの分類装置。
【請求項３】
クラスタ検索手段において、被クラスタリングデータについて、各クラスタの中心値と入力データの距離を各クラスタの中心値で正規化した値を各クラスタについて求め、その値が最小となるクラスタを最も近いクラスタＣｎｅａｒｅｓｔとして抽出するようにしたことを特徴とする請求項１又は２記載の時系列データの分類装置。
【請求項４】
計算手段において、クラスタリングのための各クラスタの評価値Diameterを、新しく挿入する被クラスタリングデータを含めたそのクラスタ内の２つのデータの距離の自乗総和値に基づいて定めることを特徴とする請求項１又は２記載の時系列データの分類装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、時系列的に生じる種々の要因を含むデータの分析に関するもので、分析のためにデータをクラスタリングするための時系列データの分類装置に関するものである。
【０００２】
このような時系列データとしては、例えばコンビニエンスストアや商店等における特定顧客がＡ商品購入後一定期間内にＢ商品を購入する場合、医療分野で、ある患者が病気Ａを罹患後に、一定期間後に病気Ｂを罹患する場合等がある。それぞれ分野毎で事象の発生する間隔が異なる他、同じ分野例えば商品購入の場合でも短い間隔で発生する場合や、長い間隔で発生する場合等、様々のケースがある。これらのデータを分析することによって、事前に次回商品購入案内のダイレクトメールを発送する、病気の早期発見・予防のための検査を受ける等が可能となり、その効果は大きい。
【０００３】
本発明は、このように時系列的に生じる種々の要因を含むデータについて、時間間隔が短い場合から長い場合まで幅広いデータについて、高い精度で適切なクラスタリングが行え相関関係の解析に有効で、様々の分野に広く応用できるデータ分析の方法を提供するものである。
【０００４】
【従来の技術】
時系列的に生じる種々の要因を含むデータについて、事象毎にデータを抽出し、クラスタリングする手法は、例えば文献１（Mariko Yoshida,Tetsuya Iizuka,Hisako Shiohara：Mining Sequential Patterns Including Time Intervals/Proceedings of SPIE Vol.4057  p213〜p220,April 2000）に開示されている。
【０００５】
はじめに、従来の手法について説明する。図７は、時系列データの一例でUserIDは個人を識別する記号、Timeはある時点を基準とした時にその事象が生じた時刻、Itemは事象を識別する番号である。これを具体例におきかえて説明すると、データ番号１は、Ａさんが４月１９日に（基準点を４月１日とした場合）商品２を購入した。データ番号７は、Ｂさんが４月２０日に商品４を購入したことを表わしている。このようなデータが多数存在する。
【０００６】
図８は、図７のデータのうち特定の事象列に着目した説明図で、具体例で説明すると、商品１を購入してから、次に商品４を購入する場合について、データをプロットしたもので、図７のデータ番号４、５に示されるように、Ａさんが商品１を購入した後、１０日後に（４７−３７＝１０）商品４を購入している。図８の１→４欄の▲１▼の１０はこの事象を表現したもので、図８において丸付き数字は図７のデータにおいて、１→４が生じる順番を、その下の数字は事象がおきた時間間隔を示し、事例を時間間隔の短い順にプロットしている。
【０００７】
図８において▲２▼は、図７のデータ番号１３および１５をプロットしたもので、Ｃさんが商品１を購入してから８日後に（３５−２７＝８）商品４を購入していることによるデータである。
【０００８】
同様にして、このようなデータが多数プロットされる。
【０００９】
図９は、図８に示したデータを従来の手法を用いてクラスタリングする場合の説明図である。
【００１０】
図９は、事象がおきる時間間隔をクラスタリングする精度を表わすパラメータMaxDiameterを３とした場合で、このMaxDiameterは、このデータの利用者（ユーザ）が有意と思う時間間隔から設定される。
【００１１】
図８のデータ▲１▼（１０）を図９においてクラスタリングすると、最初のデータなので、クラスタの区分を表わすＣi は０とし、データ数は１、クラスタ区分Ｃi=0 の中心値は１０、データ欄は１０となる。
【００１２】
次に図８のデータ▲２▼（８）をクラスタリングする場合は、
｜８−１０｜≦３（MaxDiameter）（centeri=0 （Ｃi=0 の中心値）は１０）
であり、新しいデータ８とクラスタＣi=0 の中心値１０との差の絶対値は、MaxDiameter＝３より小さいので、このデータはクラスタＣi=0 にクラスタリングされる。
【００１３】
従って、クラスタＣi=0は、データ数が１→２となり、Ｃi=0 の中心値（Ｃcenteri=0 ）は（１０＋８）／２＝９であるから１０→９となる。
【００１４】
さらに図８のデータ▲３▼（２０）をクラスタリングする場合は、
｜２０−９｜≧３（MaxDiameter）なので、
これはクラスタＣi=0 には含まれず新しいクラスタＣi=１ となり、クラスタＣi=１ の欄にデータ数１、Ｃi=１ の中心値２０、データ欄は２０となる。
【００１５】
次に図８のデータ▲４▼（１８）も同様にクラスタリングされ、図９に例示するように区分される。このような手法により多数のデータがクラスタリングされる。
【００１６】
従来の手法は、上記のような方法としているため以下のような欠点があった。
【００１７】
▲１▼  新しいデータをクラスタリングする時、既存のＣi の中心値と新しいデータの時間間隔ｄとの距離がユーザが設定した閾値（MaxDiameter）より大きいか小さいかだけで評価しており、クラスタ内のデータ数については、考慮されていなかったので、データ数が多いクラスタと、データ数が少ないクラスタを同じように評価していた。
【００１８】
▲２▼  どのような値の時間間隔データについても、同じ閾値（MaxDiameter）で評価していたので、例えば前記したコンビニや商店での商品購入間隔と、医療分野での病気罹患の間隔とでは時間間隔が大きく異なるので、閾値と対象データの関係が適切でない場合、すなわち閾値に対し対象データの時間間隔が長い場合は近視眼的な評価をすることになり、また反対の場合にはマクロ的な評価しかできないことになり、適切なクラスタリングが行えないという欠点があった。
【００１９】
【発明が解決しようとする課題】
本発明は上記の事情に鑑みてなされたもので、データのクラスタリングをサンプル数を考慮した高い精度で行え、かつ対象となるデータの時間間隔に応じて適切なクラスタリングが行え、相関関係の解析に有効なクラスタリングが行える時系列データの分類装置を提供することを目的とする。
【００２０】
【課題を解決するための手段】
上記目的を達成するために本発明は、時系列的に生じる複数のデータをクラスタリングする時系列データの分類装置において、クラスタリング条件を利用者の指定に基づき、各クラスタのクラスタリングの精度を表わすパラメータMaxDiameterを、クラスタＣｎｅａｒｅｓｔの中心値centerｎｅａｒｅｓｔが大きいほど大きな値に、クラスタＣｎｅａｒｅｓｔの中心値centerｎｅａｒｅｓｔが小さいほど小さな値となる関数として設定するクラスタリング条件設定手段と、被クラスタリングデータをどのクラスタに含めるか最も近いクラスタを探すクラスタ検索手段と、被クラスタリングデータについてクラスタリングのための評価尺度を計算する計算手段と、前記計算手段の結果と前記クラスタリング条件設定手段の条件に基づきクラスタ分けを決定する判定手段とから構成されることを特徴とするものである。
また本発明は、時系列的に生じる複数のデータをクラスタリングする時系列データの分類装置において、クラスタリング条件を利用者の指定に基づき、各クラスタのクラスタリングの精度を表わすパラメータMaxDiameterを、クラスタＣｎｅａｒｅｓｔの中心値centerｎｅａｒｅｓｔの一次関数（ただし、傾きの係数は正）として設定するクラスタリング条件設定手段と、被クラスタリングデータをどのクラスタに含めるか最も近いクラスタを探すクラスタ検索手段と、被クラスタリングデータについてクラスタリングのための評価尺度を計算する計算手段と、前記計算手段の結果と前記クラスタリング条件設定手段の条件に基づきクラスタ分けを決定する判定手段とから構成されることを特徴とするものである。
【００２８】
また本発明は、前記時系列データの分類装置のクラスタ検索手段において、被クラスタリングデータについて、各クラスタの中心値と入力データの距離を各クラスタの中心値で正規化した値を各クラスタについて求め、その値が最小となるクラスタを最も近いクラスタＣｎｅａｒｅｓｔとして抽出するようにしたことを特徴とするものである。
【００３０】
また本発明は、前記時系列データの分類装置の計算手段において、クラスタリングのための各クラスタの評価値Diameterを、新しく挿入する被クラスタリングデータを含めたそのクラスタ内の２つのデータの距離の自乗総和値に基づいて定めることを特徴とするものである。
【００４１】
本発明は、クラスタリングする時、クラスタリング精度を各クラスタについて事象が生じる時間間隔に応じて設定するようにし、また被クラスタリングデータを既存のどのクラスタに含めるか、あるいは新しいクラスタを起すかの判断をするときの判断尺度として、クラスタ内に存在するデータ数を考慮するようにし、またクラスタの中心値と被クラスタリングデータとの時間間隔の差分や上記クラスタ内のデータ数を考慮した評価値を上記クラスタリング精度との比較により行うようにするものである。
【００４２】
【発明の実施の形態】
以下図面を参照して本発明の実施形態例を詳細に説明する。
【００４３】
本発明を実現するための構成手段の実施形態例を図１に示す。
【００４４】
図１において、１は時系列データを蓄積し、後述するクラスタリング処理を行うための前処理を行うための情報蓄積・処理部、１１は、時系列の生データを蓄積する情報蓄積部、１２は図７に例示したように情報蓄積部１１のデータをクラスタリングの前処理としてデータを整理する情報変換部、１３は図８に例示したように事象Ａの次に事象Ｂが生じたデータを抽出する等クラスタリングの前処理を行う候補パターン生成部である。
【００４５】
２は候補パターン生成部１３のデータをクラスタリング処理するクラスタリング処理部で、２１はクラスタリングする条件を設定するためのパラメータMaxDiameter設定部、２２はMaxDiameter設定部２１の条件の下に後述するクラスタリング処理を行うクラスタリング制御部、２３はクラスタリング制御部２２での処理過程ならびに処理結果を蓄積するクラスタリングデータ部である。
【００４６】
３はユーザとのインタフェースをとる入出力部で、３１はクラスタリング処理部２でのクラスタリングの条件を指定するための条件設定部、３２はクラスタリングデータ部２３の内容を表示する表示部である。
【００４７】
このように構成された本発明の動作を以下に説明する。
【００４８】
図９に示した従来のクラスタリング手法に対して、本発明は図２ならびに図３に示すように処理するものである。（図２および後述する図３の処理は、考え方を説明するためのもので、このような考え方の処理を実行するプログラムを含んでいる）図２、図３の処理を行うときの条件設定として、ユーザは条件指定部３１において、MaxDiameter設定部２１に対して、例えば
【００４９】
【数７】
0003650572.tif 000002
【００５０】
のように条件設定を行う。
【００５１】
ここで、centerｎｅａｒｅｓｔは、クラスタリングされるデータ（被クラスタリングデータ）ｄをクラスタリングするのに最も適しているクラスタ（Ｃｎｅａｒｅｓｔ）の中心値であり、例えば図９のクラスタＣi=１では１９に相当する。Ｃｎｅａｒｅｓｔについては後述する。
【００５２】
各クラスタの中心値Ｃcenter が、例えば図４左欄のような場合、MaxDiameterは、それぞれ同右欄のようになる。
【００５３】
これは、事象が起きる時間間隔に応じてMaxDiameterを変化させることにより、時間間隔が比較的長いデータに対しては、小さなMaxDiameterで処理すると近視眼的尺度でクラスタリングする、もしくは無用な精度でクラスタリングすることになり、これをさけるためである。また時間間隔が短いデータの場合も同様に、それに見合った精度でクラスタリングできるようにするもので、従来はMaxDiameterが固定であることによる欠点を改善するものである。
【００５４】
なおMaxDiameterとcenterｎｅａｒｅｓｔの関係は、上記式（１）に限定されることはなく、分析対象データに応じて経験則やユーザの都合に応じて設定すればよい。
【００５５】
次に、個々の被クラスタリングデータｄi （ｉ＝０〜ｎ）についてクラスタリングを行う手法について、図２ならびに図１により説明する。
【００５６】
入力される被クラスタリングデータｄi について、クラスタリング制御部２２は、クラスタリングデータ部２３から、ｄi と最も近いクラスタＣｎｅａｒｅｓｔを探し、ユーザが設定したMaxDiameterに基づいて、以下の論理によりｄi をＣｎｅａｒｅｓｔに挿入するか、新しいクラスタをつくるかを決定する。
【００５７】
つまり、
Diameter（Ｃｎｅａｒｅｓｔ）≦ MaxDiameter（centerｎｅａｒｅｓｔ)  式（２）
であれば、ｄi をＣｎｅａｒｅｓｔに挿入し、式（２）が成立しなければ新しいクラスタを作成する。
【００５８】
ここでDiameter（Ｃi ）は、クラスタリングする時の精度を表わす他のパラメータで、次式で表わされる。
【００５９】
【数８】
0003650572.tif 000003
【００６０】
これは、クラスタ内のデータの各ペアの距離の２乗和を組合せの数で割ったもので、文献２（Tian Zhang,Raghu,Ramakrishnan,Miron Livny/BIRCH: An Efficient Data Clustering Method for Very Large Databases/ Proceedings of the 1996 ACM SIGMOD international conference on Management of data June 3-6,1996,Montreal Canada  ｐ．103〜114）等に記載されている。
Diameter（Ｃi ）は、新しく挿入するデータｄi を含むクラスタのクラスタ内距離であり、詳細については後述する。
【００６１】
このようにして、個々のデータのクラスタリングを行う。
【００６２】
ここで、上記において被クラスタリングデータｄjと最も近いクラスタＣｎｅａｒｅｓｔを選択する手順を図３に示す。
【００６３】
Ｃｎｅａｒｅｓｔを決定するための評価値としてＤj を設定する。
【００６４】
Ｄj ＝｜Ｃjcenter −ｄj ｜／Ｃjcenter                   式（４）
を各クラスタについて計算し、Ｄj が最小となるクラスタＣjをＣｎｅａｒｅｓｔとして選択する。ここで、式（４）は各クラスタの中心値Ｃjcenter とｄj との距離をＣjcenter で正規化することを意味し、距離として差分絶対値ではなく、差分自乗値の平方根を用いてもよい。
【００６５】
また上記説明において、クラスタリング時の精度を表わす他のパラメータDiameter（Ｃi ）の意義について図５を例にとり説明する。
【００６６】
時間間隔ｄ＝７．０というデータをクラスタリングする場合、これに最も近いクラスタに含まれる既存のデータがcase１の場合とcase２の場合を想定する。
【００６７】
データの数はcase１では１０個、case２では３個、クラスタの中心はcase１，２ともに１０．０、新しいデータｄ＝７．０に対するクラスタ中心との距離は、case１，２ともに３である。
【００６８】
従って、従来の手法でMaxDiameter＝３とすると、｜７．０−１０．０｜≦MaxDiameter＝３であるから、ｄはcase１，２ともこのクラスタに含まれる。またMaxDiameter＝４とすると、case１，２とも、このクラスタには含まれず、新しいクラスタを生成することになる。
【００６９】
これに対し、本発明による手法によれば、式（３）から
case２（図５（ｂ））の場合は、
【００７０】
【数９】
0003650572.tif 000004
【００７１】
case１（図５（ａ））の場合については、同様にして
Diameter＝２．２１となる。MaxDiameterを例えば３とするとcase１ではこのクラスタに含まれるが、case２では、このクラスタに含まれず新しいクラスタを生成することになり、従来の手法と結果が異なってくる。
【００７２】
すなわち、本発明ではそのクラスタに含まれるデータの数を考慮して、クラスタリングを行うので、より精度の高いクラスタリングが行えることを示している。
【００７３】
本発明では、時系列データのクラスタリングにおいて、クラスタリングの精度を表わすMaxDiameterを固定ではなく、被クラスタリングデータｄをクラスタリングするのに最も適したクラスタ（Ｃｎｅａｒｅｓｔ）の中心値centerｎｅａｒｅｓｔの関数とし、ユーザが設定できるようにした。
【００７４】
またＣｎｅａｒｅｓｔを探すとき、ｄとＣｎｅａｒｅｓｔの中心との距離を、クラスタ中心値centerｎｅａｒｅｓｔで基準化した値Ｄを評価値とし、このＤが最小になるクラスタをＣｎｅａｒｅｓｔとするようにした。
【００７５】
また、データｄをクラスタリングする際、クラスタＣｎｅａｒｅｓｔを探しユーザが設定したMaxDiameterに基づいて、ｄをＣｎｅａｒｅｓｔに入れるか、新しいクラスタを作るかの決定を
Diameter（Ｃｎｅａｒｅｓｔ）≦ MaxDiameter（centerｎｅａｒｅｓｔ）であれば、ｄをＣｎｅａｒｅｓｔに挿入し、そうでなければ新しいクラスタを作成する。ここでDiameterは、新しく挿入するデータを含めたクラスタ内距離とし、クラスタ内のデータ数が反映されるようにした。
【００７６】
このように構成した本発明の効果を図６により説明する。
【００７７】
図６は、図８の説明図と同様に事象Ａの後にＢが生じたデータを時間間隔の長さを横軸としてプロットしたもので、横軸に対応した数字は、基準時からデータが生じるまでの時間間隔の例で、図６では時間間隔の短いもの（例えば、３日前後から）長いもの（例えば、３６０日前後）のデータがある場合を示している。（説明の都合上、データの部分的な集合を図６（ａ）に示すようにそれぞれイ〜ニ部とする）
図６（ａ）および（ｂ）は、従来の手法でクラスタリングした場合で、（ａ）はMaxDiameter＝５、（ｂ）はMaxDiameter＝３０で、それぞれ横長の楕円で囲んだ範囲が注目するクラスタとして抽出された場合を示している。
【００７８】
図６（ａ）の場合では、データの部分的な集合としてイ部が抽出される他、事象Ａの１〜５日後に事象Ｂが出現する例えばロ部のような集合も抽出されてしまう。反面ハ部、ニ部にも、データの部分集合があるが、これらは抽出されない。
【００７９】
また図６（ｂ）の場合では、イ部とロ部が一緒になって抽出されてしまう。
【００８０】
これに対し、本発明では図６（Ｃ）部に示すように、イ部、ハ部、ニ部が抽出され、同図の楕円の大きさが示すようにデータの時間間隔に見合った適切な精度でクラスタリングすることができる。
【００８１】
すなわち、短い時間間隔で事象が生じる場合は、短い間隔の高い精度でクラスタリングし、長い時間間隔で事象が生じる場合は、その時間間隔に見合った適切な精度でクラスタリングし、近視眼的なクラスタリングによる見落しがないようにすることができる。
【００８２】
また、図５で説明したように、クラスタリングにおいて、クラスタ内のデータ数も考慮してクラスタリングできるようにしたので、より精度の高いクラスタリングが可能となった。
【００８３】
尚、本発明における時系列データの分類方法は、具体的にはパーソナルコンピュータ（ＰＣ）等のコンピュータにより、予め所定のコンピュータ読み取り可能な記録媒体に記録された時系列データの分類プログラムに基づいて実行される。
【００８４】
すなわち、時系列的に生じる複数のデータをクラスタリングする時系列データの分類プログラムを記録した記録媒体において、クラスタリング条件を利用者の指定に基づき設定するクラスタリング条件設定手順、被クラスタリングデータをどのクラスタに含めるか最も近いクラスタを探すクラスタ検索手順、被クラスタリングデータについてクラスタリングのための評価尺度を計算する計算手順、前記計算手順の結果と前記クラスタリング条件設定手順の条件に基づきクラスタ分けを決定する判定手順をコンピュータに実行させる。
【００８５】
また、前記クラスタ検索手順において、被クラスタリングデータについて、各クラスタの中心値と入力データの距離を各クラスタの中心値で正規化した値を各クラスタについて求め、その値が最小となるクラスタを最も近いクラスタＣｎｅａｒｅｓｔとして抽出するようにしたことを特徴とする。
【００８６】
また、前記クラスタリング条件設定手順において、各クラスタのクラスタリングの精度を表わすパラメータMaxDiameterを、クラスタ検索手順で得られたクラスタＣｎｅａｒｅｓｔの中心値centerｎｅａｒｅｓｔを含む関数とするようにしたことを特徴とする。
【００８７】
また、前記計算手順において、クラスタリングのための各クラスタの評価値Diameterを新しく挿入する被クラスタリングデータを含めたそのクラスタ内の各データｄi （ｉ＝１〜Ｎ，ｊ＝１〜Ｎ）とそのクラスタ内の全データ数Ｎとの関係を
【００８８】
【数１０】
0003650572.tif 000005
【００８９】
としたことを特徴とする。
【００９０】
また、前記判定手順において、クラスタＣｎｅａｒｅｓｔの中心値centerｎｅａｒｅｓｔとパラメータMaxDiameterと評価値Diameterとの関係が、Diameter（Ｃｎｅａｒｅｓｔ）≦MaxDiameter（centerｎｅａｒｅｓｔ）であるとき、被クラスタリングデータｄをクラスタＣｎｅａｒｅｓｔに含め、上記関係が成立しないとき、ｄを新しいクラスタに含めるようにしたことを特徴とする。
【００９１】
【発明の効果】
以上述べたように本発明によれば、時系列データを時間間隔が短い場合から長い場合まで、適切にかつ高い精度でクラスタリングすることができるので、広い範囲の分野のデータに対して適用することができる。これによりデータの分析・相関関係の解析を適切に行うことができる。
【図面の簡単な説明】
【図１】本発明の実施形態例を示す構成説明図である。
【図２】本発明の実施形態例に係るクラスタリング処理の一例を示すフローチャートである。
【図３】本発明の実施形態例に係るクラスタリング処理の部分例を示すフローチャートである。
【図４】本発明の実施形態例に係るMaxDiameterの設定例を示す説明図である。
【図５】本発明の実施形態例に係るDiameterの一例を示す説明図である。
【図６】本発明の実施形態例に係る効果を示す説明図である。
【図７】従来の時系列データのサンプル例を示す説明図である。
【図８】従来の特定の事象例を示す説明図である。
【図９】従来の手法によるクラスタリングの例を示す説明図である。
【符号の説明】
１    情報蓄積・処理部
２    クラスタリング処理部
３    入出力部
１１    情報蓄積部
１２    情報変換部
１３    候補パターン生成部
２１    MaxDiameter設定部
２２    クラスタリング制御部
２３    クラスタリングデータ部
３１    条件指定部
３２    表示部
【図１】
0003650572.tif 000006
【図２】
0003650572.tif 000007
【図３】
0003650572.tif 000008
【図４】
0003650572.tif 000009
【図５】
0003650572.tif 000010
【図６】
0003650572.tif 000011
【図７】
0003650572.tif 000012
【図８】
0003650572.tif 000013
【図９】
0003650572.tif 000014