Knowledge hiding in decision trees

Abstract

My research is motivated by the emerging need for privacy-safe sharing among different organizations. In this doctoral thesis, we present two different approaches to hiding decision tree rules. In the first one, we propose a look-ahead technique using linear Diophantine equations to add the appropriate number of instances while maintaining the initial entropy of the nodes. This method adds an optimizing look-ahead perspective to an existing method, and it can be used to hide one or more decision tree rules, sequentially or in parallel. This method adopts a record augmentation approach by also modifying the class labels to hide critical classification rules in binary datasets. Moreover, we present a novel technique, Local Distortion Hiding (LDH), which does not affect the class labels of the sensitive instances, as our previous techniques do, but instead modifies the attributes’ values of these specific instances. Such a hiding methodology, as well as the first one, is preferred over other heuristic solutions like output perturbation or cryptographic techniques which they actually limit the usability of the data since the raw data itself is readily available for public use. While the new technique may need to modify more values of the initial data set, it does so by not requiring the addition of extra instances, and it thus saves on the size of the sanitized data set. This trade-off is an extra tool in the arsenal of the data engineer who might want to explore a range of possibilities when tasked with a data hiding mandate. In the proposed method, we first identify the instances that contribute to the creation of a specific rule and then, by appropriately changing attribute values, we can successfully hide this rule with minimum impact on the rest of the decision tree. Finally, we apply the method regarding the local distortion hiding (LDH) in different data sets and present some well-chosen examples, in the fields of Medicine, Finance and Education to demonstrate the efficient hiding of pre-selected decision tree rules and measure the corresponding accuracy of this method.

Η έρευνα αυτή εστιάζει στην αναδυόμενη ανάγκη για ανταλλαγή δεδομένων μεταξύ των διαφόρων οργανισμών. Σε αυτή τη διδακτορική διατριβή παρουσιάζουμε δύο διαφορετικές προσεγγίσεις για την απόκρυψη των κανόνων δέντρων αποφάσεων. Στην πρώτη, προτείνουμε μια τεχνική look-ahead χρησιμοποιώντας γραμμικές Διοφαντικές εξισώσεις για να προσθέσουμε τον κατάλληλο αριθμό παρατηρήσεων διατηρώντας την αρχική εντροπία των κόμβων. Αυτή η μέθοδος προσθέτει μια βελτιστοποιημένη οπτική γωνία σε μια υπάρχουσα μέθοδο και μπορεί να χρησιμοποιηθεί για να κρύψει έναν ή περισσότερους κανόνες δέντρων αποφάσεων, διαδοχικά ή παράλληλα. Αυτή η μέθοδος υιοθετεί μια προσέγγιση αύξησης παρατηρήσεων, τροποποιώντας επίσης τις τιμές των κλάσεων για την απόκρυψη των κριτηρίων κριτικής ταξινόμησης σε δυαδικά σύνολα δεδομένων. Στην συνέχεια παρουσιάζουμε μια νέα τεχνική, τη μέθοδο της απόκρυψης με τοπική παραμόρφωση (LDH), που δεν επηρεάζει τις τιμές των κλάσεων των ευαίσθητων παρατηρήσεων, όπως συμβαίνει στην προηγούμενη τεχνική, αλλά τροποποιεί τις τιμές των ιδιοτήτων αυτών των συγκεκριμένων παρατηρήσεων. Μια τέτοια μέθοδος απόκρυψης κανόνων σε ένα δέντρο απόφασης προτιμάται σε σχέση με άλλες ευρετικές λύσεις όπως διαταραχές εξόδου ή κρυπτογραφικές τεχνικές - που περιορίζουν τη χρηστικότητα των δεδομένων - δεδομένου ότι τα ίδια τα πρωτογενή δεδομένα είναι άμεσα διαθέσιμα για δημόσια χρήση. Στην προτεινόμενη μέθοδο, προσδιορίζουμε πρώτα τις παρατηρήσεις που συμβάλλουν στη δημιουργία ενός συγκεκριμένου κανόνα και στη συνέχεια, με κατάλληλες μεταβολές στις τιμές κάποιων χαρακτηριστικών, μπορούμε να κρύψουμε με επιτυχία αυτόν τον κανόνα με ελάχιστο αντίκτυπο στο υπόλοιπο δέντρο αποφάσεων. Επιπλέον, η νέα αυτή τεχνική (LDH) τροποποιεί τις τιμές των ιδιοτήτων του αρχικού συνόλου δεδομένων χωρίς να απαιτείτε η προσθήκη πρόσθετων παρατηρήσεων. Η τεχνική (LDH) θα μπορούσε να είναι ένα νέο εργαλείο για τον μηχανικό δεδομένων προκειμένου να μπορέσει να τροποποιήσει κατάλληλα τα δεδομένα με σκοπό να αποκρύψει κάποιον κανόνα, ο οποίος κρίνεται «ευαίσθητος» και θα μπορούσε να γνωστοποιηθεί μετά την εφαρμογή ενός μοντέλου δέντρου αποφάσεων σε αυτά τα δεδομένα. Τέλος, εφαρμόζουμε τη μέθοδο της απόκρυψης με τοπική παραμόρφωση (LDH) σε διαφορετικά σύνολα δεδομένων και παρουσιάζουμε μερικά επιλεγμένα παραδείγματα στους τομείς της Ιατρικής, των Οικονομικών και της Εκπαίδευσης για να αποδείξουμε την αποτελεσματική απόκρυψη των προεπιλεγμένων κανόνων δέντρων αποφάσεων και να μετρήσουμε την αντίστοιχη ακρίβεια αυτής της μεθόδου.