A COMPARATIVE STUDY ON MICROAGGREGATION TECHNIQUES FOR MICRODATA PROTECTION

Abstract
Microaggregation is an efficient Statistical Disclosure Control (SDC) perturbative technique for microdataprotection. It is a unified approach and naturally satisfies k-Anonymity without generalization orsuppression of data. Various microaggregation techniques: fixed-size and data-oriented for univariate andmultivariate data exists in the literature. These methods have been evaluated using the standard measures:Disclosure Risk (DR) and Information Loss (IL). Every time a new microaggregation technique wasproposed, a better trade-off between risk of disclosing data and data utility was achieved. Though thereexists an optimal univariate microaggregation method but unfortunately an optimal multivariatemicroaggregation method is an NP hard problem. Consequently, several heuristics have been proposed butno such method outperforms the other in all the possible criteria. In this paper we have performed a studyof the various microaggregation techniques so that we get a detailed insight on how to design an efficientmicroaggregation method which satisfies all the criteria. 

KEYWORDS

Statiscal Disclosure Control, Information Loss, Disclosure Risk, microdata, anonymity, microaggregation

مطالعه تطبیقی در مورد تکنیک های ریزتجمعی برای حفاظت از میکرو داده¬ها

چکیده
روش ریزتجمعی یک تکنیک اختلالی کنترل افشای آماری (SDC) کارآمد برای حفاظت از میکرو داده است. این یک رویکرد یکپارچه و به طور طبیعی برای عدم آشکارسازی بدون تعمیم یا سرکوب داده¬ها است. تکنیک های مختلف روش ریزتجمعی عبارتند از: روش اندازه ثابت و داده گرا برای داده¬های تک متغیره و چند متغیره موجود در ادبیات تحقیق. این روش¬ها با استفاده از معیارهای استاندارد از قبیل: ریسک پذیری (DR) و از دست رفتن اطلاعات (IL) ارزیابی شده است. هر بار که یک روش ریزتجمعی جدید پیشنهاد می¬شود، یک معاوضه خوب بین ریسک افشای داده و کاربرد داده بوجود می¬آید. هر چند یک روش ریزتجمعی تک متغیره بهینه وجود دارد اما متاسفانه یافتن یک روش ریزتجمعی چند متغیره بهینه یک مشکل سخت NP است. در نتیجه، چند فن آوری هوشمند ارائه شده است اما هیچ روش دیگر بهتری در تمام معیارهای ممکن وجود ندارد. در این مقاله ما مطالعه¬ای از تکنیک¬های مختلف روش ریزتجمعی را انجام داده¬ایم، به طوری¬که ما بینشی دقیق در مورد چگونگی طراحی یک روش کارآمد ریزتجمعی برای برآورد تمام معیارها بدست آوردیم.

کلیدواژه¬ها: کنترل افشای آماری، از دست دادن اطلاعات، ریسک پذیری، میکرو داده، عدم آشکارسازی، روش ریزتجمعی.

