(57)【要約】【課題】決定木分析の学習フェーズにおけるデータの秘匿性を向上させる。【解決手段】データ分析サーバは、第１高機能暗号で暗号化された説明変数の値と、所定の暗号方式で暗号化された目的変数の値と、説明変数の値の学習用情報における出現件数に基づき、第２高機能暗号で暗号化された基礎点と、を含む基礎点付き情報を保持し、該所定の暗号方式で暗号化された目的変数の値、に対応づけられた葉ノードを有する決定木を生成し、決定木生成処理における分岐規則決定処理を、説明変数の値及び基礎点が暗号化されたまま実行する。【選択図】図３
2019184852.tif 000002
【特許請求の範囲】
【請求項１】
データ分析サーバであって、
プロセッサと、メモリと、を含み、
前記メモリは、学習用情報から生成された基礎点付き情報を保持し、
前記基礎点付き情報は、第１高機能暗号で暗号化された説明変数の値と、所定の暗号方式で暗号化された目的変数の値と、前記説明変数の値の前記学習用情報における出現件数に基づく基礎点と、が対応づけられた複数のレコードを含み、
前記基礎点付き情報が保持する基礎点は、第２高機能暗号で暗号化されており、
前記プロセッサは、
前記基礎点付き情報に含まれる前記所定の暗号方式で暗号化された目的変数の値、に対応づけられた葉ノードを有する決定木を生成する決定木生成処理を実行し、
前記決定木生成処理において、前記決定木における前記説明変数の値による分岐規則を決定し、
前記分岐規則の決定において、
１以上の分岐規則候補を生成し、
前記１以上の分岐規則候補それぞれについて、前記基礎点付き情報を参照して、当該分岐規則候補における説明変数の値に前記基礎点付き情報において対応する基礎点を集計する処理と、
前記１以上の分岐規則候補それぞれについて、前記集計した基礎点と所定の評価関数とに基づいて当該分岐規則候補における評価点を算出する処理と、
前記算出した評価点に基づいて、前記１以上の分岐規則候補から採用する分岐規則を決定する処理と、を前記１以上の分岐規則候補における説明変数の値及び当該説明変数の値に対応する基礎点が暗号化されたまま実行する、データ分析サーバ。
【請求項２】
請求項１に記載のデータ分析サーバであって、
前記第１高機能暗号は検索可能暗号である、データ分析サーバ。
【請求項３】
請求項１に記載のデータ分析サーバであって、
前記第２高機能暗号は集計比較可能暗号である、データ分析サーバ。
【請求項４】
請求項１に記載のデータ分析サーバであって、
前記プロセッサは、
複数の前記決定木を生成する処理を実行し、
前記複数の決定木それぞれを生成する処理において、
前記基礎点付き情報から複数のレコードを抽出し、
前記抽出した複数のレコードについて、前記決定木生成処理を実行する、データ分析サーバ。
【請求項５】
請求項１に記載のデータ分析サーバであって、
前記メモリは、前記第１高機能暗号で暗号化された説明変数の値を含む分析用情報を保持し、
前記プロセッサは、
前記分析用情報に含まれる説明変数の値と、前記生成した決定木における分岐規則と、を比較して、当該説明変数の値に対応する葉ノードを特定する処理を、前記決定木に含まれる説明変数の値と前記分析用情報に含まれる説明変数の値とが暗号化されたまま実行し、
前記特定した葉ノードに対応する、前記所定の暗号方式で暗号化された目的変数の値、を出力する、データ分析サーバ。
【請求項６】
データ提供サーバと、データ分析サーバと、を含むデータ分析システムであって、
前記データ提供サーバは、
説明変数の値と、目的変数の値と、が対応づけられた複数のレコードを含む学習用情報を保持し、
前記説明変数の値の前記学習用情報における出現件数と、所定の関数と、に基づいて基礎点を算出し、
前記説明変数の値と、前記学習用情報において前記説明変数に対応する目的変数の値に基づく目的変数と、前記算出した基礎点と、を対応付けたレコードを含む基礎点付き情報を生成し、
前記基礎点付き情報に含まれる、説明変数の値を第１高機能暗号で、目的変数の値を所定の暗号方式で、基礎点を第２高機能暗号で、それぞれ暗号化し、
暗号化後の前記基礎点付き情報を、前記データ分析サーバに送信し、
前記データ分析サーバは、
前記基礎点付き情報に含まれる前記所定の暗号方式で暗号化された目的変数の値、に対応づけられた葉ノードを有する決定木を生成する決定木生成処理を実行し、
前記決定木生成処理において、前記決定木における前記説明変数の値による分岐規則を決定し、
前記分岐規則の決定において、
１以上の分岐規則候補を生成し、
前記１以上の分岐規則候補それぞれについて、前記基礎点付き情報を参照して、当該分岐規則候補における説明変数の値に前記基礎点付き情報において対応する基礎点を集計する処理と、
前記１以上の分岐規則候補それぞれについて、前記集計した基礎点と所定の評価関数とに基づいて当該分岐規則候補における評価点を算出する処理と、
前記算出した評価点に基づいて、前記１以上の分岐規則候補から採用する分岐規則を決定する処理と、を前記１以上の分岐規則候補における説明変数の値及び当該説明変数の値に対応する基礎点が暗号化されたまま実行する、データ分析システム。
【請求項７】
請求項６に記載のデータ分析システムであって、
前記データ提供サーバは、
前記学習用情報に含まれない説明変数の値を生成し、
前記生成した説明変数の値と、空白値である目的変数の値と、が対応付けられた追加レコードを学習用情報に追加し、
前記追加レコードを追加した学習用情報を用いて、前記基礎点付き情報を生成する、データ分析システム。
【請求項８】
請求項６に記載のデータ分析システムであって、
分析委託サーバを含み、
前記分析委託サーバは、
説明変数の値を含む分析用情報を保持し、
前記分析用情報に含まれる説明変数の値を、前記第１高機能暗号で暗号化し、
暗号化後の前記分析用情報を、前記データ分析サーバに送信し、
前記データ分析サーバは、
前記分析用情報に含まれる説明変数の値と、前記生成した決定木における分岐規則と、を比較して、当該説明変数の値に対応する葉ノードを特定する処理を、前記決定木に含まれる説明変数の値と前記分析用情報に含まれる説明変数の値とが暗号化されたまま実行し、
前記特定した葉ノードに対応する、前記所定の暗号方式で暗号化された目的変数の値、を前記分析委託サーバに送信し、
前記分析委託サーバは、前記データ分析サーバから受信した前記所定の暗号方式で暗号化された目的変数の値を復号する、データ分析システム。
【請求項９】
データ分析サーバによるデータ分析方法であって、
前記データ分析サーバは、学習用情報から生成された基礎点付き情報を保持し、
前記基礎点付き情報は、第１高機能暗号で暗号化された説明変数の値と、所定の暗号方式で暗号化された目的変数の値と、前記説明変数の値の前記学習用情報における出現件数に基づく基礎点と、が対応づけられた複数のレコードを含み、
前記基礎点付き情報が保持する基礎点は、第２高機能暗号で暗号化されており、
前記データ分析方法は、
前記データ分析サーバが、
前記基礎点付き情報に含まれる前記所定の暗号方式で暗号化された目的変数の値、に対応づけられた葉ノードを有する決定木を生成する決定木生成処理を実行し、
前記決定木生成処理において、前記決定木における前記説明変数の値による分岐規則を決定し、
前記分岐規則の決定において、
１以上の分岐規則候補を生成し、
前記１以上の分岐規則候補それぞれについて、前記基礎点付き情報を参照して、当該分岐規則候補における説明変数の値に前記基礎点付き情報において対応する基礎点を集計する処理と、
前記１以上の分岐規則候補それぞれについて、前記集計した基礎点と所定の評価関数とに基づいて当該分岐規則候補における評価点を算出する処理と、
前記算出した評価点に基づいて、前記１以上の分岐規則候補から採用する分岐規則を決定する処理と、を前記１以上の分岐規則候補における説明変数の値及び当該説明変数の値に対応する基礎点が暗号化されたまま実行する、ことを含むデータ分析方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ分析サーバ、データ分析システム、及びデータ分析方法に関する。
【背景技術】
【０００２】
近年、効率的なデータ分析を目的に、近年、情報システムを自組織が維持するのではなく、他組織が提供する情報システムにデータ分析を依頼するデータ分析代行サービスが注目されている。また、データ分析手法の一種である決定木分析や、これを拡張したランダムフォレストは広く使われており、例えば、非特許文献１に決定木分析とランダムフォレストが記載されている。
【０００３】
上述したようなデータ分析代行サービスを利用する場合、分析を代行する外部組織へデータ内容が漏洩してしまう。そこで、非特許文献２には、プライバシ情報などの機微情報が含まれているデータに対して暗号化技術を適用することにより安全に、ランダムフォレスト分析を行う技術が記載されている。具体的には、非特許文献２には、ランダムフォレスト分析を、学習フェーズと分析フェーズに分類し、分析フェーズにおいてデータ内容が漏洩しない手法が記載されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｔｒｅｖｏｒ  Ｈａｓｔｉｅ，Ｒｏｂｅｒｔ  Ｔｉｂｓｈｉｒａｎｉ，Ｊｅｒｏｍｅ  Ｆｒｉｅｄｍａｎ，“Ｔｈｅ  Ｅｌｅｍｅｎｔ  ｏｆ  Ｓｔａｔｉｓｔｉｃａｌ  Ｌｅａｒｎｉｎｇ”  Ｓｐｒｉｎｇｅｒ  Ｓｅｒｉｅｓ  ｉｎ  Ｓｔａｔｉｃｓ．  Ｓｐｒｉｎｇｅｒ  Ｎｅｗ  Ｙｏｒｋ  Ｉｎｃ．，２００１、ｐ．３０５−３１６、ｐ．５８７−６０４
【非特許文献２】Ｄａｖｉｄ  Ｊ．  Ｗｕ，Ｔｏｎｙ  Ｆｅｎｇ，Ｍｉｃｈａｅｌ  Ｎａｅｈｒｉｇ，  ａｎｄ  Ｋｒｉｓｔｉｎ  Ｌａｕｔｅｒ，“Ｐｒｉｖａｔｅｌｙ  Ｅｖａｌｕａｔｉｎｇ  Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅｓ  ａｎｄ  Ｒａｎｄｏｍ  Ｆｏｒｅｓｔｓ”米国ＰＥＴＳ学会、２０１６
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、例えば学習用データに機微情報が含まれている可能性もあるため、決定木分析の学習フェーズにおいても、データの秘匿性を向上させる必要がある。そこで本発明の一態様は、決定木分析の学習フェーズにおけるデータの秘匿性を向上させることを目的とする。
【課題を解決するための手段】
【０００６】
上記課題を解決するため、本発明の一態様は以下の構成を採用する。データ分析サーバであって、プロセッサと、メモリと、を含み、前記メモリは、学習用情報から生成された基礎点付き情報を保持し、前記基礎点付き情報は、第１高機能暗号で暗号化された説明変数の値と、所定の暗号方式で暗号化された目的変数の値と、前記説明変数の値の前記学習用情報における出現件数に基づく基礎点と、が対応づけられた複数のレコードを含み、前記基礎点付き情報が保持する基礎点は、第２高機能暗号で暗号化されており、前記プロセッサは、前記基礎点付き情報に含まれる前記所定の暗号方式で暗号化された目的変数の値、に対応づけられた葉ノードを有する決定木を生成する決定木生成処理を実行し、前記決定木生成処理において、前記決定木における前記説明変数の値による分岐規則を決定し、前記分岐規則の決定において、１以上の分岐規則候補を生成し、前記１以上の分岐規則候補それぞれについて、前記基礎点付き情報を参照して、当該分岐規則候補における説明変数の値に前記基礎点付き情報において対応する基礎点を集計する処理と、前記１以上の分岐規則候補それぞれについて、前記集計した基礎点と所定の評価関数とに基づいて当該分岐規則候補における評価点を算出する処理と、前記算出した評価点に基づいて、前記１以上の分岐規則候補から採用する分岐規則を決定する処理と、を前記１以上の分岐規則候補における説明変数の値及び当該説明変数の値に対応する基礎点を暗号化したまま実行する、データ分析サーバ。
【発明の効果】
【０００７】
本発明の一態様によれば、決定木分析の学習フェーズにおけるデータの秘匿性を向上させることができる。
【０００８】
上記した以外の課題、構成及び効果は、以下の実施形態の説明により明らかにされる。
【図面の簡単な説明】
【０００９】
【図１】実施例１におけるデータ分析システムの構成例を示すブロック図である。
【図２】実施例１における提供者サーバの構成例を示すブロック図である。
【図３】実施例１における分析代行サーバの構成例を示すブロック図である。
【図４】実施例１における委託者サーバの構成例を示すブロック図である。
【図５】実施例１における学習用テーブルの一例である。
【図６】実施例１における決定木の一例を示す説明図である。
【図７】実施例１におけるデータ分析システムによる処理の一例を示すシーケンス図である。
【図８】実施例１における基礎点付きテーブル生成処理の一例を示すフローチャートである。
【図９】実施例１における、学習用テーブルから基礎点付きテーブルが作成される処理の概要の一例を示す説明図である。
【図１０】実施例１における決定木の生成処理の一例を示すフローチャートである。
【図１１】実施例１における決定木の生成処理の概要の一例を示す説明図である。
【図１２Ａ】実施例１における決定木の一例である。
【図１２Ｂ】実施例１における決定木テーブルの一例である。
【図１３】実施例１におけるノード探索処理の一例を示すフローチャートである。
【図１４】実施例１における分析用テーブルの暗号化処理の一例を示す説明図である。
【図１５】実施例１における分析処理の一例を示すフローチャートである。
【図１６Ａ】実施例１における分析処理の概要の一例を示す説明図である。
【図１６Ｂ】実施例１における葉ノードテーブルの一例である。
【図１７】実施例２における決定木生成処理の一例を示すフローチャートである。
【図１８】実施例２における、暗号化された基礎点付きテーブルからのレコード抽出処理の概要の一例を示す説明図である。
【図１９】実施例２における、複数の決定木テーブルを用いた分析処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１０】
以下、本発明の実施形態を図面に基づいて詳細に説明する。本実施形態において、同一の構成には原則として同一の符号を付け、繰り返しの説明は省略する。なお、本実施形態は本発明を実現するための一例に過ぎず、本発明の技術的範囲を限定するものではないことに注意すべきである。
【００１１】
まず、本発実施形態で使用される用語と記号を定義する。
【００１２】
（１）テーブル
テーブルとは、データ構造の一種である。本実施形態では表形式で取り扱われるデータをテーブルと呼ぶ。また、テーブルを行単位（横軸）に分割した際のデータの集合をレコードと呼び、テーブル内の一要素をセルと呼ぶ。セルにはデータが入力されている。さらに、テーブルを列単位（縦軸）に分割し、各列はそれぞれ属性を示す。例えば、名前、性別、年齢等がテーブルの属性に用いられる。属性ごとに、入力可能な値が定められており、これらの値の集合を平文空間と呼ぶ。属性が「性別」である場合は、（男、女）が平文空間である。属性が「がん」である場合は、食道、大腸、皮膚、膀胱などが平文空間の一例である。属性が年齢である場合は、０から１００程度の整数からなる集合は平文空間の一例である。
【００１３】
なお、本実施形態において後述するデータ分析システムが使用する情報がテーブルである例を説明するが、当該情報は、データ構造に依存せずどのようなデータ構造で表現されていてもよい。例えば、テーブルの他、リスト、データベース又はキューから適切に選択したデータ構造体が、情報を格納することができる。
【００１４】
学習用テーブルを例にとって、テーブルについて説明する。図５は、学習用テーブルの一例である。学習用テーブルの０行目のレコード内の各セルにはある病院の患者の属性が記載されている。１列目の属性は患者の性別であり、性別の平文空間は男性と女性で構成される。従って、１列目の各セルの値は男性、女性のいずれかである。また、２列目の属性は患者の癌（がん）の発生個所が記載されており、２列目の各セルの値は、平文空間（食道、大腸、皮膚、膀胱）に含まれる値のいずれかである。３列目の属性は患者が併発しやすいがんの部位が記載されている。
【００１５】
（２）暗号化と復号化
本実施形態では、暗号化されていないデータを平文データと呼ぶ。暗号化とは、暗号鍵と平文データを入力として受け付け、平文データを変換した暗号化データを出力することを指す。本実施形態では、暗号化したデータをＥ（）で表す。例えば０と１を暗号化すると、それぞれ暗号化データＥ（０）、Ｅ（１）が得られる。また、復号化とは、復号鍵と暗号化データを入力として受け付け、暗号化データから逆変換した平文データを出力することを指す。
【００１６】
（３）標準暗号
標準暗号とは、暗号化と復号化の機能を備えた暗号化方式である。
【００１７】
（４）検索可能暗号
検索可能暗号とは、暗号化と復号化の機能に加え、検索可能暗号で暗号化したデータを、暗号化したままで等号を判定する機能を備えた暗号化方式である。この判定機能は、２つの暗号化データを入力として受け付け、それぞれの暗号化前の平文データの値に基づき判定する。例えば、Ｅ（０）とＥ（１）が入力された場合、検索可能暗号の検索機能は、値が異なること（０＝！１）を意味する記号を出力する。また、Ｅ（０）とＥ（０）が入力された場合は、検索機能は、値が同じであること（０＝０）を意味する記号を出力する。検索可能暗号は、高機能暗号及び関数型暗号の一例である。
【００１８】
（５）集計比較可能暗号
集計比較可能暗号とは、暗号化と復号化の機能に加え、暗号化したまま集計する機能と、集計した暗号化データを暗号化したまま値の大小を比較する機能を備えた暗号化方式である。比較機能は、２つの暗号化データを入力として受け付け、それぞれの値に基づき、大小関係の判定結果を出力する。例えば、Ｅ（０）とＥ（１）が入力された場合は一方の値が大きいこと（０＜１）を意味する記号を出力する。また、比較機能は、Ｅ（０）とＥ（０）が入力された場合は値が同じであること（０＝０）を意味する記号を出力する。また、比較機能は、Ｅ（０）とＥ（１）を集計したＥ（０＋１）と、Ｅ（１）とＥ（１）を集計したＥ（１＋１）とを比較し、Ｅ（０＋１）＜Ｅ（１＋１）を判定できる。集計比較可能暗号として、暗号化状態での任意の演算を実現可能とする完全準同型暗号や、ネットワーク経由で実施する秘匿計算などの手段が知られている。集計比較可能暗号は、高機能暗号及び関数型暗号の一例である。
【００１９】
（６）決定木と決定木分析
決定木分析とは、予測や判別等を目的とした機械学習の一種である。一般に、決定木分析では、学習用テーブルを用いた学習フェーズにおいて決定木と呼ばれる学習モデルを構築し、分析フェーズにおいて決定木を用いて分析用テーブルの判別や予測を実施する。決定木の最上位である根ノード、及び根ノード以外の内部ノードには学習用テーブルの変数（レコード）が関連付けられ、最下位の葉ノードには判別や予測結果に関する値が関連付けられている。
【００２０】
図６は、図５の学習用テーブルの属性１と属性２の値を用いて、属性３の値を予測する場合の決定木の一例を示す説明図である。根ノードには学習用テーブル２２２が関連付けられており、ノード番号として１番が割り当てられている。学習用テーブル２２２の属性１（性別）で、根ノードから分岐する枝が設定されている場合、男性又は女性で、学習用テーブル２２２を振り分ける。すなわち、「男性」で分岐したノードには、２番が割り振られ、属性１（性別）が男性のレコードのみが関連付けられる。同様に、「女性」で分岐したノードには、３番が割り振られ、属性１（性別）が女性のレコードのみが関連付けられる。
【００２１】
２番のノード以下及び３番のノード以下の分岐は、属性２（がん）が用いられた、最下位の葉ノードに到達するまでの分岐用の枝、が伸びている。葉ノードには条件を満たす学習用テーブル２２２が分類や予測に関連する結果として関連付けられている。例えば、決定木分析の結果、８番の葉ノードに至った場合、分析結果として属性３の口腔がんを得る。
【００２２】
決定木分析では、決定木を構築した後、分析用のテーブルの判別や分類をする分析フェーズを実施する。分析フェーズでは決定木による分岐に従い、根ノードから葉ノードまでの経路を辿り、葉ノードに関連付けられた分類や予測に関連する結果を出力する。
【００２３】
（７）ランダムフォレスト分析
ランダムフォレスト分析は、決定木分析の一種である。学習フェーズにおいて、学習用テーブルからランダムなデータ抽出を繰り返し行うことにより多数の決定木を作成し、分析フェーズにおいて多数の決定木による決定木分析の結果を集約し、最終的な分類や予測結果を作成する手法である。結果を集約する際には、多数決による判定方法や、複数の結果の平均値や中央値等が利用される。
【実施例１】
【００２４】
図１は、本実施例のデータ分析システムの構成例を示すブロック図である。データ分析システムは、例えば、提供者サーバ２００、分析代行サーバ３００、及び委託者サーバ４００を含む。例えば、提供者サーバ２００と分析代行サーバ３００、委託者サーバ４００と分析代行サーバ３００は、ネットワーク１００を介して互いにデータを送受信できる。
【００２５】
提供者サーバ２００は、分析代行サーバ３００に対して、決定木を作成するための学習用テーブルを暗号化した上で提供する。委託者サーバ４００は、分析用データを暗号化した上で分析代行サーバ３００に送信し、分析代行サーバ３００に分析を委託する。分析代行サーバ３００は、暗号化された学習用テーブルから決定木を生成し、決定木を用いて分析用データを分析する。
【００２６】
図２は、本実施例の提供者サーバ２００の構成例を示すブロック図である。提供者サーバ２００は、例えば、入力部２０１、出力部２０２、通信部２０３、演算部２１０、及び記憶部２２０を含む。入力部２０１は、例えば、キーボード及びマウス等の周辺機器に接続され、オペレータからの入力を受け付けるインターフェースである。
【００２７】
出力部２０２は、例えば、ディスプレイ及びプリンタ等の周辺機器に接続され、プログラムの実行結果をオペレータが視認可能な形式で出力するインターフェースである。通信部２０３は、ネットワーク１００を介して所定のプロトコルに従って、他の装置との通信を制御するネットワークインターフェース装置である。
【００２８】
演算部２１０は、プロセッサを含み、記憶部２２０に格納されたプログラムを実行する。記憶部２２０は、メモリ及び補助記憶装置を含む。メモリは、不揮発性の記憶素子であるＲＯＭ及び揮発性の記憶素子であるＲＡＭを含む。ＲＯＭは、不変のプログラム（例えば、ＢＩＯＳ）などを格納する。ＲＡＭは、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）のような高速かつ揮発性の記憶素子であり、プロセッサが実行するプログラム及びプログラムの実行時に使用されるデータを一時的に格納する。
【００２９】
補助記憶装置は、例えば、磁気記憶装置（ＨＤＤ）、フラッシュメモリ（ＳＳＤ）等の大容量かつ不揮発性の記憶装置であり、演算部２１０に含まれるプロセッサが実行するプログラム及びプログラムの実行時に使用されるデータを格納する。すなわち、プログラムは、補助記憶装置から読み出されて、メモリにロードされて、プロセッサによって実行される。
【００３０】
演算部２１０が実行するプログラムは、リムーバブルメディア（ＣＤ−ＲＯＭ、フラッシュメモリなど）又はネットワーク１００を介して提供者サーバ２００に提供され、非一時的記憶媒体である不揮発性の補助記憶装置に格納される。このため、提供者サーバ２００は、リムーバブルメディアからデータを読み込むインターフェースを有するとよい。分析代行サーバ３００及び委託者サーバ４００についても同様である。
【００３１】
提供者サーバ２００は、物理的に一つの計算機上で、又は、論理的又は物理的に構成された複数の計算機上で構成される計算機システムであり、同一の計算機上で別個のスレッドで動作してもよく、複数の物理的計算機資源上に構築された仮想計算機上で動作してもよい。分析代行サーバ３００及び委託者サーバ４００についても同様である。
【００３２】
演算部２１０は、例えば、基礎点付きテーブル生成部２１１及び暗号化部２１２を含む。例えば、演算部２１０は、記憶部２２０にロードされた基礎点付きテーブル生成プログラムに従って動作することで、基礎点付きテーブル生成部２１１として機能し、記憶部２２０にロードされた暗号化プログラムに従って動作することで、暗号化部２１２として機能する。分析代行サーバ３００及び委託者サーバ４００の演算部に含まれる各部についても同様である。記憶部２２０は、暗号化鍵２２１、学習用テーブル２２２、及び評価関数２２３を格納する。
【００３３】
基礎点付きテーブル生成部２１１は、学習用テーブル２２２と評価関数２２３とを用いて、基礎点付きテーブルを生成する。暗号化部２１２は、暗号化鍵２２１を用いて、学習用テーブル２２２内の定められた領域に対して、標準暗号や集計比較可能暗号で暗号化し、基礎点付きテーブルを暗号化する。
【００３４】
暗号化鍵２２１は、学習用テーブル２２２の値を暗号化するための暗号化鍵である。学習用テーブル２２２は、分析代行サーバ３００が決定木を生成するための学習用テーブルを格納する。評価関数２２３は、学習用テーブルから基礎点を算出するための関数である。
【００３５】
図３は、本実施例の分析代行サーバ３００の構成例を示すブロック図である。分析代行サーバ３００は、例えば、入力部３０１、出力部３０２、通信部３０３、演算部３１０、及び記憶部３２０を含む。入力部３０１、出力部３０２、通信部３０３、演算部３１０、及び記憶部３２０についての説明は、それぞれ、入力部２０１、出力部２０２、通信部２０３、演算部２１０、及び記憶部２２０についての説明と同様であるため省略する。
【００３６】
演算部３１０は、例えば、決定木生成部３１１、ノード探索部３１２、決定木分析部３１３、暗号判定部３１４を含む。記憶部３２０は、例えば、評価関数３２１を格納する。決定木生成部３１１は、暗号化された基礎点付きテーブルを用いて、暗号化された状態のまま、決定木を生成する。ノード探索部３１２は、決定木生成部３１１が決定木を生成する際に、ノード探索を実施する。
【００３７】
決定木分析部３１３は、決定木生成部３１１が生成した決定木と、後述する暗号化された分析用テーブルと、を用いて、暗号化したまま、分析用テーブルを分析する。暗号判定部３１４は、分析用テーブルにおいて、暗号化したまま、比較や一致判定を実施する。評価関数３２１は、ノード探索における評価点を算出するための関数である。
【００３８】
図４は、本実施例の委託者サーバ４００の構成例を示すブロック図である。委託者サーバ４００は、例えば、入力部４０１、出力部４０２、通信部４０３、演算部４１０、及び記憶部４２０を含む。入力部４０１、出力部４０２、通信部４０３、演算部４１０、及び記憶部４２０についての説明は、それぞれ、入力部２０１、出力部２０２、通信部２０３、演算部２１０、及び記憶部２２０についての説明と同様であるため省略する。
【００３９】
演算部４１０は、暗号化部４１１及び復号化部４１２を含む。記憶部４２０は、分析用テーブル４２１、暗号化鍵４２２、及び復号化鍵４２３を格納する。暗号化部４１１は、暗号化鍵４２２を用いて、学習用テーブル２２２内の定められた領域に対し、標準暗号や集計比較可能暗号で暗号化する。復号化部４１２は、受け取った分析結果を復号する。
【００４０】
分析用テーブル４２１は、分析代行サーバ３００による決定木を用いた分析対象のデータである。暗号化鍵４２２は、分析用テーブル４２１の値を暗号化するための暗号化鍵である。復号化鍵４２３は、分析代行サーバ３００から受信した分析結果を復号化するための復号化鍵である。
【００４１】
なお、委託者サーバ４００の一部又は全部の機能を提供者サーバ２００が担ってもよいし、提供者サーバ２００の一部又は全部の機能を委託者サーバ４００が担ってもよい。
【００４２】
図７は、本実施例のデータ分析システムによる処理の一例を示すシーケンス図である。具体的には、図７は、具体的には、提供者サーバ２００、分析代行サーバ３００、及び委託者サーバ４００それぞれによる処理の概要の一例と、ネットワーク１００経由で送受信されるデータの概要の一例を示す。
【００４３】
データ分析システムによる処理は、学習フェーズと分析フェーズとを含む。学習フェーズにおいて、提供者サーバ２００が学習用テーブル２２２を暗号化し、分析代行サーバ３００は暗号化された学習用テーブル２２２から決定木を生成する。分析フェーズにおいて、委託者サーバ４００が分析用テーブルを暗号化し、分析代行サーバ３００は暗号化された分析用テーブルから決定木を用いて分析し、分析結果を委託者サーバ４００に提供するまでの分析フェーズと、を含む。
【００４４】
まず、学習フェーズについて説明する。基礎点付きテーブル生成部２１１は、学習用テーブル２２２の基礎点を算出し、算出した基礎点を学習用テーブル２２２に付加した基礎点付きテーブルを生成する（Ｓ２１０）。基礎点付きテーブルの生成処理の詳細については後述する。次に、暗号化部２１２は、基礎点付きテーブルを暗号化し（Ｓ２２０）、分析代行サーバ３００へ送信する（Ｓ２３０）。
【００４５】
分析代行サーバ３００が基礎点付きテーブルを受信すると、決定木生成部３１１、決定木分析部３１３、及び暗号判定部３１４は、受信した基礎点付きテーブルから、決定木を作成する（Ｓ３３０）。決定木の作成処理の詳細については後述する。
【００４６】
続いて、分析フェーズを表すシーケンスを説明する。暗号化部４１１は、分析用テーブル４２１を暗号化し（Ｓ４１０）、分析代行サーバ３００へ送信する（Ｓ４２０）。分析代行サーバ３００が分析用テーブルを受信すると、決定木分析部３１３は、分析用テーブルを分析し（Ｓ３５０）、分析結果を、委託者サーバ４００へ送信する（Ｓ３７０）。分析処理の詳細については後述する。委託者サーバ４００は、受信した分析結果が暗号化されている場合、復号する（Ｓ４３０）。
【００４７】
図８は、ステップＳ２１０における、基礎点付きテーブル生成処理の一例を示すフローチャートである。基礎点付きテーブル生成部２１１は、学習用テーブル２２２における属性を、説明変数と目的変数に分類し、説明変数に分類した属性それぞれの平文空間の値の組合せから一時テーブルを作成する（Ｓ２１１）。なお、どの属性を説明変数に分類し、どの属性を目的変数に分類するかは、例えば、予め定められていてもよいし、提供者サーバ２００のユーザの入力によって定められてもよい。
【００４８】
図９は、学習用テーブル２２２から基礎点付きテーブルが作成される処理の概要の一例を示す説明図である。例えば、学習用テーブル２２２が３種類の属性（性別、がん、併発）を有している場合、基礎点付きテーブル生成部２１１は、ステップＳ２１１において、「性別」と「がん」を説明変数に、「併発」を目的変数に分類する。
【００４９】
基礎点付きテーブル生成部２１１は、ステップＳ２１１において説明変数それぞれの平文空間の値の組合せである（男性、食道）（女性、食道）（男性、大腸）（女性、大腸）（男性、皮膚）、（女性、皮膚）、（男性、膀胱）、（女性、膀胱）それぞれを、レコードとして有する一時テーブル２５１を作成する。また、基礎点付きテーブル生成部２１１は、一時テーブル２５１に目的変数欄を追加する。
【００５０】
なお、基礎点付きテーブル生成部２１１は、学習用テーブル２２２に出現しない属性の値を含む、平文空間の値の組み合わせを生成してもよい。具体的には、例えば、「年齢」のような、数値型の属性については、学習用テーブル２２２に出現しない値であっても、所定の範囲（例えば０歳〜１００歳）に含まれる値であれば、平文空間の値として扱われる。また、例えば、「性別」のような文字型の属性（又は数値型であるが名義尺度を示す属性）については、学習用テーブル２２２に「男性」のレコードしかない場合であっても、予め定められた値である「男性」、「女性」の双方を平文空間の値として扱われる。これにより、学習用テーブル２２２の秘匿性が向上する。
【００５１】
また、基礎点付きテーブル生成部２１１は、平文空間の値を集約してもよい。具体的には、基礎点付きテーブル生成部２１１は、例えば、「年齢」のような、数値型の属性については、所定の範囲ごとに（例えば０〜９歳、１０〜１９歳、・・・、９０〜９９歳、１００歳以上）値を集約して、平文空間の新たな値としてもよい。また、例えば、基礎点付きテーブル生成部２１１は、例えば、「併発」のような文字型の属性（又は数値型であるが名義尺度を示す属性）については、予め定められたグループに値を集約して（例えば、「大腸」及び「小腸」をグループ１、「食道」及び「膀胱」をグループ２、・・・等）、平文空間の新たな値としてもよい。これにより、学習フェーズ及び分析フェーズの処理量、及び後述する決定木のデータ量が低減する。
【００５２】
また、基礎点付きテーブル生成部２１１は、例えば、一時テーブル２５１のレコードの説明変数の値の組み合わせそれぞれについて、学習用テーブル２２２において対応する目的変数の属性値のうち最も出現件数が多い属性値を抽出する。基礎点付きテーブル生成部２１１は、抽出した属性値それぞれを、一時テーブル２５１における説明変数の値の組合わせに対応する目的変数の値として、一時テーブル２５１の目的変数欄に格納する。
【００５３】
図９では、例えば、説明変数の値の組み合わせ（男性、食道）に学習用テーブル２２２において対応する目的変数の値のうち、最も出現件数の多いものが「口腔」であったため、一時テーブル２５１の、説明変数の値の組み合わせ（男性、食道）のレコードにおける目的変数欄に値「口腔」が格納されている。また、図９では、例えば、説明変数の値の組み合わせ（男性、皮膚）に学習用テーブル２２２において対応する目的変数の値がない、又は学習用テーブル２２２に説明変数の値の組み合わせ（男性、皮膚）が存在しないため、一時テーブル２５１の説明変数の値の組み合わせ（男性、食道）のレコードにおける目的変数欄の値が空白値（例えば、ｎｕｌｌ値）である。
【００５４】
なお、基礎点付きテーブル生成部２１１は、一時テーブル２５１に付加する目的変数の値として、学習用テーブル２２２に存在しない値を新たに生成してもよい。説明変数の値の組み合わせ（男性、食道）に、学習用テーブル２２２において対応する目的変数の値として、「口腔」が８０件、「小腸」が２０件あった場合を想定する。この場合、基礎点付きテーブル生成部２１１は、例えば、併発の割合を示す新たな目的変数の値「口腔：８０％、小腸：２０％」を生成し、一時テーブル２５１の対応するレコードに格納してもよい。
【００５５】
次に、基礎点付きテーブル生成部２１１は、一時テーブル２５１の各レコードの説明変数の組み合わせが、学習用テーブル２２２において出現する出現件数を集計する（Ｓ２１２）。例えば、学習用テーブル２２２において平文空間の値の組み合わせが（男性、食道）であるレコードが１００件あった場合は、一時テーブル２５１の（男性、食道）レコードの出現件数を１００件と評価する。基礎点付きテーブル生成部２１１は、同様の処理を一時テーブル２５１の各レコードについて行い、図９の例における出現件数を示すカラム２５２を生成する。
【００５６】
次に、基礎点付きテーブル生成部２１１は評価関数２２３に基づいて、基礎点を算出する（Ｓ２１３）。誤り率、情報エントロピー、及びジニ係数等はいずれも評価関数２２３の一例である。本実施例では、評価関数２２３が誤り率である場合の処理を説明する（評価関数２２３がジニ係数又は情報エントロピーの場合であっても同様の処理であるため、これらの場合における説明は省略する）。
【００５７】
評価関数２２３が誤り率の場合、基礎点付きテーブル生成部２１１は、出現件数をそのまま基礎点として算出し、基礎点を示すカラムを一時テーブル２５１に付加した、基礎点付きテーブルを生成する（Ｓ２１４）。なお、図９では、基礎点付きテーブルにおける各レコードに説明変数が１つだけ格納されている（即ち、目的変数の組み合わせに対して説明変数が一意に定まる）例を説明したが、基礎点付きテーブルにおけるレコードに複数の目的変数が格納されていてもよい。
【００５８】
また、前述したようにステップＳ２２０において暗号化部２１２は、基礎点付きテーブルの各セルを暗号化する。具体的には、例えば、暗号化部２１２は、基礎点欄を集計比較可能暗号により暗号化し、説明変数欄を検索可能暗号で暗号化し、目的変数欄を標準暗号で暗号化する。なお、目的変数欄は標準暗号以外の暗号（例えば、検索可能暗号や集計比較可能暗号）で暗号化されていてもよいが、暗号化処理及び復号化処理の処理量が少なく、かつセキュリティレベルが高い暗号方式である標準暗号が採用されることが望ましい。基礎点付きテーブルが暗号化されることにより、暗号化された基礎点付きテーブル２５３が生成される。
【００５９】
図１０は、ステップＳ３３０における決定木生成処理の一例を示すフローチャートである。図１１は、決定木生成処理の概要の一例を示す説明図である。図１２Ａは、決定木の一例である。図１２Ｂは、図１２Ａの決定木を表す決定木テーブルの一例である。図１６Ｂは、葉ノードテーブルの一例である。
【００６０】
決定木の生成処理において、決定木生成部３１１は、最上位のノードである根ノードから下位に向かい、評価関数３２１を用いて、もっとも良い値を出力する枝を逐次的に探索しながら、決定木を生成する。
【００６１】
まず、決定木生成部３１１は、変数ｉを０で初期化し、基礎点付きテーブル２５３に親ノード番号と子ノード番号それぞれの管理用の列（それぞれ、親ノード管理列、子ノード管理列と呼ぶ）を追加する（Ｓ３３１）。但し、親ノード管理列の番号の初期値は１（根ノードの番号）、子ノード管理列の番号の初期値は−（値なし）とする（図１１の上部に描かれた基礎点付きテーブル２５３を参照）。
【００６２】
続いて、決定木生成部３１１は、各セルに値が格納されていない決定木テーブルを生成する（Ｓ３３２）。決定木テーブルは４列（親ノード番号、分岐属性、分岐条件、子ノード番号）のテーブルである。決定木テーブルの１行目は根ノード、を示し、１行目の親ノード番号欄には１が格納されている（図１２Ｂを参照）。決定木生成部３１１は、変数ｉに親ノード番号の最小値を設定する（Ｓ３３３）。
【００６３】
続いて、決定木生成部３１１は、変数ｉの親ノードから子ノードを探索する（Ｓ３３４）。なお、子ノードの探索処理の詳細については後述する。決定木生成部３１１は、子ノードを発見できたか否かを判定する（Ｓ３３５）。決定木生成部３１１は、子ノードを発見できた場合は（Ｓ３３５：Ｙｅｓ）、ステップＳ３３６へ進み、発見できなかった場合は（Ｓ３３５：Ｎｏ）、ステップＳ３３７へ進む。
【００６４】
決定木生成部３１１は、発見した子ノードの子ノード番号を、決定木テーブルの子ノード番号欄に記入する（Ｓ３３６）。本実施例では二分木を生成する例を説明するため、子ノード番号は、ｉの２倍（２ｉ）と２倍に１を加えた値（２ｉ＋１）とする。図１１の中部に描かれた基礎点付きテーブル２５３は、親ノード（根ノード）からの分岐を決定する属性（以下、分岐属性とも呼ぶ）が「性別」であることを示す。さらに、当該基礎点付きテーブル２５３は、「性別」が「男性」である場合には親ノードからノード番号２の子ノードへ、「女性」である場合には親ノードからノード番号２の子ノードへ分岐することを示す。分岐属性における分岐先のノードを決定する属性値を分岐条件とも呼ぶ。
【００６５】
また、ステップＳ３３６において、決定木生成部３１１は、基礎点付きテーブル２５３の子ノード番号欄の値を親ノード番号欄に上書きし、子ノード番号を空白値（例えばｎｕｌｌ値）に変更する（図１１の下部に描かれた基礎点付きテーブル２５３を参照）。また、ステップＳ３３６において、決定木生成部３１１は、決定木テーブルにおいて、分岐属性を当該親ノード番号に対応する分岐属性欄に、分岐条件を当該親ノード番号に対応する分岐条件欄に、さらに発見した子ノードの子ノード番号を子ノード番号欄に、それぞれに格納する。さらに、子ノード番号はそれぞれ親ノード番号に登録する。
【００６６】
図１２Ｂの例における、決定木テーブルの１行目は、ノード番号１の親ノード（根ノード）からの分岐属性がＥ（性別）であり、分岐条件がＥ（男性）及びＥ（女性）であり、分岐先の子ノードがノード番号２の子ノード及びノード番号３の子ノードであることを示す。なお、分岐条件欄の値と、子ノード欄の値、について同じ順番の値が対応する。即ち、図１２Ｂの決定木テーブルの１行目は、属性値がＥ（男性）である場合の分岐先がノード番号２の子ノードであり、属性値がＥ（情勢）である場合の分岐先がノード番号３の子ノードであることを示す。
【００６７】
図１０の説明に戻る。決定木生成部３１１は、子ノードを発見できなかった場合は（Ｓ３３５：Ｎｏ）、葉ノードテーブル３３６を更新する（Ｓ３３７）。具体的には、決定木生成部３１１は、ｉを葉ノード番号として登録し、基礎点付きテーブル２５３の該当する目的変数を分析結果として登録する。
【００６８】
図１６Ｂの例では、葉ノードテーブル３３６は、葉ノード番号欄と目的変数欄を含む。続いて、決定木生成部３１１、親ノードの管理列において、ｉよりも大きな親ノード番号が存在するか判定する（Ｓ３３８）。決定木生成部３１１は、ｉよりも大きな親ノード番号が存在すると判定した場合（Ｓ３３８：Ｙｅｓ）、ステップＳ３３３へ戻る。決定木生成部３１１は、ｉよりも大きな親ノード番号が存在しないと判定した場合（Ｓ３３８：Ｎｏ）、決定木の生成処理を終了する。
【００６９】
図１２Ａの決定木について説明する。図１２Ａの決定木において、根ノード（１番）から二分木で枝が伸びており、枝は内部ノード（２番、３番、・・・・、７番）を経由し、葉ノード（８番、９番、・・・・・、１５番）に至るまで伸びている。枝上には分岐条件が記載されており（分岐属性も記すことが望ましいが、スペースの都合上省略されている）、例えば根ノードから２番の内部ノードへの分岐条件は、分岐属性がＥ（性別）かつ値がＥ（男性）に一致することである。同様に３番の内部ノードへの分岐条件は、分岐属性がＥ（性別）かつ値がＥ（女性）に一致することである。
【００７０】
図１３は、ステップＳ３３４におけるノード探索処理の一例を示すフローチャートである。ノード探索部３１２は暗号化された基礎点付きテーブル２５３から属性を１つ選択する（Ｓ３３４−１）。例えば、図９等の例では、ノード探索部３１２は、暗号化された基礎点付きテーブル２５３から、Ｅ（性別）又はＥ（がん）を選択する。
【００７１】
続いて、ノード探索部３１２は、選択した属性において、暗号化データの分岐規則を探索し、分岐規則を一つ選択する（Ｓ３３４−２）。例えば、ノード探索部３１２が属性Ｅ（性別）による分岐を選択した場合、属性Ｅ（性別）における平文空間の点はＥ（男性）とＥ（女性）の２種類のみであるため、Ｅ（男性）とＥ（女性）のいずれかに分岐させる１通りの分岐規則しか存在しない。従って、この場合には、ノード探索部３１２は、ステップＳ３３４−２において、当該分岐規則を選択する。
【００７２】
一方、例えば、ノード探索部３１２が属性Ｅ（がん）を選択した場合、属性Ｅ（がん）の平文空間の点としてはＥ（食道）、Ｅ（大腸）、Ｅ（皮膚）、及びＥ（膀胱）の４種類の値が存在する。従って、この場合、Ｅ（食道）ｏｒＥ（大腸）とＥ（皮膚）ｏｒＥ（膀胱）のいずれかに分岐させる分岐規則、Ｅ（食道）ｏｒＥ（皮膚）とＥ（大腸）ｏｒＥ（膀胱）のいずれかに分岐させる分岐規則、及びＥ（食道）とｏｒ（膀胱）とＥ（大腸）ｏｒＥ（皮膚）のいずれかに分岐される分岐規則、からなる３通りの分岐規則が存在する。ステップＳ３３４−２において、ノード探索部３１２によって、これらの分岐規則のうち未選択の一つの分岐規則を、例えばランダムに選択する。
【００７３】
なお、上述した例では、平文空間の値が２ｎ個（ｎは１以上の自然数）の場合には、当該２ｎ個の値のうちのｎ個の値からなる集合と、他のｎ個の値からなる集合と、のいずれかに分岐させる分岐規則が選択対象の分岐規則であるが、これらの集合における値の数がｎ個ずつでなくてもよい。具体的には、例えば、前述の、属性Ｅ（がん）の平文空間の値として、Ｅ（食道）、Ｅ（大腸）、Ｅ（皮膚）、及びＥ（膀胱）の４種類の値が存在する例において、Ｅ（食道）ｏｒＥ（大腸）ｏｒＥ（皮膚）と、Ｅ（膀胱）と、のいずれかに分岐させる分岐規則が存在してもよい。
【００７４】
同様に平文空間の値が２ｎ＋１個（ｎは１以上の自然数）の場合には、当該２ｎ個の値のうちのｎ個の値からなる集合と、他のｎ＋１個の値からなる集合と、のいずれかに分岐させる分岐規則が選択対象の分岐規則であるが、これらの集合における値の数がｎ個とｎ＋１個でなくてもよい。
【００７５】
続いて、ノード探索部３１２は、選択した分岐規則に従い、分岐規則の基礎点を集計する（Ｓ３３４−３）。例えば、図９の基礎点付きテーブル２５３でＥ（性別）を選択した場合、Ｅ（男性）の基礎点はレコード１行目、３行目、５行目、７行目の基礎点（本実施例では出現件数）の合計であり、Ｅ（１００＋６０＋４０＋２０）＝Ｅ（２２０）である。同様に、Ｅ（女性）の基礎点はＥ（１００＋６０＋２０＋５）＝Ｅ（１８５）である。
【００７６】
続いて、ノード探索部３１２は、集計した全ての基礎点を評価関数３２１に入力し、評価点を得る（Ｓ３３４−４）。評価点を算出するための評価関数３２１としては、以下のような計算式が知られている。
【００７７】
（１）誤り率：Ｅ（ｔ）＝１−ｍａｘ｛Ｐｒ（Ｃｉ｜ｔ）｝
（２）情報エントロピー：−ΣＰｒ（Ｃｉ｜ｔ）ｌｏｇ｛Ｐｒ（Ｃｉ｜ｔ）｝
（３）ジニ係数：１−Σ｛Ｐｒ（Ｃｉ｜ｔ）２｝
【００７８】
ただし、Ｐｒは出現確率、Ｃｉはレコードの値、ｔはノードの番号を指す。一般に、決定木分析では、これらの評価関数３２１を用い、評価点を算出し、もっとも評価点が低いものを子ノードとして採用する。なお、出現確率がノードの出現レコード数を全レコードで割った値であるため、本実施例では、評価関数３２１において出現確率ではなく、出現件数を用いるものとする。
【００７９】
例えば、誤り率の場合、レコード件数をｎとし、評価関数３２１がｎＥ（ｔ）＝ｎ−ｎｍａｘ｛Ｐｒ（Ｃｉ｜ｔ）｝であるとする。即ち、ｎｍａｘ｛Ｐｒ（Ｃｉ｜ｔ）｝はノードｔの出現件数なので、評価関数３２１がレコード件数で表される。例えば、男性と女性による分岐規則における評価点として、Ｅ（２２０＋１８５）−ｍａｘ｛Ｅ（２２０）、Ｅ（１８５）｝＝Ｅ（４０５）−Ｅ（２２０）＝Ｅ（１８５）が得られる。
【００８０】
続いて、ノード探索部３１２は、選択した属性のすべての分岐規則を評価したか否かを判定する（Ｓ３３４−５）。ノード探索部３１２は、評価していない分岐規則があると判定した場合（Ｓ３３４−５：Ｎｏ）、ステップＳ３３４−２に戻る。ノード探索部３１２は、すべての分岐規則を評価したと判定した場合（Ｓ３３４−５：Ｙｅｓ）、すべての属性を選択済であるか否かを判定する（Ｓ３３４−６）。
【００８１】
ノード探索部３１２は、未選択の属性があると判定した場合（Ｓ３３４−６：Ｎｏ）、ステップＳ３３４−１に戻る。ノード探索部３１２は、すべての属性を選択済であると判定した場合（Ｓ３３４−６：Ｙｅｓ）、最小の評価点を求め（Ｓ３３４−７）、当該最小の評価値を有する分岐手段を決定木の枝として採用する（Ｓ３３４−８）。
【００８２】
なお、評価関数３２１が誤り率である例を前述したが、情報エントロピーやジニ係数の式を用いてもよい。その場合、ノード探索部３１２は、基礎点として、（出現件数）×ｌｏｇ（出現件数）又は（出現件数）の自乗を基礎点として設定する。
【００８３】
ここまで、分析代行サーバ３００が暗号化された学習用テーブル２２２から決定木を生成するまでの学習フェーズに関する処理を説明した。前述した学習フェーズにより、学習用テーブル２２２を暗号化したまま、即ち分析代行サーバ３００に対して学習用テーブル２２２を秘匿した状態で、決定木を作成することできる。
【００８４】
続いて、分析代行サーバ３００が暗号化された分析用テーブルから分析結果を出力するまでの分析フェーズに関する処理を説明する。図１４は、ステップＳ４１０における分析用テーブル４２１の暗号化処理の一例を示す説明図である。暗号化部２１２は、分析用テーブル４２１の各セルを、検索可能暗号で暗号化する。
【００８５】
図１５は、ステップＳ３５０における分析処理の一例を示すフローチャートである。まず、決定木分析部３１３は、暗号化された分析用テーブルからレコードを選択する（Ｓ３５１）。以下、このレコードを分析用レコードと呼ぶ。
【００８６】
次に、決定木分析部３１３は、変数ｉを０で初期化する（Ｓ３５２）。決定木分析部３１３は、決定木テーブルから、親ノードをｉ番とするレコードを選択し、暗号判定部３１４は、当該選択されたレコードの属性と一致する分析用レコードの属性を選択する（Ｓ３５３）。以下、決定木分析部３１３が決定木テーブルから選択したレコードを決定木レコードと呼ぶ。
【００８７】
ステップＳ３５３において、暗号判定部３１４は、検索可能暗号の判定機能を用いて、決定木レコード及び分析用レコードが暗号化されたまま、双方の属性が同じであるかを判定する。また、暗号判定部３１４は、分析用レコードの選択した属性に関する暗号化データが、決定木レコードの分岐条件に列挙される暗号化データが同じかを判定する（Ｓ３５４）。
【００８８】
暗号判定部３１４は、分岐条件において同じである暗号化データが存在すると判定した場合（Ｓ３５４；Ｙｅｓ）、変数ｉに子ノード番号を割り当て（ステップＳ３５５）、ステップＳ３５３に戻る。一方、暗号判定部３１４は、分岐条件において同じである暗号化データが存在しないと判定した場合（Ｓ３５４：Ｎｏ）、葉ノードテーブル３３６における葉ノード番号と同レコードの目的変数のセルの値を、分析結果として出力する（Ｓ３３６）。
【００８９】
なお、ステップＳ３５１〜Ｓ３５６において、分析用テーブルから１レコードが選択された場合の処理について説明したが、分析代行サーバ３００は、ステップＳ３５０において、これらの処理を分析用テーブルのすべてのレコードに対して行い、分析結果を出力する。
【００９０】
図１６Ａは、分析処理の概要の一例を示す説明図である。図１６Ａは、属性Ｅ（性別）がＥ（男性）であり、属性Ｅ（がん）がＥ（大腸）である例を示す。また、図１６Ａの分析処理で用いられる葉ノードテーブル３３５は、図１６Ｂの葉ノードテーブルである。図１６Ａの例では、分析結果として、属性値Ｅ（併発）がＥ（口腔）であることが委託者サーバ４００に返される。
【００９１】
以上、本実施例のデータ分析システムは、学習用テーブル２２２を分析代行サーバ３００に対して秘匿した状態で学習を行う（決定木を生成する）ことができ、さらに分析用テーブル４２１を分析代行サーバ３００に対して秘匿した状態で、決定木分析を実行することができる。
【００９２】
なお、本実施例では分析代行サーバ３００が決定木を生成する例を説明したが、提供者サーバ２００自身が決定木を生成して、生成した決定木を分析代行サーバ３００に送信してもよい。この場合、提供者サーバ２００は、基礎点付きテーブル２５３を暗号化することなく、決定木テーブルを生成してもよい。但し、提供者サーバ２００は、決定木テーブルを分析代行サーバ３００に送信する前には、決定木テーブルの各列の値が暗号化されている必要がある。
【実施例２】
【００９３】
本実施例のデータ分析システムは、決定木分析を拡張したデータ分析手法の一つである、ランダムフォレストを実現する。以下では、実施例１と異なる点を説明する。実施例２におけるステップＳ３３０における決定木の生成処理、及びステップＳ３５０における分析処理が、実施例１と異なる。
【００９４】
図１７は、ステップＳ３３０における決定木生成処理の一例を示すフローチャートである。まず、決定木生成部３１１は、生成する決定木の本数（１以上）を、設定する（Ｓ３３０−Ａ）。生成する決定木の本数は、例えば、予め定められていてもよいし、分析代行サーバ３００のユーザ等によって決定木生成処理開始時に指定されてもよい。決定木生成部３１１は、暗号化された基礎点付きテーブルから、ランダムにレコードを抽出する（Ｓ３３０−Ｂ）。
【００９５】
図１８は、ステップＳ３３０−Ｂにおける、暗号化された基礎点付きテーブルからのレコード抽出処理の概要の一例を示す説明図である。決定木生成部３１１は、抽出処理において、暗号化された基礎点付きテーブルに抽出チェック列を追加し、抽出チェック列の全てのセルの値としてＦａｌｓｅを格納する。
【００９６】
次に、決定木生成部３１１は、基礎点付きテーブルのレコード数を上限、１を下限とする異なる乱数（例えば１以上の自然数）を、所定数（但し、１以上かつ基礎点付きテーブルのレコード数以下であり、基礎点付きテーブルのレコード数の１／２以上であることが望ましい）生成する。最後に、決定木生成部３１１は、生成した乱数を行数とする抽出チェック列のセルの値をＴｒｕｅに変更する。これにより、基礎点付きテーブルからランダムなレコードの抽出処理が実現できる。
【００９７】
続いて、決定木生成部３１１は、基礎点付きテーブルの抽出チェック用の列がＴｒｕｅであるレコードのみから、決定木テーブルを生成する（Ｓ３３１〜Ｓ３３８）。なお、ステップＳ３３１〜Ｓ３３８は実施例１と同様である。
【００９８】
決定木生成部３１１は、ステップＳ３３０−Ａで設定した本数の決定木テーブルを生成したか判定する（Ｓ３３０−Ｃ）。決定木生成部３１１は、当該本数の決定木テーブルを生成していないと判定した場合は（Ｓ３３０−Ｃ：Ｎｏ）、基礎点付きテーブルの抽出チェック列の値を全てＦａｌｓｅに再設定し、ステップＳ３３０−Ｂへ戻る。決定木生成部３１１は、当該本数の決定木テーブルを生成したと判定した場合は（Ｓ３３０−Ｃ：Ｙｅｓ）、決定木の生成処理を終了する。この結果、複数の決定木テーブルが生成される。
【００９９】
なお、実施例２におけるステップＳ３３０の処理において、複数の演算部（ＣＰＵ）を備える計算機等が、複数の決定木を並列処理で生成してもよい。具体的には例えば、乱数生成処理の並列実行し、複数の抽出チェック列を用意することにより、複数の決定木を並列処理で生成できる。
【０１００】
図１９は、複数の決定木テーブルを用いた、ステップＳ３５０における分析処理の一例を示すフローチャートである。ステップＳ３５１〜Ｓ３５５の処理は、実施例１と同様である。本実施例では、これらの処理にステップＳ３５０−Ａ、ステップＳ３５０−Ｂ、ステップＳ３５０−Ｃが追加される。
【０１０１】
ステップＳ３５１に続いて、決定木分析部３１３は、ステップＳ３５２〜Ｓ３５５の決定木分析に用いる決定木テーブルを選択する（Ｓ３５０−Ａ）。但し、決定木分析部３１３は、ステップＳ３５１で選択した分析用レコードの決定木分析には利用していない決定木テーブルを選択し、同じ分析用レコードの分析に同一の決定木テーブルの再選択は行わないものとする。
【０１０２】
続いて、ステップＳ３５２〜Ｓ３５５の処理が実行された後、決定木分析部３１３は、ステップＳ３５１で選択した分析用レコードに対し、全ての決定木テーブルを選択したかを判定する（Ｓ３５０−Ｂ）。決定木分析部３１３は、未選択の決定木テーブルがあるいと判定した場合は（Ｓ３５０−Ｂ：Ｎｏ）ステップＳ３５０−Ａへ戻る。決定木分析部３１３が、全ての決定木テーブルを選択したと判定した場合（ステップＳ３５０−Ｂ：Ｙｅｓ）、暗号判定部３１４は、複数の決定木分析の分析結果の集約を行う（Ｓ３５０−Ｃ）。
【０１０３】
一般に、決定木の構造が異なれば、分析結果が異なる場合がある。暗号判定部３１４は、例えば、多数決方式及び、並びに平均値及び代表値の算出によりステップＳ３５０−Ｃの集約処理を行う。例えば、目的変数が標準暗号の一例である決定性暗号で暗号化されている場合には、暗号判定部３１４は、どの暗号化データが多数であるか判定でき、即ち多数決方式を採用することができ、多数の暗号化データを集約した分析結果として採用することができる。
【０１０４】
また、例えば、集計比較可能暗号等の暗号化状態での演算が可能な暗号化方式で目的変数が暗号化されている場合には、暗号判定部３１４は、平均値や中央値の導出が可能な状態に集約できる、即ち平均値及び代表値の算出による集約処理ができる。
【０１０５】
なお、委託者サーバ４００のユーザ等が高度な集約を分析結果として望む場合は、分析代行サーバ３００が決定木毎の分析結果を委託者サーバに送信（Ｓ３７０）した後に、委託者サーバ４００が分析結果を復号後、平文で分析結果をさらに算出してもよい。
【０１０６】
なお、上述のステップＳ３５１〜Ｓ３５０−Ｃにおける説明は、分析用テーブルから１レコードを選択した場合の処理についての説明である。ステップＳ３５０では、分析代行サーバ３００は、当該処理を分析用テーブルのすべてのレコードに対して行う。
【０１０７】
なお、ステップＳ３５０の処理は、複数の演算部（ＣＰＵ）を備える計算機が、並列処理で決定木の選択処理と分析処理とを並列実行してもよい。
【０１０８】
なお、本発明は上記した実施例に限定されるものではなく、様々な変形例が含まれる。例えば、上記した実施例は本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施例の構成の一部を他の実施例の構成に置き換えることも可能であり、また、ある実施例の構成に他の実施例の構成を加えることも可能である。また、各実施例の構成の一部について、他の構成の追加・削除・置換をすることが可能である。
【０１０９】
また、上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行することによりソフトウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等の記録装置、または、ＩＣカード、ＳＤカード、ＤＶＤ等の記録媒体に置くことができる。
【０１１０】
また、制御線や情報線は説明上必要と考えられるものを示しており、製品上必ずしも全ての制御線や情報線を示しているとは限らない。実際には殆ど全ての構成が相互に接続されていると考えてもよい。
【符号の説明】
【０１１１】
２００  提供者サーバ、２１０  演算部、２１１  基礎点付きテーブル生成部、２１２  暗号化部、２２０  記憶部、２２１  暗号化鍵、２２２  学習用テーブル、２２３  評価関数、３００  分析代行サーバ、３１０  演算部、３１１  決定木生成部、３１２  ノード探索部、３１３  決定木分析部、３１４  暗号判定部、３２０  記憶部、３２１  評価関数、４００  委託者サーバ、４１０  演算部、４１１  暗号化部、４１２  復号化部、４２０  記憶部、４２１  暗号化鍵、４２３  復号化鍵
【図１】
2019184852.tif 000003
【図２】
2019184852.tif 000004
【図３】
2019184852.tif 000005
【図４】
2019184852.tif 000006
【図５】
2019184852.tif 000007
【図６】
2019184852.tif 000008
【図７】
2019184852.tif 000009
【図８】
2019184852.tif 000010
【図９】
2019184852.tif 000011
【図１０】
2019184852.tif 000012
【図１１】
2019184852.tif 000013
【図１２Ａ】
2019184852.tif 000014
【図１２Ｂ】
2019184852.tif 000015
【図１３】
2019184852.tif 000016
【図１４】
2019184852.tif 000017
【図１５】
2019184852.tif 000018
【図１６Ａ】
2019184852.tif 000019
【図１６Ｂ】
2019184852.tif 000020
【図１７】
2019184852.tif 000021
【図１８】
2019184852.tif 000022
【図１９】
2019184852.tif 000023