Privacy-aware Klassifikation auf Datenströmen am Beispiel des DAHOT Algorithmus

Term Paper (Advanced seminar) , 2018 , 25 Pages , Grade: 1,0

Computer Science - General

Um das Risiko eines Patienten für eine bestimmte Krankheit einzuschätzen, kann ein Klassifikationsmodell verwendet werden, das aus den Daten anderer Patienten gebaut wurde. Wenn im Gesundheitswesen Patientendaten verarbeitet werden, ist es wichtig, dabei die Privacy der Patienten zu gewährleisten. In der Vergangen-heit hat sich gezeigt, dass die Privacy der Patienten auch dann gefährdet sein kann, wenn die Trainingsdaten vor der Klassifikation anonymisiert wurden. Die meisten Methoden zur Gewährleistung der Privacy beziehen sich jedoch auf Da-ten in einer Datenbank und berücksichtigen die besonderen Anforderungen bei der Verarbeitung von Datenströmen nicht. Der DAHOT-Algorithmus ist eine Kombination aus Hoeffding-Baum, k-Anonymität und ℓ-Diversität und stellt die Privacy der Patienten bei der Klassi-fikation von Datenströmen sicher. In dieser Seminararbeit wird der DAHOT-Algorithmus und die dafür notwendigen Grundlagen vorgestellt. Außerdem wird auf die Effektivität und die Grenzen des DAHOT-Algorithmus eingegangen.

Zusammenfassung. Um das Risiko eines Patienten für eine bestimmte Krank­heit einzuschätzen, kann ein Klassifikationsmodell verwendet werden, das aus den Daten anderer Patienten gebaut wurde. Wenn im Gesundheitswesen Patien­tendaten verarbeitet werden, ist es wichtig, dabei die Privacy der Patienten zu gewährleisten. In der Vergangenheit hat sich gezeigt, dass die Privacy der Pati­enten auch dann gefährdet sein kann, wenn die Trainingsdaten vor der Klassifi­kation anonymisiert wurden. Die meisten Methoden zur Gewährleistung der Privacy beziehen sich jedoch auf Daten in einer Datenbank und berücksichtigen die besonderen Anforderungen bei der Verarbeitung von Datenströmen nicht. Der DAHOT-Algorithmus ist eine Kombination aus Hoeffding-Baum, k-Anonymität und I -Diversität und stellt die Privacy der Patienten bei der Klas­sifikation von Datenströmen sicher. In dieser Seminararbeit wird der DAHOT- Algorithmus und die dafür notwendigen Grundlagen vorgestellt. Außerdem wird auf die Effektivität und die Grenzen des DAHOT-Algorithmus eingegan­gen.

1 Einleitung

Unter Data Mining versteht man die Extraktion neuer, zuvor unbekannter Informatio­nen oder Muster aus großen Datenmengen 9. Eine mögliche Data-Mining-Technik ist die Klassifikation von Datensätzen. Im Bereich des Data Mining hat sich die Ge­währleistung der Privacy zu einem wichtigen Anliegen entwickelt 1. Unter Privacy versteht man dabei die Fähigkeit einer Person, selbst zu bestimmen, welche persönli­chen Informationen sie preisgibt und gegenüber wem sie das tut 7. Nach der Daten­schutzgrundverordnung ist die Privacy einer Person dann sichergestellt, wenn die personenbezogenen Daten anonymisiert wurden und dadurch nicht mehr einer be­stimmten Person zugeordnet werden können 4.

Unter Klassifikation versteht man die Voraussage einer Klasse für einen bisher un­bekannten Datensatz 16. Sie kann beispielsweise eingesetzt werden, um die Kredit­würdigkeit eines neuen Bankkunden vorauszusagen 3 oder das Risiko eines neuen Patienten für bestimmte Krankheiten einzuschätzen 13. Liefert die Klassifikation genaue Ergebnisse, kann dies jedoch die Privacy der Bankkunden oder der Patienten gefährden. Veröffentlicht beispielweise ein Krankenhaus Informationen über die behandelten Krankheiten und den Krankheitsverlauf der Patienten, können diese In­formationen von außenstehenden genutzt werden, um die Krankheit eines bestimmten Patienten herauszufinden. Dies kann auch dann der Fall sein, wenn eindeutige Be­zeichner wie Name oder Versichertennummer vor der Veröffentlichung gelöscht werden 19.