1. مقدمه
با ظهور تکنیک¬های مختلف داده کاوی، فرآیند کشف دانش از طریق پایگاه¬های داده بزرگ و یا مجموعه¬های داده، بطور قابل توجهی بهبود یافته است. دانش کشف شده که قبلاً ناشناخته بود، فرآیندهای تصمیم¬گیری در مناطق مختلف بازاریابی و مدیریت زنجیره عرضه، مراقبت¬های پزشکی و سلامت، تصمیم¬گیری سیاست¬ها و استراتژی¬های برنامه¬ریزی و غیره تسهیل کرده است. اجازه دهید برخی از سناریوهایی را که در آن تکنیک¬های داده کاوی نقش مهم در تجزیه و تحلیل داده¬ها و کشف دانش دارند بررسی نماییم. اگر دولت تصمیم بر اجرای طرح¬های مختلف رفاه اجتماعی برای مردم آن کشور بگیرد، و سپس مطالعه دقیق بافت جمعیتی منطقه، جمعیت و غیره مورد نیاز باشد. برای یک شرکت راه اندازی هر محصول جدید در بازار، اولین نیاز مطالعه بازار مانند روند مصرف، عادات خرید مردم و غیره می¬باشد. برای چنین تجزیه و تحلیل تحقیق و برنامه ریزی، تعداد زیادی از پایگاه¬های داده به اشتراک گذاشته و منتشر شده است، که به نوبه خود ریسک نقض حریم خصوصی افراد مرتبط با پایگاه داده را افزایش می¬دهد. یک روش کارآمد برای تجزیه و تحلیل مؤثر داده¬ها بدون آسیب رساندن به احساسات افراد مورد نیاز می¬باشد. این مشاهده شده است که شناسایی ساده مورد توجه برای از بین بردن صفات شناسایی پایگاه داده برای محافظت از حریم خصوصی افراد موثر نیست. یکی از بهترین راه¬ها برای محافظت از حریم خصوصی افراد، تغییر داده قبل از انتشار آن می¬باشد. اما چالش اینجا است که در چنین روشی داده¬ها چگونه تغییر داده شوند به طوری¬که کاربرد داده بالاتر از حد آستانه خاص حتی پس از اصلاح آن نهفته است. این چالش، کشمش «dêtre» برای کنترل افشای آماری است که در [1] بیان شده است. کنترل افشای آماری (SDC) تلاش برای ایجاد توازن بین حقوق افراد به عنوان حریم خصوصی و حق جامعه برای درک داده¬های مورد تجزیه و تحلیل می¬باشد. تعریف حریم خصوصی به طور رسمی در [2] به عنوان "حق یک نهاد برای اطمینان از افشای غیر مجاز اطلاعات حساس موجود در یک مخزن الکترونیکی و یا به عنوان تجمعی از اطلاعات پیچیده داده¬های ذخیره شده در یک مخزن الکترونیکی" عنوان شده است.
به طور سنتی، روش¬های SDC برای محافظت از حریم خصوصی پاسخ دهندگان توسط تضمین درجاتی از اصلاح داده¬ها ابداع شده¬اند. روش تجمعی یک تکنیک اختلالی کنترل افشای آماری کارآمد برای حفاظت از میکروداده¬ها و به عنوان مثال حفاظت از اطلاعات فردی است. بر خلاف روش عدم آشکارسازی، روش ریزتجمعی داده¬ها را بدون سرکوب و یا تعمیم آنها تغییر می¬دهد. این برای اولین بار در سال 1995 توسط دیفایس و انور به عنوان یک مشکل خوشه خاص که در آن یک مجموعه داده به گروه¬های کوچک همگن تقسیم می¬شد، ارائه شده است. هر گروه شامل حداقل k سابقه و بجای انتشار مقادیر میکروداده اولیه بود، میانگین گروهی که آنها متعلق به آن بودند در جای خود قبل از انتشار آنها گزارش شده است. بنابراین، می¬توان گفت که روش ریزتجمعی به طور طبیعی عدم آشکارسازی را برآورد می¬کند. اما روش ریزتجمعی در مورد خوشه بندی ساده و یا پارتیشن بندی یک مجموعه داده به گروه¬های همگن که در آن هر گروه متشکل از حداقل سوابق k است، نمی¬باشد. آن برای سوابق گروه در هر روشی که ریسک افشای اطلاعات در سطح حداقل نگه داشته شود در حالی که کاربرد داده زیاد باشد بسیار مهم است. به عبارت دیگر می توان گفت که یک معاوضه بهتر بین ریسک ناشی از افشای اطلاعات حساس و از دست دادن اطلاعات اتفاق افتاده با توجه به تغییر داده¬ها مورد نیاز است. روش ریزتجمعی توسط دیفایس و نانوپولوس [3] در اصل برای داده¬های مستمر تعریف شده بود و همچنین در آثار دیگران می توان در [4، 5] مشاهده نمود. سپس آن برای داده¬های طبقه بندی شده [7] و بعد برای داده-های ناهمگن [6] تعمیم یافت. روش ریزتجمعی بهینه پارتیشن بندی یک مجموعه داده به گروه¬های بیش از اندازه بزرگ بین k و 2k-1 می¬باشد. کاربران پارامتر k را تصمیم گیری برای درجه ای از اختلال، مقدار بزرگ k برای حریم خصوصی داده¬های بالاتر از اطمینان تعریف کرده¬اند اما این داده¬ها ممکن است برای تجزیه و تحلیل آماری به عنوان از دست دادن اطلاعات ممکن بالاتر مفید نباشد. به طور معمول، مقدار k به عنوان 3، 4، 5 یا 10 در هر روش ریزتجمعی در نظر گرفته شده است.
ادامه مقاله به شرح زیر سازماندهی شده است. بخش 2 مفاهیم روش ریزتجمعی و حفاظت از میکرو داده¬ها را توضیح می¬دهد. بخش 3 رویکردهای مختلف و روش ریزتجمعی و آثار مربوط به آن را مرور می¬کند. بخش 4 مقایسه¬های مختلف اندازه ثابت و روش ریزتجمعی داده¬گرا را مبتنی بر پیچیدگی و مقایسه آنها در مجموعه داده واقعی با توجه به معیار از دست رفتن اطلاعات (IL) لیست کرده است. در نهایت، در بخش 5 نتیجه¬گیری با جهت به مسیر تحقیقات آینده ممکن ترسیم شده است.
2. روش ریزتجمعی و حفاظت از میکروداده¬ها
1.2. مفهوم میکروداده
میکروداده اطلاعاتی در مورد مخاطب منحصر به فرد برای مثال اطلاعات شرکت، اطلاعات مربوط به یک فرد و غیره است. آن را به عنوان یک فایل شامل n سابقه فردی با m ویژگی مشاهده شده است. ویژگی¬های میکرو داده را می¬توان به دسته¬های زیر طبقه بندی نمود:
شناسه؛ این ویژگی¬ها می توانند برای شناسایی سوابق فردی منحصر به فرد، برای مثال ID کارمند، کد بیمار و غیره مورد استفاده قرار گیرد.
شبه شناسه؛ این ویژگی¬ها می توانند برای شناسایی سوابق فردی، اما نه منحصر به فرد، به عنوان سوابق شناسایی شده ممکن مبهم، برای مثال شخص، نام و غیره مورد استفاده قرار گیرد.
ویژگی¬های محرمانه؛ این ویژگی شامل برخی از اطلاعات شخص پاسخ دهنده است که در طبیعت به حدی حساس است. برای مثال گزارش تشخیص بیمار، اجتماع فردی و غیره.
ویژگی غیرمحرمانگی؛ ویژگی¬هایی که در هر یک از این دسته¬هایی که در بالا ذکر شد، قرار نگیرند متعلق به این دسته¬اند. برای مثال سرگرمی فرد، مهارت¬های زبان و غیره. این نوع از صفات را نمی¬توان به عنوان آنهایی که می¬تواند بخشی از شبه شناسه باشد در نظر گرفت.
فایل¬های میکرو داده در میان کاربران و تحلیلگران برای تجزیه و تحلیل تحقیقات مختلف به اشتراک گذاشته شده که ریسک افشای برخی از اطلاعات حساس در مورد افراد و اطلاعات را افزایش می¬دهد. تکنیک¬های مختلف در دسترسی برای حفاظت از میکرو داده¬ها برای شناسایی فردی وجود دارد. می¬توان آن را یا با پوشش داده و یا اصلاح داده¬ها و یا با تولید داده¬های مصنوعی انجام داد [12]. در هر دو روش، هدف اصلی، دریافت مجموعه ای جدید از میکرو داده V' از همتای اصلی آن V می باشد. صرف نظر از تکنیک¬های به کار گرفته شده برای به دست آوردنV'، آن باید برای هدف اصلی از کم کردن ریسک نگهداری افشای اطلاعات با محتوای اطلاعات آماری بالا به کار گرفته شود. این تکنیک پوشش داده¬ها می¬تواند به طور گسترده¬ای برای دو دسته طبقه بندی نشان داده شده در [9، 10] به کار رود:
روش اختلالی؛ در این روش داده قبل از انتشار آن تحریف شده است. انتقال رتبه [14]، نمونه¬گیری مجدد [16]، روش ریزتجمعی [4]، صدای فزاینده [15] و غیره برخی از تکنیک¬های زیرمجموعه این دسته هستند.
روش غیر اختلالی؛ در این روش داده در مورد استفاده از روش اختلالی تحریف نشده است، اما می¬تواند تعمیم و یا قبل از انتشار آن سرکوب شده باشد. برخی از تکنیک¬هایی که در این دسته بندی قرار می¬گیرند عبارتند از؛ سوابق جهانی و یا تعمیم [10]، سرکوب محلی [11]، کدگذاری بالا و پایین [13] و غیره.
این روش پوشش داده برای اثربخشی بیشتر ترکیب داده از نظر کاربرد داده و ریسک افشای اطلاعات دریافت شده است. همانطور که در [8] مشاهده شد با توجه به بیش اتصالات داده¬های اصلی، داده مصنوعی دارای گرایش شناختی مجدد می¬باشند.
جداول 1 و 2 روش¬های مختلف اختلالی و غیراختلالی و انواع داده¬هایی را که در آن روش¬های مربوطه می¬تواند استفاده شود را نشان می¬دهد.
روش¬های مختلف ممکن است برای حفظ حریم خصوصی داده¬ها استفاده شود. در یک مقاله مروری [2] الایزا برتینو و همکاران نشان دادند که حریم خصوصی حفظ الگوریتم داده کاوی می¬تواند بر اساس مجموعه معیارهای زیر ارزیابی شود:
سطح حریم خصوصی؛ آن تعیین می¬کند که چقدر نزدیک بودن به اطلاعات حساس در مجموعه داده¬ها را می¬توان پس از هر تکنیک حریم خصوصی حفظ شده برای کاربرد آن شناسایی نمود.
کیفیت داده¬ها؛ این نشان می¬دهد که آیا تجزیه و تحلیل در مجموعه داده¬ها با استفاده از روش اختلالی یا غیر اختلالی به دست آمده، شبیه به داده¬های اصلی می¬باشد.
پنهان کردن شکست؛ این روش شکست تکنیک حفظ حریم خصوصی برای مخفی کردن بخشی از اطلاعات حساس مجموعه داده¬ها را نشان می¬دهد.
پیچیدگی؛ این معیار عملکرد روش حفظ حریم خصوصی را از نظر زمان محاسباتی و منابع مصرف شده نشان می دهد.
2.2. روش¬های ریزتجمعی
روش ریزتجمعی یک روش کنترل افشای آماری (SDC) است که از نظر ماهیت اختلالی است. این یک روش کارآمد برای حفاظت از میکرو داده¬ها است و برای اولین بار توسط دیفایس و انور [4] در سال 1995 ارائه شده است. این روش در اصل برای داده¬های پیوسته توسط دیفایس و نانوپولوس [3] تعریف شده است و همچنین می¬توان در آثار دیگران در [4 ، 5] مشاهده نمود که پس از آن برای داده¬های طبقه بندی شده [7] و بعد از آن برای داده¬های ناهمگن [6] تعمیم یافته است. روش ریزتجمعی عمدتاً در دو مرحله زیر است؛ اول در پارتیشن بندی مجموعه داده¬ها به گروه¬های همگن، که در آن هر گروه متشکل از حداقل k سابقه می¬باشد و سپس هر سابقه از گروه با مقدار متوسط گروه مربوطه جایگزین می¬شود (که در آن k یک پارامتر تعریف شده کاربر است). هیچ محدودیتی در تعداد گروه¬هایی که می¬تواند تشکیل شود وجود ندارد اما اندازه گروه باید بین k و2k-1 باشد. روش ریزتجمعی به طور خودکار عدم آشکارسازی [17] را بدون تعمیم یا سرکوب داده برآورد می¬کند. در روش عدم آشکارسازی، هر رکورد از حداقل (k-1) سوابق دیگر غیر قابل تشخیص است. معمولاً اندازه¬گیری فاصله برای تعیین شباهت سوابق استفاده می¬شود که در روش ریزتجمعی، فاصله اقلیدسی نامیده می¬شود. برای اینکه مشخص¬تر شود اجازه دهید ما یک مجموعه R از میکرو داده¬ها را با متغیرهای d بعدی بر روی n فرد در نظر بگیریم. حال، زمانی که روش ریزتجمعی در مجموعه¬ای از میکرو داده¬ها به کار ¬رود پس از آن گروه¬های m با حداقل سوابق k در هر گروه تشکیل می¬شود. پارتیشن بندی بهینه از مجموعه¬ میکرو داده¬ها در گروه مجموع مربعات (SSW) (1) و یا معادل آن به صورت جمع بین گروهی مربعات (SSB) (2) اندازه گیری شده است. ارزش SSW باید حداقل باشد، درحالی¬که ارزش SSB باید تا آنجایی که ممکن است بالا باشد.

