過半数判定アルゴリズム（LeetCode / Majority Elementより）

過半数を獲得した候補者を効率的に特定するにはどんな方法が良いと思いますか？

今日の問題は、そう読み替えてみるとなかなか奥が深いです。

https://leetcode.com/problems/majority-element/

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:
Input: [3,2,3]
Output: 3

Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2

n個の値からなるリストについて、n/2回より多く登場する値を特定する問題です。

解答・解説

解法1

アルゴリズムを特段考えないと、辞書を用意して出現回数をカウントし回数の最も多い値を返す、というのが最も思いつきやすい処理でしょうか。

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        d = {}
        for n in nums:
            if n not in d.keys():
                d[n] = 1
            else:
                d[n] += 1
        return max(d, key=d.get)

max(d, key=d.get)でvalueの最も大きいkeyを取得することができます。

時間計算量は、空間計算量もです。

解法2

n/2回よりも多く登場するものを見つけるんだから、わざわざ全要素を見なくても良さそうだな、と考えます。
すると、昇順でも降順でも良いですがsortして、中央にある要素を取得すれば、それが最も多く登場する要素になっている、というのがこちらの考え方です。

具体例をあげます。

nが奇数の場合：
nums = [1,1,2,2,2]のとき、nums[2]が2なので答えは2

nが偶数の場合：
nums = [1,2,2,2]のとき、nums[1]もしくはnums[2]が2なので答えは2

以下のようにnが奇数か偶数かで場合分けしても良いのですが、

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        if len(nums) % 2 == 0:
            return nums[len(nums)/2]
        else:
            return nums[(len(nums)-1)/2]

nが奇数でも偶数でも、len(nums)を2で割った商のインデックスを参照すれば良いので、以下のようにシンプルに書けます。

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return nums[len(nums)//2]

時間計算量は、空間計算量は上記のように与えられたリストに対して破壊的な処理が許されているならです。

解法3

今回の問題に対して計算量の点で最も優れているのが、Boyer-Moore Voting Algorithmです。
数学的な証明がぱっとは分からないんですが、こんなアルゴリズムがあるのかと感心しました。

これは「投票結果から過半数の票を獲得した候補者がいるのであれば、それは誰か」という判定を効率的に行うアルゴリズムです。
変数が2つ、線形時間で計算も済む、という優れものです。

変数candidateで、過半数を獲得する可能性のある値を記憶します。
一方で変数countをカウンタとして用意します。candidateが現れたら+1、candidate以外が現れたら-1します。

値のリストを順に処理していき、countが0になったらそのcandidateが過半数を占めることはないと（一旦）考えて忘れ、次の値を新たなcandidateとして記憶します。
「一旦」と書いているのは、後でその値が再登場する可能性があるからですが、とにかく一旦忘れることとします。
すると、過半数を占める値が存在すれば、最後に残ったcandidateが過半数を占める値になっています。
もし過半数を占める値が存在しなければ、最後に残ったcandidateは必ずしも最も多く出現した値ではない点が、要注意であり面白いポイントです。

具体的な動作は以下の通りです。リストの各要素を処理したときの(candidate, count)をリスト右に示します。

Input: [2,2,1,1,1,2,2]

[2,2,1,1,1,2,2] (2,1)

[2,2,1,1,1,2,2] (2,2)

[2,2,1,1,1,2,2] (2,1)

[2,2,1,1,1,2,2] (1,1)

[2,2,1,1,1,2,2] (1,2)

[2,2,1,1,1,2,2] (1,1)

[2,2,1,1,1,2,2] (2,1)

Output: 2

面白いアルゴリズムですが、最大の難点は過半数を占める値があることが前提になっている点で、現実にはそこが保証されているケースはほとんどないので、日の目を見ることは少ないかもしれません。
ブロックチェーンが51%アタックを食らったときに攻撃者を特定する、とか・・・？

実装は以下のようになります。

class Solution:
    def majorityElement(self, nums):
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate

時間計算量は、空間計算量はです。

木構造のDFS（AtCoder Beginner Contest 138より）

1週間遅れですが、ABCで木構造の問題が解けなかったので、2度同じ間違いを繰り返さぬようメモります。

問題内容・解法

D - Ki

atcoder.jp

問題文その通りの考え方をすると、以下のように計算されていくことになります（ピンクの丸が頂点id、白い丸が値）。

しかし、このロジックのまま実装すると何度も下層に降りて和を計算する必要があるため、非効率です。 このようなケースの常套手段として、累積和をとる方法があります。図にすると以下のような考え方です。

各頂点直下の頂点にのみ値を足し、足された値をまた直下の頂点に足すことで、結果的に問題文の指示通りの和が計算されることになります。

さて、このようにどんどん下層に降りていって和をとる問題なので、DFSを適用することになります。

コードは@dn6049949さんのものを多少改変して転載しています。

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]

