Modified k-nearest neighbor classifiers for dealing with secure encrypted data

Abstract

Son zamanlarda veri depolama ve veri yönetme amaçlı olarak ortaya çıkanpaylaşımlı serverların kullanımı, özellikle bu veriler kişisel ve hassas bilgileriçermekteyse, veri sahipleri için çok sayıda güvenlik açığı ortaya koymaktadır. Busorunların üstesinden gelmek amacıyla veriler yalnızca kripto şifresine sahip yetkilikişilerin erişimine izin vermek amacıyla kriptolanmaktadır. Veri kriptolama işlemi buverilere geleneksel veri madenciliğinin uygulanmasını imkânsız hale getirmektedir,çünkü bu tekniklerin bu verilerdeki değerlere ve içerikteki her özelliğin veri türüneerişiminin olması gerekmektedir.Veri madenciliği her şirket için verilerinden en yüksek verimi alabilmek amacıylaçok önemlidir. En önemli veri madenciliği uygulamalarınsan biri sınıfı henüz belliolmayan bir veri grubunun (tuple) sınıfının mevcut sınıflandırılmış verilere dayanaraktahmin edilmesini mümkün kılan Veri Sınıflandırmasıdır. Bu bağlamda, kriptolamaşifresini veri yönetim serverına göstermeden veya depolanmış herhangi bir veriyi buveriyle ilgisi olmayan başka bir yetkili kullanıcının görmesine gerek kalmayacak şekildekriptolanmış verilerin sınıflandırılması elzem hale gelmiştir. Verilerinsınıflandırılmasında yaygın olarak k-En Yakın Komşu sınıflandırma sistemikullanılmaktadır. Verilere erişim olmaksızın bir verisetinin sınıflandırılması için homomorfik kripto sistemleri kullanarak uygulanan güvenli birçok k-EYKsınıflandırıcıları önerilmektedir. Homomorfik kripto sistemlerinde kriptolanmış verilerüzerinde uygulanan bir matematiksel işlemin kriptolanmış sonucu bu veriler deşifreedilmeksizin hesaplanabilmektedir. Mevcut güvenli k-EYK sınıflandırıcıları, verilerdedepolanmış olan kriptolanmış değerlere bağlı olan veri grupları (tuples) arasındakimesafeleri bulmak amacıyla homomorfik hesaplamalara dayanmaktadır.Bu araştırmada veri grupları arasındaki mesafelerin hesaplanması için verilerinkriptolanmış değerine ve asıl sınıflandırmadaki katkısına göre her özelliğin ağırlığınadayanan ve homomorfik metotları kullanan güvenli-modifiye k-EYK sınıflandırıcılarıönerilmektedir. Bu araştırmada iki ağırlıklandırma metodu test edilmektedir; BilgiEntropisi ve Gini Çeşitlililik Endeksi. Her metot iki değişik şekilde test edilmiştir, lokalve global. Global ağırlıklandırma her özellik için bir ağırlık hesaplamaktadır; diğeryandan, lokal ağırlıklandırma her özellik için her sınıfın ağırlığını hesaplamaktadır.Deneysel sonuçlar sınıflandırma sonuçlarında Temel Sınıflandırma Sistemine göreönemli düzeyde gelişme göstermektedir.Anahtar Kelimeler: Veri Madenciliği; Sınıflandırma; Kriptolama; Homomorfik; k-EnYakın Komşu (k-EYK).

The recent trend of using shared servers for data storage and management posesmany challenges to the data owners to protect the information being outsourced,especially if these data contain personal or sensitive information. To overcome theseproblems, the data are encrypted so that only authorized clients, who have theencryption key, are able to decrypt the contents of these data. Data encryption makes itimpossible to apply traditional data mining techniques to these data, as these techniquesmust access the values stored in the data and the data type of each attribute. Data miningis very important for any corporation to make the best use of their data. One of the mostimportant data mining tasks is the data classification, which enables predicting a classfor a new unclassified tuple depending on the existing classified data. Thus, it hasbecome mandatory to classify encrypted data without the need to reveal the encryptionkey to the data management server or expose any stored data to any other authorizedclient who is unrelated to those data. k-Nearest Neighbors classifier is widely used toclassify data. Thus, many Secure k-NN classifiers are proposed to enable classifying adataset without having access to these data using homomorphic cryptosystems, whichare cryptosystems where an encrypted result of a mathematical operation on encrypteddata may be calculated without decrypting these data. The existing Secure k-NN classifiers rely on homomorphic calculations to find the distances among tuplesdepending on the encrypted values stored in the data.In this study, modified Secure k-NN classifiers are proposed that use homomorphiccalculations to compute distances among tuples depending on the encrypted values ofthe data and the weight of each attribute, according to its contribution to the actualclassification. Two weighting methods are tested in this study, which are informationentropy and Gini diversity index. Each method is tested in two different schemes thatare global and local. Global weighting calculates one weight per attributes while localweighting calculates a weight per each class for each attribute. The experimental resultsshow significant improvement in classification results, compared to the basic classifier.Keywords: Data Mining; Classification; Encryption; Homomorphic; k-NearestNeighbors.