JP3659318B2

JP3659318B2 - 空間データマイニング装置

Info

Publication number: JP3659318B2
Application number: JP2000135928A
Authority: JP
Inventors: 康彦森本; 晴信久保
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 2000-05-09
Filing date: 2000-05-09
Publication date: 2005-06-15
Anticipated expiration: 2020-05-09
Also published as: US20010051947A1; JP2001318938A; US7024402B2

Description

【０００１】
【発明の属する技術分野】
本発明は、空間データマイニングにおけるデータベース処理に関し、より詳しくは、空間データマイニングの基本機能である最適距離または最適方角を算出する手法、装置等に関する。
【０００２】
【従来の技術】
データベースにある住所などの空間情報を空間的な文脈で解釈し、その空間的な法則を大量のデータの中から導き出す新しい技術を空間データマイニングと呼ぶ。この空間データマイニングは、大量データに対して、コストの高い空間・幾何学演算を行なう必要があり、技術的にはかなり難しい問題に直面する場合が多い。そのために、空間データマイニングはあまり発展しているとは言えず、未開拓の研究分野である。しかしながら、その一方で、空間データマイニングは、情報産業の中でも最もビジネスボリュームの大きなデータベースやＧＩＳ(Geographical Information System：地理情報システム)分野を大いに発展させる可能性を秘めた基礎技術と考えられ、ビジネス的、また技術的にも大変有望な技術分野である。
【０００３】
ここで、既存の空間データマイニングシステムとして、あらかじめ距離を定めた上で空間相関ルールを導き出すものが知られている。例えば、Ｊ.Ｈａｎらによる手法("Spatial Data Mining: Progress and Challenges,"SIGMOD'96 Data Mining Workshop,pp.55-69,1996)では、述語として「close to」「far from」という距離述語を定義し、空間情報を有するデータベースから、例えば、
「close to 公園」→「住宅地である」（支持度５％、確信度８０％）、
「地価下落」→「far from 駅」（支持度１０％、確信度７０％）
のような距離述語を含んだ空間相関ルールを導き出している。
【０００４】
また、既存の空間データマイニングシステムとして、あらかじめ方位を定めた上で空間相関ルールを導き出すものも知られている。例えば、上記Ｊ.Ｈａｎらによる手法では、述語として「west of」「north of」という方角述語を定義し、空間情報を有するデータベースから、例えば、
「west of 公園」→「住宅地である」（支持度５％、確信度８０％）、
「地価下落」→「north of 駅」（支持度１０％、確信度７０％）
のような方位述語を含んだ空間相関ルールを導き出すことが可能である。
【０００５】
【発明が解決しようとする課題】
しかしながら、Ｊ.Ｈａｎらによる手法のような「close to」「far from」は、あらかじめマイニング開始前に、「close to Ｘ」＝「Ｘから距離Ｙ以内である」、「far from Ｘ」＝「Ｘから距離Ｚ以遠である」のような距離を与えて定義しておく必要がある。また、上述した「west of」「north of」は、あらかじめマイニング開始前に、「west of Ｘ」＝「Ｘの西側に隣接する１辺がＹの長さで長方形の内側である」、「north of Ｘ」＝「Ｘから方角でＹ１°からＹ２°である」のように存在範囲や角度等を与えて定義しておく必要がある。このとき、多くの分析業務においては、ある目的を最適化するＹ、Ｚのような距離自体、また、ある目的を最適化するＹ１°、Ｙ２°のような厳密な方角を規定する数値自体が必要とされており、最先端の既存技術を適用しても、かかる多くの分析業務で十分な対応を図ることができない。
【０００６】
例えば、「Ａ地区で、現金自動預払機(ＡＴＭ)の単位距離あたりの存在密度を最大化する、コンビニエンスストアからの半径を求めよ」といった検索や、「強い大気汚染が広がっているのは、各ゴミ処分場からどの方角であるかを求めよ」といったような検索には、既存のデータマイニングシステムでは対応することができない。
【０００７】
本発明は、以上のような技術的課題を解決するためになされたものであって、その目的とするところは、予め距離や方位を定めた上で空間相関ルールを導き出すことなく、多くの分析業務で要求される距離自体、方位自体を求める技術を提供することにある。
また他の目的は、距離自体、方位自体を求める際に、マイニング作業の高速化を図ることにある。
更に他の目的は、ユーザ(お客様)に対して利便性の高いマイニング出力結果を提供することにある。
【０００８】
【課題を解決するための手段】
かかる目的のもと、本発明は、予め距離や方位を定めた上で空間相関ルールを導き出すのではなく、入力パラメータとして距離や方位の定義、始点集合の定義、目的関数の定義から、多くの分析業務にて要求される、ある目的を最適化する距離自体または方位自体を求める空間データマイニングを提供するものである。即ち、本発明は、コンピュータにて実行され、住所などの空間情報を含むデータベースの中から空間的な法則を導き出す空間データマイニング方法であって、データベースから始点または始点群を与えるステップと、与えられた前記始点または前記始点群から距離または方位を定義するステップと、空間的な法則を導き出すために定義された目的関数を入力するステップと、空間情報を含むデータベースから与えられた始点群からなる始点集合データを用いてデータテーブルを生成するステップと、生成されたデータテーブルを用いてデータベースにおける各質問点の属性値を距離の値に応じて集計することで、入力された目的関数を最適化するような前記始点または前記始点群からの距離区間または方位区間を算出するステップとを含むことを特徴としている。
【０００９】
ここで、この目的関数は、分析業務に要求される距離自体または方位自体が与えられていない関数であることを特徴としている。また、距離の定義、始点または始点群の定義、および目的関数の定義を入力パラメータとして入力するステップとを更に含むことを特徴とすることができる。
更に、距離区間を算出するステップは、始点群からなる始点集合データと定義された目的関数とに基づいて中間テーブルを生成すると共に、生成された中間テーブルに基づいてデータベースにおける各質問点の属性値を距離の値に応じて集計することを特徴とすれば、計算時間を大幅に短縮することができる点で好ましい。
また、算出された始点または始点群からの距離区間または方位区間を地図上に表示するステップとを更に含むことを特徴とすれば、計算されたルールを視覚的に把えることが可能となり、ユーザに対する利便性を向上させることができる。
【００１０】
ここで、算出された方位区間は、この目的関数を最適化する方位を数値として算出することを特徴とすることができる。また、算出された方位区間は、検索対象となるデータの範囲として方位を算出するのに適した始点または始点群からの等距離範囲を選択することを特徴とすることができる。始点または始点群から無限遠まで計算するのは殆ど不可能であり、最適化される領域を定めることは有効である。
【００１１】
また、本発明は、コンピュータにて実行され、空間情報を含むデータベースの中から方位に関する空間的な法則を導き出すためのデータテーブルを生成する空間データマイニング方法であって、空間情報を含むデータベースから始点の集合および質問点の集合を与えるステップと、データベースから与えられた始点の集合と質問点の集合との距離の上限を指定するステップと、データベースから個々の質問点を読み出し、読み出された質問点に対して始点との距離を計算するステップと、計算された始点との距離が指定された上限に含まれる質問点に対して、始点との角度を計算するステップと、計算された始点との角度を用いてデータテーブルを生成するステップとを含むことを特徴とすることができる。ここで、質問点とは、例えば顧客データの点集合等が挙げられ、実際に始点や始点群からの距離、方位が計算される対象である。
【００１２】
本発明を装置から把えると、本発明は、住所などの空間情報を含むデータベースの中から最適な距離を計算する空間データマイニング装置であって、距離最適化に必要な目的関数を入力する入力手段と、データベースにおける始点集合データおよび質問点集合データに基づいて始点と質問点との距離を計算して中間テーブルを生成する中間テーブル生成手段と、この中間テーブル生成手段によって生成された中間テーブルに基づいて入力手段により入力された目的関数の値を最適化する距離を計算する最適距離計算手段とを備えたことを特徴とすることができる。
【００１３】
ここで、この中間テーブル生成手段は、データベースにおける始点集合データからボロノイ図を作成するボロノイ図作成手段と、このボロノイ図作成手段によって作成されたボロノイ図とデータベースにおける質問点集合データとに基づいて各始点と各質問点との距離を計算してデータレコードを生成する距離計算手段と、調べたい目的関数から最適化関数を選択して距離区間毎に最適値に必要なレコード値をデータレコードから集計する距離別計算手段とを含むことを特徴とすることができる。
更に、このボロノイ図作成手段は、入力始点数に応じて平面四分割を繰り返し、入力始点数を末端の分割平面ピクセルに振り分けて各ピクセルの中にある始点の中から１つをピクセルの代表点として選択し、各段ピクセルを中間ノードとする四分木を作成し、この四分木の各ノードを広さ優先順に最上段から走査して順序付けされた始点集合を出力することを特徴とすれば、処理を高速化することが出来る点で好ましい。
また、この四分木の構造を事前に計算しておき、メモリに蓄積するように構成すれば、この四分木の構造は距離最適化や方位最適化に関するマイニングで頻繁に利用することから、マイニング作業を更に高速化することができる点で好ましい。
【００１４】
一方、本発明は、住所などの空間情報を含むデータベースの中から最適な方位を計算する空間データマイニング装置であって、方位最適化に必要な目的関数を入力する入力手段と、このデータベースにおける始点集合データおよび質問点集合データに基づいて、始点から特定方向を０度とする角度を用いて質問点の位置する方位を含む中間テーブルを生成する中間テーブル生成手段と、この中間テーブル生成手段によって生成された中間テーブルに基づいて入力手段により入力された目的関数の値を最適化する方位を計算する最適方位計算手段とを備えたことを特徴とすることができる。
ここで、この中間テーブル生成手段は、このデータベースにおける始点集合データからボロノイ図を作成するボロノイ図作成手段と、このボロノイ図作成手段によって作成されたボロノイ図とデータベースにおける質問点集合データとに基づいて各始点と各質問点との距離を計算する距離計算手段と、この距離計算手段により計算された距離の中から、指定された上限距離以内の質問点の始点からの方位を計算して中間テーブルのレコードとする方位計算手段と、調べたい目的関数から最適化関数を選択して方位区間毎に最適値に必要なレコード値をこのデータレコードから集計する方位別計算手段とを含むことを特徴とすることができる。
【００１５】
本発明を他の観点から把えると、本発明は、住所などの空間情報を含むデータベースの中から最適な距離または方位を計算して出力する空間データマイニング装置であって、分析業務に要求される距離自体および方位自体が与えられていない目的関数を入力する入力手段と、このデータベースにおける始点集合データおよび質問点集合データに基づいて始点と質問点との距離または方位を求めると共に、この目的関数の値を最適化する最適距離または最適方位を計算する最適距離・方位計算手段と、最適距離・方位計算手段により計算された最適距離または最適方位を地理情報システムの画面上に表示する表示手段とを備えたことを特徴とすることができる。
【００１６】
ここで、この表示手段は、最適距離・方位計算手段により計算された最適距離を各始点を中心とする円形領域にて表示することを特徴とすることができる。また、この表示手段は、最適距離・方位計算手段により計算された最適方位を各始点からの扇形領域にて表示することを特徴とすることができる。これらによれば、求まった最適距離や最適方位を地図上に解かり易く表示することが可能となり、お客様の使い勝手を各段に向上させることができる。
【００１７】
また、本発明は、住所などの空間情報を含むデータベースの中から空間的な法則を導き出す空間データマイニング装置であって、データベースから始点または始点群を与える始点付与手段、空間的な法則を導き出すために調べる目的関数の定義の入力を受け付ける目的関数定義入力手段、入力された目的関数を最適化するような始点または始点群からの距離区間を算出する距離区間算出手段、与えられた始点または始点群から方位を定義する方位定義手段、定義された目的関数を最適化するような始点または始点群からの方位区間を算出する方位区間算出手段とを含むことを特徴とすることができる。
更に、データベースから始点の集合および質問点の集合を与える始点/質問点付与手段、付与された始点の集合と質問点の集合との距離の上限を指定する距離上限指定手段、質問点に対して始点との距離を計算する距離計算手段、計算された始点との距離が指定された上限に含まれる質問点に対して、始点との角度を計算する角度計算手段、計算された始点との角度を用いてデータテーブルを生成するデータテーブル生成手段とを含むことを特徴とすることができる。
【００１８】
また更に、本発明は、距離自体および方位自体が与えられていない目的関数に基づいて住所などの空間情報を含むデータベースの中から空間的な法則を導き出すためのコンピュータにて実行されるプログラムを格納した記憶媒体であって、このプログラムは、データベースから始点または始点群を与えるステップと、与えられた始点または始点群からの距離または方位を定義するステップと、調べたいものとして定義された目的関数の入力を受け付けるステップと、空間情報を含むデータベースから与えられた始点群からなる始点集合データを用いてデータテーブルを生成するステップと、このデータテーブルを用いてデータベースにおける各質問点の属性値を距離の値に応じて集計することで、入力された目的関数を最適化するような、始点または始点群からの距離区間または方位区間を算出するステップとを含むことを特徴とすることができる。この記憶媒体としては、例えばＣＤ−ＲＯＭ等の可搬性のある媒体の他、ネット等を介してプログラムをダウンロードするための、プログラムを提供する側のハードディスク等の記憶媒体、ダウンロード等によってプログラムの提供を受けたユーザ側のハードディスク等の記憶媒体を含むものである。
【００１９】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいてこの発明を詳細に説明する。
まず、本実施の形態における空間データマイニングの理解を容易にするために、本方式のモデリングとアルゴリズムについて説明する。
図１は、本実施の形態におけるモデリング１として、距離最適化エンジンによる出力例を示した図である。地図１１上に、始点(または始点群)１２〜１４であるコンビニエンスストア(ＣＳ)から、目的関数を最適化するような距離(あるいは距離区間)が、所定の半径を有する円１５〜１７で表示される。図１に示す例では、「ひったくりの発生率を最大化するコンビニエンスストアからの距離を求めよ。」といった検索から、その目的関数を最適化するような始点１２〜１４からの距離が示されている。
【００２０】
この出力例では、例えば、
「ひったくり」→(「コンビニエンスストア」,「[０,１００]」),「５」件
といった内容が出力される。その意味は、
「ひったくり」の発生率を最大化するのは、
「コンビニエンスストア」から半径「０」ｍ以上「１００」ｍ以内で、
半径(ｍ)あたり「５」件発生している。
である。始点からの距離の出力としては、以下のような例がある。
「ひったくり」→(「駅」,「[５０,１８０]」),「６.１」件
「ひったくり」→(「銀行」,「[２００,−]」),「２.２」件
「強盗」→(「銀行」,「[６０,２００]」),「１.３」件
「殺人」→(「飲食店」,「[０,５０]」),「０.４」件
【００２１】
図２は、本実施の形態におけるモデリング２として、方位最適化エンジンによる出力例を示した図である。地図１１上に、始点(または始点群)１２〜１４であるコンビニエンスストア(ＣＳ)から、目的関数を最適化するような始点１２〜１４からの方位区間１８〜２０が算出されて示されている。図２に示す例では、「ひったくりの発生率を最大化するコンビニエンスストアからの方角を求めよ。」といった検索から扇型の領域で表現される角度が示されている。
この出力例では、例えば、
「ひったくり」→(「コンビニエンスストア」,「[０,１００]」),「５」件
といった内容が出力される。その意味は、
「ひったくり」の発生率を最大化するのは、
「コンビニエンスストア」から方位「０」°以上「１００」°以内で、
１０°あたり「５」件発生している。
である。始点からの方位の出力としては、その他に、
「ひったくり」→(「神社」,「[１２０,２４０]」),「６.１」件
等の出力例が挙げられる。
【００２２】
図３は、本実施の形態における距離・方位最適化エンジンのアルゴリズムの概略を説明するためのフローチャートである。まず、始点(または始点群)を与える(ステップ１０１)。即ち、距離最適化の場合には距離を計算する際の起点となる地図上のエンティティ(実体)を指定し、方位を最適化する際にはどの地点から見た方角なのかを計算するために方角基準点として地図上のエンティティを指定する。この始点は、各計算毎に１つでも複数でもよく、それを始点あるいは始点群(集合)とする。次に、その始点(または始点群)からの距離・方位を定義する(ステップ１０２)。方位では、どこを起点とするかを定義する。但し、常に距離をユークリッド距離として定める場合には、距離に対する定義は不要となる。そして、例えば、ある商品の売り上げ総額、犯罪の発生件数などの調べたいものの目的関数を定義する(ステップ１０３)。その後、その目的関数を最適化するような始点からの距離区間、あるいは方位区間を算出する(ステップ１０４)。その後、距離・方位のバケット集計と最適化距離の計算が実行される。尚、ｎを質問点数、ｍを始点点数とし、Ｎ＝ｎ＋ｍと仮定すると、距離算出の平均実行時間はＯ(Ｎ)で表わすことができる。即ち、質問点に対応する始点を見つけるのに、平均計算量でＯ(logｎ)、距離の計算はＯ(１)で可能であり、この処理にＯ(ｎlogｎ)かかる。しかし、距離がユークリッド距離である場合は、後述する四分木構造(quaternary incremental method)を利用することで、平均実行時間をＯ(ｎ)とすることができる。ここで質問点とは、処理の対象となるデータベースにおける顧客データ等である。
【００２３】
図４は、データベース例を示した図である。本実施の形態では、図に示すようなスキーマ(仕様)を有するデータベースと関連付けされた統合化地理情報システムの存在を前提としている。このデータベースの各スキーマには、データを区別するためのＩＤ情報と、位置(座標)情報が含まれている。この位置情報は、住所データで表わされる場合の他、地図情報に対応した座標情報等が格納されている。また、下線で示される数値属性や、下線した斜体文字で示されるカテゴリカル属性が含まれている。このデータベースから、距離や方位に関する最適化ルールがマイニングされる。
【００２４】
図５は、入力パラメータとして始点群や基点群(方位の始点群)の定義例を示した図であり、図３のフローチャートのステップ１０１にて示した距離の始点群や方位の始点群を定義する例を示している。この始点や基点の定義としては、例えば、郵便局、学校、警察等のエンティティが指定される。ここで、例えば、郵便局(ＡＬＬ)であれば、集配局や特定郵便局等の複数のカテゴリカル属性に基づく郵便局を統合して定義される。同様に学校(ＡＬＬ)であれば、各種学校や小学校、中学校等のカテゴリカル属性を統合して定義される。また、例えば、駅であれば、乗降客Ｘ以上や乗降客Ｘ未満等の数値属性に基づいて、始点群や基準群を定義できる。同様に、例えば、コンビニエンスストア(コンビニ)では、売上Ｘ以上、売上Ｘ未満等の数値属性に基づく定義が可能である。
【００２５】
図６は、距離や方位の定義例を示した図であり、図３のフローチャートにおけるステップ１０２の定義例である。これらの定義は、最適化ルールをマイニングする場合に、入力パラメータとして指定されるものである。距離の定義としては、ユークリッド距離やネットワーク距離がある。このユークリッド距離はボロノイ図などを利用して計算されるが、高速に計算する場合やごく近距離の場合には、地図の実体とかい離することがある。また、ネットワーク距離はダイクストラ法などで計算される。このダイクストラ法は、各ノードへの最短距離をスタートノードの周辺から１つずつ確定して徐々に範囲を広げていき、最終的に全てのノードへの最短距離を求める方法であり、計算時間は多く必要となるが地図上での実体を反映することができる。尚、本実施の形態では、ユークリッド距離の場合に適用される計算法を用いており、それ以外の距離では計算法が全く異なる。ユークリッド距離として決める場合には、距離の定義は不要である。また、方位の定義としては、例えば、北を０°として時計回りに３６０°で１周する方位スケールを定義する等があり、これらの方位スケール上で方位区間が定義される。
【００２６】
図７は、目的関数の定義例を示した図であり、図３のフローチャートにおけるステップ１０３の定義例である。これらの目的関数は最適化ルールをマイニングする際に指定されるものである。この目的関数の定義としては、各スキーマに対して、図の下線で示される数値(あるいは数値として派生する)属性、下線した斜体文字で示されるカテゴリカル(あるいはカテゴリ値として派生する)属性を用いて定義することができる。例えば、顧客スキーマとして、数値属性を用いて「支持率Ｓ以上の顧客の「平均年収」最大化距離」や、カテゴリカル属性を用いて「支持率Ｓ以上の顧客「年齢６０歳以上」の顧客比率最大化距離」等の定義や、例えばＡＴＭスキーマとして「支持率Ｓ以上の顧客の「ＡＴＭ数/顧客数」最大化距離」等を定義することができる。
【００２７】
次に、図３のフローチャートにおけるステップ１０４では、定義された目的関数を最適化するような始点からの距離区間、方位区間が算出される。本実施の形態では、後述するように中間テーブルを作成して高速化処理が図られている。この中間テーブルでは、始点集合を母点とする幾何図形であるボロノイ図(ティーセン分割)を、逐次添加法によって作成している。即ち、ｍ個の母点Ｐ₁,…,Ｐ_mからなるボロノイ図Ｖ_mに新たな母点Ｐ_m+1を加え、ｍ＋１個の点からなるボロノイ図Ｖ_m+1を作っている。
【００２８】
図８は、逐次添加法による処理の流れを示した図である。図の左側は処理の流れをフローチャートで示し、図の右側に形成過程におけるボロノイ図の例を示している。まず、Ｐ₁,…,Ｐ_mの中でＰ_m+1に最も近い点Ｐを「ボロノイ図の高速点位置決定法」(後述)により求める(ステップ１１１)。次に、Ｐのボロノイ領域内にＰＰ_m+1の垂直２等分線Ｌを引く(ステップ１１２)。次に、Ｌが接するボロノイ領域の母点に対しても同様に垂直２等分線を引く(ステップ１１３)。上記の作業を繰り返し、Ｐ_m+1のボロノイ領域を作成してＶ_m+1とする(ステップ１１４)。
【００２９】
図９は、ボロノイ図の点位置決定法における処理の流れを示した図である。ここで示す「ボロノイ図の点位置決定法」は、ある点Ｐがｍ個の母点Ｐ₁,…,Ｐ_mからなるボロノイ図Ｖ_mのどの母点に最も近いかを求める(どのボロノイ領域にあるかを求める)ものである。まず、Ｐ₁,…,Ｐ_mの中で任意の点Ｐiを選び、点Ｐとの距離ｄを求める(ステップ１２１)。次に、Ｐiの各隣接母点ＰjとＰとの距離ｄjを計算し、ｄと比較する(ステップ１２２)。ここで、ｄj＜ｄが判断され(ステップ１２３)、ｄj＜ｄであればｄ＝ｄj、Ｐi＝Ｐjとしてステップ１２２に戻る。そのような母点がない場合には、Ｐiを答えて(ステップ１２５)終了する。
【００３０】
図１０は、逐次添加法の前処理における処理の流れを示した図である。まず、母点が各ピクセルにおよそ１つ含まれるような深さｄの四分木を作成する(ステップ１３１)。次に、図(ａ)のようにピクセルに番号を付ける(ステップ１３２)。この図(ａ)は、地図(２次元平面)のビューを示しており、ここに示される矢印は、ピクセル番号を付ける順序を示したものである。次に、各母点を座標値によってそれぞれピクセル(四分木の葉)に割り当て、各葉にラベルを付ける(ステップ１３３)。次に、番号順に、各葉の全ての(まだラベルのない)先祖に対して、自分のラベル値をコピーする(ステップ１３４)。最後に、この四分木の各節と葉を、広さ優先順に並べ、その順に「逐次添加法」を実行する(ステップ１３５)。図(ｂ)は深さ３の四分木のビューを示しており、深さ方向ではなく横方向の順番にて「逐次添加法」が実行される。
尚、駅、郵便局、警察、学校、公園など、分析対象になり易く、あまり位置的に変更のない地図上のエンティティについては、予めボロノイ図を構成しておくこともできる。
【００３１】
その後、ボロノイ図を利用した始点からの距離が計算される。ここでは、「ｎ個の質問点に対し、ｍ個の母点Ｐ₁,…,Ｐ_mからなるボロノイ図Ｖ_mを使った点位置決定問題を解く」ことが行なわれる。即ち、ｎ個(かなり多い数)の各質問点(例えば犯罪データなど)と、ｍ点(コンビニなど)からなる始点集合との距離が計算される。但し、距離は、最寄の始点との距離とする。より具体的には、ピクセルで最初の質問点に対しては、逐次点においてそのピクセルのラベルとなった母点により、質問点が各ピクセル毎に計算される。また、ピクセルで最初の質問点でない場合には、前回の距離・方位計算で最近点とされた母点によって質問点が各ピクセル毎に計算される。以上のようにして、中間テーブルが作成される。
【００３２】
最後に、距離、方位のバケット集計と最適距離計算がなされる。ここでは、ｎ個(このｎはかなり多い数)の各質問点の属性値を、距離・方位の値に応じて集計する。即ち、各バケット毎に「データ数」と目的関数値算出に必要なデータが集計される。例えば、「顧客スキーマ」(支持率Ｓ以上の顧客の「平均年収」最大化距離)という目的関数の場合には、距離に応じたデータ数と年収合計数が順次、加算され、集計結果が出力される。このような集計情報を１回スイープすることで、最適化距離が求められる。この結果は、例えば図１や図２に示したように、地図上に円形形状や扇形状等によって表示される。
【００３３】
以上、本発明における処理のアルゴリズムを説明した。このような処理アルゴリズムは、コンピュータ・プログラムによって実現し、実行することができる。
図１１は、空間データマイニング装置としてのコンピュータ・システムの概略構成を説明するための図である。本実施の形態における処理アルゴリズムは、図示するようなコンピュータ・システムにおいて実行可能なプログラムとすることもできる。処理プログラムは、ハードディスクドライブ(ＨＤＤ)７５に格納され、実行時にはメインメモリ７２にロードされ、ＣＰＵ７１によって処理される。また、ＨＤＤ７５は住所などの空間情報を含む大量のデータベースをも含んでおり、処理プログラムはそのデータベースに対するアクセスを行うものである。地図情報システム(ＧＩＳ)等の地図情報や最適化距離、最適化方位の計算結果は、表示装置７６によってユーザに提示される。ユーザは、入力装置７７にて調べたい目的関数の入力や、データ出力の命令等を入力する。このような入力装置７７には、キーボードやマウス、ポインティング・デバイスやディジタイザ等を含む。さらに、出力結果を補助記憶装置であるフロッピーディスクドライブ(ＦＤＤ)７３のフロッピーディスクに記憶したり、また新たなデータをＦＤＤ７３から入力することもできる。さらに、ＣＤ−ＲＯＭドライブ７４を用いて、データを入力することもできる。
【００３４】
更に、本実施の形態における処理アルゴリズムを実現したコンピュータ・プログラムは、フロッピーディスクやＣＤ−ＲＯＭといった記憶媒体に記憶して、持ち運ぶことができる。この場合、通常のデータベース検索プログラムのデータ取り出し部分や、表示装置７６に表示するだけの処理を行うプログラムは、すでにＨＤＤ７５に記憶されている場合もある。従って、それ以外の部分が上記のような各種記憶媒体にて流通することは通常行われる事項である。また、図示されていない通信装置がバス７８に接続されて、遠隔地にあるデータベースを用いて処理したり、処理結果を遠隔地に送信するように構成することも可能である。即ち、住所などの空間情報を含む大量のデータベースを図１１に示す構成の外部に設けるように構成することもできる。
【００３５】
次に、本実施の形態における構成を、更に、機能ブロック図等を用いて詳述する。
図１２は、本実施の形態における空間データマイニングシステムの構成を説明するためのブロック図であり、図１１で示したＣＰＵ７１における構成を詳述したものである。ここでは、大きく、中間テーブル作成部３０と最適距離計算部３９とを備えている。この中間テーブル作成部３０は、ボロノイ図作成部３１、距離計算部３２、および距離別計算部３３とを備えている。このボロノイ図作成部３１は、ＩＤ、名前、地図上の座標等からなる、例えばコンビニの点集合等の始点集合データを受けて、始点添加順決定部３４およびボロノイ図点追加部３５によりボロノイ図を作成している。距離計算部３２では、ＩＤ、名前、地図上の座標、買上金額等からなる、例えば顧客データの点集合等の質問点集合データを受けて、距離の計算された顧客データレコードあるいはレコード集合を生成している。また、距離別計算部３３では、距離計算部３２から出力された顧客データレコードを基に、距離区間毎に最適化に必要なレコード値を集計している。その結果として、図１２に示されるような中間テーブルが作成される。ここでは、距離区間毎にレコード値と買上金額計が示されている。最適距離計算部３９では、この中間テーブルをスキャンして最適化関数値の最も良くなる距離が計算され、距離最適化ルールとして出力がなされる。
【００３６】
次に、図１３および図１４を用いてボロノイ図作成部３１における始点添加順決定部３４の機能を説明する。
図１３は、ボロノイ図作成部３１における始点添加順決定部３４の構成を説明するためのブロック図である。この始点添加順決定部３４は、平面四分割機能４１、始点分配機能４２、代表点決定機能４３、四分木作成機能４４、および添加順序決定機能４５を備えている。平面四分割機能４１は、始点集合データを全て入力し、入力始点数ｍに応じて、図に示すように平面四分割をｔ(ｔ＝ｍ^1/2−１)回、繰り返す。即ち、各段の１ピクセルを４等分するが、各ピクセルには、ほぼ１点の始点を有することが好ましい。
【００３７】
図１４は、分割された平面ピクセルと作成された四分木を説明する図である。図１４に示すように、平面四分割機能４１によって分割されたピクセルには番号が付けられる。ここでは深さ３として０〜６３の６４のピクセルに分割される。図１３に示す始点分配機能４２では、ｍ個の入力始点が末端の分割平面(ここでは０〜６４)のピクセルに振り分けられる。図１４では、ピクセル０に始点８(Ｓ８)と始点１９(Ｓ１９)が、ピクセル６０に始点１２(Ｓ１２)が振り分けられている。次に、図１３に示す代表点決定機能４３では、各ピクセルの中にある始点の中から、一つを、そのピクセルの代表点として選定する。例えば、図１４のピクセル６０では始点１２(Ｓ１２)が選ばれている。複数始点がある場合には、任意の一つを選び(例えば、ピクセル０では始点８(Ｓ８)が選ばれている)、始点がない場合には、代表点は「なし」となる。
【００３８】
図１３に示す四分木作成機能４４では、前述の四分割の繰り返し過程で現われる、(最下段ではない)各段の各ピクセルを中間ノードとする四分木が作成される(図１４右図参照)。更に、木の下段の中間ノードから順に、各中間ノードの代表点が決定される。図１４では、各中間ノードにおける子ノードの代表点の中から一つを代表点としており、始点８(Ｓ８)が順に選ばれている。図１３に示す添加順序決定機能４５では、四分木の各ノードを広さ優先順に最上段から走査していく。即ち、深さ方向(深さ優先順)ではなく、各段ごとに横方向に走査する。その過程で、各ノードのまだリストにない代表点を出力始点リストの最後に加えていく。最下段の葉ノードに関しては、代表点だけではなく、そのノードに属する全ての(まだリストにない)始点が加えられる。即ち、図１４の例では、ピクセル０の始点１９(Ｓ１９)が加えられる。以上のようにして、始点添加順決定部３４から、順序付けされた始点集合が図１２に示したボロノイ図点追加部３５に出力される。
【００３９】
図１５は、図１２に示したボロノイ図作成部３１のボロノイ図点追加部３５の構成を説明するためのブロック図である。このボロノイ図点追加部３５は、大きく高速点位置決定機能５１と領域分割機能５２を有している。更にこの高速点位置決定機能５１は、開始位置決定機能５３および漸近機能５４とを備え、Ｐ₁,…,Ｐ_mの中でＰ_m+1に最も近い点Ｐを「高速点位置決定法」により求めている。この開始位置決定機能５３では、入力点が四分木の最下段でどのピクセルＸに属するかが計算され、ピクセルＸの代表点の始点(ボロノイ点)Ｐiを開始位置とされる。但し、代表点「なし」の場合には、親ノードの代表点を開始位置とされる。また、漸近機能５４では、Ｐiと入力点Ｐ_m+1との距離ｄが計算される。そして、Ｐiの各隣接ボロノイ点ＰjとＰ_m+1との距離ｄjが計算され、ｄとの比較がなされる。ｄj＜ｄならばｄ＝ｄj, Ｐi＝Ｐjとされる。そのような隣接母点がなければ、Ｐiが答えとされる。そして、ピクセルＸの代表点はＰiとされる。領域分割機能５２では、右図に示すように、Ｐのボロノイ領域内にＰＰ_m+1の垂直２等分線Ｌがひかれる。Ｌが接するボロノイ領域の始点をＰとし、同様に垂直２等分線がひかれる。これを垂直２等分線で囲まれる領域ができるまで繰り返されることによって、右図のようなｍ＋１点からなる中間ボロノイ図Ｖ_m+1を得ることができる。
【００４０】
図１２に示した中間テーブル作成部３０では、以上のようにして作成されたボロノイ図作成部３１にて作成されたボロノイ図と、質問点集合データから、前述したように、距離計算部３２によって距離の計算された顧客データレコードが出力される。即ち、質問点集合の各レコードにおける質問点レコードと中間ボロノイ図Ｖ_m+1とから、高速点位置決定法によって入力点に最も近いボロノイ点が抽出され、質問点レコードとボロノイ点との距離を計算し、距離付き質問点レコードを出力する。その後、前述したように、距離別計算部３３を経て、距離区間毎にレコード値が集計された中間テーブルが中間テーブル作成部３０から出力される。出力された中間テーブルの情報は、例えばＨＤＤ７５等に格納される。
【００４１】
このソートされた中間テーブルを用いて、最適距離計算部３９にて最適距離が計算される。例えば、図１２に示したような質問点集合データにおける顧客データであれば、距離の小さなレコードから順に、買上金額をアキュムレート(累算)し、その過程で「アキュムレートされた買上金額/これまでのアキュムレートされたレコード数」の最も高い値を出す距離を記録する。その際、一般的には、このアキュムレートの過程で、最高値を出したレコードと、中間テーブルにおけるその次のレコードの距離との中間値を暫定最適距離として記録する。このように目的関数の最高値を出す暫定最適距離を維持しながら中間テーブルを１度スキャンすることで、最適距離を求めることができる。求めた最適距離は、表示装置７６を用いて図１のように表示することが可能である。
【００４２】
方位最適化を図るアルゴリズムの中間テーブルには、図２に示したように最適化する対象である各円の内側のデータのみが含まれる。即ち、空間情報と関連付けられているデータベースの各レコード(質問点)に対して、基準点との距離を計算し、半径以内に含まれているものについて基準点との角度を計算し、角度の値に応じて中間テーブルのレコードへ集計される。但し、検索対象となる円が互いに重なっている場合には、複数の円に同時に含まれる質問点が存在する場合があり得ることから、中間テーブルを作成する際に、以下の二通りのどちらかの方法で処理を行うこととする。
・それぞれの基準点に基づく角度を、全ての対応する中間テーブルのレコードに加える。
・一番距離の近い基準点に対する角度に対応するレコードにのみ、中間テーブル
へ加える。
【００４３】
方位最適化の際の中間テーブルには、このように等間隔の昇順あるいは降順の角度区間を属性として有している。例えば、目的関数が平均年収である場合に、中間テーブルは、その計算に必要な年収合計とレコード数とを属性として持つ。

【００４４】
その後、中間テーブルを用いて目的関数の最適方位の範囲を決定する。例えば、角度の小さなレコード順のインデックスをｓ,ｔとして、区間[ｓ,ｔ]の平均年収Ｘ[ｓ,ｔ]を、
Ｘ[ｓ,ｔ]＝「区間[ｓ,ｔ]の間に含まれるレコードの年収の総和 ÷ 区間[ｓ,ｔ]の給与所得者数」と表わすと、Ｘ[ｓ,ｔ]を最適化する区間[ｓ,ｔ]を求める問題となる。そのための区間アルゴリズムは、中間テーブルサイズをｎとしてＯ(ｎ)で実行可能であるが、角度を数値化した時に発生する０度での不連続性を考慮したアルゴリズムを適用する。例えば、ソートされた中間テーブルのレコードに対し、年収とレコード数とをそれぞれ累積演算させながら、
・Σ年収 / Σレコード数を最大にするレコード位置ｔとｔにおけるΣ年収とΣレコード数
・Σ年収 / Σレコード数を最小にするレコード位置ｓとｓにおけるΣ年収とΣレコード数
を記憶しておく。３６０度までスキャンしたときの値から、最適方角を求めることが可能である。ｓ＜ｔならば、最適区間は０をまたがずに[ｓ,ｔ]と与えられ、その平均年収も直ぐに求めることができる。ｔ＜ｓならば、最適区間は０をまたぐ[ｓ,ｔ]で、その平均年収も全質問点数と全質問点との年収総額を用いて求めることが可能である。このようにして求めた結果は、表示装置７６を用いて図２のように地図上に表示することが可能である。
【００４５】
このように、本実施の形態によれば、必要に応じて入力パラメータとして距離の定義(ユークリッドか(この場合ほぼ線形時間)ネットワークか(この場合多項式時間))や方位(方角)の定義、始点集合の定義、および目的関数の定義を指定することで、最適化ルールを計算して列挙することが可能となる。例えば、

を指定した場合、各始点集合から各目的関数の最適化ルールは、例えば、
「平均年収を最大化するのは郵便局からＸ以内(支持率ｓ，平均年収ｘ)」
「性別の相互情報量を最大化するのは大学からＸ以内(支持率ｓ，エントロピーゲインｇ)」
などのようなルールがそれぞれの組み合わせに対して列挙され、ユーザは自分の興味に従って、これらのルールをソートしたり、ファイリングしたりすることが可能となる。また、特に関心があるものについては、図１や図２に示したようにＧＵＩを用いて地図上にルールを表示することもできる。
【００４６】
【発明の効果】
以上説明したように、本発明によれば、予め距離や方位を定めた上で空間相関ルールを導き出すのではなく、多くの分析業務にて要求される、ある目的を最適化する距離自体、方位自体を求める空間データマイニングを提供することが可能となる。
【図面の簡単な説明】
【図１】本実施の形態におけるモデリング１として、距離最適化エンジンによる出力例を示した図である。
【図２】本実施の形態におけるモデリング２として、方位最適化エンジンによる出力例を示した図である。
【図３】本実施の形態における距離・方位最適化エンジンのアルゴリズムの概略を説明するためのフローチャートである。
【図４】データベース例を示した図である。
【図５】入力パラメータとして始点群や基準群の定義例を示した図である。
【図６】距離や方位の定義例を示した図である。
【図７】目的関数の定義例を示した図である。
【図８】逐次添加法による処理の流れを示した図である。
【図９】ボロノイ図の点位置決定法における処理の流れを示した図である。
【図１０】逐次添加法の前処理における処理の流れを示した図である。
【図１１】空間データマイニング装置としてのコンピュータ・システムの概略構成を説明するための図である。
【図１２】本実施の形態における空間データマイニングシステムの構成を説明するためのブロック図である。
【図１３】ボロノイ図作成部３１における始点添加順決定部３４の構成を説明するためのブロック図である。
【図１４】分割された平面ピクセルと作成された四分木を説明する図である。
【図１５】図１２に示したボロノイ図作成部３１のボロノイ図点追加部３５の構成を説明するためのブロック図である。
【符号の説明】
１１…地図、１２〜１４…始点(または始点群)、１５〜１７…円、１８〜２０…方位区間、３０…中間テーブル作成部、３１…ボロノイ図作成部、３２…距離計算部、３３…距離別計算部、３４…始点添加順決定部、３５…ボロノイ図点追加部、３９…最適距離計算部、４１…平面四分割機能、４２…始点分配機能、４３…代表点決定機能、４４…四分木作成機能、４５…添加順序決定機能、５１…高速点位置決定機能、５２…領域分割機能、５３…開始位置決定機能、５４…漸近機能、７１…ＣＰＵ、７２…メインメモリ、７３…フロッピーディスクドライブ(ＦＤＤ)、７４…ＣＤ−ＲＯＭドライブ、７５…ハードディスクドライブ(ＨＤＤ)、７６…表示装置、７７…入力装置、７８…バス

Claims

住所などの空間情報を含むデータベースの中から最適な距離を計算する空間データマイニング装置であって、
距離最適化に必要な目的関数を入力する入力手段と、
前記データベースにおける始点集合データおよび質問点集合データに基づいて始点と質問点との距離を計算して中間テーブルを生成する中間テーブル生成手段と、
前記中間テーブル生成手段によって生成された前記中間テーブルに基づいて前記入力手段により入力された前記目的関数の値を最適化する距離を計算する最適距離計算手段とを備えたことを特徴とする空間データマイニング装置。
前記中間テーブル生成手段は、
前記データベースにおける始点集合データからボロノイ図を作成するボロノイ図作成手段と、
前記ボロノイ図作成手段によって作成された前記ボロノイ図と前記データベースにおける質問点集合データとに基づいて各始点と各質問点との距離を計算してデータレコードを生成する距離計算手段と、
調べたい目的関数から最適化関数を選択して距離区間毎に最適値に必要なレコード値を前記データレコードから集計する距離別計算手段とを含むことを特徴とする請求項１記載の空間データマイニング装置。
前記ボロノイ図作成手段は、入力始点数に応じて平面四分割を繰り返し、前記入力始点数を末端の分割平面ピクセルに振り分けて各ピクセルの中にある始点の中から１つを当該ピクセルの代表点として選択し、各段ピクセルを中間ノードとする四分木を作成し、当該四分木の各ノードを広さ優先順に最上段から走査して順序付けされた始点集合を出力することを特徴とする請求項２記載の空間データマイニング装置。
住所などの空間情報を含むデータベースの中から最適な方位を計算する空間データマイニング装置であって、
方位最適化に必要な目的関数を入力する入力手段と、
前記データベースにおける始点集合データおよび質問点集合データに基づいて、始点から特定方向を０度とする角度を用いて質問点の位置する方位を含む中間テーブルを生成する中間テーブル生成手段と、
前記中間テーブル生成手段によって生成された前記中間テーブルに基づいて前記入力手段により入力された前記目的関数の値を最適化する方位を計算する最適方位計算手段とを備え、
前記中間テーブル生成手段は、
前記データベースにおける始点集合データからボロノイ図を作成するボロノイ図作成手段と、
前記ボロノイ図作成手段によって作成された前記ボロノイ図と前記データベースにおける質問点集合データとに基づいて各始点と各質問点との距離を計算する距離計算手段と、
前記距離計算手段により計算された距離の中から、指定された上限距離以内の質問点の前記始点からの方位を計算して前記中間テーブルのレコードとする方位計算手段と、
調べたい目的関数から最適化関数を選択して方位区間毎に最適値に必要なレコード値を前記レコードから集計する方位別計算手段とを含むことを特徴とする空間データマイニング装置。