n,q = LI()

v = [[] for i in range(n)]
for i in range(n-1):
  a,b = LI()
  a -= 1 # listのindex参照をそのまま使いたいので頂点id(1から始まっている)を-1しておく
  b -= 1 # aと同様
  v[a].append(b)
  v[b].append(a)

f = [0]*n
for i in range(q):
  p,x = LI()
  p -= 1 # aと同様
  f[p] += x

def dfs(x,d,s): # x:計算する頂点（上側）, d:計算済み(0)か否か(1), s:頂点xの値
  for y in v[x]: # 頂点xとつながる各頂点yの計算を行う
    if d[y]: # 頂点yが計算未了の場合
      s += f[y] # 頂点xの値sに頂点yの値を足す
      ans[y] = s # 頂点yの値はsに確定
      d[y] = 0 # 頂点yの計算は終わったのでd[y]=0とする
      dfs(y,d,s) # 頂点yの下層についても再帰的に計算
      s -= f[y] # 頂点yの下層の計算が終わったので、sを頂点xの値に戻す

ans = [0]*n
d = [1]*n
d[0] = 0
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
print(*ans)

LeetCode / Excel Sheet Column Title

https://leetcode.com/problems/excel-sheet-column-title/

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 
...

エクセルシートの列名をインデックスに読み換える問題です。実務で必要とされることが多そうな処理ですね。

解答・解説

解法1

まず、Discussionにとても素敵な整理表がありましたので共有します。

列名とインデックスの対応はこのようになっています。

一の位は、nを26で割った時の余りに対応しています。割り切れた場合はZに対応します。
十の位は、nを26で割った時の商を、26で割った時の余りに対応しています。割り切れた場合はZに対応します。
百の位以上も同様です。

とすると、{1:'A', 2:'B', ... , 25:'Y', 0:'Z'} というような列名とインデックスの対応を格納した辞書を作成した上で、
nを26で割った余りを格納し、次はnを26で割った商を26で割った余りを格納し、、、を繰り返していけば良いように一瞬思えます。

ただ1つ落とし穴があって、この方法だと2桁以上のZZ, ZZZといったZのみから成る列名でうまくいきません。
例えば702は本来ZZですが、702/26の商は27・余りは0、27/26の商は1・余りは1で、AAZとなってしまいます。
nを26で割った時の商を次のループに回すのではなく、n-1を26で割った時の商をを次のループに回せば、うまくいきます。

from string import ascii_uppercase

class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        d = {0:'Z'}
        for i,s in enumerate(ascii_uppercase):
            d[i+1] = s
        result = []
        while n > 0:
            result.append(d[n%26])
            n = (n-1) // 26
        result.reverse()
        return ''.join(result)

nを26で割った時の余りの値を列名に対応させるのは、{1:'A', 2:'B', ... , 25:'Y', 0:'Z'} ではなく {0:'A', 1:'B', ... , 24:'Y', 25:'Z'} として、
n-1を26で割った時の余りの値を列名に対応させても良いので、コードをすっきりさせることができます。

from string import ascii_uppercase

class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        d = {}
        for i,s in enumerate(ascii_uppercase):
            d[i] = s
        result = []
        while n > 0:
            result.append(d[(n-1)%26])
            n = (n-1) // 26
        result.reverse()
        return ''.join(result)

解法2