1997 veröffentlichte die Krankenversicherungsgesellschaft der staatlichen Ange­stellten im US-Bundesstaat Massachusetts medizinische Daten über ihre Versicherten, damit Forscher diese für wissenschaftliche Zwecke nutzen können. Um die Privacy der Angestellten sicherzustellen, wurden die Namen und die Sozialversicherungs­nummern vor der Veröffentlichung entfernt. Andere Angaben wie Geburtsdatum, Postleitzahl oder Geschlecht blieben jedoch erhalten 14. Latanya Sweeney 19 kombinierte die veröffentlichten Daten mit dem Wählerverzeichnis des Bundesstaats, in dem neben dem Name und der Adresse auch das Geburtsdatum, das Geschlecht und die Postleitzahl enthalten waren. Auf diese Weise konnte sie die Krankendaten des damaligen Gouverneurs eindeutig identifizieren. Sie fand außerdem heraus, dass 87 % der US-Bevölkerung anhand von Geburtsdatum, Geschlecht und Postleitzahl eindeutig identifiziert werden können.

Bei der Klassifikation reicht es nicht aus, die Privacy der Patienten nur in den Ein­gabedaten sicherzustellen 11. Vielmehr muss auch die Privacy der Patienten auch im Klassifikationsergebnis gewährleistet sein. Das bedeutet, dass es nicht möglich sein darf, anhand des Klassifikationsergebnisses die Klasse einzelner Datensätze, die zur Klassifikation genutzt wurden, herauszufinden.