که در آن؛
میانگین بردار داده بیش از گروه i ام. : x ̅_i
سابقه j ام در گروه i ام. : x_ij
کل میانگین از مجموعه داده¬ها. : x ̅
k_if سوابق در گروه i ام. : k_i
کل مجموع مربعات محاسبه شده است، به عنوان:

از دست دادن اطلاعات (IL) موجب ایجاد روش ریزتجمعی اندازه گیری شده می¬شود، به عنوان:

با توجه به ابعاد داده¬ها در مجموعه¬ای از میکرو داده¬ها، روش ریزتجمعی را می¬توان به دو دسته تقسیم نمود:
روش ریزتجمعی یک متغیره؛ این روش برای هر متغیر از مجموعه میکرو داده¬ها به نحو مستقل استفاده شده است. زمانی¬که تنها یک متغیر درگیر باشد، مشکل آسان¬تر می¬شود، به طوری¬که در آن حالت ایده رتبه بندی منحصر به فرد می¬تواند همانطور که در [5] دیده شده، استفاده شود. علاوه بر این، در [18] ما می توانیم مشاهده کنیم که یک الگوریتم چندجمله¬ای بهینه برای روش ریزتجمعی تک متغیره وجود دارد.
روش ریزتجمعی چندمتغیره؛ در این روش، فرآیند گروه¬بندی برای مجموعه¬ای از متغیرهای مجموعه¬ میکرو داده¬ استفاده می¬شود. در این مورد، زمانی که همه متغیرها با هم تجمع یافته¬اند، روش عدم آشکارسازی به طور خودکار در نتیجه کاهش ریسک افشای اطلاعات می¬باشد. بنابراین، می¬توان در به حداکثر رساندن کاربرد داده تمرکز کرد. یک روش ریزتجمعی چند متغیره بهینه در زمان چند جمله¬ای یک مشکل سخت NP است که در [19] بیان شده است. در نتیجه، چند فن آوری هوشمند تحت این دسته ارائه شده است.
صرف نظر از ابعاد داده¬های مجموعه میکرو داده¬، روش ریزتجمعی می¬تواند به صورت اندازه ثابت و یا داده¬گرا (اندازه های مختلف) باشد. روش اندازه ثابت پارتیشن بندی یک مجموعه میکرو داده¬ به گروه¬هایی از اندازه k می¬باشد که در آن هر گروه شامل k سابقه است به جز یکی که ممکن است حاوی بیش از k سابقه باشد و آن زمانی است که تعدادی از سوابق در مجموعه¬ میکرو داده مضربی از k باشد، درحالی¬که روش ریزتجمعی داده¬گرا گروه¬هایی از اندازه متغیر تولید می¬کند، و اندازه گروه بین k و 2k-1 است. هر چند روش ریزتجمعی اندازه ثابت در پارتیشن بندی مجموعه داده با کاهش فضای جستجو، زمان محاسبه کمتری دارد اما روش اندازه متغیر در گروه بندی سوابق انعطاف پذیرتر است به طوری¬که آن می¬تواند در توزیع داده¬های مختلف، در نتیجه افزایش همگنی گروه و تحمیل از دست رفتن اطلاعات کمتر، انطابق پذیر باشد.
3. رویکردهای مختلف به روش ریزتجمعی
روش¬های ریزتجمعی تک متغیره مختلفی ارائه شده است و حتی یک روش ریزتجمعی بهینه تک متغیره [18] در ادبیات تحقیق وجود دارد، اما یافتن یک روش ریزتجمعی بهینه چند متغیره یک مشکل سخت NP است، همانطور که در [19] بیان شده است.
در نتیجه چندین روش ریزتجمعی اکتشافی در ادبیات تحقیق مطرح شده است. در این بخش ما به بررسی اجمالی رویکرد¬های مختلف روش ریزتجمعی موجود در ادبیات تحقیق می¬پردازیم.
1.3. روش ریزتجمعی مبتنی بر الگوریتم ژنتیک
الگوریتم ریزتجمعی مبتنی بر الگوریتم - ژنتیک (G-A) در [27] ارائه شده است. الگوریتم ژنتیک روشی برای حرکت از یک جمعیت کروموزوم به یک جمعیت جدید با استفاده از یک نوع انتخاب طبیعی همراه با اپراتورهای ژنتیک الهام گرفته از تقاطع، جهش، و وارونگی است.
در [27] یک الگوریتم ژنتیک اصلاح شده برای رسیدگی به مسائل ریزتجمعی وجود دارد که در آن ازN آرایه کدگذاری استفاده شده است. در این روش، هر کروموزوم برای داشتن یک عدد ثابت ژن برابر تعدادی از سوابق در مجموعه داده¬ها در نظر گرفته شده است. در نتیجه، ارزش ژن i ام در یک کروموزوم، پارتیشن گروه K از سابقه i ام مجموعه داده¬های متعلق به آن را تعریف می¬کند. هر چند مجموع مربعات خطاها (SSE) (5) از G-A که همگنی درون گروهی را نشان می¬دهد بهتر از MDAV است اما کاهش بهره¬وری در مورد مجموعه داده¬های بزرگ وجود دارد. بنابراین، یک روش ترکیبی نیز در [27] ارائه شده است، که مزیت هر دو روش MDAV و الگوریتم ژنتیک کلاسیک را دارد و بهترین نتیجه را با شرایط SSE در مواجهه با مجموعه داده-های چند متغیره بزرگ ارائه کرده است. SSE به شرح زیر محاسبه شده است:

که در آن؛
C کل تعداد خوشه¬ها یا گروه¬ها است.
C_i خوشه i ام و x ̅_i مرکز C_i است.
روش ترکیبی می¬تواند به شرح زیر خلاصه شود:
1. یک مقدار کوچک از k گرفته می¬شود (به عنوان مثال K = 3).
2. اجازه دهید K بزرگتر از k و بخش¬پذیر بر k، و به اندازه کافی کوچک برای تناسب الگوریتم ژنتیک اصلاح شده باشد (به عنوان مثال K = 21).
3. از هر روش اکتشافی اندازه ثابت (به عنوان مثال MDAV) برای ایجاد K پارتیشن از مجموعه داده¬ها استفاده نمایید.
4. با توجه به ورودی سوابق، و بردار متوسط به دست آمده در مرحله قبل، روش اکتشافی اندازه ثابت برای ایجاد گروه بزرگ (به عنوان مثال مجموعه بردارهای متوسط) با اندازه K / k استفاده شده است.
5. برای هر داده گروه بزرگ، بردارهای متوسط توسط k سابقه اصلی برای به دست آوردن K پارتیشن جایگزین شده¬اند.
در نهایت، روش G-A برای هر گروه بزرگ در K پارتیشن به منظور تولید k پارتیشن بهینه یا نزدیک بهینه گروه بزرگ اعمال می¬شود. ترکیب k پارتیشن از همه گروه¬های بزرگ موجب تولید k پارتیشن برای کل مجموعه داده¬ها است.
2.3. میکروداده ترکیبی با استفاده از روش ریزتجمعی
روش جدیدی به نام میکرو ترکیبی در [28] ارائه شده است، و نشان داده که داده¬های ترکیبی را می¬توان با استفاده از روش ریزتجمعی با هر تولید کننده داده¬های ترکیبی به دست آورد. در اینجا، روشی طراحی شده که داده¬های ترکیبی بدون پیروی از روش مرسوم ترکیب داده¬های اصلی و ترکیبی برای ایجاد داده¬های ترکیبی تولید می¬شود. اجازه دهید V مجموعه داده اصلی شامل n سابقه باشد. در حال حاضر، با استفاده از روش [28] مجموعه داده ترکیبی V' با k∈[1,n] تولید شده است. داده ترکیبی V' تولید شده از میانگین و کوواریانس داده اصلی مجموعه V حفاظت می¬کند. این روش، دو الگوریتم نامیده می¬شود:
یک تولید کننده داده¬ ترکیبی که مجموعه¬ای از داده¬های ترکیبی را ایجاد می¬کند.
یک روش ریزتجمعی اکتشافی، که پارتیشن بندی یک مجموعه داده به گروه¬های با اندازه بین k و 2k-1 را ایجاد می¬کند.
روش میکرو ترکیبی را می توان به شرح زیر خلاصه نمود:
1. پارتیشن بندی مجموعه داده V به خوشه¬های حاوی k و (2K-1) سوابق.
2. کاربرد یک الگوریتم تولید کننده داده¬های ترکیبی برای به دست آوردن یک نسخه ترکیبی از هر خوشه.
3. جاگذاری سوابق اصلی در هر خوشه توسط سوابق خوشه ترکیبی مربوطه.
در مرحله 3، از روش متعارف روش ریزتجمعی پیروی نشده به طوری¬که در آن سوابق با مقدار متوسط خوشه متعلق به آن جایگزین شده است. روش میکرو ترکیبی یک روش ساده برای حفظ حریم خصوصی داده¬ها است، و می¬توان آن را برای هر نوع داده به کار برد و برای گروه¬های با اندازه متغیر تولید کرد.
3.3. الگوریتم مبتنی بر تراکم (DBA) برای روش ریزتجمعی
یک الگوریتم مبتنی بر تراکم (DBA) برای روش ریزتجمعی در [29] ارائه شده است. روش DBA دو مرحله را دنبال می¬کند، ابتدا پارتیشن بندی DBA-1 مجموعه داده به گروه¬هایی که در آن هر گروه شامل حداقل k سابقه می¬باشد. برای پارتیشن بندی مجموعه داده¬ها، DBA-1 از k سابقه با بالاترین تراکم k در میان تمام سوابق که به هر گروه اختصاص داده نشده، استفاده می¬کند. روند گروه بندی ادامه می¬یابد تا k سابقه اختصاص داده نشده باقی بماند. این k سابقه باقیمانده به نزدیکترین گروه خود تخصیص داده می¬شود.
مرحله دوم DBA به عنوان DBA-2 شناخته شده است و به منظور دستیابی به از دست دادن کم اطلاعات و کاربرد بالای داده در تحقیقات آتی استفاده می¬شود. DBA-2 ممکن است گروه¬های تشکیل یافته را تجزیه کرده یا ممکن است سوابق آنها را به گروه¬های دیگر ادغام نماید. معیار تجزیه، از دست دادن اطلاعات است. اجازه دهید ILbmerge از دست دادن اطلاعات گروه G باشد قبل از اینکه هر گونه گروه Gi در آن ادغام شود و ILamerge از دست دادن اطلاعات پس از ادغام گروه Gi در G باشد. اگر ILbmerge> ILamerge سپس گروه ادغامی تجزیه می¬گردد و هر سابقه Gi را با نزدیکترین گروه آن ادغام می¬کند. اگر در پایان روش DBA-2، چند گروه با داشتن بیش از (2k-1) سوابق به پایان برسد سپس در آن صورت الگوریتم MDAV-1 [29] برای هر گروه با اندازه بالا (2k-1) اعمال می¬شود. در این راه از دست دادن اطلاعات به حداقل رسیده است. این حالت در نهایت MDAV-2 نامیده می¬شود. روش DBA-2 مشابه روش TFRP-2 است اما روش TFRP-2 برای ادغام یک سابقه با یک گروه در اندازه (4k-1) اجازه نمی¬دهد.
4.3. حداکثر فاصله تا بردار میانگین (MDAV)
MDAV یکی از بهترین روش¬های اکتشافی برای تکنیک ریزتجمعی چند متغیره است. این یک روش اندازه ثابت است و برای اولین بار در [13] ارائه و به عنوان بخشی از یک روش ریزتجمعی چند متغیره اجرا در بسته μ-Argus برای کنترل افشای آماری اجرا شد. بعد از چندین نوع روش¬ ارائه شده در ادبیات تحقیق با تغییرات کوچک ایجاد شد. الگوریتم آن به شرح زیر است:
الگوریتم: MDAV
1. محاسبه مرکز C از مجموعه داده D.
2. یافتن دورترین سابقه X از مرکز C.
3. ایجاد گروه Gi با نزدیکترین سابقه (K-1) به X.
4. یافتن دورترین سابقه XS از X.
5. ایجاد گروه Gi+1 با نزدیکترین سابقه (K-1) به XS.
6. تکرار مراحل 1 تا 5 تا زمانی که بیش از (2k-1) سابقه در هر گروه تخصیص یافته وجود داشته باشد.
7. اگر بیش از (K-1) سابقه باقیمانده باشد آنها را به یک گروه جدید با سوابق باقی مانده تخصیص دهید.
8. اختصاص سوابق باقیمانده به نزدیک ترین گروه.
9. ایجاد مجموعه داده ریزتجمعی D' با جایگزین کردن سوابق با مقدار متوسط خود در گروه متعلق به آن.
در مرحله 8، اگر کمتر از k سابقه باقی بماند، تمام سوابق این زیرگروه به نزدیک ترین گروه تعیین شده توسط محاسبات فاصله بین مرکز گروه¬ها اختصاص داده شود. MDAV در نهایت تا تشکیل گروه¬های هم اندازه k به جز یک گروه، به پایان می رسد.
5.3. مرجع ثابت دو نقطه (TFRP)
مرجع ثابت دو نقطه (TFRP) که توسط چانگ و همکاران در [22] ارائه شده است، یک روش دو مرحله برای تکنیک ریزتجمعی است و دو مرحله دارد که به ترتیب با عناوین TFRP-1 و TFRP-2 مشخص می¬شوند. TFRP دارای یک زمان محاسبه O(n2/k) و زمان از دست دادن کم اطلاعات به ویژه در مجموعه داده¬های پراکنده با مقدار بزرگ k می¬باشد. الگوریتم TFRP به شرح زیر است:
الگوریتم: TFRP-1 (مرحله اول)
1. محاسبه دو نقطه مرجع R1 و R2. همه بردارها به یک مجموعه (SET) تخصیص داده شود.
2. انتخاب یک نقطه مرجع.
3. انتخاب یک نقطه اولیه xi از نقطه مرجع.
4. محاسبه فاصله هر بردار تا xi.
5. انتخاب نزدیکترین بردار (K-1) همراه با xi برای تشکیل یک گروه، و حذف بردار k از SET.
6. انتخاب نقطه مرجع دیگر، و سپس رفتن به مرحله 2 تا زمانی که | SET< | K باشد.
7. اختصاص هر بردار باقیمانده SET به نزدیک ترین گروه آن.
در مرحله 1 دو نقطه مرجع R1 و R2 دو نقطه فزاینده در مجموعه میکرو داده هستند. در مرحله 7، هر بردار باقیمانده به نزدیک ترین گروه خود اختصاص داده می¬شود. این مشخص شده است که در این گروه مجموع مربعات (SSE) (5) از گروه تشکیل شده بیشتر است، در نتیجه برای کاهش از دست دادن اطلاعات از الگوریتم TFRP و مرحله دوم (TFRP-2) استفاده می¬شود.
الگوریتم: TFRP-2 (مرحله دوم)
1. محاسبه SSE هر گروه و مرتب کردن آنها در کاهش موارد انتخاب.
2. انتخاب یک گروه Gi برای انتخاب و محاسبه مقدار کل فعلی مربعات خطا (SSE1)در گروه.
3. محاسبه فاصله هر بردار Gi تا هر گروه دیگر.
4. اختصاص هر بردار Gi به نزدیکترین گروه آن، و محاسبه مقدار کل فعلی مربعات خطا (SSE2)در گروه .
5. اگر SSE1> SSE2 باشد، سپس هر بردار Gi به نزدیکترین گروه آن اختصاص یابد؛ در غیر این صورت، Gi مجدداً به دست آید.
6. بازگشت به مرحله 2 و تکرار آن، تا هر گروه بررسی شود.
پس از استفاده TFRP-2، اگر چند گروه شامل سوابق بزرگتر یا مساوی 2k باشد پس از آن گروه¬ها را با استفاده از هر روش ریزتجمعی اندازه ثابت تجزیه کنید. و در مورد اندازه نزدیکترین گروه با بردار xi اختصاص داده شده به سوابق (4k-1) استفاده شود و سپس بردار xi به نزدیکترین گروه دوم خود اختصاص داده شود.
6.3. حداکثر فاصله اندازه متغیر تا بردار میانگین (V-MDAV)
MDAV اندازه متغیر و یا V-MDAV [23] در تضاد با MDAV اندازه ثابت، در زمینه k پارتیشن با اندازه گروه مختلف بین k و 2k-1 است. چنین انعطاف پذیری می¬تواند برای رسیدن به بالاتر گروه همگن و پارتیشن بهینه از داده¬ها باشد. روش V-MDAV توسط آگوستی سولانس و آنتونی مارتینز و بالاستی ارائه شده است. این یک رویکرد اکتشافی برای تکنیک ریزتجمعی چند متغیره است که گروه¬های اندازه متغیر و در نتیجه درون گروه همگن اندازه گیری شده توسط SSE بالاتر، با هزینه محاسباتی شبیه به یکی از روش¬های اکتشافی ریزتجمعی اندازه ثابت فراهم می¬کند. علاوه بر این، روشی که در آن V-MDAV گروه¬ها توسعه می¬یابد را می-توان با استفاده از عامل افزایش γ تنظیم نمود. ارزش γ به عنوان 0.2 مجموعه داده¬های پراکنده و γ = 1.1 برای مجموعه داده خوشه تعیین شده است. این رویکرد برای روش V-MDAV به شرح زیر است:
الگوریتم: V-MDAV
1. محاسبه ماتریس فاصله از مجموعه داده¬های D.
2. محاسبه مرکز C از مجموعه داده D.
3. انتخاب دورترین سابقه x از مرکز C.
4. ایجاد نزدیکترین سوابق (K-1) به x.
5. توسعه گروه gi.
6. تکرار مراحل 3 تا 5 تا سابقه (K-1) هر گروه تخصیص داده شود.
7. اختصاص سوابق اختصاص داده نشده باقیمانده به نزدیکترین گروه آن.
8. ایجاد مجموعه داده ریزتجمعی ' D با جایگزین کردن سوابق با مقدار متوسط خود در گروه متعلق به آن.
در مرحله 5، توسعه Gi گروه با آزمون انجام می¬شود اگر فاصله din بین نزدیکترین سابقه x اختصاص داده نشده به یک گروه gi کمتر از γ باشد توسط حداقل فاصله dout از سابقه x انتخاب شده به هر یک از سابقه-های اختصاص داده نشده باقی می¬ماند، به عنوان مثال اگر din < γ باشد dout نیز x را به gi اضافه می¬کند در غیر این صورت اضافه نمی¬کند. در پایان الگوریتم اگر هنوز هم چند سابقه اختصاص داده نشده وجود داشته باشد آنها را به نزدیکترین گروه اضافه می¬کنیم. هر چند عامل کسب γ می¬تواند برای پارتیشن بندی مؤثر مجموعه داده¬ها وابسته به توزیع داده¬ باشد اما تعیین مقدار بهینه γ تنظیم یک کار مستقیم نیست.

جهت خرید فایل تماس بگیرید 
09375520909 - شبستری
shabestari716@gmail.com