解法1ではstringライブラリを使いましたが、ord(s)でアスキーコードを取り出して数列を作り、chr(n)で文字に戻すことでA-Zの文字列から成るリストを作ることができます。

class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        capitals = [chr(x) for x in range(ord('A'), ord('Z')+1)]
        result = []
        while n > 0:
            result.append(capitals[(n-1)%26])
            n = (n-1) // 26
        result.reverse()
        return ''.join(result)

LeetCode / Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists/

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

これもとんち的問題。2つのLinked Listが交わるnodeを返します。
ポイントはNotesのYour code should preferably run in O(n) time and use only O(1) memory.に尽きます。余計な空間計算量は使わずに解を出す必要があります。

解答・解説

解法1

私のsubmitしたコード。計算量オーダーについて条件は満たしていますが、かなり冗長になっています。

2つのポインタを2つのLinked Listの始点から動かし、終点まで移動させます。
このとき先に到着するポインタと後に到着するポインタの移動距離の差をとっておきます。
再度、2つのポインタをLinked Listの始点から動かしますが、このときは後に到着したポインタをさきほどとっておいた差の分だけ先に進めておいてから、2つのポインタをスタートさせます。
そうすると、交わる点があればポインタは必ず出会いますし、逆にポインタが出会わなければ交わる点はない、ということになります。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        pa = headA
        pb = headB
        diff = 0
        if headA is headB: return headA
        while pa and pb:
            pa = pa.next
            pb = pb.next
        if not pa:
            while pb:
                pb = pb.next
                diff += 1
            while diff > 0:
                headB = headB.next
                diff -= 1
        else:
            while pa:
                pa = pa.next
                diff += 1
            while diff > 0:
                headA = headA.next
                diff -= 1
        while headA and headB:
            if headA is headB: return headA
            headA = headA.next
            headB = headB.next
        return None

解法2

よりスッキリしたコードがこちら。
2つのポインタを2つのLinked Listの始点から動かし、終点まで移動させるのは同じですが、終点に到達したら、もう一方のLinked Listの始点に移動してさらに動いていくのがミソです。
このようにすると、headA is headBとなった地点を返してやれば、交差するnodeがあればそのnodeが返りますし、交差するnodeがなければnullが返ります。
なるほどですね。。。

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA is None or headB is None:
            return None
        pa = headA
        pb = headB
        while pa is not pb:
            pa = headB if pa is None else pa.next
            pb = headA if pb is None else pb.next
        return pa

LeetCode / Min Stack

https://leetcode.com/problems/min-stack/

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

変わり種の問題ですが、push, pop, top, getMinのメソッドを持つクラスを定義する問題です。
クラス・メソッドの定義の仕方が分かっていれば造作もない問題ですが、ちょっとした落とし穴はあります。

解答・解説

解法1

何も考えずに書けば、このようになると思います。

class MinStack(object):

    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append(x)

    def pop(self):
        if len(self.stack) > 0: self.stack.pop()

    def top(self):
        if len(self.stack) == 0: return None
        return self.stack[-1]

    def getMin(self):
        return min(self.stack)

これでもsubmitは通るんですが、getMinメソッドの実行時にの空間計算量が必要になります。しかし実際にはその必要はありません。

解法2

今回は、push, pop, topメソッドで各要素を追加・削除・取得すること以外には、getMinで最小値を取得することだけがやりたい処理です。

そこでpushメソッドでlistの変数stackにappendする値を、(追加した要素, これまでの最小値と追加した要素のうち小さい方の値)のタプルにします。
これにより、getMinではstack[-1][1]で最小値を取得できるので、で処理できることになります。

class MinStack(object):

    def __init__(self):
        self.stack = []

    def push(self, x):
        if len(self.stack) == 0:
            self.stack.append([x,x])
        else:
            self.stack.append([x, min(x, self.stack[-1][1])])

    def pop(self):
        if len(self.stack) > 0: self.stack.pop()

    def top(self):
        if len(self.stack) == 0: return None
        return self.stack[-1][0]

    def getMin(self):
        return self.stack[-1][1]

LeetCode / Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Follow-up:
Can you solve it without using extra space?

