Locally differentially private mechanisms for sequential and high-dimensional data analysis
Sıralı ve yüksek-boyutlu veri analizi için lokal diferansiyelmahremiyetli mekanizmalar
- Tez No: 941896
- Danışmanlar: DR. ÖĞR. ÜYESİ MEHMET EMRE GÜRSOY
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2025
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Bilimi ve Mühendisliği Bilim Dalı
- Sayfa Sayısı: 82
Özet
Veri mahremiyeti ve koruması ihtiyacının artmasıyla birlikte, lokal diferansiyel mah remiyet (LDP), mahremiyet-korumalı veri toplanması için yaygın olarak kabul edilen bir standart haline gelmiştir. LDP tekil veriler için kapsamlı ¸ sekilde çalışılmış olsa da, LDP'nin sıralı ve yüksek-boyutlu verilere uygulanması hala yeterince araştı rılmamıştır. Bu tezde, LDP'nin bu iki veri türüne uygulanmasındaki güncel lit eratürü ilerletmek için yeni LDP mekanizmaları öneriyoruz. İlk olarak, sıralı verilerden LDP altında ayrık zamanlı Markov zinciri model lerinin öğrenilmesi için Prima'yı öneriyoruz. Markov zincirleri, konum izleri, zaman serileri, doğal dil ve konuşma gibi sıralı verilerin analizinde ve modellenmesinde sıkça kullanılmaktadır. Ancak, bu tür veri kaynaklarının çoğunun mahremiyet açısından hassas olduğu göz önüne alındığında, Markov zincirlerinin öğrenilmesi için mahremiyet korumalı yöntemler tasarlanması gerekmektedir. Prima, bu ihtiyacı karşılamaktadır. Prima'da, her kullanıcı sıralı veri kaydını kendi cihazında yerel olarak kodlar ve LDP protokollerini kullanarak bozar. Bu amaçla iki bitvektör tabanlı LDP protokolünü (RAPPOR ve OUE) uyarlıyoruz; ek olarak, GRR pro tokolünün yeni bir uzantısı olan AdaGRR'ı geliştiriyoruz. Ayrıca, dengesiz dizi uzun luklarına sahip durumlarda faydayı daha iyi korumak için mahremiyet bütçesinin eşit olmayan şekilde bölümünü sağlayan bütçe tahsis stratejileri kullanmayı öneriyoruz. Sunucu tarafında, Prima bozulmuş verilerden Markov olasılıklarını kestirmek için yeni algoritmalar kullanmaktadır. Prima'yı üç gerçek dünya veri kümesi, dört fayda ölçütü ve çeşitli mahremiyet bütçeleri ile bütçe tahsis stratejisi kombinasyonları kul lanarak deneysel olarak değerlendiriyoruz. Sonuçlar, mahremiyet kısıtlamaları ol madan öğrenilen Markov zincirleri ile karşılaştırıldığında, Prima'nın yüksek fayda ve düşük hatalı Markov zincirleri öğrenmeyi sağladığını göstermektedir. İkinci olarak, çok-boyutlu verilerin toplanması için yeni bir LDP mekanizması olan MCM'yi (Matris-Tabanlı Veri Toplama Mekanizması) öneriyoruz. MCM'de, her kullanıcı çok-boyutlu kaydını bir bitmatrisi kullanarak kodlar. Bitmatrislerinin satırları LDP'yi sağlayacak şekilde bozulur. Ardından, MCM'nin temel katkısı, sunucunun öznitelik alanlarında yer alan tüm değer çiftlerinin eş oluşum sayılarını geri kazanmasını sağlayan yeni sunucu-taraflı kestirim sürecidir. MCM'yi, iki popüler öznitelik seçme metriği olan bilgi kazancı ve ki-kare kullanarak çok-boyutlu veriler den öznitelik seçimi yapmak amacıyla kullanıyoruz. MCM ve ona eşlik eden öznitelik seçme algoritmalarını üç veri kümesi, iki fayda ölçütü ve değişken mahremiyet bütçeleri kullanarak deneysel olarak değerlendiriyoruz. Ayrıca, çözümümüzü LDP altında öznitelik seçimi yapılmasını sağlayan en son yöntem olan LDP-FS ile karşılaştırıyoruz. Çözümümüzün deneysel olarak LDP-FS'e kıyasla daha doğru bilgi kazancı ve ki-kare değerleri sağladığını ve böylece literatürü ilerlettiğini gösteriyoruz. Ayrıca, LDP sağlanırken, öznitelik seçimi için öznitelikler arasındaki korelasyonların doğru luklu biçimde korunduğunu gösteriyoruz.
Özet (Çeviri)
With the increasing need for data privacy and protection, local differential privacy (LDP) has emerged as a widely accepted standard for privacy-preserving data col- lection. While LDP has been studied extensively for singular data, its application to sequential and multidimensional data remains underexplored. In this thesis, we propose novel LDP mechanisms for advancing the state-of-the-art in the application of LDP to these two data types. First, we propose Prima for learning discrete-time Markov chain models from sequential data under LDP. Markov chains are frequently used in the analysis and modeling of sequential data such as location traces, time series, natural language, and speech. However, considering that many such data sources are privacy-sensitive, it is imperative to design privacy-preserving methods for learning Markov chains. Prima addresses this need. In Prima, each user locally encodes and perturbs their sequential record on their own device using LDP protocols. For this purpose, we adapt two bitvector-based LDP protocols (RAPPOR and OUE); and furthermore, we develop a novel extension of the GRR protocol called AdaGRR. We also propose to utilize custom privacy budget allocation strategies for perturbation, which enable uneven splitting of the privacy budget to better preserve utility in cases with uneven sequence lengths. On the server side, Prima uses novel algorithms for estimating Markov probabilities from perturbed data. We experimentally evaluate Prima using three real-world datasets, four utility metrics, and various combinations of privacy budget and budget allocation strategies. Results show that Prima enables learning Markov chains with high utility and low error compared to Markov chains learned without privacy constraints. Second, we propose MCM (Matrix-Based Data Collection Mechanism), a novel LDP mechanism for the collection of multidimensional data. In MCM, each user encodes their multidimensional record into a bitmatrix. The rows of the bitmatrix are perturbed in a way that satisfies LDP. Then, the key contribution of MCM lies in its novel server-side estimation process, which enables the server to recover co- occurrence counts of all pairs of values in attribute domains. We utilize MCM to perform feature selection from multidimensional data using two popular feature se- lection metrics: information gain and chi-square. We experimentally evaluate MCM and the accompanying feature selection algorithms using three datasets, two utility metrics, and varying privacy budgets. Furthermore, we compare our solution with LDP-FS, a state-of-the-art solution for feature selection under LDP. We experimen- tally show that our solution yields more accurate information gain and chi-square values compared to LDP-FS, thereby improving the state-of-the-art. Furthermore, we demonstrate that correlations between attributes are accurately preserved in feature selection while LDP is satisfied.
Benzer Tezler
- Privacy-preserving data collection and sharing in modern mobile internet systems
Modern mobil internet sistemlerinde gizlilik korumalı veri toplama ve paylaşma
MEHMET EMRE GÜRSOY
Doktora
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGeorgia Institute of TechnologyBilgisayar Bilimleri Ana Bilim Dalı
PROF. DR. LİNG LİU
- The role of inflammatory factors and differentially expressed mirnas in chordoma pathophysiology
İnflamatuvar faktörlerin ve farklı seviyelerde ifade edilen mirnaların kordoma patofizyolojisindeki rolü
ŞÜKRÜ GÜLLÜOĞLU
Doktora
İngilizce
2017
Moleküler TıpYeditepe ÜniversitesiBiyoteknoloji Ana Bilim Dalı
DOÇ. DR. ÖMER FARUK BAYRAK
- Kalbe özgü 'subtractive' hibridizasyon kütüphanesinden seçilen yeni genlerin analizleri
Analysis of the novel genes selected from heart specific subtractive hybridization library
AYŞE EVRİM BAYRAK
- Identification of potential transcriptomic biomarkers for varroa resistance in honey bees (Apis mellifera anatoliaca)
Bal arılarında (Apis mellifera anatoliaca) varroa direnci için potansiyel transkriptomik biyobelirtiçleri tanımlaması
HAŞİM HAKANOĞLU
Yüksek Lisans
İngilizce
2022
BiyoistatistikSabancı ÜniversitesiMoleküler Biyoloji-Genetik ve Biyomühendislik Ana Bilim Dalı
YRD. DOÇ. DR. CHRISTOPHER LOUIS MAYACK
DR. ÖĞR. ÜYESİ STUART JAMES LUCAS
- Tectonic and magmatic structure of Lake Van basin and its structural evolution, Eastern Anatolia accretionary complex (EAAC), East-Turkey
Van Gölü havzasının tektonik ve magmatik yapısı ve yapısal evrimi, Doğu Anadolu yığışım karmaşığı (DAYK), Doğu Türkiye
MUSTAFA TOKER
Doktora
İngilizce
2011
Jeofizik Mühendisliğiİstanbul Teknik Üniversitesiİklim ve Deniz Bilimleri Ana Bilim Dalı
PROF. DR. A. M. CELAL ŞENGÖR
