(57)【要約】【課題】点の分布から過度に複雑な形状の領域が生成されるのを抑制する。【解決手段】記憶部１１は、探索対象領域における点の分布を示す分布データ１３と、探索対象領域を分割した複数の分割領域の位置を示す領域データ１４とを記憶する。処理部１２は、領域データ１４から、複数の分割領域の間の隣接関係を示す隣接行列１５を生成する。処理部１２は、探索対象領域のうち連続する２以上の分割領域の選択を示す変数１６と分布データ１３と隣接行列１５とを用いて、２以上の分割領域の選択を評価する評価関数１７を生成する。処理部１２は、現在の変数１６の値から評価関数１７の値の勾配を算出し、算出した勾配を用いて変数１６の値を更新する勾配法探索を実行する。処理部１２は、勾配法探索の結果に基づいて、２以上の分割領域の選択を決定する。【選択図】図１
2019192086.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
探索対象領域における点の分布を示す分布データと、前記探索対象領域を分割した複数の分割領域の位置を示す領域データとを取得し、
前記領域データから、前記複数の分割領域の間の隣接関係を示す隣接行列を生成し、
前記探索対象領域のうち連続する２以上の分割領域の選択を示す変数と前記分布データと前記隣接行列とを用いて、前記２以上の分割領域の選択を評価する評価関数を生成し、
現在の前記変数の値から前記評価関数の値の勾配を算出し、前記算出した勾配を用いて前記変数の値を更新する勾配法探索を実行し、
前記勾配法探索の結果に基づいて、前記２以上の分割領域の選択を決定する、
処理を実行させる領域生成プログラム。
【請求項２】
前記評価関数は、前記変数と前記分布データとを用いて、前記点の分布に対する前記２以上の分割領域のフィッティングを評価する第１の評価項目と、前記変数と前記隣接行列とを用いて、前記２以上の分割領域の形状を評価する第２の評価項目とを含む、
請求項１記載の領域生成プログラム。
【請求項３】
前記第２の評価項目は、前記２以上の分割領域が他の分割領域と接する辺が少ないほど、前記２以上の分割領域の形状を高く評価する、
請求項２記載の領域生成プログラム。
【請求項４】
前記勾配法探索は、前記第１の評価項目による評価と前記第２の評価項目による評価とを合成した評価値を最大化する前記変数の値を探索する、
請求項２記載の領域生成プログラム。
【請求項５】
前記隣接行列は、前記複数の分割領域の間の辺の共有関係を示す第１の隣接行列と、前記複数の分割領域の間の頂点の共有関係を示す第２の隣接行列とを含む、
請求項１記載の領域生成プログラム。
【請求項６】
探索対象領域における点の分布を示す分布データと、前記探索対象領域を分割した複数の分割領域の位置を示す領域データとを記憶する記憶部と、
前記領域データから、前記複数の分割領域の間の隣接関係を示す隣接行列を生成し、前記探索対象領域のうち連続する２以上の分割領域の選択を示す変数と前記分布データと前記隣接行列とを用いて、前記２以上の分割領域の選択を評価する評価関数を生成し、現在の前記変数の値から前記評価関数の値の勾配を算出し、前記算出した勾配を用いて前記変数の値を更新する勾配法探索を実行し、前記勾配法探索の結果に基づいて、前記２以上の分割領域の選択を決定する処理部と、
を有する領域生成装置。
【請求項７】
コンピュータが、
探索対象領域における点の分布を示す分布データと、前記探索対象領域を分割した複数の分割領域の位置を示す領域データとを取得し、
前記領域データから、前記複数の分割領域の間の隣接関係を示す隣接行列を生成し、
前記探索対象領域のうち連続する２以上の分割領域の選択を示す変数と前記分布データと前記隣接行列とを用いて、前記２以上の分割領域の選択を評価する評価関数を生成し、
現在の前記変数の値から前記評価関数の値の勾配を算出し、前記算出した勾配を用いて前記変数の値を更新する勾配法探索を実行し、
前記勾配法探索の結果に基づいて、前記２以上の分割領域の選択を決定する、
領域生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は領域生成プログラム、領域生成装置および領域生成方法に関する。
【背景技術】
【０００２】
ある種類の事象が発生した場所を示す点の分布から、当該種類の事象が他の領域よりも密集して発生している領域を抽出して可視化したいことがある。例えば、二次元平面である地図の中から特定の疾病の患者が多い地域を抽出することや、特定の種類の車両が多く走行している地域を抽出することなどが考えられる。
【０００３】
例えば、探索対象領域を均一サイズの正方形のメッシュに区切り、点が密集しているメッシュの集合として、２以上の矩形を水平方向に連結させた形状であるAdmissible Regionと呼ばれる１つの多角形を抽出する技術が提案されている。また、例えば、探索対象領域の中から、密集した点の集合を囲む１つの矩形を抽出する技術が提案されている。また、例えば、地図に記載された複数の行政区画の間の隣接関係を示すグラフを生成し、当該グラフから所定の大きさの円に収まる部分グラフを抽出し、抽出した部分グラフを網羅的に評価して連続する２以上の行政区画を抽出する技術が提案されている。また、例えば、点の分布に応じて探索対象領域を不均一サイズの正方形のメッシュに区切り、抽出不要なメッシュを順に除外していくことで、連続する２以上のメッシュによって構成される最適領域を１つ以上抽出する技術が提案されている。
【０００４】
なお、Ｗｅｂページを分析して人と人の繋がりを判定し、ソーシャルネットワーキンググラフを生成するマイニング装置が提案されている。また、複数次元の数値データによって区切られる単位領域の集合から、最大ゲインを有する単位領域の組み合わせを抽出する最適領域抽出装置が提案されている。また、正例クラスのサンプルと負例クラスのサンプルから、データのクラス分類を行うスコア関数を学習する分類装置が提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第２０１１／１４３１５４号
【特許文献２】国際公開第２０１３／０６１４６４号
【特許文献３】特開２０１３−１４８６８４号公報
【特許文献４】特開２０１７−１０２５４０号公報
【非特許文献】
【０００６】
【非特許文献１】Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita and Takeshi Tokuyama, "Data Mining Using Two-Dimensional Optimized Association Rules: Scheme, Algorithms, and Visualization", Proc. of the 1996 ACM SIGMOD International Conference on Management of Data, pp.13-23, 04 June 1996.
【非特許文献２】Rajeev Rastogi and Kyuseok Shim, "Mining Optimized Association Rules with Categorical and Numeric Attributes", IEEE Transactions on Knowledge and Data Engineering, Volume 14 Issue 1, pp.29-50, 07 August 2002.
【非特許文献３】Toshiro Tango and Kunihiko Takahashi, "A flexibly shaped spatial scan statistic for detecting clusters", International Journal of Health Geographics 2005, 18 May 2005.
【非特許文献４】Hiroya Inakoshi, Hiroaki Morikawa, Tatsuya Asai, Nobuhiro Yugami and Seishi Okamoto, "Discovery of Areas with Locally Maximal Confidence from Location Data", Proc. of the 19th International Conference on Database Systems for Advanced Applications (DASFAA), pp.47-61, 21 April 2014.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記の非特許文献１〜３のように抽出する領域の形状や大きさを所与の条件として厳格に制限すると、点の分布にマッチする適切な領域が抽出されないリスクがある。一方で、上記の非特許文献４のように抽出する領域の形状を制限しない場合、角の多過ぎる多角形など過度に複雑な形状の領域が抽出されてしまうことがある。この点、疾病の流行など現実の事象の広がりは円形や楕円形など緩やかな形状であることが多い。このため、過度に複雑な形状の領域は現実の事象を適切に表現しておらず不自然である。
【０００８】
１つの側面では、本発明は、過度に複雑な形状の領域が生成されるのを抑制する領域生成プログラム、領域生成装置および領域生成方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
１つの態様では、コンピュータに以下の処理を実行させる領域生成プログラムが提供される。探索対象領域における点の分布を示す分布データと、探索対象領域を分割した複数の分割領域の位置を示す領域データとを取得する。領域データから、複数の分割領域の間の隣接関係を示す隣接行列を生成する。探索対象領域のうち連続する２以上の分割領域の選択を示す変数と分布データと隣接行列とを用いて、２以上の分割領域の選択を評価する評価関数を生成する。現在の変数の値から評価関数の値の勾配を算出し、算出した勾配を用いて変数の値を更新する勾配法探索を実行する。勾配法探索の結果に基づいて、２以上の分割領域の選択を決定する。
【００１０】
また、１つの態様では、記憶部と処理部とを有する領域生成装置が提供される。また、１つの態様では、コンピュータが実行する領域生成方法が提供される。
【発明の効果】
【００１１】
１つの側面では、過度に複雑な形状の領域が生成されるのを抑制できる。
【図面の簡単な説明】
【００１２】
【図１】第１の実施の形態の領域生成装置の例を説明する図である。
【図２】情報処理装置のハードウェア例を示すブロック図である。
【図３】最適領域の第１の抽出例を示す図である。
【図４】最適領域の第２の抽出例を示す図である。
【図５】最適領域の第３の抽出例を示す図である。
【図６】メッシュおよびグラフの例を示す図である。
【図７】領域抽出とペナルティの関係例を示す図である。
【図８】隣接行列の例を示す図である。
【図９】他のメッシュ例を示す図である。
【図１０】他の隣接行列の例を示す図である。
【図１１】情報処理装置の機能例を示すブロック図である。
【図１２】入力データおよび出力データの例を示す図である。
【図１３】最適領域抽出の手順例を示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。
【００１４】
図１は、第１の実施の形態の領域生成装置の例を説明する図である。
第１の実施の形態の領域生成装置１０は、二次元平面である探索対象領域に点が不均一に分布している場合に、探索対象領域の中から点が密集している部分領域を抽出する。
【００１５】
探索対象領域は、例えば、国または行政区画の地図を示す。点は、例えば、特定の種類の事象が発生した位置を示す。特定の種類の事象としては、例えば、特定の疾病の患者が発見されたこと、特定の種類の車両が走行していること、特定のサービスの利用者が存在することなどが挙げられる。領域生成装置１０は、空間疫学、計量地理学、地球統計学、交通分析、気象分析、トポロジー、幾何学など様々な科学技術分野に利用できる。
【００１６】
領域生成装置１０は、コンピュータまたは情報処理装置と呼ばれることもある。領域生成装置１０は、ユーザが操作するクライアント装置でもよいし、ネットワークを介してクライアント装置などの他の装置と通信するサーバ装置でもよい。
【００１７】
領域生成装置１０は、記憶部１１および処理部１２を有する。記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性の半導体メモリでもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性ストレージでもよい。処理部１２は、例えば、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサである。ただし、処理部１２は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路を含んでもよい。プロセッサは、ＲＡＭなどのメモリ（記憶部１１でもよい）に記憶されたプログラムを実行する。プログラムには領域生成プログラムが含まれる。複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」と言うことがある。
【００１８】
記憶部１１は、分布データ１３および領域データ１４を記憶する。
分布データ１３は、探索対象領域（全体領域）における点の分布を示す。分布データ１３は、以下に説明する分割領域毎に当該分割領域に属する点の数をカウントしたものであってもよい。分布データ１３は、基準群の分布と、基準群の部分集合であって特定の事象に当てはまる観測群の分布とを示してもよい。分布データ１３は、分割領域毎に基準群に属する点の数（支持度）と観測群に属する点の数（ヒット数）とをカウントしたものであってもよい。例えば、人口分布が基準群の分布に相当し、特定の疾病の患者の分布や特定のサービスの利用者の分布などが観測群の分布に相当する。
【００１９】
領域データ１４は、探索対象領域を分割して生成された複数の分割領域の位置を示す。複数の分割領域は、好ましくはそれぞれ矩形領域である。複数の分割領域は、均一サイズのメッシュでもよいし不均一サイズのメッシュでもよい。また、複数の分割領域は、包含する点の数が概ね均一になるように生成されてもよい。例えば、各分割領域に属する点の数が所定範囲に収まるように、探索対象領域が階層的に分割される。この場合、探索対象領域の中の点が多い場所は細分化され、点が少ない場所は細分化されない。探索対象領域の分割は、領域生成装置１０が行ってもよいし他の装置が行ってもよい。
【００２０】
処理部１２は、領域データ１４から、複数の分割領域の間の隣接関係を示す隣接行列１５を生成する。隣接行列１５は、例えば、矩形である２つの分割領域が辺を共有しているか否かの隣接関係を示す。ただし、隣接行列１５は、矩形である２つの分割領域が頂点を共有しているかの隣接関係を示すものであってもよい。また、処理部１２は、探索対象領域の中から連続する２以上の分割領域を選択する選択状況を示す変数１６を定義する。例えば、処理部１２は、各分割領域に対して当該分割領域の選択状況を示す個別変数を割り当て、複数の個別変数のベクトルを変数１６として定義する。連続する２以上の分割領域は、各分割領域が他の全ての分割領域と直接的または間接的に繋がっている分割領域の集合であり、グラフ理論における連結部分グラフとして表現することができる。
【００２１】
処理部１２は、分布データ１３（ｈ）と隣接行列１５（Ｗ）と変数１６（ｚ）を用いて評価関数１７を生成する。評価関数１７は、変数１６が示す分割領域の選択を評価した評価値を算出する関数であり、目的関数と言うこともできる。評価関数１７は、第１の評価項目と第２の評価項目を含んでもよく、評価関数１７が算出する評価値は、第１の評価項目による評価と第２の評価項目による評価とを合成したものであってもよい。
【００２２】
第１の評価項目は、例えば、分布データ１３と変数１６を用いて、選択した２以上の分割領域が点の分布にフィットしているか否かを評価する評価項目である。第１の評価項目をスコア関数と言うこともできる。第２の評価項目は、例えば、隣接行列１５と変数１６を用いて、選択した２以上の分割領域の形状（外形）を評価する評価項目である。第２の評価項目を正則化項と言うこともできる。第２の評価項目は、例えば、選択した２以上の分割領域の形状が複雑であるほど、当該２以上の分割領域の選択を低く評価する。第２の評価項目は、選択した２以上の分割領域が他の分割領域と共有する辺をカウントするものであってもよい。その場合、共有する辺が少ないほど評価が高くなる。共有する辺の数は、変数１６の値と隣接行列１５を用いて算出することが可能である。
【００２３】
処理部１２は、評価関数１７に従って、変数１６の最適な値を勾配法探索によって探索する。処理部１２は、変数１６の初期値を設定し、現在の変数１６の値から評価関数１７の勾配を算出し、算出した勾配を用いて変数１６の値を更新する。処理部１２は、勾配の算出と変数１６の値の更新を繰り返す。勾配法探索では、例えば、変数１６の値の微細変化に対する評価関数１７の評価値の変化量（傾き）が最大になる方向に、変数１６を更新していく。処理部１２は、評価関数１７を最大化する変数１６の値を探索する。
【００２４】
そして、処理部１２は、勾配法探索の結果、すなわち、勾配法探索によって決定された変数１６の値に基づいて、探索対象領域からの連続する２以上の分割領域の選択を決定する。決定した分割領域を最適領域と言うことがある。決定した分割領域は、探索対象領域の中で点が密集している場所であり、特定の種類の事象が他の分割領域よりも密集して発生していることを示している。処理部１２は、決定した分割領域を示す情報を、領域生成装置１０に接続されたディスプレイに表示してもよい。例えば、処理部１２は、決定した分割領域を囲む多角形を、地図などの探索対象領域上に表示する。また、処理部１２は、決定した分割領域を示す情報を、領域生成装置１０が有する記憶装置に書き込んでもよいし、ネットワークを介して他の装置に送信してもよい。
【００２５】
第１の実施の形態の領域生成装置１０によれば、点が不均一に分布している探索対象領域の中から、点が密集している一繋がりの分割領域が抽出されて可視化される。よって、空間疫学や交通分析など事象の発生状況の分析が容易となる。また、評価関数１７を用いて分割領域の選択が評価され、抽出する分割領域の形状やサイズを事前に厳密に制限しなくてもよい。よって、入力された点の分布に対するフィッティングの精度が向上する。また、評価関数１７に、隣接行列１５を用いて分割領域の形状を評価する正則化項が追加される。よって、抽出する分割領域の形状が過度に複雑になる（凹凸が多くなる）ことを抑制でき、事象の発生状況を適切に表現した自然な形状の分割領域を抽出することができる。また、勾配法により最適解が探索され、様々な分割領域の組み合わせを網羅的に評価しなくてもよく、計算量を削減することができる。
【００２６】
［第２の実施の形態］
次に、第２の実施の形態を説明する。
第２の実施の形態の情報処理装置は、点が不均一に分布する二次元平面から、特定の種類の点が密集している最適領域を抽出して可視化する。この情報処理装置は、空間疫学、計量地理学、地球統計学、交通分析、気象分析、トポロジー、幾何学など様々な科学技術分野に利用できる。情報処理装置は、ユーザが操作するクライアント装置でもよいし、ネットワークを介してクライアント装置などの他の装置と通信するサーバ装置でもよい。
【００２７】
図２は、情報処理装置のハードウェア例を示すブロック図である。
情報処理装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７を有する。上記ユニットはバスに接続されている。情報処理装置１００は、第１の実施の形態の領域生成装置１０に対応する。ＣＰＵ１０１は、第１の実施の形態の処理部１２に対応する。ＲＡＭ１０２またはＨＤＤ１０３は、第１の実施の形態の記憶部１１に対応する。
【００２８】
ＣＰＵ１０１は、プログラムの命令を実行するプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されたプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、情報処理装置１００は複数のプロセッサを備えてもよい。複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」と言うことがある。
【００２９】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムやＣＰＵ１０１が演算に使用するデータを一時的に記憶する揮発性の半導体メモリである。なお、情報処理装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数のメモリを備えてもよい。
【００３０】
ＨＤＤ１０３は、ＯＳ（Operating System）やミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性の記憶装置である。なお、情報処理装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）など他の種類の記憶装置を備えてもよく、複数の記憶装置を備えてもよい。
【００３１】
画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、情報処理装置１００に接続されたディスプレイ１０４ａに画像を出力する。ディスプレイ１０４ａとしては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなど、任意の種類のディスプレイを使用できる。
【００３２】
入力信号処理部１０５は、情報処理装置１００に接続された入力デバイス１０５ａから入力信号を受信する。入力デバイス１０５ａとして、マウス、タッチパネル、タッチパッド、キーボードなど、任意の種類の入力デバイスを使用できる。また、情報処理装置１００に複数の種類の入力デバイスが接続されてもよい。
【００３３】
媒体リーダ１０６は、記録媒体１０６ａに記録されたプログラムやデータを読み取る読み取り装置である。記録媒体１０６ａとして、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。媒体リーダ１０６は、例えば、記録媒体１０６ａから読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００３４】
通信インタフェース１０７は、ネットワーク１０７ａに接続され、ネットワーク１０７ａを介して他の情報処理装置と通信を行うインタフェースである。通信インタフェース１０７は、スイッチやルータなどの有線通信装置に接続される有線通信インタフェースでもよいし、基地局やアクセスポイントに接続される無線通信インタフェースでもよい。
【００３５】
次に、二次元平面から最適領域を抽出するアルゴリズムについて検討する。二次元平面には、母集合である基準群に属する点が配置される。基準群は、特定の事象に対応する点の集合である観測群とそれ以外の点の集合とに分類される。第２の実施の形態で参照する図面においては、観測群に属する点を黒点で表すことがあり、観測群に属さない点を白点で表すことがある。黒点は、特定の疾病の患者が存在する場所や特定のサービスの利用者が存在する場所など、特定の事象が発生した場所を示す。白点は、特定の疾病の患者が存在しない場所や特定のサービスの利用者が存在しない場所など、特定の事象が発生しなかった場所を示す。白点は人口に比例する密度で配置してもよい。基準群に属する点の数を支持度と言うことがあり、観測群に属する点の数をヒット数と言うことがある。
【００３６】
情報処理装置１００は、二次元平面から観測群に属する点（黒点）が密集している領域を最適領域として抽出する。このとき、基準群に対する観測群の割合が高い領域を抽出することが好ましい。ただし、抽出する領域の面積は小さ過ぎないことが好ましく、抽出する領域に含まれる基準群の点は少な過ぎないことが好ましい。これにより、二次元平面の中から特徴的な領域を抽出することができる。
【００３７】
図３は、最適領域の第１の抽出例を示す図である。
可視化画面３１は、二次元平面上に点の分布と最適領域を表示した画面である。可視化画面３１は、前述の非特許文献２のアルゴリズムに従って判定される最適領域を示している。非特許文献２のアルゴリズムは、最適領域の形状を矩形に制限するものである。また、可視化画面３１は、ある位置を中心にして円状に（等方的に）黒点が分布するクラスタと、そこから少し離れて別の位置を中心にして円状に黒点が分布する別のクラスタを示している。可視化画面３１に示すように、各クラスタの黒点の分布が等方的であれば、非特許文献２のアルゴリズムは比較的良好に最適領域を抽出することができると期待される。
【００３８】
可視化画面３２は、二次元平面上に点の分布と最適領域を表示した画面である。可視化画面３２は、前述の非特許文献１のアルゴリズムに従って判定される最適領域を示している。非特許文献１のアルゴリズムは、２以上の矩形を水平方向に連結させた形状であるAdmissible Regionと呼ばれる多角形を抽出するものである。また、可視化画面３２は、可視化画面３１と同じ分布を示している。可視化画面３２に示すように、複数のクラスタが存在する場合、非特許文献１のアルゴリズムはそれら複数のクラスタを連結したAdmissible Regionを抽出することがあり、最適領域の精度が低下し得る。
【００３９】
図４は、最適領域の第２の抽出例を示す図である。
可視化画面３３は、二次元平面上に点の分布と最適領域を表示した画面である。可視化画面３３は、前述の非特許文献２のアルゴリズムに従って判定される最適領域を示している。また、可視化画面３３は、楕円状に（非等方的に）黒点が分布するクラスタと、そこから少し離れて楕円状に黒点が分布する別のクラスタを示している。可視化画面３３に示すように、各クラスタの黒点の分布が等方的でない場合、非特許文献２のアルゴリズムは黒点を適切にカバーする最適領域を抽出することが難しい。
【００４０】
可視化画面３４は、二次元平面上に点の分布と最適領域を表示した画面である。可視化画面３４は、前述の非特許文献４のアルゴリズムに従って判定される最適領域を示している。また、可視化画面３４は、可視化画面３３と同じ分布を示している。可視化画面３４に示すように、各クラスタの黒点の分布が等方的でない場合であっても、非特許文献４のアルゴリズムは最適領域から漏れる黒点を減らすことができる。
【００４１】
図５は、最適領域の第３の抽出例を示す図である。
可視化画面３５は、二次元平面上に点の分布と最適領域を表示した画面である。可視化画面３５は、前述の非特許文献４のアルゴリズムに従って判定される最適領域を示している。非特許文献４のアルゴリズムは、最適領域の形状として任意の多角形を許容するものである。また、可視化画面３５は、等方的に黒点が分布する１つのクラスタを示している。ただし、黒点に相当する事象は確率的に発生するものであるため、クラスタが正確に円を形成しているわけではない。円の中心から離れた位置に低い確率で黒点が配置されることがあり、また、円の中心付近に白点が配置されることもある。可視化画面３５に示すように、クラスタが正確に円を形成していない場合、非特許文献４のアルゴリズムは凹凸の多い過度に複雑な多角形の最適領域を抽出することがある。
【００４２】
このように、抽出する最適領域を矩形に限定するなど最適領域の形状を予め厳しく制限すると、点の分布に対するフィッティングの精度が低下することがある。一方、最適領域の形状を制限せず形状の自由度を大きくすると、過度に複雑な多角形の最適領域が抽出されることがある。抽出する最適領域が複雑化することは、機械学習における過学習に相当すると言える。過度に複雑な形状の最適領域は、特定の事象の分布という特性を適切に表しているとは言えず好ましくない。最適領域の抽出においても、モデルの複雑さを低減する正則化が行われることが好ましい。そこで、情報処理装置１００は、フィッティング精度の向上と形状の複雑さの低減の両方を考慮して最適領域を探索する。
【００４３】
可視化画面３６は、二次元平面上に点の分布と最適領域を表示した画面である。可視化画面３６は、後述する第２の実施の形態のアルゴリズムに従って判定される最適領域を示している。また、可視化画面３６は、可視化画面３５と同じ分布を示している。可視化画面３６に示すように、クラスタが正確に円を形成していない場合であっても、第２の実施の形態のアルゴリズムは複雑さの低減された最適領域を抽出する。可視化画面３５の最適領域は２０個の頂点をもつのに対し、可視化画面３６の最適領域は６個の頂点をもつ。
【００４４】
次に、情報処理装置１００が最適領域を抽出するアルゴリズムを説明する。
図６は、メッシュおよびグラフの例を示す図である。
まず、メッシュおよびグラフの意味を説明する。探索対象領域である二次元平面は、メッシュと呼ばれる分割領域に排他的かつ網羅的に細分化される。二次元平面上の任意の位置は、何れか１つのメッシュにのみ属している。全メッシュ４１は、探索対象領域に含まれる全てのメッシュの集合である。各メッシュは正方形などの矩形である。全メッシュ４１に含まれるメッシュのサイズは均一でなくてもよい。例えば、情報処理装置１００は、メッシュ毎の基準群の点（白点および黒点）の数が概ね均一になるように、二次元平面を段階的に四分割して矩形のメッシュを生成する。
【００４５】
全メッシュ４１におけるメッシュの隣接関係は、隣接グラフ４２として表現することができる。隣接グラフ４２は、複数のノードおよび複数のエッジを含む。隣接グラフ４２の１つのノードは、全メッシュ４１の１つのメッシュに対応する。あるノードと別のノードとの間に張られたエッジは、あるノードに対応するメッシュと別のノードに対応する別のメッシュとが全メッシュ４１において隣接していることを示す。ここで言う「隣接している」とは、２つのメッシュが辺を共有していることである。第２の実施の形態の最適領域の探索では、全メッシュ４１と隣接グラフ４２とは等価である。
【００４６】
全メッシュ４１から単一のメッシュまたは連続する２以上のメッシュを抽出すると、閉領域４３が得られる。閉領域４３を隣接閉包と言うことがある。閉領域４３では、隣接関係を辿ることで１つのメッシュから他の全てのメッシュに到達することができる。閉領域４３には、分断されたメッシュや孤立したメッシュは存在しない。
【００４７】
閉領域４３におけるメッシュの隣接関係は、連結部分グラフ４４として表現することができる。連結部分グラフ４４は、隣接グラフ４２の部分グラフであり連結グラフである。連結部分グラフ４４では、エッジを辿ることで１つのノードから他の全てのノードに到達することができる。連結部分グラフ４４には、分断されたノードや孤立したノードは存在しない。連結部分グラフ４４の１つのノードは、閉領域４３の１つのメッシュに対応する。最適領域の探索では、閉領域４３と連結部分グラフ４４とは等価である。
【００４８】
例えば、全メッシュ４１は、メッシュｖ１〜ｖ９の９個のメッシュを含む。メッシュｖ１〜ｖ９は、均一サイズの正方形であり格子状に並んでいる。隣接グラフ４２は、メッシュｖ１〜ｖ９に対応する９個のノードと、これら９個のノードを格子状に結合した１２個のエッジとを含む。閉領域４３は、全メッシュ４１の中から選択されたメッシュｖ１，ｖ２，ｖ４を含む。メッシュｖ１とメッシュｖ２とが隣接し、メッシュｖ１とメッシュｖ４とが隣接し、メッシュｖ２とメッシュｖ４とは隣接していない。連結部分グラフ４４は、メッシュｖ１，ｖ２，ｖ４に対応する３個のノードと２個のエッジを含む。
【００４９】
図７は、領域抽出とペナルティの関係例を示す図である。
第２の実施の形態の情報処理装置１００は、最適領域に含めるメッシュの選択を評価する目的関数を生成し、目的関数の値を最大化するメッシュの組み合わせを探索する。このとき、情報処理装置１００は、閉領域の形状が複雑であるほど目的関数の値を小さくするペナルティを定義し、ペナルティを示す正則化項を目的関数に挿入する。正則化項としては、閉領域が隣接のメッシュと接している辺の数を用いることが考えられる。
【００５０】
全メッシュ５１は、メッシュｖ１〜ｖ１０の１０個のメッシュを含む。ここで、全メッシュ５１のうちメッシュｖ１，ｖ３，ｖ５，ｖ８，ｖ９，ｖ１０を選択したとする。この場合、閉領域が隣接のメッシュと接している辺の数は８個である。この辺の数は、全メッシュ５１に対応する隣接グラフ５２からメッシュｖ１，ｖ３，ｖ５，ｖ８，ｖ９，ｖ１０に対応するノードを切り離す際に切断されるエッジの数に相当する。
【００５１】
これに対して、全メッシュ５３は、全メッシュ５１と同じメッシュを含む。ここで、全メッシュ５３のうちメッシュｖ１，ｖ５，ｖ８，ｖ９，ｖ１０を選択したとする。この場合、閉領域が隣接のメッシュと接している辺の数は９個である。この辺の数は、全メッシュ５３に対応する隣接グラフ５４からメッシュｖ１，ｖ５，ｖ８，ｖ９，ｖ１０に対応するノードを切り離す際に切断されるエッジの数に相当する。
【００５２】
よって、メッシュｖ１，ｖ５，ｖ８，ｖ９，ｖ１０を選択する方が、メッシュｖ１，ｖ３，ｖ５，ｖ８，ｖ９，ｖ１０を選択するよりもペナルティが大きくなる。ペナルティは目的関数の値を減少させる効果があるため、最適領域としてメッシュｖ１，ｖ５，ｖ８，ｖ９，ｖ１０の組み合わせが選択されにくくなる。このように、目的関数に正則化項を追加することで、抽出される最適領域の複雑さを低減できる。
【００５３】
ここで、複数のメッシュそれぞれが最適領域に含まれるか否かを示す変数をベクトルｚとし、メッシュ間の隣接関係を示す行列を隣接行列Ｗとする。ベクトルｚの長さはメッシュ数に相当する。あるメッシュに対応するベクトルｚの要素が０であることは、当該メッシュが最適領域に含まれないことを示す。あるメッシュに対応するベクトルｚの要素が１であることは、当該メッシュが最適領域に含まれることを示す。隣接行列Ｗは、一辺の長さがメッシュ数に相当する正方行列である。隣接行列Ｗは、２つのメッシュが辺を共有しているか否かという隣接関係を示す。２つのメッシュの組に対応する隣接行列Ｗの要素が０であることは、当該２つのメッシュが辺を共有しておらず隣接していないことを示す。２つのメッシュの組に対応する隣接行列Ｗの要素が１であることは、当該２つのメッシュが辺を共有しており隣接していることを示す。
【００５４】
図８は、隣接行列の例を示す図である。
隣接行列１３１は、図７の全メッシュ５１，５３におけるメッシュｖ１〜ｖ１０の隣接関係を示す隣接行列Ｗである。隣接行列１３１は、図７の隣接グラフ５２，５４におけるノードの接続関係を示していると言うこともできる。辺の共有を示す隣接関係はメッシュ間で対称であるため、隣接行列Ｗは対称行列である。この場合、閉領域が他のメッシュと接する辺の数を示すペナルティは、（１−ｚ）ＴＷｚという行列積によって算出できる。目的関数に挿入する正則化項は、ペナルティが大きいほど目的関数の値が小さくなるように−λ（１−ｚ）ＴＷｚと定義される。λは所定の係数である。
【００５５】
次に、目的関数の数学的定義および目的関数を最大化する解の探索方法を説明する。
まず、正則化項を含まないスコア関数を定義する。スコア関数は、選択したメッシュの組み合わせが黒点の分布にフィットする精度を評価する。スコア関数の値が大きいほど、選択したメッシュの組み合わせが黒点の分布に精度よくフィットしていることを示す。スコア関数は、数式（１）のように密度ないし確信度として定義することができる。
【００５６】
ここで、二次元平面にメッシュｖ１，ｖ２，…，ｖｎのｎ個のメッシュが含まれており、メッシュｖｉ（ｉ＝１，２，…，ｎ）に対してヒット数ｈｉと支持度ｓｉが与えられているとする。ヒット数ｈｉは、メッシュｖｉに含まれる観測群の点（黒点）の数である。支持度ｓｉは、メッシュｖｉに含まれる基準群の点（白点および黒点）の数である。数式（２）に示すように、ｎ個のメッシュに対応するｎ個のヒット数を列挙したベクトルがベクトルｈである。ｎ個のメッシュに対応するｎ個の支持度を列挙したベクトルがベクトルｓである。また、メッシュｖｉに対して変数ｘｉが定義される。ｎ個のメッシュに対応するｎ個の変数を列挙したベクトルがベクトルｘである。
【００５７】
変数ｘｉはメッシュｖｉが最適領域に含まれるか否かを示す。ただし，勾配法を使うために数式（３）のようにシグモイド関数として定義し、０と１の間の値をとる。変数ｚｉは、メッシュｖｉに対して定義された変数であり、実数全体（マイナス無限大からプラス無限大まで）の値をとる。これにより、スコア関数が変数ｚｉに対して微分可能になる。数式（３）のシグモイド関数を変数ｚｉで微分すると、数式（４）のようになる。
【００５８】
数式（１）のスコア関数は、ベクトルｈとベクトルｘの内積を、ベクトルｓとベクトルｘの内積で割った値を算出する。このスコア関数は、ベクトルｘの値に応じたヒット数の重み付き和を、ベクトルｘの値に応じた支持数の重み付き和で割った値を算出している。よって、このスコア関数は、黒点の密度を評価していると言える。
【００５９】
【数１】
2019192086.tif 000003
【００６０】
【数２】
2019192086.tif 000004
【００６１】
【数３】
2019192086.tif 000005
【００６２】
【数４】
2019192086.tif 000006
【００６３】
次に、スコア関数に正則化項を追加した目的関数を定義する。この目的関数は、選択したメッシュの組み合わせを、黒点のフィッティング精度と形状の複雑さの両方の観点から総合的に評価するものである。目的関数の値が大きいほど、選択したメッシュの組み合わせが好ましいことを示す。目的関数ｆは、数式（５）のようにスコア関数と正則化項の和として定義することができる。正則化項は、前述のように、選択したメッシュによって形成される閉領域が他のメッシュと接している辺の数に基づいている。ただし、ここでは正則化項は、ベクトルｘを用いて−λ（１−ｘ）ＴＷｘと定義される。
【００６４】
【数５】
2019192086.tif 000007
【００６５】
これにより、最適領域を探索することを、目的関数ｆの値を最大にする変数ｚｉ（ｉ＝１，２，…，ｎ）の値を求める最適化問題に置き換えることができる。第２の実施の形態の情報処理装置１００は、この最適化問題を勾配法によって解くこととする。
【００６６】
情報処理装置１００は、変数ｚｉ（ｉ＝１，２，…，ｎ）を列挙したベクトルｚの初期値ｚ（０）を設定する。ベクトルｚ（０）の各要素は、実数の範囲からランダムに選択してもよいし所定の値としてもよい。ここでは、ｔステップ目（ｔ＝０，１，…）におけるベクトルｚの値をｚ（ｔ）と表記する。情報処理装置１００は、数式（６）のように、現在のベクトルｚの値ｚ（ｔ）から目的関数ｆの勾配∇ｆを算出し、勾配∇ｆと所定の係数ηの積を用いてベクトルｚを更新してｚ（ｔ＋１）を求める。情報処理装置１００は、勾配∇ｆの算出とベクトルｚの更新を、ベクトルｚが収束するまで繰り返す。
【００６７】
勾配∇ｆは、数式（７）のように、目的関数ｆを変数ｚｉで偏微分したものを列挙したベクトルである。上記の目的関数ｆの定義から、目的関数ｆは変数ｚｉについて微分可能である。目的関数ｆを変数ｚｉで偏微分することは、目的関数ｆを変数ｘｉで偏微分し、シグモイド関数である変数ｘｉを変数ｚｉで微分し、両者の積を求めることと等価である。よって、目的関数ｆの変数ｚｉによる偏微分は、数式（８）のように算出される。ただし、ωｉは隣接行列Ｗのｉ番目の列ベクトルである。
【００６８】
ベクトルｚが収束すると、情報処理装置１００は、実数であるベクトルｚの各要素を二値化して、ベクトルｚをビットベクトルに変換する。情報処理装置１００は、ｚｉ＞０ならｚｉ＝１に変換し、ｚｉ≦０ならｚｉ＝０に変換する。ビットベクトルとしてのベクトルｚは、最適領域を示している。ｚｉ＝１は、メッシュｖｉが最適領域に含まれることを示す。ｚｉ＝０は、メッシュｖｉが最適領域に含まれないことを示す。
【００６９】
【数６】
2019192086.tif 000008
【００７０】
【数７】
2019192086.tif 000009
【００７１】
【数８】
2019192086.tif 000010
【００７２】
なお、数式（１）では確信度を算出するスコア関数を示したが、数式（５）に用いるスコア関数は微分可能であればよく、他のスコア関数を用いることもできる。例えば、数式（９）のように、対数尤度比の符号を反転させたものをスコア関数として用いることができる。また、数式（１０）のように、相違度（Bichromatic Discrepancy）の符号を反転させたものをスコア関数として用いることができる。数式（９）および数式（１０）におけるｍＲ，ｂＲは数式（１１）のように定義される。ここで、「１」はすべての要素が１であるｎ次元列ベクトルである。数式（１０）におけるα，β，γは所定の係数である。黒点の分布に対する最適領域のフィッティングの精度が高いほど、対数尤度比や相違度は小さくなるため、符号を反転させたものを目的関数ｆに使用する。
【００７３】
【数９】
2019192086.tif 000011
【００７４】
【数１０】
2019192086.tif 000012
【００７５】
【数１１】
2019192086.tif 000013
【００７６】
ところで、上記の数式（５）では正則化項を−λ（１−ｘ）ＴＷｘと定義したが、閉領域が他のメッシュと接している辺の数をカウントするという観点から、数式（５）よりも一層正確にペナルティを算出することができる正則化項が考えられる。以下、他の正則化項の例について説明する。まず、他の正則化項の説明に使用する全メッシュの例を挙げ、他の正則化項に使用する隣接行列Ｗ，Ｕ，Ｑについて説明する。
【００７７】
図９は、他のメッシュ例を示す図である。
全メッシュ６１は、メッシュｖ０〜ｖ１２の１３個のメッシュを含む。メッシュｖ０は中央に配置された大きな正方形であり、メッシュｖ１〜ｖ１２はメッシュｖ０の周囲に配置された小さな正方形である。メッシュｖ０の右辺とメッシュｖ２，ｖ３の左辺が接している。メッシュｖ０の下辺とメッシュｖ５，ｖ６の上辺が接している。メッシュｖ０の左辺とメッシュｖ８，ｖ９の右辺が接している。メッシュｖ０の上辺とメッシュｖ１１，ｖ１２の下辺が接している。メッシュｖ０とメッシュｖ１，ｖ４，ｖ７，ｖ１０は辺を共有していない。ただし、メッシュｖ０の右上の頂点とメッシュｖ１の左下の頂点が接している。メッシュｖ０の右下の頂点とメッシュｖ４の左上の頂点が接している。メッシュｖ０の左下の頂点とメッシュｖ７の右上の頂点が接している。メッシュｖ０の左上の頂点とメッシュｖ１０の右下の頂点が接している。以下では、情報処理装置１００が閉領域としてメッシュｖ０を選択しメッシュｖ１〜ｖ１２を選択しない場合を考える。
【００７８】
図１０は、他の隣接行列の例を示す図である。
情報処理装置１００は、全メッシュから隣接行列Ｗ，Ｕ，Ｑを生成する。
隣接行列１３２は、前述のように、あるメッシュが別のメッシュと辺を共有する隣接関係を示す隣接行列Ｗである。隣接行列Ｗは対称行列である。２つのメッシュに対応する隣接行列Ｗの要素が１であることは、２つのメッシュが辺を共有することを示す。２つのメッシュに対応する隣接行列Ｗの要素が０であることは、２つのメッシュが辺を共有しないことを示す。図９の全メッシュ６１では、メッシュｖ０から見てメッシュｖ２，ｖ３，ｖ５，ｖ６，ｖ８，ｖ９，ｖ１１，ｖ１２との間に隣接行列Ｗの隣接関係がある。
【００７９】
隣接行列１３３は、あるメッシュの頂点が別のメッシュの頂点と接するか、または、あるメッシュの頂点が別のメッシュの辺の途中（頂点以外の位置）と接する隣接関係を示す隣接行列Ｕである。ただし、２つのメッシュが辺を共有している場合に当該共有する辺の端点である頂点については、隣接行列Ｕの隣接関係から除外する。隣接行列Ｕは対称行列でないこともある。隣接行列Ｕの要素は、上記に該当する頂点の数であり０以上の整数である。あるメッシュと別のメッシュに対応する隣接行列Ｕの要素が１以上であることは、当該あるメッシュが当該別のメッシュとの間で上記条件を満たす頂点を１以上もつことを示す。あるメッシュと別のメッシュに対応する隣接行列Ｕの要素が０であることは、当該あるメッシュが当該別のメッシュとの間で上記条件を満たす頂点をもたないことを示す。
【００８０】
図９の全メッシュ６１では、メッシュｖ０から見てメッシュｖ１，ｖ４，ｖ７，ｖ１０との間で隣接行列Ｕの隣接関係がある。メッシュｖ０はメッシュｖ２，ｖ３，ｖ５，ｖ６，ｖ８，ｖ９，ｖ１１，ｖ１２と辺を共有しており、これらメッシュとの間に隣接行列Ｕの隣接関係はない。また、メッシュｖ１から見てメッシュｖ０との間で隣接行列Ｕの隣接関係をもつ。メッシュｖ１はメッシュｖ２，ｖ１２と辺を共有しており、これらメッシュとの間に隣接行列Ｕの隣接関係はない。また、メッシュｖ２から見てメッシュｖ０，ｖ１２との間で隣接行列Ｕの隣接関係をもつ。メッシュｖ２がメッシュｖ０と隣接行列Ｕの隣接関係をもつのは、メッシュｖ２の左下の頂点がメッシュｖ０の右辺の途中に位置し、その位置がメッシュｖ０にとって頂点ではないためである。
【００８１】
以下同様に、メッシュｖ３から見てメッシュｖ０，ｖ５との間で隣接行列Ｕの隣接関係をもつ。メッシュｖ４から見てメッシュｖ０との間で隣接行列Ｕの隣接関係をもつ。メッシュｖ５から見てメッシュｖ０，ｖ３との間で隣接行列Ｕの隣接関係をもつ。メッシュｖ６から見てメッシュｖ０，ｖ８との間で隣接行列Ｕの隣接関係をもつ。メッシュｖ７から見てメッシュｖ０との間で隣接行列Ｕの隣接関係をもつ。
【００８２】
メッシュｖ８から見てメッシュｖ０，ｖ６との間で隣接行列Ｕの隣接関係をもつ。メッシュｖ９から見てメッシュｖ０，ｖ１１との間で隣接行列Ｕの隣接関係をもつ。メッシュｖ１０から見てメッシュｖ０との間で隣接行列Ｕの隣接関係をもつ。メッシュｖ１１から見てメッシュｖ０，ｖ９との間で隣接行列Ｕの隣接関係をもつ。メッシュｖ１２から見てメッシュｖ０，ｖ２との間で隣接行列Ｕの隣接関係をもつ。
【００８３】
隣接行列１３４は、あるメッシュの頂点が別のメッシュの頂点と接する隣接関係を示す隣接行列Ｑである。ただし、２つのメッシュが辺を共有している場合に当該共有する辺の端点である頂点については、隣接行列Ｑの隣接関係から除外する。隣接行列Ｑにおける非ゼロ要素の集合は、隣接行列Ｕの非ゼロ要素の集合のサブセットである。隣接行列Ｑは対称行列である。図９の全メッシュ６１では、メッシュｖ０とメッシュｖ１，ｖ４，ｖ７，ｖ１０との間に隣接行列Ｑの隣接関係がある。また、メッシュｖ２とメッシュｖ１２との間、メッシュｖ３とメッシュｖ５の間、メッシュｖ６とメッシュｖ８の間、メッシュｖ９とメッシュｖ１１の間に隣接行列Ｑの隣接関係がある。
【００８４】
閉領域が周辺のメッシュと接している辺の数は次のように計算することができる。閉領域外のメッシュ（外部メッシュ）から閉領域内のメッシュ（内部メッシュ）への隣接行列Ｗによる接続数はｗ＝ｘＴＷ（１−ｘ）である。（２）内部メッシュから外部メッシュへの隣接行列Ｕによる接続数はｕ＝（１−ｘ）ＴＵｘである。（３）内部メッシュから別の内部メッシュへの隣接行列Ｑによる接続数はｑ＝ｘＴＱｘである。閉領域が周辺のメッシュと接している辺の数は、２ｗ−ｕ−ｑであり、数式（１２）のように算出することができる。数式（１２）のスコア関数には数式（１）、（９）、（１０）などを使用できる。
【００８５】
数式（１２）の背景となる考え方は以下の通りである。図９の全メッシュ６１では、メッシュｖ０は４つの辺をもっているのに対してｗ＝８と算出される。これを補正するため、多角形においては頂点の数と辺の数が一致することに着目し、頂点の数をカウントすることとする。このとき、隣接行列Ｕによるメッシュｖ２からメッシュｖ０の隣接とメッシュｖ３からメッシュｖ０の隣接の２つを使って、隣接行列Ｗによるメッシュｖ０からメッシュｖ２への隣接とメッシュｖ０からメッシュｖ３への隣接のうちの１つを相殺する。これが２ｗ−ｕに相当する。全メッシュ６１では２ｗ−ｕ＝４であり辺の数と一致する。
【００８６】
ただし、閉領域の内部に空洞があるような複雑な閉領域に対しては、内部メッシュ間の隣接によって２ｗ−ｕが実際の辺の数より大きくなってしまうことがある。そこで、内部メッシュ間の隣接を消去した値が２ｗ−ｕ−ｑとなる。
【００８７】
【数１２】
2019192086.tif 000014
【００８８】
次に、隣接行列Ｗ，Ｕ，Ｑの隣接関係の判定方法について説明する。ここでは、二次元平面の左下が原点であり、原点から右方向がＸ軸、原点から上方向がＹ軸であるとする。
情報処理装置１００は、二次元平面をメッシュに細分化した後、Ｘ座標を第１ソートキーとしＹ座標を第２ソートキーとして二次元平面をスキャンする。すなわち、情報処理装置１００は、二次元平面上の位置をＸ座標の小さい順に水平方向にスキャンし、Ｘ座標が同じ位置についてはＹ座標の小さい順に垂直方向にスキャンする。情報処理装置１００は、下から上へのスキャン、右に移動、下から上へのスキャン、右に移動、…を繰り返すことになる。情報処理装置１００は、あるメッシュの左下の頂点が検出されると当該メッシュを活性化（アクティベート）する。また、情報処理装置１００は、あるメッシュの右上の頂点が検出されると当該メッシュを非活性化（ディアクティベート）する。隣接関係の判定では、活性化中のメッシュ同士を比較すればよい。
【００８９】
隣接行列Ｗの隣接関係について、メッシュｖ１の左下の座標を（ｌｘ１，ｌｙ１）、メッシュｖ１の右上の座標を（ｕｘ１，ｕｙ１）、メッシュｖ２の左下の座標を（ｌｘ２，ｌｙ２）、メッシュｖ２の右上の座標を（ｕｘ２，ｕｙ２）とする。数式（１３）の条件を満たすとき、メッシュｖ２がメッシュｖ１と隣接行列Ｗの隣接関係をもつ。ただし、頂点を共有する場合を除外するため、数式（１４）の条件も合わせて満たすことを要する。
【００９０】
【数１３】
2019192086.tif 000015
【００９１】
【数１４】
2019192086.tif 000016
【００９２】
隣接行列Ｕの隣接関係について、メッシュｖ１の左下の座標を（ｌｘ１，ｌｙ１）、メッシュｖ１の右上の座標を（ｕｘ１，ｕｙ１）とする。また、メッシュｖ２の何れかの頂点の座標を（ｘ２，ｙ２）とする。数式（１５）の条件を満たすとき、メッシュｖ２がメッシュｖ１と隣接行列Ｕの隣接関係をもつ。また、数式（１６）の条件を満たすときも、メッシュｖ２がメッシュｖ１と隣接行列Ｕの隣接関係をもつ。
【００９３】
【数１５】
2019192086.tif 000017
【００９４】
【数１６】
2019192086.tif 000018
【００９５】
隣接行列Ｑの隣接関係について、メッシュｖ１の左下の座標を（ｌｘ１，ｌｙ１）、メッシュｖ１の右上の座標を（ｕｘ１，ｕｙ１）、メッシュｖ２の左下の座標を（ｌｘ２，ｌｙ２）、メッシュｖ２の右上の座標を（ｕｘ２，ｕｙ２）とする。数式（１７）の条件を満たすとき、メッシュｖ２がメッシュｖ１と隣接行列Ｑの隣接関係をもつ。
【００９６】
【数１７】
2019192086.tif 000019
【００９７】
次に、情報処理装置１００の機能および処理手順を説明する。
図１１は、情報処理装置の機能例を示すブロック図である。
情報処理装置１００は、入力データ記憶部１１１、出力データ記憶部１１２、目的関数生成部１１３、最適化部１１４および最適領域表示部１１５を有する。入力データ記憶部１１１および出力データ記憶部１１２は、例えば、ＲＡＭ１０２またはＨＤＤ１０３を用いて実現される。目的関数生成部１１３、最適化部１１４および最適領域表示部１１５は、例えば、ＣＰＵ１０１が実行するプログラムを用いて実現される。
【００９８】
入力データ記憶部１１１は、最適領域の探索に用いる入力データを記憶する。入力データは、メッシュの分割結果を示す領域データと、メッシュ毎の支持度およびヒット数を示す分布データとを含む。二次元平面を複数のメッシュに分割する分割処理は、情報処理装置１００が行ってもよいし他の装置が行ってもよい。メッシュ毎の支持度およびヒット数のカウントは、情報処理装置１００が行ってもよいし他の装置が行ってもよい。
【００９９】
出力データ記憶部１１２は、判定した最適領域を示す出力データを記憶する。出力データは、前述の二値化したベクトルｚに相当する。
目的関数生成部１１３は、スコア関数と正則化項とを含む目的関数を生成する。目的関数生成部１１３は、領域データが示すメッシュにそれぞれ変数を割り当て、分布データと変数からスコア関数を生成する。また、目的関数生成部１１３は、領域データからメッシュ間の隣接関係を示す隣接行列を生成し、変数と隣接行列から正則化項を生成する。スコア関数に正則化項を追加したものが目的関数である。
【０１００】
最適化部１１４は、目的関数生成部１１３が生成した目的関数に対して勾配法による最適化処理を行い、目的関数の値を最大化する変数の値を探索する。最適化部１１４は、勾配法によって算出された解から、各メッシュが最適領域に含まれるか否かを判定し、出力データを出力データ記憶部１１２に格納する。
【０１０１】
最適領域表示部１１５は、前述の可視化画面３６のような可視化画面をディスプレイ１０４ａに表示する。可視化画面では、観測群に属する点（黒点）とそれ以外の点（白点）の分布を二次元平面に表示する。また、可視化画面では、判定した最適領域の外枠を示す多角形を、点の分布と重ねて二次元平面に表示する。なお、情報処理装置１００は、出力データまたは可視化結果を、ネットワーク１０７ａを介して他の装置に送信してもよいしプリンタなどの他の種類の出力デバイスに出力してもよい。
【０１０２】
図１２は、入力データおよび出力データの例を示す図である。
入力データ記憶部１１１は、領域データ１２１および分布データ１２２を記憶する。
領域データ１２１は、複数のレコードを含む。領域データ１２１の各レコードは、メッシュＩＤおよび座標を含む。メッシュＩＤは、メッシュを識別する識別子である。座標は、二次元平面におけるメッシュの位置を示す。例えば、座標としてメッシュの左下の頂点の座標と右上の頂点の座標が登録される。領域データ１２１に、メッシュ間の隣接関係（隣接行列Ｗに相当する隣接関係など）が予め登録されていてもよい。
【０１０３】
分布データ１２２は、複数のレコードを含む。分布データ１２２の各レコードは、メッシュＩＤ、ヒット数および支持度を含む。メッシュＩＤは、メッシュを識別する識別子である。ヒット数は、メッシュに含まれる観測群の点（黒点）の数である。支持度は、メッシュに含まれる基準群の点（黒点および白点）の数である。
【０１０４】
出力データ記憶部１１２は、最適領域データ１２３を記憶する。
最適領域データ１２３は、複数のレコードを含む。最適領域データ１２３の各レコードは、メッシュＩＤおよびフラグを含む。メッシュＩＤは、メッシュを識別する識別子である。フラグは、メッシュが最適領域に含まれるか否かを示す。フラグが１であるメッシュは最適領域に含まれ、フラグが０であるメッシュは最適領域に含まれない。
【０１０５】
図１３は、最適領域抽出の手順例を示すフローチャートである。
（Ｓ１）目的関数生成部１１３は、領域データ１２１と分布データ１２２を読み込む。
（Ｓ２）目的関数生成部１１３は、領域データ１２１が示すメッシュｖｉ（ｉ＝１，２，…，ｎ）に対して変数ｚｉを割り当て、変数ｚｉを列挙したベクトルｚを定義する。
【０１０６】
（Ｓ３）目的関数生成部１１３は、分布データ１２２に含まれる各メッシュのヒット数および支持度と、ステップＳ２で定義したベクトルｚを用いて、数式（１）、数式（９）または数式（１０）のようなスコア関数を生成する。
【０１０７】
（Ｓ４）目的関数生成部１１３は、領域データ１２１から隣接行列を生成する。例えば、目的関数生成部１１３は、辺同士の接続を示す隣接行列Ｗを生成する。または、目的関数生成部１１３は、辺同士の接続を示す隣接行列Ｗと、頂点同士の接続および頂点と辺の接続を示す隣接行列Ｕと、頂点同士の接続を示す隣接行列Ｑを生成する。
【０１０８】
（Ｓ５）目的関数生成部１１３は、ステップＳ４で生成した隣接行列とステップＳ２で定義したベクトルｚを用いて、最適領域の形状のペナルティを示す正則化項を生成する。例えば、目的関数生成部１１３は、隣接行列Ｗを用いて正則化項を生成する。または、目的関数生成部１１３は、隣接行列Ｗ，Ｕ，Ｑを用いて正則化項を生成する。
【０１０９】
（Ｓ６）目的関数生成部１１３は、ステップＳ３のスコア関数にステップＳ５の正則化項を加えた目的関数を生成する。例えば、目的関数生成部１１３は、数式（５）または数式（１２）のような目的関数を生成する。
【０１１０】
（Ｓ７）最適化部１１４は、ベクトルｚの初期値を決定する。最適領域の探索中は、ベクトルｚの各要素は任意の実数をとることができる。最適化部１１４は、ベクトルｚの初期値をランダムに決めてもよいし所定の実数としてもよい。
【０１１１】
（Ｓ８）最適化部１１４は、数式（７）および数式（８）のように、現在のベクトルｚの値からステップＳ６の目的関数の勾配を算出する。
（Ｓ９）最適化部１１４は、数式（６）のように、ステップＳ８で算出した勾配を用いて現在のベクトルｚの値を更新する。例えば、最適化部１１４は、勾配に所定の重み（−η）をかけて現在のベクトルｚの値に加算する。
【０１１２】
（Ｓ１０）最適化部１１４は、ベクトルｚの値が収束したか判断する。例えば、最適化部１１４は、ステップＳ９の更新後のベクトルｚの大きさ（絶対値）と更新前のベクトルｚの大きさ（絶対値）との差が閾値未満である場合、ベクトルｚの値が収束したと判断する。または、最適化部１１４は、ステップＳ９の更新後のベクトルｚと更新前のベクトルｚとの間の距離（ノルム）が閾値未満である場合、ベクトルｚの値が収束したと判断する。収束した場合はステップＳ１１に進み、収束していない場合はステップＳ８に進む。
【０１１３】
（Ｓ１１）最適化部１１４は、ベクトルｚの要素である変数ｚｉの値から各メッシュの採否（最適化領域に採用するか否か）を決定する。例えば、最適化部１１４は、二値化前の変数ｚｉの値が０より大きい場合、メッシュｖｉを採用すると決定し、二値化前の変数ｚｉの値が０以下である場合、メッシュｖｉを採用しないと決定する。最適化部１１４は、最適領域データ１２３を生成して出力する。
【０１１４】
（Ｓ１２）最適領域表示部１１５は、領域データ１２１、分布データ１２２および最適領域データ１２３に基づいて、最適領域を可視化した可視化画面を生成し、生成した可視化画面をディスプレイ１０４ａに表示する。可視化画面には、二次元平面における点の分布や最適領域の外枠の多角形などが表示される。
【０１１５】
第２の実施の形態の情報処理装置１００によれば、黒点および白点が不均一に分布している二次元平面の中から、点が密集している１以上の閉領域が最適領域として抽出されて可視化される。よって、空間疫学や交通分析など事象の発生状況の分析が容易となる。また、目的関数を用いて閉領域の選択が評価される。よって、抽出する最適領域の形状やサイズを予め厳密に制限しなくてもよく、黒点および白点の分布に応じて柔軟に閉領域を設定できフィッティング精度が向上する。また、隣接行列を用いた正則化項が目的関数に追加される。よって、フィッティング精度と閉領域の複雑さが総合的に評価される。このため、抽出される最適領域の形状が過度に複雑になることを抑制でき、事象の発生状況を適切に表現した自然な形状の最適領域を抽出することができる。また、勾配法により目的関数の最適解が探索される。よって、様々な閉領域の組み合わせを網羅的に評価しなくてもよく、計算量を削減することができる。
【符号の説明】
【０１１６】
１０  領域生成装置
１１  記憶部
１２  処理部
１３  分布データ
１４  領域データ
１５  隣接行列
１６  変数
１７  評価関数
【図１】
2019192086.tif 000020
【図２】
2019192086.tif 000021
【図３】
2019192086.tif 000022
【図４】
2019192086.tif 000023
【図５】
2019192086.tif 000024
【図６】
2019192086.tif 000025
【図７】
2019192086.tif 000026
【図８】
2019192086.tif 000027
【図９】
2019192086.tif 000028
【図１０】
2019192086.tif 000029
【図１１】
2019192086.tif 000030
【図１２】
2019192086.tif 000031
【図１３】
2019192086.tif 000032