こちらの問題に続き、連結リストがお題。
この問題では、与えられた連結リストに循環構造(cycle)が含まれている場合、cycleが始まる地点を返す必要があります。
そしてこの問題でも、空間計算量を定数時間に抑えて行う方法を考えます。

解答・解説

解法1

空間計算量を定数時間に抑えるということで、ポインタを使うんだなということは想像がつきます。実際、今回も1ずつ進むslowと2ずつ進むfastのポインタを使います。しかし今回はcycleが始まる地点も返す必要があり、これをどうメモリを使わずに計算するかです。

これはなかなか自力で思いつきづらい気がしますが、下図のような状況を考えます。

slowとfastを同じ地点からスタートさせ（前の問題ではスタート地点を1ずらしていました）、次にslowとfastが出会うまでの間に、slowがH+D進み、fastはH+L+D進む状況を考えます。
すると、fastはslowの2倍の距離進んでいるので、2(H + D) = H + D + L の関係が成り立ちます。移項すれば、H = L - D の関係が成り立ちます。

求めたいcycleが始まる地点はHに相当しますが、H = L - D ということは、下図のようにslowをfastと出会った地点からスタートさせ、一方でheadというポインタを始点からスタートさせたとき、ちょうどcycleの始点で出会うことを意味します。

つまり、まずslowとfastを同じ地点からスタートさせ、slowとfastが出会ったら、そこからslowだけスタートさせ、同時に始点からheadをスタートさせれば、slowとheadが出会った地点が求めたい答えである、ということになります。

コードに落とすと、以下の通りとなります。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = fast = head
        # まず、slowとfastが再び出会うまで動かす
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                break
        else:
            return None
        # slowとheadが出会うまで動かす
        while head is not slow:
            slow = slow.next
            head = head.next
            print(head.val, slow.val)
        return head

機械学習用データ公開におけるプライバシー保護に関する留意点

データサイエンスコンペの題材としてデータ公開する際、プライバシー保護は避けて通れない論点と考え「データ解析におけるプライバシー保護（佐久間淳）」を読んだのですが、非常によくまとまっていたので、重要と考えた点をまとめます。

そして願わくば、プライバシー保護についてよくわからないままにデータ公開を避けたり、あるいは推進したりする、思考停止した残念な人種が少しでも減ればと思います。
結構いると思うんですよね、こういう人種。

QA形式で、データ提供者が、いの一番に気になるであろう点をまとめてみました。
内容は私見を加えた上でまとめているので、詳細は原著を読んで確認してください。

尚、「機械学習用・・・」というタイトルにしていますが、個人情報を含み得るデータを公開する場合には、共通して考慮すべき内容と考えます。

Q1. 本のタイトルは「プライバシー保護」になっているけど、個人情報保護とプライバシー保護って同じもの？違うもの？

一言で言えば、個人情報保護は法令に基づき遵守すべきもの、プライバシー保護は世論の反応も鑑みて行うべきもの、です。

従って、個人情報に該当するかグレーな場合でも、プライバシー保護に配慮したデータ加工などをしてからでないと公開しない、という判断は十分あり得えます。

例えば、メールアドレスは個人情報であるか否かグレーな情報ですが、かと言って杜撰な取り扱いをしてよいデータかと言えば、プライバシー保護の観点では良くないという世論が主流と考えられ、相応の対応が必要だと言えます。

Q2. そもそも「個人情報」って具体的に何？

日本の個人情報保護法で定められている「個人情報」の定義は以下の通りです。

生存する個人に関する情報であって、当該情報に含まれる氏名、生年月日その他の記述等により特定の個人を識別できるもの（他の情報と容易に照合することができ、それにより特定の個人を識別することができることとなるものを含む。）

しかし、マイナンバーや氏名などは明らかに個人情報であると分かりますが、グレーな情報も数多く存在します。
例えば、メールアドレスやSNSアカウント情報など、個人の活動にかかわる様々な情報を蓄積した情報は、法律の枠組みでは個人情報に該当するか明確ではありません。
ただ繰り返しになりますが、個人情報だと明確に言えない情報も、先に述べたプライバシー保護の観点からは保護すべきという世論が優勢なら、データ公開者もその世論に配慮すべきと言えます。

