بخشی از مقاله
چکیده
حفظ حریم خصوصی افراد در داده کاوی توزیع شده از موضوعات بسی ار با اهمیت برای افراد و سازمانها است. در این پژوهش بر مبنای رویکرد -Kگمنامی و دو روش مبتنی بر آنتروپی جهت افزایش بی نظمی، کاهش احتمال افشای اطالعات پزشکی در پایگاه داده توزیع شده پیشنهاد شده است. این دو روش بر روی پایگاه داده Adult پیاده سازی و ارزیابی شده است. نتایج ارزیابی نشان می دهد که روش های پیشنهادی منجر به افزایش بی نظمی و کاهش احتمال افشای اطالعات افراد می گردد.
کلمات کلیدی:محیط های توزیع شده،آنتروپی، -kگمنامی
-1 مقدمه
انقلاب داده ای کنونی مرهون پیشرفت در شبکه های کامپیوتری و دستگاههای محاسباتی است، اما هرجا که گسترش شبکههای کامپیوتری پیش رو باشد، ناگزیر با مسئله تبادل اطلاعات برخورد دارد .حوزه پزشکی یکی از حوزه های پرکاربرد برای داده کاوی است. از جایی که داده های پزشکی بیماران معمولا حساس است، مسئله ای که در اینجا با اهمیت می باشد، حفظ حریم خصوصی کاربران و بیماران است. چگونگی انتشار یک نسخه از اطلاعات خصوصی که از شناسایی آن ها توسط افراد جلوگیری می کند، با استفاده از مدل حفاظت -kگمنامی انجام می شود. مسئله این پژوهش حفظ حریم خصوصی بیماران یک بیمارستان در محیط توزیع شده است .
مدل حفاظت -kگمنامی این است که اطلاعات منتشر شده هر فرد، حداقل برای k-1 نفر از افرادی که اطلاعات آن ها نیز منتشر شده، قابل شناسایی نباشد. در اینجا k عدد طبیعی است و به این صورت تعریف می شود که حداقل k رکورد با شبه شناسه یکسان وجود دارند.روش -kگمنامی برای حفظ حریم خصوصی بیماران و پزشکان در دادهکاوی متمرکز و توزیعی استفاده می شود. در حقیقت -kگمنامی مدلی است که به منظور گمنامی افراد در پایگاه داده ها به کار می رود و شناسایی افراد را از طریق شبه-شناسه آن ها مشکل می کند.در این مدل ویژگی ها یا فیلد داده ها به سه مجموعه تقسیم می شوند:
. ویژگی های Quasi-identifier یا QID که مجموعه ای از ویژگی های غیر حساس هستند، ولی به کمک ترکیبی از این مجموعه می توان به صورت یکتا به داده های حساس افراد دست پیدا کرد.
. ویژگی های حساس: مجموعه ی داده های حساس که فاش شدن این داده ها به منزله ی نقض حریم خصوصی افراد می باشد.
. ویژگی غیر حساس: مجموعه داده هایی که در مجموعه یک و دو قرا نمی گیرند.
الگوریتم این مدل به این صورت است که، در ابتدا هر رکورد را در یک کلاستر مجزا قرار می دهد. الگوریتم نزدیکترین رکوردها را در یک کلاستر قرار می دهد و این کار را تا زمانی که همه کلاسترها بیش از k رکورد عضو داشته باشد ادامه می دهد. نزدیکترین رکوردها با استفاده از تعریف فاصله اقلیدسی بین رکوردهای داده مشخص می شوند.مسئله -kگمنامی یک مسئله NP-hard است که برای دستیابی به مدل -kگمنامی در حفظ حریم خصوصی افراد به طور کلی دو روش فرونشانی1 و کلی سازی2 وجود دارد.در داده کاوی توزیع شده نیز مساله کشف و استخراج دانش مشابه داده کاوی عادی در زمینه های خوشه بندی توزیع شده، کشف قواعد وابستگی بصورت توزیع شده و طبقه بندی توزیع شده - که با نام یادگیری توزیع شده طبقه بند هم از آن نام برده می شود - مورد تحقیق و بررسی قرار دارد.
ضمن اینکه در بحث داده کاوی توزیع شده، مساله مربوط به محرمانگی داده ها - Privacy - Preserving حتما باید مدنظر قرار گیرد.[1] این مقاله به بررسی نقش آنتروپی و دو روش مبتنی بر آن بر مبنای رویکرد -kگمنامی با تغییر آنتروپی در مجموعه کلاس های داده و تغییر در ویژگی ها سعی در افزایش بینظمی سیستم و تاثیر آن در بهبود امنیت دادهها و کاهش احتمال افشای اطلاعات پرداخته است.باقی مقاله به صورت ذیل سازماندهی شده است: بخش 2 شامل کارهای مرتبط، بخش 3 معرفی کننده مدل پیشنهادی، بخش 4 پیاده سازی و ارزیابی ودر نهایت بخش 5 نتیجه گیری را ارائه می کند.
-2 کارهای مرتبط
در این بخش با مروری اجمالی کارهایی که در این حیطه صورت گرفته است شرح داده می شود.در سال های اخیر، الگوریتم های متعددی برای اجرای -Kگمنامی از طریق فرونشانی و تعمیم مطرح شده است. Samarati الگوریتمی با استفاده از جستجوی دودویی در سلسله مراتب تعمیم دامنه معرفی کرده است که به شناسایی جداول -kگمنامی حداقل می پردازد .[2] این الگوریتم با ترکیب تکنیکهای مبتنی بر تابع چکیده ساز3 بهبود یافتهاست.[3] دیگری [4] از یک جدول به طور کامل تعمیم شده، شروع به کار می کند و مجموعه داده را به جدول -kگمنام مشخص تبدیل می کند. لفور و همکاران [5] الگوریتمی با استفاده از روش پایین به بالا ارائه کردند. فونگ و همکاران [6] از روش اکتشافی بالا به پایین برای ساخت جدول -kگمنام بهره برده اند.
از منظر نتایج نظری، میرسون و ویلیامز[7] و آگاروال و همکاران[8] اثبات کردند که مسئله -kگمنامی یک مسئله NP-hard است - بر اساس تعداد سلول ها و تعدادی از ویژگیهایی که تعمیم و فرونشانی - و توصیف الگوریتم های تقریبی برای -kگمنامی بهینه شدهاند.رویکرد پیشنهادی بر مبنای آنتروپی و بررسی دو روش مبتنی بر آن علاوه بر نوآوری در روش -kگمنامی نسبت به روش های پیشین، با تغییر آنتروپی در مجموعه کلاس های داده و تغییر در ویژگی ها سعی در افزایش بی نظمی سیستم و تاثیر آن در بهبود امنیت داده ها و کاهش احتمال افشای اطلاعات پرداخته است.در صورتی که روش های دیگر از جمله -pحساسیت در -K گمنامی[9]، -lتنوع[10]و -tنزدیکی[11] با توجه به ماهیت حساسیت ویژگی ها نیز محدودیت هایی دارند.[12]
-3استفاده از آنتروپی در حفظ حریم خصوصی بر مبنای -kگمنامی
واژه آنتروپی یااِنتروپی - بی نظمی - در رشتههای گوناگون علمی، معانی متفاوت دارد. مفهوم آنتروپی به اندازه گیری "بی نظمی" یک سیستم می پردازد. در تئوری اطلاعات ، آنتروپی عدم اطمینان را با استفاده از یک متغیر تصادفی اندازه گیری میکند.[13] بنابراین مفهوم آنتروپی در تئوری اطلاعات مشابه آنتروپی شانون است. به معنای ارزش مورد انتظار از اطلاعات موجود در یک پیام - معمولا در واحد بیت - .اگر صفت هدف بتواند c مقدار مختلف بگیرد پس بی نظمی S مربوط به این دسته بندی cتایی به شکل زیر تعریف می شود:که pi نسبتی از اعضای S می باشد که متعلق به دستهء i هستند.[14]در این مقاله دو روش پیشنهاد شده است .در روش اول برای بهبود و افزایش میزان آنتروپی سیستم به تغییر میزان آنتروپی هر دسته از کلاسهای موجود در دادهها میپردازیم. روش دوم پیچیدهتر بوده و بر اساس مفهوم آنتروپی جزیی1 انجام میشود.[15] در ادامه این دو روش به تشریح معرفی خواهند شد.
-1-3 افزایش آنتروپی سیستم با تغییر آنتروپی مجموعه کالسهای داده
الگوریتم پیشنهادی در این بخش با این فرض شروع به کار میکند که هر بیماری در مجموعه دادهها یک کلاس از دادهها را تشکیل میدهد. بطور مثال فرض کنیداگر کلاسهای بیماری در مجموعه داده شامل سرماخوردگی، آنفولانزاو سرطان باشد، که به ترتیب با a, b, c نشان داده می شوند. آنتروپی سیستم توسط فرمول زیر محاسبه میشود.الگوریتم پیشنهادی H-Entropy ارائه شده با بدست آوردن مقدار آنتروپی از طریق فرمول فوق شروع به کار میکند. اگر مقدار آنتروپی از آستانه H بیشتر یا مساوی باشد، الگوریتم به اتمام میرسد. در غیر اینصورت باید بتوان با استفاده از مکانیزمهای تعمیم یا سرکوب مقدار آنتروپی را افزایش داد. بنابراین شرط خاتمه این الگوریتم شرط است. که در آن آنتروپی بیانگر مقدار کل آنتروپی سیستم است.
در صورتی که شرط برآورده نشود، الگوریتم وارد فاز بعدی میشود. این مرحله را میتوان به دو روش مختلف انجام داد.
·شکستن کلاس با بالاترین احتمال رخداد به کلاسهای کوچکتر
·ادغام دو کلاس با کوچکترین مقدار احتمال رخداد و ایجاد یک کلاس بزرگتر
بنابراین در هر یک از این دو روش در ابتدا لازم است کلاسها بر اساس احتمال رخداد مرتب شوند. برای مثال اگر در مجموعه داده دو کلاس بیماری سرماخوردگی و آنفولانزا دارای کمترین میزان احتمال رخداد باشند، رکوردهای موجود در این دو کلاس ادغام شده و کلاس جدیدی به نام "سرماخوردگی یا آنفولانزا" در مجموعه داده تشکیل می شود. الگوریتم پیشنهادی بدین صورت عمل می کند که در ابتدا به ادغام مجموعه کلاسها در دادهها میپردازد و اگر با این روش نتوان به میزان H از آنتروپی رسید، به شکستن کلاس های با بزرگترین احتمال رخداد می پردازد. شکل 1 الگوریتم پیشنهادی را نشان می دهد.هر کلاس بیماری به عنوان یک کلاس مجزا در مجموعه داده در نظر گرفته میشود.
اگر تعداد کلاسهای موجود در این مجموعه از عدد 2 بزرگتر باشد، مقدار احتمال رخداد برای این کلاس ها بصورت صعودی مرتب می شود. بنابراین دو کلاس با کمترین مقدار احتمال رخداد در بالای لیست قرار دارد. با ترکیب این دو کلاس و حذف آنها از مجموعه جواب، کلاس حاصل به مجموعه جواب اضافه میشود. حال مقدار آنتروپی سیستم برای مجموعه جواب جدید بدست آمده محاسبه می شود. در صورتی که آنتروپی بدست آمده از حد آستانه بیشتر باشد، به جواب مسئله دست یافته ایم، در غیر این صورت عملیات ترکیب دو کلاس با کمترین مقدار احتمال رخداد ادامه خواهد یافت.اگر نتوانیم شرط خاتمه را با بدست آوردن آنتروپی بالاتر از H ارضاء کنیم، به مجموعه جوابی با دو کلاس میرسیم. در این حالت از مجموعه جواب اولیه شروع و این بار به جای ادغام کلاسهایی با کمترین مقدار احتمال رخداد، به تجزیه کلاسهایی با بیشترین احتمال رخداد پرداخته می شود و این عمل تا ارضا شدن شرط - Entropy ادامه می شود.
-2-3 افزایش آنتروپی سیستم با تغییر آنتروپی مجموعه ویژگیها
از آنتروپی تمامی ویژگیهایی که در بدست آوردن کلاس داده تاثیر گذارند و مجموعه داده را تشکیل میدهند، استفاده می شود. مقادیر ویژگی باید گسسته باشد و یا در صورت مقادیر پیوسته، قابلیت تغییر به مقادیر گسسته وجود داشته باشد. بطور مثال اگر در مجموعه داده ویژگیهای سن و وزن وجود داشته باشد، مقدار آنتروپی برای هر یک از آنها محاسبه می شود. پس از محاسبه
