匿名データ生成装置、匿名データの生成方法およびプログラム
【課題】データの匿名化に関し、ユーザの行動履歴のような複数の属性とその依存関係（あるいは順序性）を有するようなデータに対しても適用可能な匿名データ生成装置、匿名データの生成方法およびプログラムを提供する。
【解決手段】グラフ作成部が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成し、グラフマージ部が、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。そして、削除処理部が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除する。
【解決手段】グラフ作成部が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成し、グラフマージ部が、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。そして、削除処理部が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザの行動履歴を匿名化するための匿名データ生成装置、匿名データの生成方法およびプログラムに関し、特に、ユーザの行動履歴のような複数の属性とその依存関係（あるいは順序性）を有するようなデータに対しても適用可能な匿名データ生成装置、匿名データの生成方法およびプログラムに関する。
【背景技術】
【０００２】
従来、データを公開する場合や解析に使う場合において、データの所有者のプライバシを保護するため、データの変形を行う必要がある。そこで、従来方式では、Ｋ−匿名性などの定義に基づいてデータを変形してデータ所有者を特定できない匿名データを出力する手法が提案されていた（例えば、非特許文献１参照。）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｂ．Ｆｕｎｇ ａｎｄ Ｋ．Ｗａｎｇ ａｎｄ Ｐ．Ｙｕ， “Ｔｏｐ−ｄｏｗｎ ｓｐｅｃｉａｌｉｚａｔｉｏｎ ｆｏｒ ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖａｔｉｏｎ“ Ｐｒｏｃ ｏｆ ＩＣＤＥ ２００５ ｐｐ．２０５−２１６
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記の従来の技術では、ある種の一般的なデータの匿名化は可能であったが、ユーザの行動履歴のような複数の属性とその依存関係（あるいは順序性）を有するようなデータに対しては、その技術をそのまま適用できないという問題があった。
【０００５】
そこで、本発明は、上述の課題に鑑みてなされたものであり、データの匿名化に関し、ユーザの行動履歴のような複数の属性とその依存関係（あるいは順序性）を有するようなデータに対しても適用可能な匿名データ生成装置、匿名データの生成方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、上記の課題を解決するために、以下の事項を提案している。なお、理解を容易にするために、本発明の実施形態に対応する符号を付して説明するが、これに限定されるものではない。
【０００７】
（１）本発明は、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成するグラフ作成手段（例えば、図１のグラフ作成部１１０に相当）と、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形するグラフマージ手段（例えば、図１のグラフマージ部１２０に相当）と、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する削除処理手段（例えば、図１の削除処理部１３０に相当）と、を備えたことを特徴とする匿名データ生成装置を提案している。
【０００８】
この発明によれば、グラフ作成手段は、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成する。グラフマージ手段は、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。削除処理手段は、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除する。つまり、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形し、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除するため、特定の人物の行動履歴を抽出することができない。
【０００９】
（２）本発明は、（１）の匿名データ生成装置について、前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とする匿名データ生成装置を提案している。
【００１０】
この発明によれば、グラフが、各ノード間を行動履歴に対応した矢印で結合する有向グラフである。すなわち、有向グラフを用いることにより、複数の属性間の依存関係や順序性を明確に表現することができる。
【００１１】
（３）本発明は、（２）の匿名データ生成装置について、前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除することを特徴とする匿名データ生成装置を提案している。
【００１２】
この発明によれば、削除処理手段は、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除する。したがって、複数のユーザの行動履歴を集計したとしても、全体の傾向さえも把握することができない。
【００１３】
（４）本発明は、グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法であって、前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成する第１のステップ（例えば、図５のステップＳ１０１に相当）と、前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップ（例えば、図５のステップＳ１０２に相当）と、前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップ（例えば、図５のステップＳ１０３に相当）と、を備えたことを特徴とする匿名データの生成方法を提案している。
【００１４】
この発明によれば、グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成し、グラフマージ手段が、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。そして、削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除する。したがって、特定の人物の行動履歴を抽出することができない。
【００１５】
（５）本発明は、（４）の匿名データの生成方法について、前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とする匿名データの生成方法を提案している。
【００１６】
この発明によれば、グラフが、各ノード間を行動履歴に対応した矢印で結合する有向グラフである。すなわち、有向グラフを用いることにより、複数の属性間の依存関係や順序性を明確に表現することができる。
【００１７】
（６）本発明は、グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法であって、前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを矢印で結びつけた複数のグラフを作成する第１のステップ（例えば、図１１のステップＳ２０１に相当）と、前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップ（例えば、図１１のステップＳ２０２に相当）と、前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップ（例えば、図１１のステップＳ２０３に相当）と、前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除する第４のステップ（例えば、図１１のステップＳ２０４に相当）と、を備えることを特徴とする匿名データの生成方法を提案している。
【００１８】
この発明によれば、グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成し、グラフマージ手段が、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。そして、削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除し、さらに、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除する。したがって、複数のユーザの行動履歴を集計したとしても、全体の傾向さえも把握することができない。
【００１９】
（７）本発明は、グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法をコンピュータに実行させるためのプログラムであって、前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成する第１のステップ（例えば、図５のステップＳ１０１に相当）と、前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップ（例えば、図５のステップＳ１０２に相当）と、前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップ（例えば、図５のステップＳ１０３に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００２０】
この発明によれば、グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成し、グラフマージ手段が、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。そして、削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除する。したがって、特定の人物の行動履歴を抽出することができない。
【００２１】
（８）本発明は、（７）のプログラムについて、前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とするプログラムを提案している。
【００２２】
この発明によれば、グラフが、各ノード間を行動履歴に対応した矢印で結合する有向グラフである。すなわち、有向グラフを用いることにより、複数の属性間の依存関係や順序性を明確に表現することができる。
【００２３】
（９）本発明は、グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法をコンピュータに実行させるためのプログラムであって、前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを矢印で結びつけた複数のグラフを作成する第１のステップ（例えば、図１１のステップＳ２０１に相当）と、前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップ（例えば、図１１のステップＳ２０２に相当）と、前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップ（例えば、図１１のステップＳ２０３に相当）と、前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除する第４のステップ（例えば、図１１のステップＳ２０４に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００２４】
この発明によれば、グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成し、グラフマージ手段が、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。そして、削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除し、さらに、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除する。したがって、複数のユーザの行動履歴を集計したとしても、全体の傾向さえも把握することができない。
【発明の効果】
【００２５】
本発明によれば、ユーザの行動履歴を匿名化することができ、様々な解析や動向調査に使用することができるという効果がある。したがって、例えば、各ユーザのプライバシを保ったまま、購買履歴を解析しマーケットリサーチを行うといったようなサービスを構築することができるという効果がある。
【図面の簡単な説明】
【００２６】
【図１】本発明の第１の実施形態に係る匿名データ生成装置の構成を示す図である。
【図２】本発明の第１の実施形態に係るグラフの作成を例示した図である。
【図３】本発明の第１の実施形態に係るグラフのマージを例示した図である。
【図４】本発明の第１の実施形態に係るマージしたグラフから所定の要件を満たすノードを削除した場合を例示した図である。
【図５】本発明の第１の実施形態に係る匿名データ生成装置の処理を示す図である。
【図６】本発明の第２の実施形態に係る匿名データ生成装置の構成を示す図である。
【図７】本発明の第２の実施形態に係るグラフの作成を例示した図である。
【図８】本発明の第２の実施形態に係るグラフのマージを例示した図である。
【図９】本発明の第２の実施形態に係るマージしたグラフから所定の要件を満たすノードを削除した場合を例示した図である。
【図１０】本発明の第２の実施形態に係るマージしたグラフから所定の要件を満たすノードを削除した場合を例示した図である。
【図１１】本発明の第２の実施形態に係る匿名データ生成装置の処理を示す図である。
【発明を実施するための形態】
【００２７】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００２８】
＜第１の実施形態＞
図１から図５を用いて、本実施形態に係る匿名データ生成装置について説明する。
【００２９】
＜匿名データ生成装置の構成＞
本実施形態に係る匿名データ生成装置は、図１に示すように、グラフ作成部１１０と、グラフマージ部１２０と、削除処理部１３０とから構成されている。
【００３０】
ここで、グラフ作成部１１０は、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成する。具体的に、図２を用いて説明すると、ユーザＡ（図中、（Ａ）参照）は、自宅からコンビニ、駅Ａ、駅Ｂをたどって学校に行った履歴が、自宅、コンビニ、駅Ａ、駅Ｂ、学校という各ノードを矢印で結んだ有向グラフで示されている。一方、ユーザＢ（図中、（Ｂ）参照）は、自宅から駅Ａ、駅Ｂ、デパートをたどって駅Ｃに行った履歴が、自宅、駅Ａ、駅Ｂ、デパート、駅Ｃという各ノードを矢印で結んだ有向グラフで示されている。ここで、有向グラフを用いることにより、複数の属性間の依存関係や順序性を明確に表現することができる。なお、本実施形態では、有向グラフとして矢印を用いる例を示したが、これに限らず、例えば、点線を右向きの矢印、一点鎖線を左向きの矢印というように、予めルール化して、このような結線を用いてもよい。また、各ノードの名称についても、予めルール化した記号等で表してもよい。
【００３１】
グラフマージ部１２０は、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。具体的に、図２および図３を用いて説明すると、図２のユーザＡの行動履歴を示すグラフとユーザＢの行動履歴を示すグラフとでは、ノードとして、「自宅」、「駅Ａ」、「駅Ｂ」が共通する。グラフマージ部１２０は、この共通ノードを抽出し、重ね合わせ処理を行うことにより、図２に示す２つのグラフを図３に示すような１つのグラフに変形する。
【００３２】
削除処理部１３０は、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、そのノードの下流ノードを削除する。具体的に、Ｋ＝２とした場合の図３および図４を用いて説明すると、ノード「デパート」は、２個以上の分岐がなく、下流ノード「駅Ｃ」が２個以上の分岐を持たないため、図３からノード「駅Ｃ」とノード「デパート」からノード「駅Ｃ」への矢印が削除される。なお、ノード「学校」のように、分岐をもたないノードは、この処理から除外される。これにより、特定の人物の行動履歴を抽出することができなくなる。
【００３３】
＜匿名データ生成装置の処理＞
図５を用いて、本実施形態に係る匿名データ生成装置の処理について説明する。
まず、グラフ作成部１１０が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成する（ステップＳ１０１）。グラフマージ部１２０は、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する（ステップＳ１０２）。そして、削除処理部１３０は、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、そのノードの下流ノードを削除する（ステップＳ１０３）。
【００３４】
以上、説明したように、本実施形態によれば、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形し、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除するため、特定の人物の行動履歴を抽出することができない。
【００３５】
＜第２の実施形態＞
図６から図１１を用いて、本実施形態に係る匿名データ生成装置について説明する。
第１の実施形態においては、特定の人物の行動履歴を抽出することは不可能となるが、複数ユーザの行動履歴を集計した全体の傾向をつかむことはできるという問題がある。この問題を解決するためには、より高度な匿名化が必要である。ここで、高度な匿名化とは、利用者がある行動を取っていたと判明したとき、それ以降の行動履歴の一部分でもＫ以下に絞り込まれるケースをいう。本実施形態では、これを実現する匿名データ生成装置を構築する。
【００３６】
＜匿名データ生成装置の構成＞
本実施形態に係る匿名データ生成装置は、図６に示すように、グラフ作成部１１０と、グラフマージ部１２０と、削除処理部２３０とから構成されている。なお、第１の実施形態と同様の符号を付す構成要素については、同様の機能を有することから、その詳細な説明は、省略する。
【００３７】
削除処理部２３０は、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、そのノードの下流ノードを削除するとともに、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除する。
【００３８】
＜匿名データ生成装置の処理＞
図１１を用いて、本実施形態に係る匿名データ生成装置の処理について説明する。
まず、グラフ作成部１１０が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成する（ステップＳ２０１）。具体的に、図７を用いて説明すると、ユーザＡ（図中、（Ａ）参照）は、自宅からコンビニ、駅Ａ、駅Ｂをたどって学校に行った履歴が、自宅、コンビニ、駅Ａ、駅Ｂ、学校という各ノードを矢印で結んだ有向グラフで示されている。一方、ユーザＢ（図中、（Ｂ）参照）は、自宅から駅Ａ、駅Ｂ、デパートをたどって駅Ｃに行った履歴が、自宅、駅Ａ、駅Ｂ、デパート、駅Ｃという各ノードを矢印で結んだ有向グラフで示されている。ここで、有向グラフを用いることにより、複数の属性間の依存関係や順序性を明確に表現することができる。なお、本実施形態では、有向グラフとして矢印を用いる例を示したが、これに限らず、例えば、点線を右向きの矢印、一点鎖線を左向きの矢印というように、予めルール化して、このような結線を用いてもよい。また、各ノードの名称についても、予めルール化した記号等で表してもよい。
【００３９】
グラフマージ部１２０は、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する（ステップＳ２０２）。具体的に、図７および図８を用いて説明すると、図７のユーザＡの行動履歴を示すグラフとユーザＢの行動履歴を示すグラフとでは、ノードとして、「自宅」、「駅Ａ」、「駅Ｂ」が共通する。グラフマージ部１２０は、この共通ノードを抽出し、重ね合わせ処理を行うことにより、図７に示す２つのグラフを図３に示すような１つのグラフに変形する。
【００４０】
そして、削除処理部２３０は、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、そのノードの下流ノードを削除し（ステップＳ２０３）、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除する（ステップＳ２０４）。具体的に、Ｋ＝２とした場合の図８および図９を用いて説明すると、ノード「デパート」は、２個以上の分岐がなく、下流ノード「駅Ｃ」が２個以上の分岐を持たないため、図８からノード「駅Ｃ」とノード「デパート」からノード「駅Ｃ」への矢印が削除される。なお、ノード「学校」のように、分岐をもたないノードは、この処理から除外される。これにより、特定の人物の行動履歴を抽出することができなくなる。
【００４１】
しかしながら、上記までの処理では、複数ユーザの行動履歴を集計した全体の傾向をつかむことはできるという問題がある。この問題を解決するためには、より高度な匿名化が必要である。そこで、図１０に示すように、分岐を持たないノード（図９のノード「学校」、「デパート」）を除き、２個以上への分岐を持たないすべてのノード（図９のノード「駅Ａ」、ノード「駅Ｂ」）について矢印すべてを削除する。
【００４２】
以上、説明したように、本実施形態によれば、さらに、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除することにより、複数のユーザの行動履歴を集計したとしても、全体の傾向さえも把握することができないことを担保することができる。
【００４３】
なお、匿名データ生成装置の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを匿名データ生成装置に読み込ませ、実行することによって本発明の匿名データ生成装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００４４】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００４５】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００４６】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００４７】
１１０；グラフ作成部
１２０；グラフマージ部
１３０；削除処理部
２３０；削除処理部
【技術分野】
【０００１】
本発明は、ユーザの行動履歴を匿名化するための匿名データ生成装置、匿名データの生成方法およびプログラムに関し、特に、ユーザの行動履歴のような複数の属性とその依存関係（あるいは順序性）を有するようなデータに対しても適用可能な匿名データ生成装置、匿名データの生成方法およびプログラムに関する。
【背景技術】
【０００２】
従来、データを公開する場合や解析に使う場合において、データの所有者のプライバシを保護するため、データの変形を行う必要がある。そこで、従来方式では、Ｋ−匿名性などの定義に基づいてデータを変形してデータ所有者を特定できない匿名データを出力する手法が提案されていた（例えば、非特許文献１参照。）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｂ．Ｆｕｎｇ ａｎｄ Ｋ．Ｗａｎｇ ａｎｄ Ｐ．Ｙｕ， “Ｔｏｐ−ｄｏｗｎ ｓｐｅｃｉａｌｉｚａｔｉｏｎ ｆｏｒ ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖａｔｉｏｎ“ Ｐｒｏｃ ｏｆ ＩＣＤＥ ２００５ ｐｐ．２０５−２１６
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記の従来の技術では、ある種の一般的なデータの匿名化は可能であったが、ユーザの行動履歴のような複数の属性とその依存関係（あるいは順序性）を有するようなデータに対しては、その技術をそのまま適用できないという問題があった。
【０００５】
そこで、本発明は、上述の課題に鑑みてなされたものであり、データの匿名化に関し、ユーザの行動履歴のような複数の属性とその依存関係（あるいは順序性）を有するようなデータに対しても適用可能な匿名データ生成装置、匿名データの生成方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、上記の課題を解決するために、以下の事項を提案している。なお、理解を容易にするために、本発明の実施形態に対応する符号を付して説明するが、これに限定されるものではない。
【０００７】
（１）本発明は、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成するグラフ作成手段（例えば、図１のグラフ作成部１１０に相当）と、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形するグラフマージ手段（例えば、図１のグラフマージ部１２０に相当）と、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する削除処理手段（例えば、図１の削除処理部１３０に相当）と、を備えたことを特徴とする匿名データ生成装置を提案している。
【０００８】
この発明によれば、グラフ作成手段は、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成する。グラフマージ手段は、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。削除処理手段は、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除する。つまり、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形し、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除するため、特定の人物の行動履歴を抽出することができない。
【０００９】
（２）本発明は、（１）の匿名データ生成装置について、前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とする匿名データ生成装置を提案している。
【００１０】
この発明によれば、グラフが、各ノード間を行動履歴に対応した矢印で結合する有向グラフである。すなわち、有向グラフを用いることにより、複数の属性間の依存関係や順序性を明確に表現することができる。
【００１１】
（３）本発明は、（２）の匿名データ生成装置について、前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除することを特徴とする匿名データ生成装置を提案している。
【００１２】
この発明によれば、削除処理手段は、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除する。したがって、複数のユーザの行動履歴を集計したとしても、全体の傾向さえも把握することができない。
【００１３】
（４）本発明は、グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法であって、前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成する第１のステップ（例えば、図５のステップＳ１０１に相当）と、前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップ（例えば、図５のステップＳ１０２に相当）と、前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップ（例えば、図５のステップＳ１０３に相当）と、を備えたことを特徴とする匿名データの生成方法を提案している。
【００１４】
この発明によれば、グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成し、グラフマージ手段が、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。そして、削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除する。したがって、特定の人物の行動履歴を抽出することができない。
【００１５】
（５）本発明は、（４）の匿名データの生成方法について、前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とする匿名データの生成方法を提案している。
【００１６】
この発明によれば、グラフが、各ノード間を行動履歴に対応した矢印で結合する有向グラフである。すなわち、有向グラフを用いることにより、複数の属性間の依存関係や順序性を明確に表現することができる。
【００１７】
（６）本発明は、グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法であって、前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを矢印で結びつけた複数のグラフを作成する第１のステップ（例えば、図１１のステップＳ２０１に相当）と、前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップ（例えば、図１１のステップＳ２０２に相当）と、前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップ（例えば、図１１のステップＳ２０３に相当）と、前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除する第４のステップ（例えば、図１１のステップＳ２０４に相当）と、を備えることを特徴とする匿名データの生成方法を提案している。
【００１８】
この発明によれば、グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成し、グラフマージ手段が、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。そして、削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除し、さらに、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除する。したがって、複数のユーザの行動履歴を集計したとしても、全体の傾向さえも把握することができない。
【００１９】
（７）本発明は、グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法をコンピュータに実行させるためのプログラムであって、前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成する第１のステップ（例えば、図５のステップＳ１０１に相当）と、前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップ（例えば、図５のステップＳ１０２に相当）と、前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップ（例えば、図５のステップＳ１０３に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００２０】
この発明によれば、グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成し、グラフマージ手段が、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。そして、削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除する。したがって、特定の人物の行動履歴を抽出することができない。
【００２１】
（８）本発明は、（７）のプログラムについて、前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とするプログラムを提案している。
【００２２】
この発明によれば、グラフが、各ノード間を行動履歴に対応した矢印で結合する有向グラフである。すなわち、有向グラフを用いることにより、複数の属性間の依存関係や順序性を明確に表現することができる。
【００２３】
（９）本発明は、グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法をコンピュータに実行させるためのプログラムであって、前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを矢印で結びつけた複数のグラフを作成する第１のステップ（例えば、図１１のステップＳ２０１に相当）と、前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップ（例えば、図１１のステップＳ２０２に相当）と、前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップ（例えば、図１１のステップＳ２０３に相当）と、前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除する第４のステップ（例えば、図１１のステップＳ２０４に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００２４】
この発明によれば、グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成し、グラフマージ手段が、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。そして、削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除し、さらに、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除する。したがって、複数のユーザの行動履歴を集計したとしても、全体の傾向さえも把握することができない。
【発明の効果】
【００２５】
本発明によれば、ユーザの行動履歴を匿名化することができ、様々な解析や動向調査に使用することができるという効果がある。したがって、例えば、各ユーザのプライバシを保ったまま、購買履歴を解析しマーケットリサーチを行うといったようなサービスを構築することができるという効果がある。
【図面の簡単な説明】
【００２６】
【図１】本発明の第１の実施形態に係る匿名データ生成装置の構成を示す図である。
【図２】本発明の第１の実施形態に係るグラフの作成を例示した図である。
【図３】本発明の第１の実施形態に係るグラフのマージを例示した図である。
【図４】本発明の第１の実施形態に係るマージしたグラフから所定の要件を満たすノードを削除した場合を例示した図である。
【図５】本発明の第１の実施形態に係る匿名データ生成装置の処理を示す図である。
【図６】本発明の第２の実施形態に係る匿名データ生成装置の構成を示す図である。
【図７】本発明の第２の実施形態に係るグラフの作成を例示した図である。
【図８】本発明の第２の実施形態に係るグラフのマージを例示した図である。
【図９】本発明の第２の実施形態に係るマージしたグラフから所定の要件を満たすノードを削除した場合を例示した図である。
【図１０】本発明の第２の実施形態に係るマージしたグラフから所定の要件を満たすノードを削除した場合を例示した図である。
【図１１】本発明の第２の実施形態に係る匿名データ生成装置の処理を示す図である。
【発明を実施するための形態】
【００２７】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００２８】
＜第１の実施形態＞
図１から図５を用いて、本実施形態に係る匿名データ生成装置について説明する。
【００２９】
＜匿名データ生成装置の構成＞
本実施形態に係る匿名データ生成装置は、図１に示すように、グラフ作成部１１０と、グラフマージ部１２０と、削除処理部１３０とから構成されている。
【００３０】
ここで、グラフ作成部１１０は、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成する。具体的に、図２を用いて説明すると、ユーザＡ（図中、（Ａ）参照）は、自宅からコンビニ、駅Ａ、駅Ｂをたどって学校に行った履歴が、自宅、コンビニ、駅Ａ、駅Ｂ、学校という各ノードを矢印で結んだ有向グラフで示されている。一方、ユーザＢ（図中、（Ｂ）参照）は、自宅から駅Ａ、駅Ｂ、デパートをたどって駅Ｃに行った履歴が、自宅、駅Ａ、駅Ｂ、デパート、駅Ｃという各ノードを矢印で結んだ有向グラフで示されている。ここで、有向グラフを用いることにより、複数の属性間の依存関係や順序性を明確に表現することができる。なお、本実施形態では、有向グラフとして矢印を用いる例を示したが、これに限らず、例えば、点線を右向きの矢印、一点鎖線を左向きの矢印というように、予めルール化して、このような結線を用いてもよい。また、各ノードの名称についても、予めルール化した記号等で表してもよい。
【００３１】
グラフマージ部１２０は、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する。具体的に、図２および図３を用いて説明すると、図２のユーザＡの行動履歴を示すグラフとユーザＢの行動履歴を示すグラフとでは、ノードとして、「自宅」、「駅Ａ」、「駅Ｂ」が共通する。グラフマージ部１２０は、この共通ノードを抽出し、重ね合わせ処理を行うことにより、図２に示す２つのグラフを図３に示すような１つのグラフに変形する。
【００３２】
削除処理部１３０は、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、そのノードの下流ノードを削除する。具体的に、Ｋ＝２とした場合の図３および図４を用いて説明すると、ノード「デパート」は、２個以上の分岐がなく、下流ノード「駅Ｃ」が２個以上の分岐を持たないため、図３からノード「駅Ｃ」とノード「デパート」からノード「駅Ｃ」への矢印が削除される。なお、ノード「学校」のように、分岐をもたないノードは、この処理から除外される。これにより、特定の人物の行動履歴を抽出することができなくなる。
【００３３】
＜匿名データ生成装置の処理＞
図５を用いて、本実施形態に係る匿名データ生成装置の処理について説明する。
まず、グラフ作成部１１０が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成する（ステップＳ１０１）。グラフマージ部１２０は、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する（ステップＳ１０２）。そして、削除処理部１３０は、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、そのノードの下流ノードを削除する（ステップＳ１０３）。
【００３４】
以上、説明したように、本実施形態によれば、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形し、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、ノードの下流ノードを削除するため、特定の人物の行動履歴を抽出することができない。
【００３５】
＜第２の実施形態＞
図６から図１１を用いて、本実施形態に係る匿名データ生成装置について説明する。
第１の実施形態においては、特定の人物の行動履歴を抽出することは不可能となるが、複数ユーザの行動履歴を集計した全体の傾向をつかむことはできるという問題がある。この問題を解決するためには、より高度な匿名化が必要である。ここで、高度な匿名化とは、利用者がある行動を取っていたと判明したとき、それ以降の行動履歴の一部分でもＫ以下に絞り込まれるケースをいう。本実施形態では、これを実現する匿名データ生成装置を構築する。
【００３６】
＜匿名データ生成装置の構成＞
本実施形態に係る匿名データ生成装置は、図６に示すように、グラフ作成部１１０と、グラフマージ部１２０と、削除処理部２３０とから構成されている。なお、第１の実施形態と同様の符号を付す構成要素については、同様の機能を有することから、その詳細な説明は、省略する。
【００３７】
削除処理部２３０は、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、そのノードの下流ノードを削除するとともに、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除する。
【００３８】
＜匿名データ生成装置の処理＞
図１１を用いて、本実施形態に係る匿名データ生成装置の処理について説明する。
まず、グラフ作成部１１０が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、各ノードを結びつけた複数のグラフを作成する（ステップＳ２０１）。具体的に、図７を用いて説明すると、ユーザＡ（図中、（Ａ）参照）は、自宅からコンビニ、駅Ａ、駅Ｂをたどって学校に行った履歴が、自宅、コンビニ、駅Ａ、駅Ｂ、学校という各ノードを矢印で結んだ有向グラフで示されている。一方、ユーザＢ（図中、（Ｂ）参照）は、自宅から駅Ａ、駅Ｂ、デパートをたどって駅Ｃに行った履歴が、自宅、駅Ａ、駅Ｂ、デパート、駅Ｃという各ノードを矢印で結んだ有向グラフで示されている。ここで、有向グラフを用いることにより、複数の属性間の依存関係や順序性を明確に表現することができる。なお、本実施形態では、有向グラフとして矢印を用いる例を示したが、これに限らず、例えば、点線を右向きの矢印、一点鎖線を左向きの矢印というように、予めルール化して、このような結線を用いてもよい。また、各ノードの名称についても、予めルール化した記号等で表してもよい。
【００３９】
グラフマージ部１２０は、複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する（ステップＳ２０２）。具体的に、図７および図８を用いて説明すると、図７のユーザＡの行動履歴を示すグラフとユーザＢの行動履歴を示すグラフとでは、ノードとして、「自宅」、「駅Ａ」、「駅Ｂ」が共通する。グラフマージ部１２０は、この共通ノードを抽出し、重ね合わせ処理を行うことにより、図７に示す２つのグラフを図３に示すような１つのグラフに変形する。
【００４０】
そして、削除処理部２３０は、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、そのノードの下流ノードを削除し（ステップＳ２０３）、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除する（ステップＳ２０４）。具体的に、Ｋ＝２とした場合の図８および図９を用いて説明すると、ノード「デパート」は、２個以上の分岐がなく、下流ノード「駅Ｃ」が２個以上の分岐を持たないため、図８からノード「駅Ｃ」とノード「デパート」からノード「駅Ｃ」への矢印が削除される。なお、ノード「学校」のように、分岐をもたないノードは、この処理から除外される。これにより、特定の人物の行動履歴を抽出することができなくなる。
【００４１】
しかしながら、上記までの処理では、複数ユーザの行動履歴を集計した全体の傾向をつかむことはできるという問題がある。この問題を解決するためには、より高度な匿名化が必要である。そこで、図１０に示すように、分岐を持たないノード（図９のノード「学校」、「デパート」）を除き、２個以上への分岐を持たないすべてのノード（図９のノード「駅Ａ」、ノード「駅Ｂ」）について矢印すべてを削除する。
【００４２】
以上、説明したように、本実施形態によれば、さらに、分岐を持たないノードを除き、Ｋ個以上への分岐を持たないすべてのノードについて矢印すべてを削除することにより、複数のユーザの行動履歴を集計したとしても、全体の傾向さえも把握することができないことを担保することができる。
【００４３】
なお、匿名データ生成装置の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを匿名データ生成装置に読み込ませ、実行することによって本発明の匿名データ生成装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００４４】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００４５】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００４６】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００４７】
１１０；グラフ作成部
１２０；グラフマージ部
１３０；削除処理部
２３０；削除処理部
【特許請求の範囲】
【請求項１】
複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成するグラフ作成手段と、
前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形するグラフマージ手段と、
Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する削除処理手段と、
を備えたことを特徴とする匿名データ生成装置。
【請求項２】
前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とする請求項１に記載の匿名データ生成装置。
【請求項３】
前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除することを特徴とする請求項２に記載の匿名データ生成装置。
【請求項４】
グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法であって、
前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成する第１のステップと、
前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップと、
前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップと、
を備えたことを特徴とする匿名データの生成方法。
【請求項５】
前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とする請求項４に記載の匿名データの生成方法。
【請求項６】
グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法であって、
前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを矢印で結びつけた複数のグラフを作成する第１のステップと、
前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップと、
前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップと、
前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除する第４のステップと、
を備えることを特徴とする匿名データの生成方法。
【請求項７】
グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法をコンピュータに実行させるためのプログラムであって、
前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成する第１のステップと、
前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップと、
前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップと、
をコンピュータに実行させるためのプログラム。
【請求項８】
前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とする請求項７に記載のプログラム。
【請求項９】
グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法をコンピュータに実行させるためのプログラムであって、
前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを矢印で結びつけた複数のグラフを作成する第１のステップと、
前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップと、
前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップと、
前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除する第４のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１】
複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成するグラフ作成手段と、
前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形するグラフマージ手段と、
Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する削除処理手段と、
を備えたことを特徴とする匿名データ生成装置。
【請求項２】
前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とする請求項１に記載の匿名データ生成装置。
【請求項３】
前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除することを特徴とする請求項２に記載の匿名データ生成装置。
【請求項４】
グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法であって、
前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成する第１のステップと、
前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップと、
前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップと、
を備えたことを特徴とする匿名データの生成方法。
【請求項５】
前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とする請求項４に記載の匿名データの生成方法。
【請求項６】
グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法であって、
前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを矢印で結びつけた複数のグラフを作成する第１のステップと、
前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップと、
前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップと、
前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除する第４のステップと、
を備えることを特徴とする匿名データの生成方法。
【請求項７】
グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法をコンピュータに実行させるためのプログラムであって、
前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを結びつけた複数のグラフを作成する第１のステップと、
前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップと、
前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップと、
をコンピュータに実行させるためのプログラム。
【請求項８】
前記グラフが、前記各ノード間を行動履歴に対応した矢印で結合する有向グラフであることを特徴とする請求項７に記載のプログラム。
【請求項９】
グラフ作成手段と、グラフマージ手段と、削除処理手段と、を備えた匿名データ生成装置における匿名データの生成方法をコンピュータに実行させるためのプログラムであって、
前記グラフ作成手段が、複数のユーザの各行動を示すノードと行動との依存関係あるいは順序性とを反映し、前記各ノードを矢印で結びつけた複数のグラフを作成する第１のステップと、
前記グラフマージ手段が、前記複数のグラフに対して、同一の部分を抽出して、重ね合わせ１つのグラフに変形する第２のステップと、
前記削除処理手段が、Ｋ（Ｋ：正の整数）個以上分岐がないノードでかつ下流ノードがＫ個以上の分岐を持たない場合に、該ノードの下流ノードを削除する第３のステップと、
前記削除処理手段が、分岐を持たない前記ノードを除き、Ｋ個以上への分岐を持たないすべての前記ノードについて矢印すべてを削除する第４のステップと、
をコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１３−１１４４４５（Ｐ２０１３−１１４４４５Ａ）
【公開日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願番号】特願２０１１−２５９８８１（Ｐ２０１１−２５９８８１）
【出願日】平成２３年１１月２９日（２０１１．１１．２９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願日】平成２３年１１月２９日（２０１１．１１．２９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]