Q3. プライバシー保護って、氏名とかマイナンバーとか、個人を特定できるものを除けば良いと思っていたけど、それじゃダメなの？

最低限の対応としては必須ですし正しいですが、それだけでプライバシー保護上のリスクがなくなるわけではありません。

具体的にどんなリスクがあるか、書籍で説明されています。
日本の個人情報保護法で、明確に配慮が必要なリスクは「特定」「連絡」「直接被害」の３種類です。
さらに言えば、パーソナルデータ提供におけるプライバシー上の問題は５種類に分けられます。

• 特定：ある個人と一意に結びつく情報（マイナンバーや運転免許番号など）が取り除かれ、どの個人に関するデータかわからないデータについて、そのデータを該当する個人と再び結びつけること

• 連結：ある個人に関するデータを、同一人物に関する別のデータと結びつけること（個人の特定がされている・いないに関わらない）

• 属性推定：ある個人に関するデータの一部が削除、あるいは抽象化されているときに、それを復元あるいは推定すること（個人の特定がされている・いないに関わらない）

• 連絡：ある個人に関するデータを保持するものが、何らかの手段でその個人に連絡すること

  • 個人を特定しないまま、入手したメールアドレスを通じて連絡するのは、「特定を経ない連絡」

• 直接被害：ある個人に関するデータを保持するものが、その個人に直接的な被害を与えること

  • クレジットカードの無断使用、SNSアカウントの無断停止など

この中で「連絡」「直接被害」は分かりやすいと思いますが、「特定」「連結」「属性推定」について具体例で補足します。

「特定」「連結」の事例

マサチューセッツ州のGroup Insurance Comission(GIC)が提供した、州職員とその家族についての医療保険データについて、個人を特定する情報が取り除かれていたはずが、外部データである選挙人名簿との照合によって再び個人が特定できる情報に復元されてしまったケースです。

当時のマサチューセッツ州知事のWilliam Weldは、ケンブリッジ在住でした。ケンブリッジの選挙人名簿によれば、6人が彼と同じ生年月日で、うち3人が男性、同じ郵便番号の人は他にいませんでした。
よって、提供情報のみからWilliam Weldの診断結果や利用内容を知ることができた、というケースです。

これは、医療保険データの側から見れば、選挙人名簿の情報を用いて「特定」が発生しており、
選挙人名簿の側から見れば、医療保健データの情報を用いて「連結」が発生したという問題です。

「属性推定」の事例

氏名情報を持たず・病名情報を持つパーソナルデータが提供され、攻撃者（データ利用者）側が氏名情報を持ち・病名情報を持たないデータを保有していたとします。
このとき、特定を伴わずとも個人の属性情報が確定的に知られるリスクがあります。

Q4. 結局、プライバシー保護のためにはどこまで気をつけたら良いの？

Q3の事例の通り、プライバシー上の問題が起こるリスクは攻撃者側が保有するデータにも依存するため、リスクが絶対的に0になることはありません。

かと言って、リスクを0に近づけるために匿名化などのデータ加工を繰り返すと、データの有用性が下がり、当初の目的であるデータ解析が実現できなくなってしまいます。

現実的な落とし所は、
「機械的に照合可能な直接／間接識別情報(※)を経由した特定は、仮名化／匿名化の技術により防ぎつつ、高度なデータ解析技術による特定は法制度によって禁じる」
という対処になると考えられます。

※ 直接識別情報、間接識別情報をはじめとするパーソナルデータの種別は、書籍の中で以下のように定義されています。

• 直接識別情報：それ単体で直接に個人の特定を可能にする情報

  • マイナンバー、運転免許番号など
  • 氏名は同姓同名者がいることもあるため常に特定可能ではないが、データベースが限られた特徴を持つ個人の集団であれば同姓同名者が存在する可能性は低いため、直接識別情報に準ずる情報と言える
  • 具体的に住居が特定できる住所は、世帯についての直接識別情報と解釈することもできる

