(57)【要約】【課題】グラフ構造環境を利用した個人の個人情報を適切に匿名化する。【解決手段】個人情報匿名化装置が、記憶手段と、匿名化手段を有する。記憶手段が、有限個の複数の位置のどの位置にどの位置が隣接するかの隣接関係を表した隣接関係タプルを各位置について含んだ隣接関係情報と、個人の識別情報と前記複数の位置においてその個人が利用する位置を表す位置情報とを含んだ個人情報である個人情報タプルを各個人について含んだ個人管理情報とを記憶する。匿名化手段が、隣接関係情報が示す隣接関係にある位置同士のみを集合化することにより、同一の位置集合を含んだ複数の匿名化された個人情報タプルに対応する異なる個人の数が所定の閾値以上になるように、各個人情報タプルを匿名化する。【選択図】図１
2012079205.tif 000002
【特許請求の範囲】
【請求項１】
有限個の複数の位置のどの位置にどの位置が隣接するかの隣接関係を表した隣接関係タプルを各位置について含んだ隣接関係情報と、個人の識別情報と前記複数の位置においてその個人が利用する位置を表す位置情報とを含んだ個人情報である個人情報タプルを各個人について含んだ個人管理情報とを記憶する記憶手段と、
前記隣接関係情報が示す隣接関係にある位置同士のみを集合化することにより、同一の位置集合を含んだ複数の匿名化された個人情報タプルに対応する異なる個人の数が所定の閾値以上になるように、各個人情報タプルを匿名化する匿名化手段と
を有する個人情報匿名化装置。
【請求項２】
請求項１記載の個人情報匿名化装置であって、
前記個人情報タプル内の位置情報が表す位置が属する経路を前記各個人情報タプルについて推定する経路推定手段、
を更に有し、
前記隣接関係情報が、各隣接関係について、位置とその位置に隣接する位置とを結ぶリンクを含んだ経路を表す情報を含み、
前記匿名化手段が、同一路線の同一の位置集合を含んだ複数の匿名化された個人情報タプルに対応する異なる個人の数が所定の閾値以上になるように、前記各個人情報タプルを匿名化する、
個人情報匿名化装置。
【請求項３】
請求項２記載の個人情報匿名化装置であって、
前記隣接関係情報が表す各経路の構造は、直線構造と環状構造のいずれかであり、
前記匿名化手段が、Ｈｕ−Ｔｕｃｋｅｒ木を構成することによって生成される二分木を用いて、前記各個人情報タプルを匿名化する、
個人情報匿名化装置。
【請求項４】
請求項１又は２に記載の個人情報匿名化装置であって、
前記匿名化手段が、前記複数の位置のうちの第１の位置に隣接する２以上の位置のうち、利用される個人の数が最も少ない位置を第２の位置とし、前記各個人情報タプルの匿名化において、前記第１の位置と前記第２の位置を集合化する、
個人情報匿名化装置。
【請求項５】
請求項４記載の個人情報匿名化装置であって、
前記第２の位置は、前記第１の位置（Ｘ）に隣接する２以上の位置である集合化候補Ｓのうち、（−Ｘの頻度）×ｌｏｇ（Ｘの頻度／（Ｘの頻度＋Ｓの頻度））−Ｓの頻度×ｌｏｇ（Ｓの頻度／（Ｘの頻度＋Ｓの頻度））の値が最も小さい位置である、
個人情報匿名化装置。
【請求項６】
請求項１乃至５のうちのいずれか１項に記載の個人情報匿名化装置であって、
前記各個人情報タプルが、利用した位置に入場又は利用した位置から退場した時刻を表す時刻情報を含み、
前記各個人情報タプルが有する時刻情報が表す時刻を時区間に曖昧化する時区間化手段、
を更に有し、
匿名化された各個人情報タプルは、時区間を表す情報を含み、
前記匿名化手段は、同一の位置集合及び時区間を含んだ複数の匿名化された個人情報タプルに対応する異なる個人の数が所定の閾値以上になるように、前記各個人情報タプルを匿名化する、
個人情報匿名化装置。
【請求項７】
請求項１乃至５のうちのいずれか１項に記載の個人情報匿名化装置であって、
前記各個人情報タプルが、利用した位置への入場であるかその位置からの退場であるかを表す入退場情報を含み、
前記匿名化手段は同一の位置集合及び入退場情報を含んだ複数の匿名化された個人情報タプルに対応する異なる個人の数が所定の閾値以上になるように、前記各個人情報タプルを匿名化する、
個人情報匿名化装置。
【請求項８】
請求項６記載の個人情報匿名化装置であって、
前記各個人情報タプルが、利用した位置への入場であるかその位置からの退場であるかを表す入退場情報を含み、
前記匿名化手段は、同一の位置集合、時区間及び入退場情報を含んだ複数の匿名化された個人情報タプルに対応する異なる個人の数が所定の閾値以上になるように、前記各個人情報タプルを匿名化する、
個人情報匿名化装置。
【請求項９】
請求項６又は８記載の個人情報匿名化装置であって、
前記時区間化手段が、時区間に属する時刻を表す情報を含んだ個人情報タプルの数が、複数の時区間で実質的に均一となるように、前記各個人情報タプル内の時刻を時区間に曖昧化する、
個人情報匿名化装置。
【請求項１０】
請求項１乃至９のうちのいずれか１項に記載の個人情報匿名化装置であって、
前記匿名化手段が、前記個人管理情報記憶手段に含まれる同一の位置に関しては、同一の位置集合となるように、前記各個人情報タプルを匿名化する、
個人情報匿名化装置。
【請求項１１】
請求項１乃至５のうちのいずれか１項に記載の個人情報匿名化装置であって、
前記各個人情報タプルは、位置情報として、２以上の異なる位置を表す情報を含み、
前記匿名化手段が、前記２以上の異なる位置の各々について、前記隣接関係情報が示す隣接関係にある位置同士のみを集合化することにより、前記２以上の異なる位置の各々について同一の位置集合を含んだ複数の匿名化された個人情報タプルに対応する異なる個人の数が所定の閾値以上になるように、各個人情報タプルを匿名化する、
個人情報匿名化装置。
【請求項１２】
有限個の複数の位置のどの位置にどの位置が隣接するかの隣接関係を表した隣接関係タプルを各位置について含んだ隣接関係情報を参照し、
個人の識別情報と前記複数の位置においてその個人が利用する位置を表す位置情報とを含んだ個人情報である個人情報タプルを各個人について含んだ個人管理情報における各個人情報タプルを、前記隣接関係情報が示す隣接関係にある位置同士のみを集合化することにより、同一の位置集合を含んだ複数の匿名化された個人情報タプルに対応する異なる個人の数が所定の閾値以上になるように、匿名化する、
個人情報匿名化方法。
【請求項１３】
有限個の複数の位置のどの位置にどの位置が隣接するかの隣接関係を表した隣接関係タプルを各位置について含んだ隣接関係情報を参照し、
個人の識別情報と前記複数の位置においてその個人が利用する位置を表す位置情報とを含んだ個人情報である個人情報タプルを各個人について含んだ個人管理情報における各個人情報タプルを、前記隣接関係情報が示す隣接関係にある位置同士のみを集合化することにより、同一の位置集合を含んだ複数の匿名化された個人情報タプルに対応する異なる個人の数が所定の閾値以上になるように、匿名化する、
ことをコンピュータに実行させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、個人情報を匿名化するコンピュータ技術に関する。
【背景技術】
【０００２】
個人にまつわる膨大なデータの集積化が進む昨今、個人情報を扱う企業にとってはプライバシへの配慮が必要不可欠なものになっている。個人情報取り扱い事業者にとって、少なくとも個人情報の保護に関する法律（以下、保護法）や関係法令の遵守が必須となっている。保護法は、個人情報の収集や利用等に対して、管理対応を義務付けており、さらにその具体的な措置を各省庁のガイドラインが規定している。
【０００３】
これらのガイドラインが規定する管理措置の１つに個人情報の匿名化がある。例えば、厚生労働省は医療に関する個人情報の第三者提供、学会発表、医療事故報告等において、特段の必要がない限りはこれを匿名化することを求めている。また、経済産業省でも個人情報の匿名化を第三者提供時の望ましい措置として挙げている。
【０００４】
個人情報の匿名化を適用する対象として、氏名、住所、年齢といった個人の属性が挙げられるとともに、現在流行となりつつあるＬＢＳ（Location  Based  Service）の前提となるＧＰＳ（Global  Positioning  System）情報や、電子交通乗車券によりログとして残される履歴（鉄道の場合は改札入退場履歴）といった位置情報の匿名化が求められている。この種の匿名化技術は、例えば非特許文献１に記載されている。
【０００５】
非特許文献１には、個人のタプル（（時刻、位置）で構成されたタプル）が多数あった場合に、時刻及び位置を曖昧にすることで、少なくとも所定件数以上の個人が同じルートを辿るデータに変換することを保証する方法が記載されている。つまり、非特許文献１の技術は、ＧＰＳデータのように任意の位置を取り得るケースについての位置情報匿名化技術である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】M.E.Nergiz,  M.Atzori,  and  Y.Saygin,  “Towards Trajectory Anonymization: AGeneralization-Based Approach,”  Proceedings  of  the  SIGSPATIAL  ACM  GIS  2008  International  Workshop  on  Security  and  Privacy  in  GIS  and  LBS,  California,  pp.52−61,  2008.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
どの位置とどの位置が隣接するかが定義されたグラフ構造を持つ移動環境（以下、グラフ構造環境）がある。そのような移動環境として、例えば、鉄道（例えば、位置＝駅）、路線バス（例えば、位置＝停留所）、飛行機（位置＝空港）、あるいは、道路網（例えば、位置＝交差点）がある。
【０００８】
グラフ構造環境では、必ずしも、隣接する位置が距離的に最も近いとは限らない。
【０００９】
こうした理由から、任意の位置を取り得るケースについての位置情報匿名化技術（非特許文献１の匿名化技術）を、グラフ構造環境を利用した個人の個人情報の匿名化に適用すると、隣接していない位置同士が同じグループに曖昧化されてしまうことがある。故に、グラフ構造環境を利用した個人の個人情報を匿名化することに非特許文献１の技術を適用することは、実用上の観点からは好ましくない。
【００１０】
従って、本発明の目的は、グラフ構造環境を利用した個人の個人情報を適切に匿名化することにある。
【課題を解決するための手段】
【００１１】
個人情報匿名化装置が、記憶手段と、匿名化手段を有する。記憶手段が、有限個の複数の位置のどの位置にどの位置が隣接するかの隣接関係を表した隣接関係タプルを各位置について含んだ隣接関係情報と、個人の識別情報と前記複数の位置においてその個人が利用する位置を表す位置情報とを含んだ個人情報である個人情報タプルを各個人について含んだ個人管理情報とを記憶する。匿名化手段が、隣接関係情報が示す隣接関係にある位置同士のみを集合化することにより、同一の位置集合を含んだ複数の匿名化された個人情報タプルに対応する異なる個人の数が所定の閾値以上になるように、各個人情報タプルを匿名化する。
【発明の効果】
【００１２】
グラフ構造環境の利用者の個人情報を適切に匿名化することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施例１に係る個人情報匿名化装置が適用された計算機の構成例を示す。
【図２】図２Ａは、駅隣接構造テーブル１３１の一例を示す。図２Ｂは、図２Ａが示すテーブル１３１が表す隣接関係の模式図である。
【図３】実施例１に係る改札入退場テーブル１３２の一例を示す。
【図４】実施例１に係る最小同値件数情報１３４の一例を示す。
【図５】実施例１に係る匿名改札入退場テーブル１３３の一例を示す。
【図６】実施例１に係る計算機１００が実行する処理の全体の流れの一例を示す。
【図７】図６のＳ６０１の詳細な流れの一例を示す。
【図８】図６のＳ６０２の詳細な流れの一例を示す。
【図９】図８のＳ８０３の詳細な流れの一例を示す。
【図１０】図１０Ａ及び図１０Ｂは、実施例１に係る予測開示リスクの一例の説明図である。
【図１１】本発明の実施例２に係る個人情報匿名化装置が適用された計算機の構成例を示す。
【図１２】図１２Ａは、路線駅隣接構造テーブル１１３１の構成例を示す。図１２Ｂは、図１２Ａが示すテーブル１１３１が表す路線構造の模式図である。
【図１３】実施例２に係る路線探索部１１２２の出力例を示す。
【図１４】実施例２に係る匿名改札入退場テーブルの一例を示す。
【図１５】実施例２に係る計算機１００が実行する処理の全体の流れの一例を示す。
【図１６】図１５のＳ１５０３の詳細な流れの一例を示す。
【図１７】図１５のＳ１５０３の詳細な流れの別の一例を示す。
【図１８】図１８Ａは、直線的な路線構造の一例を示す。図１８Ｂは、環状的な路線構造の一例を示す。
【図１９】図１９Ａは、実施例２に係るＨｕ−Ｔｕｃｋｅｒ木の一例を示す。図１９Ｂは、実施例２に係る利用頻度の一例を示す。
【図２０】図１７のＳ１７０３の詳細の流れの一例を示す。
【図２１】本発明の実施例３に係る個人情報匿名化装置が適用された計算機の構成例を示す。
【図２２】実施例３に係る定期マスタテーブル２１３１の一例を示す。
【図２３】実施例３に係る匿名定期マスタテーブル２１３２の一例を示す。
【図２４】実施例３に係る計算機１００が実行する処理の全体の流れの一例を示す。
【図２５】本発明の実施例４に係る個人情報匿名化装置が適用された計算機の構成例を示す。
【図２６】実施例４に係る路線探索部２５２２の出力の一例を示す。
【図２７】実施例４に係る計算機１００が実行する処理の全体の流れの一例を示す。
【図２８】図２７のＳ２７０２の詳細な流れの一例を示す。
【図２９】図２７のＳ２７０２の詳細な流れの別の一例を示す。
【発明を実施するための形態】
【００１４】
以下、本発明の幾つかの実施例を、図面を参照して詳細に説明する。
【００１５】
なお、以下の説明では「ｘｘｘテーブル」の表現にて各種情報を説明することがあるが、各種情報は、テーブル以外のデータ構造で表現されていても良い。データ構造に依存しないことを示すために「ｘｘｘテーブル」を「ｘｘｘ情報」と呼ぶことができる。
【００１６】
また、以下の説明では、要素を特定するためにＩＤ（識別子）が使用されるが、ＩＤに代えて、識別情報として、名前又は番号などが使用されて良い。
【００１７】
また、以下の説明では、「プログラム」がプロセッサ（例えばＣＰＵ（Central  Processing  Unit））によって実行されることで発揮される機能を主語にして処理を説明することがあるが、定められた処理を、適宜に記憶資源（例えばメモリ）及び／又は通信インタフェース装置（例えば通信ポート）を用いながら行うため、処理の主語がプロセッサとされても良い。プロセッサは、プロセッサが行う処理の一部又は全部を行うハードウェア回路を含んでも良い。コンピュータプログラムは、プログラムソースから各計算機にインストールされても良い。プログラムソースは、例えば、プログラム配布サーバ又は記憶メディアであっても良い。
【００１８】
また、以下の全ての実施例は、主に電子的な形態の個人情報を保護する技術に関する。実施例１及び２では、匿名化される個人情報は、グラフ構造環境における位置（隣接関係を定義可能な位置）を表す位置情報のログデータ（移動ログデータ）である。位置は、例えば、鉄道のケースでは駅、バスのケースでは停留所、メッシュ化した地図情報のケースではメッシュである。
【００１９】
以下の全ての実施例では、グラフ構造環境として鉄道を例に取る。以下の実施例１及び２において、個人情報の匿名化とは、情報主体（利用者）を一意に識別できないように移動ログデータを変換する処理をいう。また、再符号化とは、移動ログデータに含まれている時刻情報や位置情報を、より曖昧な概念へと置き換えることをいう。また、以下の説明では、「駅」という用語は、通常通りにある１つの駅単体に対して用いる。また、「駅Ａまたは駅Ｂまたは駅Ｃ」を、「駅｛Ａ，Ｂ，Ｃ｝」のように駅集合で表現することがある。
【実施例１】
【００２０】
以下の説明では、「入退場非区別方式」と「入退場区別方式」を説明する。それぞれの方式で、別個の意味を持つ場合には明確にその旨を記す。特に方式を区別しない場合には、両方式共通であることを意味する。
【００２１】
図１は、本発明の実施例１に係る個人情報匿名化装置が適用された計算機の構成例を示す。
【００２２】
計算機１００は、情報処理装置であり、例えば、ＰＣ（Personal  Computer）、サーバ或いはワークステーションである。計算機１００は、ＣＰＵ（Central  Processing  Unit）１０１、メモリ１０２、ストレージ１０３、入力装置１０４、出力装置１０５及び通信装置１０６を有する。これらは全て、バスなどの内部通信線１０７により互いに接続されている。
【００２３】
ストレージ１０３は、例えばＣＤ−Ｒ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅｃｏｒｄａｂｌｅ）やＤＶＤ−ＲＡＭ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、シリコンディスク等の記憶メディア及び当該記憶メディアの駆動装置、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）等である。ストレージ１０３は、駅隣接構造テーブル１３１、改札入退場テーブル１３２、匿名改札入退場テーブル１３３、最小同値件数情報１３４及びプログラム１５１を記憶する。
【００２４】
駅隣接構造テーブル１３１は、どの駅がどの駅の隣駅であるかの情報を格納する。
【００２５】
改札入退場テーブル１３２は、複数の個人が駅に存在する改札を利用した際に残される個人の位置情報の履歴（移動ログデータ）を格納する。
【００２６】
匿名改札入退場テーブル１３３は、改札入退場テーブル１３２が有する移動ログデータを匿名化した結果を格納する。
【００２７】
最小同値件数情報１３４は、しきい値を格納する。
【００２８】
プログラム１５１は、後述する機能を実現するためのものである。
【００２９】
入力装置１０４は、例えばキーボード、マウス、スキャナ、マイク等である。出力装置１０５は、ディスプレイ装置、プリンタ、スピーカ等である。入力装置１０４及び出力装置が一体になっていても良い（例えば、タッチパネル型のディスプレイ装置）。
【００３０】
通信装置１０６は、例えば、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）ボード等であり、通信ネットワーク（図示略）と接続することができる。
【００３１】
ＣＰＵ１０１は、メモリ１０２上にプログラム１５１をロードし、実行することにより、時区間化部１２１及び位置匿名化部１２２を実現する。
【００３２】
時区間化部１２１は、改札入退場テーブル１３２を入力とし、テーブルに含まれる時刻情報を、該時刻情報を含む２つの時刻の間の時区間へと変換したテーブルを出力とし、位置匿名化部１２２の入力に渡す。
【００３３】
位置匿名化部１２２は、時区間化部１２１から渡されたテーブル、及び駅隣接構造テーブル１３１、並びに最小同値件数情報１３４を入力とする。入退場非区別方式の場合には、位置匿名化部１２２は、任意の時区間に任意の駅に存在した総人数が０（又は、最小同値件数情報１３４に格納された値以上）になるよう、駅を再符号化する。入退場区別方式の場合には、位置匿名化部１２２は、任意の時区間に任意の駅に入場した総人数、及び、任意の時区間に任意の駅から退場した総人数が、それぞれ０（又は、最小同値件数情報１３４に格納された値以上）になるよう、駅を再符号化する。位置匿名化部１２２は、再符号化により得られた結果を匿名改札入退場テーブル１３３に格納する。なお、位置匿名化部１２２は、その再符号化により得られた結果を、出力装置１０５を介して出力してもよい。
【００３４】
次に、上述した各テーブルの詳細を説明する。
【００３５】
図２Ａは、駅隣接構造テーブル１３１の一例を示す。
【００３６】
駅隣接構造テーブル１３１は、複数のレコードを有する。各レコードは、どの駅とどの駅が隣り合っているかを示す。図２Ａのテーブル１３１は、図２Ｂに示す線路構造２００で表されるグラフ構造を表している。即ち、線路構造２００は、駅を表す位置（ノード）２０１と駅と駅との隣接関係（線路）を表す辺（リンク）２０２で構成され、各辺は、駅隣接構造テーブル１３１の各レコードに対応する（つまり、レコードと辺が１対１で対応する）。
【００３７】
なお、駅隣接構造テーブル１３１の構成は、図２Ａに示す例に限られない。グラフ構造には様々な表現形式が存在し、実際の駅の隣接関係を定義できるものであれば、その何れでも良い。
【００３８】
図３は、改札入退場テーブル１３２の一例を示す。
【００３９】
改札入退場テーブル１３２は、複数のレコードを有する。１つのレコードは、ある個人がある駅にある時刻に入場または退場したことを意味する。即ち、改札入退場テーブル１３２は、移動ログ毎に、下記の情報を有するレコード、
（１）移動ログに関わる個人の識別子であるユーザＩＤ３０１、
（２）個人が存在した駅の識別子である駅３０２、
（３）個人が駅に入場又は駅から退場した時刻を表す時刻３０３、
（４）個人が駅に入場したのか退場したのかを示す入退場３０４、
を有する。図３の例によれば、ユーザＩＤ「２」の個人が２０１０年５月１２日７時２２分１９秒に駅「Ｂ」に入場し、駅「Ｈ」まで移動し、駅「Ｈ」から同日７時４２分１１秒に退場し、再度、同日７時４８分５２秒に駅「Ｈ」に入場したことが分かる。
【００４０】
改札入退場テーブル１３２は、随時に又は定期的に更新される。
【００４１】
なお、改札入退場テーブル１３２の構成は、図３に示した例に限られない。例えば、ユーザの入場と退場をセットにしたテーブルが採用されても良い。しかし、図３のようなテーブル表現形式に変換可能なテーブルが望ましい。また、図３の例によれば、鉄道の改札入退場履歴が移動ログとして採用されるが、前述のようにバスの停留所やグラフ構造を持つ地理情報など、グラフ構造における任意の位置について移動ログが取得されて良い。
【００４２】
図４は、最小同値件数情報１３４の一例を示す。
【００４３】
図４の例によれば、最小同値件数４０１が５件である。最小同値件数４０１は、入退場非区別方式では、任意の時区間に任意の駅に存在する個人の数が０又は最小同値件数４０１以上となる情報（匿名化された情報）を公開しても個人を一意に特定することが困難であると見なされる値である。ここで、「存在する」とは、本実施例では、入場または退場を行ったことを意味する。なお、任意の時区間及び任意の駅に存在するレコードの数ではなく、個人の数であることが重要である。また、入退場区別方式の場合には、最小同値件数４０１は、任意の時区間に任意の駅に改札を通って入場した個人の数と改札を通って退場した個人の数がそれぞれ０に一致または最小同値件数４０１以上となる情報（匿名化された情報）を公開しても個人を一意に特定することが困難であると見なされる値である。
【００４４】
なお、最小同値件数４０１の値は５件に限定されず、任意の値で良い。本明細書では、最小同値件数４０１の値を「ｋ」とすることがある。本実施例は、ｋ−匿名化に関するからである。
【００４５】
図５は、匿名改札入退場テーブル１３３の一例を示す。
【００４６】
匿名改札入退場テーブル１３３は、複数のレコードを有する。匿名改札入退場テーブル１３３のレコードが有する情報は、改札入退場テーブル１３２のレコードが有する情報が再符号化（曖昧化）された情報である。匿名改札入退場テーブル１３３のレコード（以下、匿名レコード）は、改札入退場テーブル１３２のレコード（以下、通常レコード）と１対１で対応している。つまり、ｎ番目の通常レコードはｎ番目の匿名レコードに対応する（ｎは自然数）。匿名改札入退場テーブル１３３の各レコードは、下記の情報、
（１）個人の識別子を表すユーザＩＤ５０１、
（２）個人が存在した駅の識別子を表す駅５０２、
（３）個人が駅に存在した時区間を表す時区間５０３、
（４）個人が駅に入場したのか退場したのかを示す入退場３０４、
を有する。
【００４７】
ｎ番目の匿名レコード内のユーザＩＤ５０１は、ｎ番目の通常レコード内のユーザＩＤ３０１に一致する。なお、本実施例では、同一の個人であれば、ユーザＩＤ５０１とユーザＩＤ３０１は同一であるが、匿名性を高めるために、ユーザＩＤ５０１として、ユーザＩＤ３０１と１対１に対応する別のユーザＩＤが採用されてもよい。
【００４８】
２番目の匿名レコードの駅５０２によれば、個人「２」は、駅「Ｂ」又は駅「Ｃ」に存在したことがわかる。２番目の通常レコード（図３参照）によれば、個人「２」は駅「Ｂ」に存在したことがわかるが、２番目の通常レコードが有する情報の匿名化により、駅３０２が表す情報「Ｂ」が、駅５０２が表す情報「Ｂ、Ｃ」に再符号化されている。
【００４９】
ｎ番目の匿名レコード内の時区間５０３が表す時区間は、ｎ番目の通常レコード内の時刻３０３が表す時刻を含んだ区間である。
【００５０】
ｎ番目の匿名レコードが有する入退場５０４は、ｎ番目の通常レコード内の入退場３０４と一致する。
【００５１】
匿名改札入退場テーブル１３３は、入退場非区別方式の場合には、以下の制約（Ｘ）を満たさねばならない。
（Ｘ）同一の駅５０２及び時区間５０３の組合せに対応した異なる個人（ユーザＩＤ５０１）の数が、ｋ以上（最小同値件数４０１以上）である。
【００５２】
一方、匿名改札入退場テーブル１３３は、入退場区別方式の場合には、以下の制約（Ｙ）を満たさなくてはならない。
（Ｙ）同一の駅５０２、時区間５０３及び入退場５０４の組合せに対応した異なる個人（ユーザＩＤ５０１）の数がｋ以上（最小同値件数４０１以上）である。
【００５３】
このテーブル１３３は、図６に示す一連の処理が行われることにより生成されたテーブルである。
【００５４】
図６は、実施例１に係る計算機１００が実行する処理の全体の流れの一例を示す。
【００５５】
まず、Ｓ６０１で、時区間化部１２１は、改札入退場テーブル１３２を参照し、時刻３０３を時区間５０３へと再符号化し、その時区間５０３を位置匿名化部１２２に入力として渡す。
【００５６】
次に、Ｓ６０２で、位置匿名化部１２２が、下記の処理、
（ａ）Ｓ６０１における時区間化部１２１の出力と、駅隣接構造テーブル１３１と、改札入退場テーブル１３２と、最小同値件数情報１３４とを参照する、
（ｂ）入退場非区別方式の場合には、匿名化改札入場テーブル１３３に格納されることになる同一の駅５０２及び時区間５０３の組合せを含んだタプル（レコード）に対応する異なる個人の数がｋ以上（最小同値件数４０１以上）になるように駅３０２を再符号化する、
（ｃ）入退場区別方式の場合には、匿名化改札入場テーブル１３３に格納されることになる同一の駅５０２、時区間５０３及び入退場５０４の組合せを含んだタプル（レコード）に対応する異なる個人の数がｋ以上（最小同件数４０１以上）になるように駅３０２を再符号化する、
（ｄ）上記（ｂ）又は（ｃ）の結果に従う駅５０２（駅３０２が再符号化されることにより得られた情報）と、それに対応するユーザＩＤ５０１、時区間５０３及び入退場５０４を、匿名改札入退場テーブル１３３に格納する、
を行う。
【００５７】
図７は、図６のＳ６０１の詳細な流れの一例を示す。従って、図７に示す全てのステップの処理の主体は、時区間化部１２１である。
【００５８】
まず、時区間化部１２１は、最終的に出力するテーブルのレコードを格納するＢを空集合（レコードなし）に初期化する（Ｓ７０１）。
【００５９】
次に、時区間化部１２１は、改札入退場テーブル１３２を参照し、これを各日ごとに分割し、それぞれの日について以下のループを実行する。なお、実行対象とする日のレコード全体をＤに格納する（Ｓ７０２）。
【００６０】
時区間化部１２１は、Ｄ内のレコードを時刻順にソートする。時区間化部１２１は、ｉ番目のレコードとｊ（ｊ＞ｉ）番目のレコードに対して、ｊの時刻がｉの時刻よりも後になるようにする（Ｓ７０３）。また、時区間化部１２１は、レコードを格納及び編集するためのテーブルＡを初期化する（Ｓ７０４）。
【００６１】
次に、時区間化部１２１は、Ｄ内のレコード数が、システムによって定められたＮよりも小さいかどうかで条件分岐を行う（Ｓ７０５）。ただし、Ｎはｋ以上の整数値とする。Ｎは、例えば１０００００などの値を持ち、最終的に各時区間の有するレコード数の概数にあたる。
【００６２】
Ｓ７０５で、時区間化部１２１は、Ｄ内のレコード数がＮよりも小さくないと判定された場合には（Ｓ７０５：Ｎｏ）、Ａ内のレコード全てを、Ａ内の任意のレコードが持つ時刻を含む時区間に置き換える（Ｓ７０６）。例えば、Ａ内のレコードの中で最も早い時刻が10/05/12 07:22:23で、最も遅い時刻が10/05/12 07:30:36の場合には、時区間化部１２１は、10/05/12 07:22:23〜10/05/12 07:30:36という時区間を算出する。さらに、時区間化部１２１は、ＢにＡ内のレコードを全て追加し、Ａを初期化する（Ｓ７０７）。なお、Ｓ７０６及びＳ７０７は、初回に実行される時にはどの変数も変化しない。
【００６３】
次に、時区間化部１２１は、ＡにＤの中の最初のＮ件のレコードを格納する。図７でＤ（Ｎ）は、Ｄの最初のＮ件を意味する。時区間化部１２１は、ＡにＮ件のレコードを格納した後、Ｄ（Ｎ）をＤから削除する（Ｓ７０８）。
【００６４】
さらに、時区間化部１２１は、Ａのレコードの時刻の中で最も遅い時刻と同じ時刻を持つレコードをＤの中から全てＡに移す。時区間化部１２１は、移したレコードをＤから削除する（Ｓ７０９）。このプロセスにより、時区間化部１２１の処理結果のデータの持つ各時区間が、重ならないようにすることができる。Ｓ７０９の処理を終えた後は、Ｓ７０５の条件分岐に再度戻る。
【００６５】
Ｓ７０５で、時区間化部１２１は、Ｄ内のレコード数がＮよりも小さいと判定された場合には（Ｓ７０５：Ｙｅｓ）、まず、Ｄ内の全てのレコードをＡに追加する（Ｓ７１０）。このプロセスにより、時区間化部１２１の処理結果のデータは、どの時区間をとっても少なくともＮ件以上あるようにすることができる。
【００６６】
続いて行うＳ７１１及びＳ７１２は、それぞれＳ７０６、Ｓ７０７と全く同一である。
【００６７】
時区間化部１２１は、以上のループ処理を、全ての日について行い、最後に、テーブルＢを出力して、Ｓ６０２の入力とし（Ｓ７１３）、処理を終える。
【００６８】
図７の例では、各時区間の持つレコードの概数をＮ件とすることにより、各時区間の持つレコード数の平準化を図っている。これは、通勤時間帯や帰宅時間帯は鉄道の利用者が大幅に増えることや、日中の鉄道利用が前記時間帯に比べて少ないことに対応するためのものである。これを行うことにより、利用頻度の高い通勤時間帯などは、時刻が他時間帯と比べてそれほど曖昧化されずに、匿名改札入退場データを利用する立場からは有用性が高いデータを生成できる。
【００６９】
また、時区間の有するレコード数を平準化する方法は、図７に示した手法に限られない。例えば、１日ｔ件のレコードが存在した場合に、時区間の分割数Ｌを予め指定しておくことで、各々の時区間をおよそｔ／Ｌのレコード数を持つよう分割していく方法なども用いることができる。
【００７０】
なお、図７は、各時区間の持つレコード数を平準化する１つの方法を例示したが、例えば、１５分毎や１時間毎といった一定の時間で区切って時区間を構成しても良い。例えば、１５分毎の場合には、07:23を07:15〜07:30に再符号化する、等である。
【００７１】
図８は、図６のＳ６０２の詳細な流れの一例を示す。従って、図８に示す全てのステップの処理の主体は、位置匿名化部１２２である。
【００７２】
まず、位置匿名化部１２２は、最終的に出力するテーブルのレコードを格納するＢを空集合（レコードなし）に初期化する（Ｓ８０１）。
【００７３】
次に、位置匿名化部１２２は、入退場非区別方式では、Ｓ６０１から入力として渡されたレコード集合を、各レコードの持つ時区間のデータを用いて、同じ時区間を持つレコード集合に分割し、分割した各レコード集合Ｄに対して以下の処理を行う。入退場区別方式では、位置匿名化部１２２は、同じ時区間と入退場のタプルを持つレコード集合に分割し、分割した各レコード集合Ｄに対して以下の処理を行う（Ｓ８０２）。
【００７４】
まず、位置匿名化部１２２は、駅隣接構造テーブル１３１をメモリ１０２にロードする（Ｓ８０３）。
【００７５】
次に、位置匿名化部１２２は、Ｄから各駅の頻度を取得する（Ｓ８０４）。ここでの頻度とは、同一駅と関連付けられる相異なるユーザＩＤの総数を意味する。
【００７６】
次に、位置匿名化部１２２は、頻度が正で、かつｋ件未満の駅があるかどうか条件判定を行う（Ｓ８０５）。ここで、正とは０を含まない。
【００７７】
Ｓ８０５で頻度が正で、ｋ件未満の駅が存在すると判定された場合には（Ｓ８０５：Ｙｅｓ）、位置匿名化部１２２は、頻度が正で、ｋ件未満の駅Ｘをランダムに１つ選択する（Ｓ８０６）。
【００７８】
次に、位置匿名化部１２２は、Ｓ８０３でメモリ１０２にロードした（あるいは、Ｓ８１０でそれを書き換えた）駅隣接関係を示すテーブルから、駅Ｘの隣駅にあたるものを全て列挙し、この集合をＣＡＮＤとおく（Ｓ８０７）。ＣＡＮＤは、図２に示すテーブル構造から簡単に取得できる。
【００７９】
次に、位置匿名化部１２２は、ＣＡＮＤの中からシステムで定まっている指標を用いて、１つの駅Ｙを選択する（Ｓ８０８）。この処理の一例については、図９を用いて後に詳しく説明する。
【００８０】
次に、位置匿名化部１２２は、Ｄ内に出現する全てのＸ、またはＹのセルを｛Ｘ、Ｙ｝に再符号化する（Ｓ８０９）。｛Ｘ、Ｙ｝は駅Ｘまたは駅Ｙに存在したことを示す。便宜上、以降駅｛Ｘ、Ｙ｝という呼び方をする。
【００８１】
次に、位置匿名化部１２２は、Ｓ８０３でメモリにロードした駅隣接構造テーブル内のＸ、Ｙも全て｛Ｘ、Ｙ｝に置き換え、｛Ｘ、Ｙ｝の頻度を駅Ｘの頻度と駅Ｙの頻度の和とする（Ｓ８１０）。以上の処理を終えたら、Ｓ８０５に戻る。
【００８２】
Ｓ８０５で、正の頻度でｋ件未満の駅がないと判定された場合には（Ｓ８０５：Ｎｏ）、位置匿名化部１２２は、ＢにＤ内のレコードを全て追加し（Ｓ８１１）、次のレコード集合に対するループ処理を行う。
【００８３】
以上のループ処理を全ての対象に対して終えると、位置匿名化部１２２は、Ｂを匿名改札入退場テーブルに出力し、処理を終える（Ｓ８１２）。
【００８４】
図８の例では、Ｓ８０６で、頻度がｋ件未満の駅がランダムに選択されるが、何らかの指標を用いて選択が行われても良い。例えば、最も頻度の小さい駅を選択するという方法が適用されても良い。
【００８５】
図９は、図８のＳ８０３の詳細な流れの一例を示す。図９を参照して、位置匿名化部１２２がＳ８０８でＣＡＮＤの中から１つの駅Ｙを選択する動作の一例を説明する。なお、図９の例では、ＣＡＮＤ、ＣＡＮＤに含まれる各駅の頻度、駅Ｘの頻度を入力として、駅Ｙが返される。
【００８６】
まず、位置匿名化部１２２は、指標を格納する変数aを無限大に初期化し、最終的に返す駅を格納する変数Ｙをヌル値に初期化する（Ｓ９０１）。
【００８７】
次に、位置匿名化部１２２は、駅Ｘと再符号化した時に指標が最小となるＣＡＮＤ内の駅を探索するために、ＣＡＮＤ内の各駅Ｓに対して以下の手続きを実行する（Ｓ９０２）。
【００８８】
位置匿名化部１２２は、ｂを以下の式で計算した指標とする（Ｓ９０３）。
【数１】
2012079205.tif 000003
【００８９】
ただし、ｃｎｔ（ｈ）は駅を引数とし、その駅の頻度を表すものとする。ｌｏｇの底はシステムで統一をしていれば任意でよい。ｌｏｇの底として、一般的には、２が用いられる。また、０ｌｏｇ０は、０とする。数１は、駅Ｘと駅Ｓを再符号化した時に失う情報エントロピーを表す量である。
【００９０】
次に、位置匿名化部１２２は、ａがｂより大きいかどうか条件判定を行う（Ｓ９０４）。ａがｂより大きいと判定された場合には、再符号化時に、より指標を小さくする駅候補が見つかったことを意味する。
【００９１】
Ｓ９０４で、ａがｂより大きいと判定された場合には（Ｓ９０４：Ｙｅｓ）、位置匿名化部１２２は、ａにｂを代入し、ＹにＳを代入する（Ｓ９０５）。
【００９２】
以上のループ処理を終えた後、位置匿名化部１２２は、Ｙの値を返して処理を終了する。
【００９３】
図９の例によれば、駅Ｘに隣接する複数の駅のうち、上記ｂの値が最も小さくなる駅が、駅Ｙとして選択される。上記ｂの値が最も小さいということは、再符号化による情報損失が最も小さいということである。これは、利用者数が最も少ない駅を利用した個人の個人情報が、利用者数が多い駅を利用した個人の個人情報よりも価値が高いという考えに基づいている。すなわち、図９の例によれば、ｋ−匿名化を実現しつつ、情報の損失が少ない匿名改札入退場テーブル１３３を作成することができる。
【００９４】
図９の例では、前述したように、損失する情報エントロピーが、再符号化対象を選択するための指標として採用されているが、特にこれに限る必要はない。例えば、地理上の距離の近さが指標とされてもよいし、利用頻度（利用者数）の和がｋにどれだけ近いかが指標とされてもよい。
【００９５】
以上のように、本実施例に係る計算機１００の１つの特徴は、時刻を時区間化する方法と隣駅だけ再符号化を行う位置匿名化方法を有することにある。複数ある隣駅から再符号化をする駅を選択する際には、何らかの指標が用いられる。図９を参照して説明したように、損失する情報エントロピーが指標として用いられれば、利用頻度の小さい駅同士が再符号化される可能性が高くなるため、過度の再符号化を避けた有用性の高い匿名改札入退場テーブル１３３を生成することができる。
【００９６】
また、本実施例によれば、乗車・降車を考慮した個人情報匿名化を行うことができる。
【００９７】
なお、計算機１００の実現する図６〜図９の動作の例では、以下のような方法で匿名性を破られてしまう可能性もある。図１０Ａのような駅隣接関係があり、駅Ｂの近くに住んでいるような場合には、ある１日の改札入退場履歴を参照した場合、最初に改札を入場した駅と最後に改札を退場した駅は同一にＢである場合が多い。図１０Ｂは、当該個人のある１日の改札入退場履歴を図６〜図９の動作の例で匿名化を行った例であるが、攻撃者は前述の前提知識により、図１０Ｂのデータだけから、｛Ａ，Ｂ｝と｛Ｂ，Ｃ｝の積集合を取って、当該個人の利用駅は駅Ｂに違いないと予測することができる。このリスクは、予測開示リスクと呼ばれ、図６〜図９の動作では回避したいリスクの対象とはなっていないものである。そこで、この予測開示リスクを回避したい場合に、どのように動作を変更すれば良いかの一例を示す。
【００９８】
まず、図８の動作例において、位置匿名化部１２２は、Ｓ８０２のループを行わず、全ての時区間のレコードをＤとする。Ｓ８０４では、位置匿名化部１２２は、全時区間での駅頻度と、（時区間、駅）のタプルでの駅頻度を両方取得する。また、Ｓ８０５の条件判定は、「頻度がｋ件未満の（時区間、駅）のタプルがある」である。Ｓ８０６では、「頻度がｋ件未満の（時区間、駅）のタプルがある駅Ｘをランダムに１つ取得する」という処理が行われる。また、図９の動作例では、入力のＣＡＮＤ内各駅の頻度と駅Ｘの頻度が、Ｓ８０４で取得した全時区間での駅頻度とされる。
【００９９】
以上の変更により、全ての時区間で、匿名化前の駅が同じであれば、それを全く同一の駅に再符号化することができる。例えば、図１０Ｂの例では、何れも駅｛Ａ，Ｂ，Ｃ｝に再符号化される。従って、前述の予測開示リスクをも回避する匿名化が可能となる。
【実施例２】
【０１００】
以下、本発明の実施例２を説明する。その際、実施例１との相違点を主に説明し、実施例１との共通点については説明を省略或いは簡略する。具体的には、例えば、実施例２を説明する場合、上述の実施例１と重複する構成に対しては同じ符号を付与して説明を省略する。また、実施例１と同じ動作に対しては、同じ符号を付与して説明を省略する。
【０１０１】
実施例２は、異なる路線の駅とは再符号化を行わないことにより、実際に改札入退場を行った路線を保存することを１つの特徴とする。
【０１０２】
図１１は、本発明の実施例２に係る個人情報匿名化装置が適用された計算機の構成例を示す。以下の説明でも実施例１と同様に、「入退場非区別方式」と「入退場区別方式」を説明する。それぞれの方式で別個の処理を持つ場合には明確にその旨を記す。特に方式を断らない場合には、両方式で共通であることを意味する。
【０１０３】
ＣＰＵ１０１は、メモリ１０２上にプログラム１１５１をロードし、実行することにより、時区間化部１２１及び位置匿名化部１１２１並びに路線探索部１１２２を実現する。
【０１０４】
路線探索部１１２２は、改札入退場テーブル１３２を入力とし、各個人の改札の入場時刻、入場駅のタプル、および該個人の直後の改札退場時刻、退場駅のタプルをセットにして、入場駅で乗車した路線および退場駅で降車した路線を算出する。路線探索部１１２２は、改札入退場テーブル１３２の各レコードに、この路線を付与して出力し、時区間化部１２１の入力に渡す。なお、路線探索部１１２２の実現には、既存の経路探索技術（例えば、Ｗｅｂ上で提供されている経路探索サービスに従う技術）をそのまま利用することができる。
【０１０５】
図１３は、路線探索部１１２２の出力例を示す。
【０１０６】
図３に示したような入力の改札入退場テーブル１３２から、路線探索部１１２２は、例えば、ユーザＩＤ「１」の個人が、2010/05/12 07:20:13に駅Ａに入場後、2010/05/12
07:43:10に駅Ｇを退場したという情報を取得する。そして、路線探索部１１２２は、これを既存の経路探索技術を用いて、ａｌｐｈａ路線で乗車、ａｌｐｈａ路線で降車という情報を推定する。さらに、路線探索部１１２２は、この情報を入場、退場それぞれのレコードに対し付与して出力する。この出力された情報の一例が、図１３に示す情報である。なお、乗車路線と降車路線が異なる場合もある。
【０１０７】
時区間化部１２１は、路線探索部１１２２の出力を入力として受け取り、実施例１と同様に、各レコードの時刻のカラムを時区間へと変換したテーブルを出力とし、位置匿名化部１１２１の入力へと渡す。
【０１０８】
位置匿名化部１１２１は、時区間化部１２１から渡されたテーブル、及び路線駅隣接構造テーブル１１３１、及び最小同値件数情報１３４を入力とする。入退場非区別方式の場合には、位置匿名化部１１２１は、任意の時区間、任意の路線上の任意の駅に存在した総人数が０（又はｋ以上）になるように駅を再符号化する。入退場区別方式の場合には、位置匿名化部１１２１は、任意の時区間に任意の路線上の任意の駅に入場した総人数、及び、任意の時区間に任意の路線上の任意の駅から退場した総人数が、それぞれ０（又はｋ以上）になるように駅を再符号化する。このとき、再符号化を行う駅同士は、何れも同一路線上の駅に限定される。位置匿名化部１２２は、以上の結果を匿名改札入退場テーブル１３３に出力する。図１４は、実施例２での匿名化により生成された匿名改札入退場テーブル１３３の一例を示しているが、匿名化後の駅が示す本来の駅がいずれも同じ路線であることがわかる。なお、このテーブル１３３が表す情報が、出力装置１０５を介して出力されてもよい。
【０１０９】
図１２Ａは、路線駅隣接構造テーブル１１３１の構成例を示す。
【０１１０】
図２に示した駅隣接構造テーブル１３１との違いは、駅と駅を結ぶ線路をどの路線が走るかを表す路線のカラムが増えている点である。図１２Ａでは、路線駅隣接構造テーブル１１３１は、図１２Ｂに示す路線構造１２００に対応する。具体的には、図１２Ａに示す路線駅隣接構造テーブル１１３１によれば、路線ａｌｐｈａが、Ａ−Ｂ−Ｃ−Ｊ−Ｋ−Ｇ−Ｌ−Ｍと構成されていることがわかり、同様に路線ｂｅｔａは、Ｃ−Ｄ−Ｅ−Ｆ−Ｇ−Ｈ−Ｉ−Ｃという環状線になっていることがわかる。なお、同一駅間を異なる路線が走る場合には、例えば(Ｎ,Ｏ,ｇａｍｍａ)、（Ｎ,Ｏ,ｄｅｌｔａ)という２つのレコードで、駅Ｎと駅Ｏの間に２つの路線ｇａｍｍａ、ｄｅｌｔａが走っていることを表すことができる。
【０１１１】
なお、路線駅隣接構造テーブル１１３１の構造は、必ずしも図１２Ａに示す構造に限られない。グラフ構造には様々な表現形式が存在し、実際の駅の隣接関係とその間を走る路線を定義できるものであれば、その何れでも良い。
【０１１２】
次に、図１５は、実施例２に係る計算機１００が実行する処理の全体の流れの一例を示す。
【０１１３】
まず、Ｓ１５０１で、路線探索部１１２２が、改札入退場テーブル１３２の各レコードの乗車又は降車の路線を推定する。なお、この推定は、前述したように、既存技術で良いので、詳細な説明を省略する。路線探索部１１２２は、改札入退場テーブル１３２の各レコードに推定路線情報（各レコードに登録されている駅の推定された路線を表す情報）が付加されたテーブルを出力する。
【０１１４】
次に、Ｓ１５０２で、時区間化部１２１が、路線探索部１１２２が出力したテーブルを入力とし、入力のテーブルの時刻のカラムを時区間へと変換する。Ｓ１５０２の詳細については、Ｓ７０２で改札入退場テーブル１３２を取得するのではなく、路線探索部１１２２の出力を取得する部分が異なる以外は、実施例１と同様なので、説明を省略する。
【０１１５】
次に、Ｓ１５０３で、位置匿名化部１１２１が、下記の処理、
（ａ）時区間化部１２１の出力と、路線駅隣接構造テーブル１１３１と、最小同値件数情報１３４とを参照する、
（ｂ）入退場非区別方式の場合には、同一路線の同一の駅５０２及び時区間５０３の組合せを含んだタプル（レコード）に対応する異なる個人の数がｋ以上（最小同値件数４０１以上）になるように駅３０２を再符号化する、
（ｃ）入退場区別方式の場合には、同一路線の同一の駅５０２、時区間５０３及び入退場５０４の組合せを含んだタプル（レコード）に対応する異なる個人の数がｋ以上（最小同件数４０１以上）になるように駅３０２を再符号化する、
（ｄ）上記（ｂ）又は（ｃ）の結果に従う駅５０２（駅３０２が再符号化されることにより得られた情報）と、それに対応するユーザＩＤ５０１、時区間５０３及び入退場５０４を、匿名改札入退場テーブル１３３に格納する、
を行う。
【０１１６】
図１６は、図１５のＳ１５０３の詳細な流れの一例を示す。図１６の各ステップを位置匿名化部１１２１が行う。図１６に示した例は、Ｓ６０２の詳細とほとんど同じであるから、動作を異とするステップのみ、異なるステップ番号を付与し、その説明を行う。
【０１１７】
Ｓ１６０１では、位置匿名化部１１２１は、入退場非区別方式では、Ｓ１５０２から入力として渡されたレコード集合を、同じ時区間を持つレコード集合に分割し、分割した各レコード集合Ｅに対して以下のループ処理を行う。入退場区別方式では、位置匿名化部１１２１は、同じ時区間と入退場のタプルを持つレコード集合に分割し、分割した各レコード集合Ｅに対して以下のループ処理を行う。
【０１１８】
Ｓ１６０２では、位置匿名化部１１２１は、Ｅに含まれるレコードを路線ごとに分割し、その各々のレコード集合Ｄに対して、以降のループ処理を行う。
【０１１９】
Ｓ１６０３では、位置匿名化部１１２１は、Ｓ１６０２で選択した路線に関する駅隣接構造を、路線駅隣接構造テーブル１１３１からメモリ１０２にロードする。
【０１２０】
以上のように、図８の処理例を変更すれば、Ｓ１５０３の１つの処理例を実現することができる。
【０１２１】
図１７は、図１５のＳ１５０３の詳細な流れの別の一例を示す。図１７の各ステップを位置匿名化部１１２１が行う。図１７の例では、図８及び図１６と同じステップには、同一のステップ番号が付与されている。図８及び図１６と異なるステップを主に説明する。
【０１２２】
図１２Ａに示したテーブルから、路線の構造として、図１８Ａに示す直線（Ａ−Ｂ−Ｃ−Ｄ−Ｅと直線的に移動する通常の路線）と、図１８Ｂに示す環状線（Ａ−Ｂ−Ｃ−Ｄ−Ｅ−Ｆ−Ａと周回的に移動する環状線）とのうちのいずれかが特定される。
【０１２３】
位置匿名化部１１２１は、Ｓ１６０３で処理中の路線の駅隣接関係と、Ｓ８０４で各駅の利用頻度とを取得した後、この駅隣接関係及び利用頻度を利用して、Ｈｕ−Ｔｕｃｋｅｒ木を生成する（Ｓ１７０１）。この符号木の構成方法として、例えば、文献「D.E.  Knuth,  “The  Art  of  Computer  Programming:  Volume  3  Sorting  and  Searching,”  Addison-Wesley,  pp.439〜444,  1973」に記載の方法を採用することができる。Ｈｕ−Ｔｕｃｋｅｒ木は、全順序関係を保存した２分木を生成するアルゴリズムである。図１８Ａに示した直線の場合には、位置匿名化部１１２１は、その直線の一端の駅から順に他端の駅までを全順序として捉える。どちらの端を先頭にするかについては、アルゴリズムは依存しない。例えば、図１８Ａの例では、Ａ→Ｂ→Ｃ→Ｄ→Ｅという順序とする。図１８Ｂに示した環状線場合には、全順序ではなく、巡回的な順序となっているが、Ｈｕ−Ｔｕｃｋｅｒ木の構成アルゴリズムでは、隣接関係の判定のみしか行われないため、問題なく実行可能である。
【０１２４】
次に、位置匿名化部１１２１は、構成したＨｕ−Ｔｕｃｋｅｒ木の各内部節点に、ラベルと頻度とを付与する（Ｓ１７０２）。具体的には、例えば、ラベルは、孫にあたる葉（実際の駅）すべてを列挙したものとする。頻度は、孫にあたる葉すべての頻度の和とする。
【０１２５】
図１９Ａは、Ｓ１７０１及びＳ１７０２で構成したＨｕ−Ｔｕｃｋｅｒ木の例を示す。
【０１２６】
図１９Ａにおいて、丸で記された節点１９０１が駅に相当し、図の破線は、Ａ−Ｂ−Ｃ−Ｄ−Ｅという路線構造を示す。例えば、図１９Ｂのような頻度情報がＳ８０４で取得された場合、Ｈｕ−Ｔｕｃｋｅｒ木の構造は、図１９Ａに記したような木となる。なお、Ａ，Ｂ，Ｃ，Ｄ，Ｅ間を直接結ぶ破線は木の枝ではない。四角で表された節点１９０２が、内部節点である。Ｓ１７０２でラベルと頻度を内部節点に付与する際には、例えば、節点１９０２のように、孫にあたる葉を並べた情報｛Ａ，Ｂ，Ｃ｝をラベルとし、葉Ａ，Ｂ，Ｃの頻度の和１０を頻度とする。また、｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝のように、再符号化された場合に最も曖昧になり、頻度が最大となる内部節点を根と呼ぶ。
【０１２７】
次に、位置匿名化部１１２１は、作成したＨｕ−Ｔｕｃｋｅｒ木上で、どの駅をどの内部節点に再符号化するかを決定し（Ｓ１７０３）、Ｄに含まれる各レコードの駅を決定された対応にしたがって再符号化する（Ｓ１７０４）。具体的には、例えば、位置匿名化部１１２１は、Ｓ１７０３で再符号化対象の節点をマークし、Ｓ１７０４では、葉から親をたどることで初めて再符号化対象とマークされた節点へと再符号化する。なお、葉が再符号化対象である場合には、再符号化は行われない。
【０１２８】
図２０は、図１７のＳ１７０３（作成したＨｕ−Ｔｕｃｋｅｒ木上での再符号化対応を決定する処理）の詳細の流れの一例を示す。図２０の各ステップを位置匿名化部１１２１が行う。
【０１２９】
まず、位置匿名化部１１２１は、スタックＳを初期化し、入力のＨｕ−Ｔｕｃｋｅｒ木の根にあたる節点をＳに入れる（Ｓ２００１）。スタックは、プッシュとポップと呼ばれる操作が可能な配列に類したデータ構造で、プッシュとは配列の末尾にデータを挿入する操作であり、ポップとは配列の末尾のデータを取り出し、配列から削除する操作である。
【０１３０】
次に、位置匿名化部１１２１は、Ｓが空であるかどうかの条件判定を行う（Ｓ２００２）。Ｓが空である場合には（Ｓ２００２：Ｙｅｓ）、処理が終了する。
【０１３１】
Ｓ２００２で、Ｓが空でないと判定されれば（Ｓ２００２：Ｎｏ）、位置匿名化部１１２１は、Ｓから節点をポップし、これをｎとおく（Ｓ２００３）。
【０１３２】
次に、位置匿名化部１１２１は、ｎが葉であるかどうかの条件判定を行う（Ｓ２００４）。
【０１３３】
Ｓ２００４でｎが葉ではないと判定されれば（Ｓ２００４：Ｎｏ）、位置匿名化部１１２１は、ｎの持つ２つの子がいずれも、０と同値か、最小同値件数４０１以上、即ちｋ以上の頻度を持つかどうかを判断する（Ｓ２００５）。
【０１３４】
Ｓ２００４でｎが葉であると判定された場合（Ｓ２００４：Ｙｅｓ）、または、Ｓ２００５でｎの少なくとも１つの子が正でｋ未満の頻度を有する場合には（Ｓ２００５：Ｎｏ）、位置匿名化部１１２１は、節点ｎを再符号化対象としてフラグを付け（Ｓ２００７）、Ｓ２００２の条件判定に戻る。
【０１３５】
Ｓ２００５で、ｎの２つの子がいずれも０と同値か、ｋ以上の頻度を持つ場合には（Ｓ２００５：Ｙｅｓ）、位置匿名化部１１２１は、正の頻度を持つｎの子を全てＳにプッシュし（Ｓ２００６）、Ｓ２００２の条件判定に戻る。
【０１３６】
以上のように、実施例２の１つの特徴は、乗車した路線と降車した路線を保存することである。これによって、匿名改札入退場データ１３３を用いて分析や経路推定を行った場合にも、正確に乗車した路線を推定することが可能である。
【０１３７】
また、図１７で示したＳ１５０３の実現方法は、Ｈｕ−Ｔｕｃｋｅｒ木を用いており、Ｈｕ−Ｔｕｃｋｅｒ木は頻度の小さいものを木の深い階層に、頻度の大きい物を木の浅い階層に配置する特徴を持つため、過度の再符号化を避けた有用性の高いデータを生成できることが期待できる。
【０１３８】
なお、実施例１の最後に説明したような予測開示リスクも、実施例２においても同様の処理の変更で回避することが可能である。
【実施例３】
【０１３９】
以下、本発明の実施例３を説明する。その際、実施例１との相違点を主に説明し、実施例１との共通点については説明を省略或いは簡略する。具体的には、例えば、実施例３を説明する場合、上述の実施例１と重複する構成に対しては同じ符号を付与して説明を省略する。また、実施例１と同じ動作に対しては、同じ符号を付与して説明を省略する。
【０１４０】
実施例３（及び後述の実施例４）では、匿名化される個人情報は、定期券のマスタテーブルに記録されている個人情報（例えば、利用者が利用する区間の一端のノードと他端のノードとを表す情報を含んだ情報）である。
【０１４１】
実施例３では、定期券のマスタテーブルの匿名化が行われる。実施例３では、実施例２で行ったような路線情報の保存を行われず、実施例１と同様の手法が行われる。
【０１４２】
図２１は、本発明の実施例３に係る個人情報匿名化装置が適用された計算機の構成例を示す。
【０１４３】
ＣＰＵ１０１は、メモリ１０２上にプログラム２１５１をロードし、実行することにより、位置匿名化部２１２１を実現する。
【０１４４】
位置匿名化部２１２１は、駅隣接構造テーブル１３１と定期マスタテーブル２１３１、及び最小同値件数情報１３４を入力とする。さらに、位置匿名化部２１２１は、後に説明する定期マスタテーブル２１３１を、テーブル中に出現する何れの駅も、少なくとも最小同値件数情報１３４に格納された値ｋ以上の人数が利用していることになるように駅を再符号化し、その結果を匿名定期マスタテーブル２１３２に出力する。なお、位置匿名化部２１２１は、出力装置１０５を介して処理結果を出力してもよい。
【０１４５】
図２２は、定期マスタテーブル２１３１の一例を示す。
【０１４６】
定期マスタテーブル２１３１は複数のレコードを有する。各レコードは、ユーザＩＤ３０１と、駅１（２２０１）と、駅２（２２０２）という情報を含む。１つのレコードは、そのレコード内のユーザＩＤ３０１から識別される個人が、駅１（２２０１）が表す駅から駅２（２２０２）が表す駅までの定期券を所持していることを意味する。図２２の例では、１人の個人が１つの定期券しか所持していないような例となっているが、必ずしもその限りでない。例えば、定期マスタテーブル２１３１の各レコードは、通過駅を表す情報として、駅ｍ（ｍは３以上の整数）という情報を含んでも良い。
【０１４７】
また、上述の定期マスタテーブル２１３１内の情報は予め格納されている。
【０１４８】
図２３は、匿名定期マスタテーブル２１３２の一例を示す。
【０１４９】
匿名定期マスタテーブル２１３２は、定期マスタテーブル２１３１が曖昧化されたテーブルである。匿名定期マスタテーブル２１３２のレコード（以下、匿名レコード）は、定期マスタテーブル２１３１のレコード（以下、通常レコード）に１対１で対応している。
【０１５０】
ｎ番目の匿名レコード内のユーザＩＤ５０１は、ｎ番目の通常レコード内のユーザＩＤ３０１に一致する。なお、本実施例では、同一の個人であれば、ユーザＩＤ５０１とユーザＩＤ３０１は同一であるが、匿名性を高めるために、ユーザＩＤ５０１として、ユーザＩＤ３０１と１対１に対応する別のユーザＩＤが採用されてもよい。
【０１５１】
ｎ番目の匿名レコードの駅１（２３０１）は、ｎ番目の通常レコードの駅１（２２０１）が再符号化された情報であり、ｎ番目の匿名レコードの駅２（２３０２）は、ｎ番目の通常レコードの駅２（２２０２）が再符号化された情報である。必ずしも、駅１（２３０１）が駅１（２２０１）を再符号化したもので、駅２（２３０２）が駅２（２２０２）を再符号化したものである必要はなく、駅１（２３０１）が駅２（２２０２）を、駅２（２３０２）が駅１（２２０１）をそれぞれ再符号化したものであってもよい。しかし、説明の簡単のために、本実施例では駅１（２３０１）が駅１（２２０１）を、駅２（２３０２）が駅２（２２０２）をそれぞれ再符号化したものであるとする。
【０１５２】
図２４は、実施例３に係る計算機１００が実行する処理の全体の流れの一例を示す。本実施例では、位置匿名化部２１２１が匿名化処理を行うのみであるから、図２４は、位置匿名化部２１２１の処理の流れの一例を示す。即ち、図２４に示す各ステップを位置匿名化部２１２１が行う。また、図２４では図８と共通するステップが多いため、それらのステップには同一の番号が付与され、ここでは説明を省略する。
【０１５３】
Ｓ２４０１では、位置匿名化部２１２１は、定期マスタテーブル２１３１を取得し、これをＤとする。
【０１５４】
Ｓ２４０２では、位置匿名化部２１２１は、Ｄから各駅の出現頻度を取得する。ただしここで各駅の出現頻度とは、駅１（２２０１）または駅２（２２０２）のいずれかが各駅と一致するユーザの総数を指す。
【０１５５】
Ｓ２４０３では、位置匿名化部２１２１は、Ｂを匿名定期マスタテーブル２１３２に出力し、処理を終了する。
【０１５６】
以上のように、実施例３の１つの特徴は、実施例１及び２とは異なり、定期券のマスタテーブルを対象として匿名化を行う点である。さらに、必ず隣接する駅とのみ再符号化を行うという特徴もある。その際に利用する指標は、実施例１と同様のものを用いることができ、情報エントロピーを指標として用いる場合に、は実施例１に記したような性質を持つ結果を得ることができる。
【実施例４】
【０１５７】
以下、本発明の実施例４を説明する。実施例４もまた、定期券のマスタテーブルの匿名化を行うものである。実施例４では、実施例２で行ったように路線情報の保存を行う手法について説明する。以下、実施例４を説明する場合、上述の実施例１、２、３と重複する構成、動作に対しては同じ符号を付与して説明を省略する。
【０１５８】
図２５は、本発明の実施例４に係る個人情報匿名化装置が適用された計算機の構成例を示す。
【０１５９】
ＣＰＵ１０１はメモリ１０２上にプログラム２５５１をロードし、実行することにより、位置匿名化部２５５１及び路線探索部２５２２を実現する。
【０１６０】
路線探索部２５２２は、定期マスタテーブル２１３１を入力とし、各定期券保持者の定期区間を示す２つの駅の情報から、両駅を乗車または降車する路線を算出し、定期マスタテーブル２１３１の各レコードにこの路線を付与して出力し、位置匿名化部２５２１の入力に渡す。この場合、路線探索部２５２２の実現には、既存の経路探索技術をそのまま利用することができる。あるいは、定期券があらかじめ路線を指定している場合には、別途その情報がストレージ１０３に記録されているか、外部の計算機（図示略）に保存されていることが考えられる。このような場合には、その情報から２つの駅がそれぞれ属する２つの路線が推定されても良い。
【０１６１】
図２６は、路線探索部２５２２の出力の一例を示す。
【０１６２】
路線探索部２５２２は、図２２に示した定期マスタテーブル２１３１から、例えばユーザＩＤが１の駅Ａと駅Ｇ間の定期を所持している情報を参照して、駅Ａで乗車または降車時にはａｌｐｈａ路線を使用、駅Ｇで乗車または降車時にはａｌｐｈａ路線を使用という情報を推定する。さらに、路線探索部２５２２は、この情報を駅１、駅２それぞれの駅に関連付けて付与し、出力する。すなわち、路線探索部２５２２から出力される情報は、定期マスタテーブル２１３１に路線情報が付加されたテーブル（駅１及び駅２のそれぞれについて推定された路線を表す情報が付加されたテーブル）である。
【０１６３】
位置匿名化部２５２１は、路線探索部２５２２から渡されたテーブルと、路線駅隣接構造テーブル１１３１と、最小同値件数情報１３４とを入力とする。さらに、位置匿名化部２５２１は、定期マスタテーブル２１３１を、テーブル中に出現する何れの駅も、少なくとも最小同値件数情報１３４に格納された値ｋ以上の人数が利用していることになるように、かつ再符号化後の駅に集合値として含まれるいずれの駅も本来の駅と同一の路線上の駅であるように駅を再符号化し、その結果を匿名定期マスタテーブル２１３２に出力する。なお、位置匿名化部２５２１は、出力装置１０５を介して処理結果を出力してもよい。
【０１６４】
図２７は、実施例４に係る計算機１００が実行する処理の全体の流れの一例を示す。
【０１６５】
まず、路線探索部２５２２が、定期マスタテーブル２１３１を入力とし、定期区間を示す両端の駅の利用路線を推定し、図２６に示したようなテーブルを作り、位置匿名化部２５２１に渡す（Ｓ２７０１）。次に、位置匿名化部２５２１が、駅を再符号化し、匿名化を達成する（Ｓ２７０２）。
【０１６６】
図２８は、図２７のＳ２７０２の詳細な流れの一例を示す。図２８の各ステップを位置匿名化部２５２１が行う。なお、図８、図１６と同一のステップについては同一の番号が付与され、説明を省略する。図２８の処理例は、実施例２で図１６に示したＳ１５０３の処理例を定期マスタ用に修正した例である。
【０１６７】
Ｓ２８０１では、位置匿名化部２５２１は、Ｓ２７０１の出力として路線探索部２５２２から渡された入力テーブルをＥとする。
【０１６８】
Ｓ２８０２では、位置匿名化部２５２１は、Ｅの含む各路線を列挙し、各路線に対して別個にループ処理を行う。ループ処理を行う際には、処理を行う路線の駅全体の集合をＤとする。
【０１６９】
Ｓ２８０３では、位置匿名化部２５２１は、Ｄに含まれる各駅の頻度をＥから取得する。この際、各駅の頻度として計上するのは、駅１または駅２のいずれかが各駅と一致するユーザの総数である。ただし、一致する駅であっても、利用路線が異なるもの（Ｅから取得できる路線情報とループで処理中の路線が異なるもの）は計上しない。
【０１７０】
Ｓ２８０４では、位置匿名化部２５２１は、ループで処理中の路線でＥに含まれる駅Ｘまたは駅Ｙのものを、駅｛Ｘ，Ｙ｝に変換する。なお、駅Ｘも駅Ｙも処理中の路線上の駅であり、同じであるはずだから、路線に関しては変換を行う必要がない。
【０１７１】
Ｓ２８０５では、位置匿名化部２５２１は、Ｄから駅Ｘ、及び駅Ｙを消去し、代わりに駅｛Ｘ，Ｙ｝を追加する。
【０１７２】
Ｓ２８０６では、位置匿名化部２５２１は、Ｅを匿名定期マスタテーブル２１３２に格納する。なお、本例では、格納時に列「路線１」と列「路線２」は取り除く。
【０１７３】
図２９は、図２７のＳ２７０２の詳細な流れの別の一例を示す。なお、図２９の全てのステップは、図８、図１６、図１７、図２８と同一であり、これらのステップについては同一の番号を付与し、説明を省略する。図２９の処理例は、実施例２で図１７に示したＳ１５０３の処理例を定期マスタ用に修正した例である。
【０１７４】
以上のように、実施例４の１つの特徴は、実施例３と同様に、定期券のマスタテーブルを対象として匿名化を行う点である。実施例３との相違点は、再符号化後の匿名定期マスタテーブルに含まれる駅タプルから推定される利用路線が、再符号化前のデータから推定される利用路線と一致する点である。
【０１７５】
以上、本発明の幾つかの実施例を説明したが、これらは、本発明の説明のための例示であって、本発明の範囲をこれらの実施例にのみ限定する趣旨ではない。すなわち、本発明は、他の種々の形態でも実施する事が可能である。例えば、上記した実施例は本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施例の構成の一部を他の実施例の構成に置き換えることが可能であり、また、ある実施例の構成に他の実施例の構成を加えることも可能である。また、各実施例の構成の一部について、他の構成の追加・削除・置換をすることが可能である。
【０１７６】
また、上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行することによりソフトウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（Solid State Drive）等の記録装置、または、ＩＣカード、ＳＤカード、ＤＶＤ等の記録媒体に置くことができる。
【０１７７】
また、制御線や情報線は説明上必要と考えられるものを示しており、製品上必ずしも全ての制御線や情報線を示しているとは限らない。実際には殆ど全ての構成が相互に接続されていると考えてもよい。
【符号の説明】
【０１７８】
１００：計算機、１０１：ＣＰＵ、１０２：メモリ、１２１：時区間化部、１２２：位置匿名化部、１０３：ストレージ、１３１：駅隣接構造テーブル、１３２：改札入退場テーブル、１３３：匿名改札入退場テーブル、１３４：最小同値件数情報、１５１：プログラム、１０４：入力装置、１０５：出力装置、１０６：通信装置、１０７：内部通信線、１１２１：位置匿名化部、１１２２：路線探索部、１１３１：路線駅隣接構造テーブル、１１５１：プログラム、２１２１：位置匿名化部、２１３１：定期マスタテーブル、２１３２：匿名定期マスタテーブル、２１５１：プログラム、２５２１：位置匿名化部、２５２２：路線探索部、２５５１：プログラム
【図１】
2012079205.tif 000004
【図２】
2012079205.tif 000005
【図３】
2012079205.tif 000006
【図４】
2012079205.tif 000007
【図５】
2012079205.tif 000008
【図６】
2012079205.tif 000009
【図７】
2012079205.tif 000010
【図８】
2012079205.tif 000011
【図９】
2012079205.tif 000012
【図１０】
2012079205.tif 000013
【図１１】
2012079205.tif 000014
【図１２】
2012079205.tif 000015
【図１３】
2012079205.tif 000016
【図１４】
2012079205.tif 000017
【図１５】
2012079205.tif 000018
【図１６】
2012079205.tif 000019
【図１７】
2012079205.tif 000020
【図１８】
2012079205.tif 000021
【図１９】
2012079205.tif 000022
【図２０】
2012079205.tif 000023
【図２１】
2012079205.tif 000024
【図２２】
2012079205.tif 000025
【図２３】
2012079205.tif 000026
【図２４】
2012079205.tif 000027
【図２５】
2012079205.tif 000028
【図２６】
2012079205.tif 000029
【図２７】
2012079205.tif 000030
【図２８】
2012079205.tif 000031
【図２９】
2012079205.tif 000032