Örnekleme yoluna dayalı K-anonimlik gizlilik koruma algoritması
Wu Xiang, Zang Hao, Yu Xiao
(Tıbbi Bilgi Okulu, Xuzhou Tıp Üniversitesi, Xuzhou, Jiangsu 221116)
K-anonimlik, bilgi gizliliğinin korunması için yaygın olarak kullanılan bir teknolojidir ve K-anonimlik teknolojisinin kullanımı, yayınlanan verilerde kaçınılmaz olarak bilgi kaybına neden olacaktır.Bu nedenle, K-anonimleştirmeden sonra veri setlerinin kullanılabilirliğinin nasıl iyileştirileceği her zaman K-anonimlik gizliliği olmuştur. Korumanın araştırma odağı. Bu bağlamda, örnekleme yoluna dayalı yerel bir genelleme algoritması - SPOLG algoritması önerilmektedir. Algoritma, genelleme yolunu daha az bilgi kaybı ile bulmak için genelleme ızgarasına dayanmaktadır.Yol bulma süresini azaltmak için eşit olasılıklı örnekleme fikri getirilmiştir.Örnekleme için eşit olasılıklı örneklemede sistematik örnekleme yöntemi seçilmekte ve örnekleme genelleme ızgarasındaki veri setinin yerine kullanılmaktadır. Hedef genelleme yolunu bulun ve son olarak bu yoldaki veri kümesini genelleştirin. Aynı zamanda, bu algoritma bilgi kaybı miktarını azaltabilen ve yayınlanan veri setinin kullanılabilirliğini artırabilen yerel genelleme teknolojisini kullanır. Deneysel sonuçlar, algoritmanın anonimleştirilmiş veri setinin düşük bilgi kaybına ve yüksek veri kullanılabilirliğine sahip olduğunu kanıtlamaktadır.
Gizlilik koruması; yol; bilgi kaybı; örnekleme; K-anonimlik
TP391 belge tanımlama kodu: ADOI: 10.16157 / j.issn.0258-7998.2016.12.030
Wu Xiang, Zang Hao, Yu Xiao. Örnekleme yoluna dayalı K-anonimlik gizlilik koruma algoritması Elektronik Teknoloji Uygulaması, 2016, 42 (12): 115-118.
İngilizce alıntı biçimi: Wu Xiang, Zang Hao, Yu Xiao. Örnekleme yoluna dayalı K-anonim gizlilik koruma algoritması. Application of Electronic Technique, 2016, 42 (12): 115-118.
0 Önsöz
K-anonimlik, basit ve etkili bir gizlilik koruma modelidir. K-anonimliğini uygulamak için iki husus dikkate alınmalıdır: (1) Veri yayınlama işlemi sırasında gizliliğin sızdırılmamasını sağlamak; (2) Yayınlanan anonim veriler pratiktir.
Yukarıdaki iki gerekliliğe dayanarak, birçok bilim insanı birçok anonim algoritma önerdi. Ancak kabaca küresel genelleme algoritması ve yerel genelleme algoritması olarak ikiye ayrılabilir. Bunun aksine, yerel genelleme algoritması sadece K-anonimliğini gerçekleştiremez, aynı zamanda anonim tablodaki bilgi kaybını da bir ölçüde azaltarak genelleştirilmiş veri setini daha kullanışlı hale getirir.
Bununla birlikte, yerel genellemede optimal K-anonimliğini bulmak NP-zor bir problem olduğunu kanıtlamıştır.K-anonimlik algoritmasının nasıl optimize edileceği ve verilerin kullanılabilirliğinin en üst düzeye nasıl çıkarılacağı, çözülmesi gereken acil bir problem haline gelmiştir. Bu nedenle, bu makale örnekleme yolu-SPOLG (Örnekleme Yolu Optimizasyonu Yerel Genelleme) algoritmasına dayalı bir yerel K-anonimlik algoritması önermektedir.
SPOLG algoritması, eşit olasılıklı örnekleme fikrini ortaya koyar, bir genelleme yolu bulmak için popülasyonun yerini alacak kadar yeterli örnek seçer ve bulunan yola göre veri kümesini yerelleştirir. Eşit olasılıklı örnekleme ile seçilen örnekler, genel veri setinin dağılımını temsil edebilir ve daha az bilgi kaybına sahip genelleme yolu, algoritmanın verimliliğini büyük ölçüde artıran örnek yolu bulma yoluyla hızlı bir şekilde bulunabilir. Aynı zamanda, algoritma tarafından benimsenen yerel genelleme teknolojisi, serbest bırakılan veri setinin yüksek kullanılabilirliğini sağlar.
1 Temel semboller ve tanımlar
1.1 K-anonimlik ile ilgili tanım
SPOLG algoritmasını uygulama sürecinde, örnekleme genelleme yoluna dayalı olarak K-anonimlik algoritmasını tanımlamak için Tablo 1'i örnek olarak alın. Veri yayıncısı tarafından tutulan veri tablosunun T (A1, A2, ..., An) olduğu varsayıldığında, tablodaki her bir grup, yaş, iş, ırk, cinsiyet, çalışma saatleri, maaş gibi belirli bir varlığın ilgili bilgilerini gösterir ( Hassas özellikler) vb.
1.2 SPOLG algoritmasıyla ilgili tanım
Tanım 2: Sistematik örnekleme: Veri kümesindeki grupları kimliğe göre sıralayın, başlangıç noktası olarak rastgele bir demet seçin ve örnek sayısı önceden belirlenmiş örnekleme oranını karşılayana kadar düzenli aralıklarla bir demeti örnekleyin.
Tanım 3: Örnekleme genelleme yolu: genelleme kafesinin kök düğümünden başlayarak, örneği genelleştirdikten sonra alt düğümlerinin bilgi kaybını hesaplayın, en az bilgi kaybına sahip alt düğümü aşağıdan genelleme kafesinin yaprağına kadar yolun içine yerleştirin düğüm.
Örneğin: Şekil 1'de, kullanıyorsanız < W1, R0 > Bu düğümün genelleştirilmiş örnek oranı < W0, R1 > Genelleştirilmiş örneğin bilgi kaybı küçükse, o zaman seçin < W1, R0 > Yolun ikinci düğümüdür vb. Gibi < W0, R0 > < W1, R0 > < W1, R1 > < W2, R1 > Bu yol, olası bir örnekleme genelleme yoludur.
Tanım 4 Örnekleme yolu bulma süresinin oranı: tüm algoritma akışındaki örnekleme verilerinden örnekleme genelleme yollarını oluşturmak için harcanan zaman SP'nin yüzdesi. Algoritmanın tamamı tarafından harcanan sürenin SA olduğunu varsayarsak, hesaplama formülü şöyledir:
2 Algoritma uygulaması
2.1 Algoritma uygulaması
Bu yazıda önerilen örnekleme yoluna dayanan yerel bir genelleme algoritması olan SPOLG algoritması, eşit olasılık örnekleme fikrini ortaya koyar ve genelleme yolunu bulmak için veri setini sistematik örnekleme örnekleriyle değiştirir. Spesifik algoritma aşağıdaki gibidir:
Giriş: Giriş tablosu T, yarı tanımlayıcı set QI, eşdeğerlik sınıfı kısıtlaması k ve örnekleme oranı .
Çıktı: Veri kümesi T "K-anonimliğini tatmin ediyor.
(1) Örnek alın
(2) Bir örnekleme genelleme yolu bulun
İşlev: yol (QI, T )
/ * QI yarı tanımlayıcı kümesidir, T örneklenen veri kümesini temsil eder * /
Başla
QI'den genelleştirilmiş bir G kafesi oluşturun;
G genelleme kafesinin 0. katman düğümü n0'ı P yolunun başlangıç noktası P0 olarak alın;
N1'in doğrudan genelleme kafesi aracılığıyla genelleştirildiği düğümü bulun, bu düğümlerin genelleştirmesi T ile elde edilen bilgi kaybını hesaplayın ve P yolunun ikinci düğümü olarak genelleştirilmiş veri kümesi T'nin en küçük bilgi kaybına sahip düğüm n2'yi seçin P1;
P yolunu elde etmek için yolun son noktası Pi olarak genelleme kafesi G'nin tepe noktasına ulaşana kadar adımını tekrarlayın;
Dönüş yolu P;
Son
(3) Anonimleştirilmiş veri sayfası
T'de K-anonimliğini sağlayan tupleları kaldırın;
Döngüyü bitir
Veri sayfasına geri dönün;
Son
Yukarıdaki adımlardan, algoritmanın esas olarak üç ana bağlantı içerdiği görülebilir: sistematik örnekleme, yol bulma ve veri setinin anonimleştirilmesi Örnekleri seçmek için sistematik örneklemeyi kullanarak, seçilen örneklerde daha düşük bilgi kaybına sahip genelleme yolunu bulun. Veri kümesini yerel olarak genelleyin. Yolun başından başlayarak, K-anonimliğini tatmin etmeyen tupleları aşağıdan yukarıya tüm tuplelar K-anonimliğini tatmin edene kadar genelleştirin.
2.2 Algoritma rasyonalitesinin analizi
Bu makaledeki algoritma, her bir demetin aynı olasılıkla örneklenmesini sağlamak için sistematik örnekleme kullanır.Daha düşük bilgi kaybına sahip genelleme yolu, eşit olasılık örnekleme örnekleri aracılığıyla hızlı bir şekilde bulunabilir, böylece veri setinin genel genellemesinden sonra bilgi kaybı küçüktür. Aynı zamanda, yerel genelleme, anonimleştirilmiş veri setinin bilgi kaybının küçük olmasını sağlar, bu nedenle bu algoritma uygulanabilir.
3 Deneysel doğrulama ve sonuç analizi
3.1 Deney ortamı
Bu makale, deneysel veri kümesi olarak UCI Makine Öğrenimi Havuzundaki Yetişkinler veri kümesini kullanır. Yetişkin veri kümesi, ABD Nüfus Sayımı verilerinden oluşur. Veri kümesindeki eğitim kümesini kullanır ve varsayılan değer kayıtlarını kaldırır. Toplamda 30162 kayıt vardır. Bu makale seçer Cinsiyet, ırk, medeni durum, eğitim düzeyi, iş, milliyet, yaş ve her bir öznitelik için genelleme kurallarına referanslar dahil olmak üzere yedi öznitelik tanımlayıcı öznitelikler olarak kullanılır. Deneysel platform yapılandırması şöyledir: Çekirdek 2.50 GHz / 8 GB, Windows 7, ilgili tüm kodlar Java tarafından uygulanır ve Eclipse Mars.2 Sürümünde (4.5.2) çalıştırılır. Deneysel veriler, beş deneyden elde edilen deneysel verilere dayanılarak elde edilen ortalama değerlerdir.
3.2 Deneysel sonuçların analizi
Deney, bu makaledeki algoritmayı temel olarak bilgi kaybı ve uygulama süresi yönlerinden ölçer. Bu deneyde, farklı sayıda yarı tanımlayıcı ve farklı k değerleri koşulları altında bilgi kaybı derecesini ve yürütme süresindeki değişikliği karşılaştırmak için karşılaştırma algoritması olarak Incognito algoritması kullanılmıştır. Bilgi kaybı derecesi, literatürün hesaplama yöntemini benimser.
Demetlerin bilgi kaybı miktarı:
3.2.1 Veri örnekleme analizi
Yol bulma süresinin oranı formül (1) ile hesaplanır ve bilgi kaybı miktarı formül (2) ve (3) 'e göre ölçülür.Şekil 2 ve Şekil 3'ten | QI | sabit olduğunda, örnekleme hızı arttıkça, Örnekleme yolu bulma süresinin oranı önemli ölçüde artmıştır, ancak bilgi kaybı miktarındaki dalgalanma küçüktür, bu nedenle daha küçük bir örnekleme oranı kullanılabilir; aynı zamanda, örnekleme hızı ne kadar büyükse, veri setinin dağılımı o kadar tutarlıdır, bu nedenle yeterli sayıda örnek kullanılmalıdır Veri kümesini temsil eder. Yukarıdakilere dayanarak, bu makaledeki aşağıdaki deneylerde% 1 örnekleme oranı kullanılmaktadır.
3.2.2 Bilgi Kaybının Analizi
Şekil 4, yarı tanımlayıcı özniteliklerin sayısı | QI | = 7 ve k 5/10/15/20/25/50 olduğunda SPOLG algoritması ile Gizli algoritma arasındaki bilgi kaybının karşılaştırmasını gösterir. Şekil 4'ten SPOLG algoritmasının ve Incognito algoritmasının çalıştırılmasının neden olduğu bilgi kaybı miktarının k değerinin artmasıyla arttığı görülmektedir.Bunun nedeni k değeri büyüdükçe her bir denklik sınıfında bulunan tuple sayısının artması ve veri setinin genelleme derecesinin artmasıdır. Büyür, böylece IL artar. Ancak k değeri büyüdükçe, SPOLG algoritması bilgi kaybı IL'deki artış daha küçüktür. Nedeni Tablo 3'te açıkça görülmektedir. Tupleların ilk üç basamağının genelleme oranı% 50'den fazladır.Veri setindeki tupleların çoğunun sadece bir kez genellemeden geçtiği, dolayısıyla genelleme sonrası veri seti bilgi kaybının IL küçüktür, k değeri arttıkça IL daha az artar. Şekil 5, k = 10 olduğunda | QL | 3/4/5/6/7 aldığında ve anonim verilerin bilgi kaybı miktarının SPOLG algoritması ve Incognito algoritması ile karşılaştırılmasını göstermektedir. Şekil 5'ten görülebileceği gibi, Gizli algoritma tarafından üretilen bilgi kaybı IL açık bir yükselme eğilimine sahiptir ve bu makaledeki algoritma, yarı tanımlayıcı özelliğinin | QI | arttıkça bilgi kaybı IL'de önemli dalgalanmalara sahip değildir. Tablo 4'teki veriler, | QI | arttığında, ilk üç adımın genelleme oranının% 60'a ulaştığını göstermektedir. Görülebileceği gibi, veri setindeki tupleların çoğunun yalnızca bir kez genelleştirmeye tabi tutulmuş olması, dolayısıyla genellemeden sonra veri setinin bilgi kaybı IL'si küçüktür ve IL | QI | artışıyla önemli ölçüde dalgalanma göstermez. Yukarıdakileri özetlemek gerekirse: Bu makaledeki algoritmanın bilgi kaybı açısından bariz avantajları vardır, serbest bırakılan veriler daha az distorsiyona ve yüksek kullanılabilirliğe sahiptir.
3.2.3 Zaman verimliliği analizi
Şekil 6 ve 8 sırasıyla çalışma süresi, k ve | QI | arasındaki ilişkiyi göstermektedir. Şekil 6'dan, | QI | sabit olduğunda, k değeri arttıkça, genelleme derecesi büyür ve üretilen eşdeğerlik sınıflarının sayısı azalır ve her bir dizinin eşdeğerlik sınıflarını bulma süresi büyük ölçüde azalır. Şekil 7'den görülebileceği gibi k değeri sabit olduğunda | QI | artışıyla kısıt koşulları artmakta, eşdeğerlik sınıflarının sayısı artmakta ve her bir demetin eşdeğerlik sınıflarını bulma süresinin artması dolayısıyla bu algoritmanın çalışma süresinin biraz farklı olduğu görülmektedir. artırmak. Şekil 6 ve Şekil 7'ye dayanarak, bu makaledeki algoritmanın zaman verimliliği açısından Gizli algoritmadan biraz daha kötü olduğu görülebilir, ancak bilgi kaybı miktarındaki önemli azalma nedeniyle, bu algoritmanın kapsamlı avantajları açıktır.
4 özet
Bu makale, yarı tanımlayıcı özniteliği olan SPOLG algoritmasının genelleme yolunu temel alan bir K-anonimleştirme algoritması önermektedir. Algoritma, genelleme yolunu hızlı bir şekilde bulmak için eşit olasılık örneklemesini kullanır ve bulunan genelleme yolu temelinde veri seti analizi gerçekleştirir. Yerel genelleme. Deneysel sonuçlar, algoritmanın genelleştirilmiş veri tablosunun daha az bilgi kaybına ve yüksek kullanılabilirliğe sahip olduğunu göstermektedir.
Referanslar
Gizliliği korumak için SWEENEY L.A modeli. International Journal on Uncertainty Fuzziness and Knowledge-Based Systems, 2002, 10 (5): 557-570.
SWEENY L. Genelleme ve bastırma kullanarak k-anonimlik özelliğinin korunması Uluslararası Belirsizlik, Bulanıklık ve Bilgi Tabanlı Sistemler Dergisi: IJUFKS, 2002, 10 (5): 571-588.
SWEENY L. Tıbbi verileri paylaşırken anonimliği garanti etmek: veri sistemi 1997 AMIA Yıllık Sonbahar Sempozyumu Bildirileri, Journal of the American Medial Informatis, Association, AMIA, 1997, 4 (ek): 51-55.
MACHANAVAJJHALA A, GEHRKE J, KIFER D. L-çeşitliliği: k-anonimliğin ötesinde gizlilik.Proc of the 22. In Conference on Data Engineering. Piscataway, NJ: IEEE, 2006: 24-36.
LI J Y, WONG C W, FU W C, vd. Öznitelik hiyerarşik yapılarında kümelenerek k-anonimliğin sağlanması. Veri Ambarlama ve Bilgi Keşfi. Springer Berlin Heidelberg, 2006: 405-416.
Ren Xiangmin K-anonimliğine dayalı gizlilik koruma yöntemleri üzerine araştırma Harbin: Harbin Teknoloji Enstitüsü, 2012.