• 間接識別情報：個人に関する不変な情報で、それ単体は個人を識別可能な状態にしないが、複数組み合わせることで個人を識別し得る情報

  • 生年月日、年齢、性別、具体的に住居が特定できない住所など

• 履歴情報：個人の活動にかかわる履歴の情報

  • 個人による購買行動、移動行動、Web検索行動など
  • 直接・間接識別情報と履歴情報は外形的には異なるが、境目は必ずしも明確でない。例えば特定の店舗での頻繁な購買履歴は、その人物の住居や職場を推測させ、間接識別情報としての性格を持つ

• 要配慮情報：特定とは直接結びつかないが、それ単体の取り扱いに配慮が必要な情報

  • 人種、国籍、宗教、犯罪歴、病歴、妊娠状態など
  • 日本の個人情報保護法では、人種・信条・社会的身分・病歴・犯罪歴などを要配慮個人情報として、個人情報よりも慎重な扱いを求めている（本人同意を得ていない取得を原則禁止している）

• 連絡情報：特定の個人への連絡を可能とする情報

  • 住所、電話番号、メールアドレスなど
  • 連絡に個人の特定は必ずしも必要ない。誰のものかわからない電話番号は、背景知識なしに特定は起こらないが、対象の個人への連絡は可能

• 個人に被害を与える情報

  • クレジットカード番号や銀行口座の暗証番号など

• データベースに関する情報

  • 多数の個人から収集したデータについては、対象とするデータがどのような集団か、それが標本調査か全数調査か、標本調査なら標本がどのような条件で抽出されたのかというデータベースそのものに関する情報は、そのデータセットが持つプライバシー上のリスクを評価する上で重要
  • 従ってデータベースに関する情報が提供されることが、プライバシー上のリスクを増大させることにつながる

Q5. 定量的に、このレベルまでは匿名化などのデータ加工をした方が良いという基準はあるの？

Q3で挙げたデータ提供に伴うリスクのうち、「連絡」「直接被害」は"自明な"リスクと言え、これを可能にする情報（「連絡」なら電話番号やメールアドレス、「直接被害」ならクレジッドカード番号やパスワード）を事前に削除することで防げるので、まずこの対応をすべきです。

問題は「特定」「連結」「属性推定」といった"非自明な"リスクへの対応です。

結論から言えば、特定性を下げるためのデータ加工の要求水準は、決まった基準はありません。
実際、リスクが絶対的に0にならない以上、どこまでデータ加工をすれば良いか？という問いには誰も答えを持たないと思います。

ただ、特定リスクを定量的に評価する指標は存在します。本記事では、匿名性と多様性について紹介します。

匿名性

匿名性は、簡単に言えば間接識別情報の値の組み合わせが同じデータのレコードが、少なくとも個存在するならば、そのデータは匿名性を持つ、と言えます。

具体例で説明します。下表のデータが提供されたとします。

このとき、もし攻撃者側が、このデータの中で「東京都港区在住の31歳の男性は山本だ」という背景知識を持っていたら、「山本は大腸ガンである」ということが特定できてしまいます。 そこで、この表の一部にマスクをかけて、下表のようにしたとします。

ここで、「東京都在住の30-39歳の男性」は2人存在するので、背景知識に対応するレコードを１件に絞ることはできません。 このとき、本表は2匿名性を持つ、と言えます。

多様性

Q3でも示した、下表の例について改めて考えます。

このような特定を伴わない確定的な属性推定は、同一の間接識別情報を共有するレコード同士で、要配慮情報が全て同じ値をとっていたために起こります。
逆に言えば、ここで要配慮情報が多様な値をとっていれば、このような属性推定のリスクは低減できます。

匿名性を持つデータの、間接識別情報の属性値の組み合わせが同じであるレコードについて、要配慮情報の属性値のバリエーションが少なくとも存在しているなら、これを多様性と呼びます。

例えば、既出の下表では、ID8827, ID2478のレコードの組は既往歴がどちらも大腸ガン、ID1204, ID0482の組はどちらも糖尿病で、多様性はありません。 一方、ID0049, ID5853の組は既往歴が喘息とアメーバ赤痢で異なっており、2多様性が保証されています。