Viele Methoden zur Gewährleistung der Privacy der Patienten im Klassifikations­ergebnis beziehen sich nur auf die Klassifikation von Daten in einer Datenbank 11. Jedoch werden Sensor-, Telekommunikations- und Börsendaten als Datenströme bereitgestellt, wodurch diese Methoden nicht anwendbar sind. Kotecha und Garg 11 schlagen daher einen Algorithmus vor, der die Klassifikation von Datenströmen er­laubt und dabei die Privacy der Personen im Klassifikationsergebnis sicherstellt. Der Algorithmus ist eine Kombination aus Hoeffding-Baum, k-Anonymität und ('-Diversität.

Diese Seminararbeit befasst sich mit der Klassifikation von Datenströmen unter Beachtung der Privacy der Personen im Klassifikationsergebnis am Beispiel des DAHOT-Algorithmus. Dazu wird in Anschnitt 2.1 zunächst die Klassifikation mit Entscheidungsbäumen erklärt. Danach werden die Grundlagen der k-Anonymität und der ('-Diversität in Abschnitt 2.2 und 2.3 erläutert. Anschließend wird in Abschnitt 2.4 auf die besonderen Anforderungen für die Verarbeitung von Datenströmen eingegan­gen. In Abschnitt 2.5 wird der Hoeffding-Baum vorgestellt, der zur Klassifikation auf Datenströmen genutzt werden kann. Darauf folgt in Abschnitt 3 die Vorstellung des von Kotecha und Garg 11 vorgeschlagenen DAHOT-Algorithmus, der zur Klassifi­kation von Datenströmen dient und die Privacy der Personen im Klassifikationser­gebnis gewährleistet. Zum Schluss folgt in Abschnitt 4 die Zusammenfassung und der Ausblick.

2 Grundlagen

Der DAHOT-Algorithmus ist ein Klassifikationsverfahren für Datenströme, das einen Hoeffding-Baum zur Klassifikation verwendet. Die Privacy der Personen, deren per- sönliche Informationen in dem Datenstrom enthalten sind, wird mithilfe von k- Anonymität und ('-Diversität gewährleistet.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1. Entscheidungsbaum zur Klassifikation der Krankheit eines Patienten. Die Beschriftung der Blätter (Dreiecke) gibt die Krankheit des Patienten an

In Abschnitt 2.1 wird zunächst erklärt, wie die Klassifikation mit Entscheidungs­bäumen funktioniert. Um die Privacy der Personen, deren Daten zur Klassifikation verwendet werden, sicherzustellen, gibt es die in Abschnitt 2.2 vorgestellte k- Anonymität. Die f-Diversität ist eine Verbesserung der k-Anonymität und wird in Abschnitt 2.3 vorgestellt.

Die zusätzlichen Anforderungen an das Klassifikationsverfahren, die notwendig sind, wenn das Klassifikationsverfahren auf Datenströmen arbeiten soll, werden in Abschnitt 2.4 behandelt. Der Hoeffding-Baum ist ein Entscheidungsbaum, mit dem Datenströme klassifiziert werden können und wird in Abschnitt 2.5 vorgestellt.

2.1 Klassifikation mit Entscheidungsbäumen

Unter Klassifikation versteht man das Vorhersagen einer Klasse für einen bisher un­bekannten Datensatz 16. Dazu wird zunächst ein Klassifikationsmodell so trainiert, dass es die Klassen der vorhandenen Datensätzen möglichst gut vorhersagt. Dieses Modell wird anschließend verwendet, um die Klasse des bisher unbekannten Daten­satzes vorherzusagen. Bekannte Klassifikationsverfahren sind Entscheidungsbäume, Bayes-Klassifikatoren und Neuronale Netze 16.

Abbildung 1 zeigt ein Beispiel für einen Entscheidungsbaum, der dazu genutzt werden kann, die Krankheit eines Patienten vorherzusagen. Jeder innere Knoten for­mulierte eine Bedingung für ein Attribut. Um vorauszusagen, an welcher Krankheit ein neuer Patient leidet, folgt man von der Wurzel aus derjenigen Kante, deren Be­schriftung für das jeweilige Attribut des neuen Patienten zutrifft. Dieses Vorgehen wiederholt man, bis man an einem Blattknoten angekommen ist. Die Blätter sind mit den jeweiligen Klassen beschriftet, die sich gemäß dem Pfad von der Wurzel zu dem Blatt ergeben 16.

Tabelle 1. Ausschnitt der Patientendatenbank eines Krankenhauses 17. Die letzte Spalte (Krankheit) enthält die Klasse, der der Datensatz zugeordnet ist

Abbildung in dieser Leseprobe nicht enthalten

Für eine 1993 geborene und geschiedene Patientin würde der Entscheidungsbaum voraussagen, dass die Patientin an Atemnot leidet. Dazu betrachtet man zunächst das Geburtsdatum der Patientin. Da die Patientin nach 1988 geboren wurde, geht man zu dem rechten Kindknoten. Dort wird das Geschlecht geprüft. Da die Patientin weiblich ist, folgt man anschließend der rechten Kante zum Knoten Familienstand. Da die Patientin geschieden ist, folgt man hier wieder der rechten Kante und endet schließ­lich in einem Blatt mit der Beschriftung Atemnot.

Um einen Entscheidungsbaum aufzubauen, werden zunächst Trainingsdaten benö­tigt. Tabelle 1 zeigt einen Ausschnitt der Patientendatenbank eines Krankenhauses. Darin ist für jeden Patienten dessen Geburtsdatum, Geschlecht, Postzeitzahl und Fa­milienstand verzeichnet. Außerdem steht in der letzten Spalte, an welcher Krankheit der Patient leidet. Die letzte Spalte entspricht dabei der Klasse, der der Patient zuge­ordnet wird.

Um nun den Entscheidungsbaum aufzubauen, muss zunächst das Attribut gefunden werden, anhand dessen sich die Datensätze am besten klassifizieren lassen. Zur Be­stimmung des besten Attributs kann die Entropie verwendet werden. Die Entropie beschreibt den Informationsgehalt der Datensätze. Sie ist umso geringer, je reiner die Daten sind. Sind alle Datensätze in derselben Klasse, sind die Daten rein und die Entropie ist 0. Ist die eine Hälfte der Datensätze in der Klasse Atemnot und die andere Hälfte in der Klasse Fieber, sind die Daten unrein und die Entropie ist 1. Die Entropie wird nach folgender Formel berechnet 18:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2. Verteilung der Klassenzugehörigkeiten der Patientendaten. Die Tabelle an dem Elternknoten gibt an, wie viele Datensätze den Klassen Atemnot bzw. Fieber zugeordnet sind, wenn der Knoten nicht gesplittet wird. Die Tabellen an den beiden Blättern geben an, viele Datensätze den Klassen Atemnot bzw. Fieber zugeordnet sind, wenn der Knoten gesplittet wird

Um den Informationsgewinn zu abzuschätzen, der sich ergibt, wenn die Datensätze anhand des Attributs a aufgesplittet werden, zieht man die Entropien der Kindknoten von der Entropie des Elternknotens ab. Die Entropien der Kindknoten werden dabei nach dem Anteil der Datensätze gewichtet, der sich in dem jeweiligen Kindknoten befindet. Somit kann der Informationsgewinn nach folgender Formel abgeschätzt werden 20:

Abbildung in dieser Leseprobe nicht enthalten

HElternknoten bezeichnet hierbei die Entropie der Datensätze im Elternknoten. Hlinks und Hrechts bezeichnen die Entropien im linken und rechten Kindknoten. nlinks und nichts stehen für die Anzahl der Datensätze im linken und rechten Kindknoten. n ist die Anzahl der Datensätze insgesamt.

Abbildung 2 zeigt die Verteilung der Klassenzugehörigkeiten der Datensätze aus Tabelle 1, wenn die Datensätze anhand des Attributs Geburtsdatum auf die Kindkno- ten verteilt werden. Dabei wird angenommen, dass alle Datensätze, deren Geburtsda­tum vor 1988 liegt, in den linken Kindknoten verschoben werden und alle anderen Datensätze in den rechten Kindknoten. Die Entropien berechnen sich wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Der Informationsgewinn wird für alle Attribute berechnet. Anschließend werden die Datensätze anhand des Attributs auf die Kindknoten verteilt, das den höchsten Infor­mationsgewinn bietet. Für die Kindknoten wird das Vorgehen rekursiv fortge- setzt. Das Prozedere endet, wenn in allen Kindknoten alle Datensätze zur gleichen Klasse gehören oder wenn ein anderes Abbruchkriterium erfüllt ist 16.

Tabelle 2. Nicht anonymisierte Patientendatenbank 17. Der Identifikator ist grün, die Quasi-Identifikatoren blau und das sensible Attribut rot hinterlegt

Abbildung in dieser Leseprobe nicht enthalten

Beim Aufbau des Entscheidungsbaums kann das Problem der Überanpassung auf­treten. In diesem Fall passt sich der Baum zu stark an die Trainingsdaten an. Dadurch liefert der Entscheidungsbaum zwar gute Ergebnisse für die Trainingsdaten, ist aber für die Klassifikation von bisher unbekannten Datensätzen zu komplex und liefert daher keine guten Ergebnisse. Um eine Überanpassung zu vermeiden, wird das Auf­bauen des Entscheidungsbaums an einem bestimmten Punkt abgebrochen, auch wenn noch nicht alle Datensätze in einem Knoten zur gleichen Klasse gehören. Dadurch wird der Baum weniger hoch und somit weniger komplex. Als Abbruchkriterium kann beispielsweise eine maximale Baumhöhe oder ein Grenzwert für den Informati­onsgewinn festgelegt werden 16.

2.2 k-Anonymität

Zur wissenschaftlichen Bewertung des Nutzens bestimmter Therapien veröffentlichen Krankenhäuser Patentendaten. Da es sich dabei auch um personenbezogene Daten handelt, ist es notwendig, diese zu anonymisieren 4. Dabei ist besonders wichtig, dass kein Rückschluss auf die Krankheit eines bestimmten Patienten gezogen werden kann.

Um dieses Ziel zu erreichen, haben Sweeney und Samarati 17 das Prinzip der k- Anonymität vorgeschlagen. Dabei werden die Attribute in die Kategorien Identifika­tor, Quasi-Identifikator und sensibles Attribut eingeteilt. Identifikatoren sind Attribu­te, die einen Datensatz eindeutig identifizieren, wie beispielsweise Name, Personal­nummer oder Krankenversichertennummer. Ein Quasi-Identifikator alleine kann eine Person nicht identifizieren. Jedoch kann eine Person anhand der Kombination mehre­rer Quasi-Identifikatoren wie Geburtsdatum, Postleitzahl oder Geschlecht in vielen Fällen eindeutig identifiziert werden 19. Das sensible Attribut enthält persönliche Informationen, die auf keinen Fall einer konkreten Person zugeordnet werden dürfen, wie beispielsweise die Krankheit, an der eine bestimmte Person leidet.

Tabelle 3. Anonymisierte Patientendatenbank mit 2-Anonymität. Die Äquivalenzklasse ist weiß, die Quasi-Identifikatoren blau und das sensible Attribut rot hinterlegt

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2 zeigt einen weiteren Ausschnitt der bereits in Abschnitt 2.1 verwendeten Patientendatenbank. Der Name des Patienten dient als Identifikator (grün hinterlegt) und identifiziert einen Patienten eindeutig. Um die Daten zu anonymisieren, muss der Name deshalb entfernt werden. Die Krankheit des Patienten ist das sensible Attribut (rot hinterlegt), das für die Auswertung der veröffentlichten Daten wichtig ist und daher erhalten bleiben muss. Die blau hinterlegten Attribute sind Quasi­Identifikatoren. Ein einzelner Quasi-Identifikator reicht noch nicht aus, um einen Patienten eindeutig zu identifizieren. So haben in dem Beispiel in Tabelle 2 Emil und Frieda am gleichen Tag Geburtstag. Kombiniert man jedoch die Quasi-Identifikatoren miteinander, ist es möglich, Patienten eindeutig zu identifizieren. In dem Beispiel in Tabelle 2 kann die Kombination aus Geburtsdatum, Geschlecht, Postleitzahl und Familienstand eindeutig einem Patienten zugeordnet werden.

Das Prinzip der k-Anonymität 17 verlangt, dass es zu jedem Datensatz mindes­tens (k-1) andere Datensätze mit den gleichen Quasi-Identifikatoren gibt. Dazu wer­den Äquivalenzklassen aus jeweils mindestens k Datensätzen gebildet, die die glei­chen Werte für die Quasi-Identifikatoren haben. Um das zu erreichen, werden die Attributwerte generalisiert und unterdrückt. Je größer der Parameter k gewählt wird, desto stärker werden die Daten anonymisiert. Da jedoch in diesem Fall auch mehr Informationen entfernt werden, sinkt der Nutzen, der aus den anonymisierten Daten gewonnen werden kann.

Generalisierung kann dann eingesetzt werden, wenn sich ein Attribut anhand einer Hierarchie verallgemeinern lässt. So kann wie in Tabelle 3 das Geburtsdatum von der Tagesebene zunächst auf die Monatsebene und anschließend auf die Jahresebene verallgemeinert werden. Die Postleitzahl kann generalisiert werden, indem man die letzten Ziffern durch einen Platzhalter ersetzt. Je stärker ein Attribut generalisiert wird, desto mehr Werte kann es annehmen und desto weniger eignet es sich, eine bestimmte Person zu identifizieren.

Die Unterdrückung der Werte ist dann sinnvoll, wenn ein Attribut nur wenige dis­krete Werte annehmen kann und es keine sinnvolle Hierarchie zwischen den Attri­butwerten gibt. In Tabelle 3 ist dies für Geschlecht und Familienstand der Fall. In diesen Spalten wird der ursprüngliche Attributwert durch einen Platzhalter ersetzt.

Durch die Generalisierung und Unterdrückung der Werte nimmt der Wahrheitsge­halt nicht ab, da keine falschen Daten eingefügt werden. Alternativ wäre es auch mög­lich, ein zufälliges Rauschen hinzuzufügen, um die Daten zu anonymisieren.

Das Erstellen einer k-anonymisierten Version der Daten ist ein NP-schweres Prob­lem 15. Jedoch gibt es Approximationsalgorithmen mit einer Approximationsgaran­tie von O(ln(k)) 10. Das bedeutet, dass das Ergebnis des Approximationsalgorith­mus im ungünstigsten Fall um O(ln(k)) schlechter ist, wie das optimale Ergebnis.

2.3 t-Diversität

Das Prinzip der k-Anonymität hat einige Schwächen, die von Machanavajjhala et al. beschrieben wurden und die in bestimmten Fällen eine eindeutige Identifizierung einer Person anhand der Quasi-Identifikatoren zulassen 12.

Eine Schwäche ist die Anfälligkeit gegen einen Homogenitätsangriff 12. Ist be­kannt, dass in den anonymisierten Patientendaten in Tabelle 3 ein Datensatz über eine bestimmte Person gespeichert ist, kann dieses Wissen in einigen Fällen ausgenutzt werden, um die Krankheit diese Person herauszufinden. Ist über eine Person bei­spielsweise bekannt, dass sie im September 1984 geboren wurde und im Postleitzahl­bereich 02141 wohnt, kann man daraus schließen, dass der Datensatz dieser Person in Äquivalenzklasse 2 liegt. Da in Tabelle 3 alle Personen in Äquivalenzklasse 2 unter Atemnot leiden, muss dies die Krankheit der gesuchten Person sein.

Um abzuschätzen, wie viele Personen von einem Homogenitätsangriff betroffen sein können, stellen Machanavajjhala et al. 12 folgende Überschlagsrechnung an: Wenn eine Datenbank mit 60.000 Datensätzen mittels 5-Anonymität anonymisiert wird, ergeben sich 12.000 Äquivalenzklassen. Kann das sensible Attribut 3 verschie­dene Werte annehmen, werden in jeder 81. Äquivalenzklasse alle Datensätze den gleichen Wert für das sensible Attribut annehmen. Bei 12.000 Äquivalenzklassen sind also 148 Äquivalenzklassen anfällig für einen Homogenitätsangriff. Da jede Äquiva­lenzklasse mindestens 5 Datensätze enthält, können so die sensiblen Attribute von 740 Personen eindeutig anhand der Quasi-Identifikatoren ermittelt werden.

Neben dem Homogenitätsangriff kann vorhandenes Hintergrundwissen über eine Person ausgenutzt werden, um mit hoher Wahrscheinlichkeit das sensible Attribut einer Person anhand der Quasi-Identifikatoren zu ermitteln 12. Ist beispielsweise bekannt, dass in den anonymisierten Patientendaten in Tabelle 3 ein Datensatz über eine bestimmte Person gespeichert ist und dass diese Person im September 1984 ge­boren wurde und im Postleitzahlbereich 0217* wohnt, kann man wie beim Homoge­nitätsangriff schließen, dass der Datensatz dieser Person in Äquivalenzklasse 1 liegt. Ist nun auch bekannt, dass die gesuchte Person in ihrer Kindheit bereits Windpocken hatte, kann man mit hoher Wahrscheinlichkeit ausschließen, dass die Person nochmal an Windpocken erkrankt ist, da eine frühere Windpockenerkrankung zu einer lebens­langen Immunität führt. Da eine Windpockenerkrankung somit ausgeschlossen ist, muss die gesuchte Person an Bluthochdruck leiden.

[...]

• College: University of Stuttgart
• Grade: 1,0
• Publication Year: 2018
• Pages: 25
• Catalog Number: V1313303
• ISBN (PDF): 9783346793263
• ISBN (Book): 9783346793270
• Language: German
• Tags: privacy-aware, klassifikation, datenströmen, beispiel, dahot, algorithmus