表全体で2多様性を維持するには、多様性のない組のどちらかの既往歴をマスクするか、偽の情報を敢えて混入し、多様化するなどの方法が考えられます。

Q6. データ提供の際、事前にどのようなデータ加工を行なっておくべき？

仮名化

直接識別情報を特定性を持たない仮名IDに置き換える処理を「仮名化」と言います。 仮名IDを生成する最も単純な方法は、下図のように各々の直接識別情報に対応する仮名IDを、重複がないようにランダムに生成し、対応表を作成する方法です。

対応表による仮名化では、ある仮名IDから元の直接識別情報が推測できる確率はで、ランダム推測と変わらない確率となるので、最も安全な仮名IDの生成方法と言えます。

但し欠点としては人の人物を含むデータの仮名化を対応表を用いて行うには、直接識別情報がbitの情報で構成されている場合、データサイズの対応表を永続的に保持しておく必要があります。これを嫌えば、鍵付きハッシュ関数による仮名化などの手段を考えることになります。

匿名化

間接識別情報を加工し特定性を低減させる処理を「匿名化」と言います。特に、表形式のデータが匿名性を満足するように加工することを匿名化と呼びます。
匿名化のための手法として、再符号化、トップコーディング・ボトムコーディング、抑制など、書籍中でいくつか紹介されています。その中の1つ、再符号化について説明します。

再符号化

再符号化はカテゴリカル属性あるいは順序属性のための加工手法で、大域的再符号化と局所的再符号化の2種類があります。

大域再符号化は、複数のカテゴリ値を1つのより抽象度の高いカテゴリ値に統合します。
例えば、年齢属性を1歳刻みの値から10歳刻みの値にしたり、職業属性をグループにまとめ「医師」「看護師」をいずれも「医療従事者」とするなどです。

局所的再符号化は、匿名性を達成したい任意のレコード群を選んで再符号化します。
下表の例だと、女性2人は年齢が同じのため職業を「医療従事者」とすることで2匿名性が達成でき、男性2人は年齢が異なるため職業を「公務員」とした上で年齢をマスクすることで、2匿名性が達成できます。

仮名化・匿名化に加えて

仮名化・匿名化を行なった上で、留意すべき点があります。例えば、履歴データの場合は同一個人が長期に渡って追跡されると、購買履歴などから住所・職場を特定される可能性があるので、一定期間ごとに仮名IDを変更しつつ仮名化する、といった対応がとられることもあります。他の留意点も書籍中でいくつか言及されています。

まとめ：データ公開を推進する立場として

私はデータ公開を推進する立場なわけですが、「プライバシー保護は世論の反応も鑑みて行うものである」という記述を読み、究極、「自分のデータをどんな形であっても使われるのは嫌だ！」という個人が日本の多勢を占めようものなら、一度データ活用先進国に経済的に叩きのめされるしかないかな、と厭世的な気持ちになりました。

しかし翻って私の周囲では、「いやいやプライバシー保護も行き過ぎじゃないの？使うべきところでは使わないとダメでしょ。」という意見が多勢を占めます。
この意見にどのくらいバイアスがかかっているか分かりませんが、決してマイノリティではないと信じてみたいです。

そうなると、データ公開が推進されるか否かは、データ提供者がデータ活用の有用性とリスクを天秤にかけ、どのような判断をするかの問題になってきます。
まずは、リスクとは何か？を定性・定量的に評価した上で取組のGo/NoGoを判断する組織をもっと増やし、そうでない組織を死滅させるしかありません。

そして、データ活用の有用性ももっと発見・共有される必要もあります。
ここはデータサイエンティストの方々も含め、我々が、データを活用することでこんな未来が開けるという可能性をできるだけ多く・大きく示していくことしかない、と決意を新たにしました。

長文となりましたが、以上です。

本記事は書籍の前半部をまとめたもので、書籍の後半部ではプライバシー保護を達成するための技術についても詳細に書かれています。
そちらに関心のある方は、是非書籍を手に取ってみていただければと思います。