دستیابی به انتشار حریم خصوصی متفاوت داده های آماری مبتنی بر مکان با استفاده از خوشه بندی شبکه

پارتیشن بندی و انتشار آماری معمولاً در خدمات کلان داده مبتنی بر مکان برای پاسخگویی به سؤالاتی مانند تعداد نقاط مورد علاقه، وسایل نقلیه موجود، جریان ترافیک، بیماران آلوده و غیره در محدوده خاصی استفاده می شود. افزودن اغتشاش نویز به داده های آماری مبتنی بر مکان با توجه به مدل حریم خصوصی دیفرانسیل می تواند خطرات مختلف ناشی از نشت حریم خصوصی مکان را کاهش دهد و در عین حال ویژگی های آماری داده های منتشر شده را حفظ کند. روش های پارتیشن بندی و انتشار آماری سنتی تجزیه و نمایه سازی فضای دو بعدی را از بالا به پایین انجام می دهد. با این حال، آنها به راحتی می توانند پدیده پارتیشن بندی یا پارتیشن بندی بیش از حد را ایجاد کنند و بنابراین نیاز به چندین بار اسکن داده ها دارند. این مقاله یک روش خوشه‌بندی شبکه و حفاظت از حریم خصوصی افتراقی را برای سناریوهای انتشار کلان داده‌های آماری مبتنی بر مکان پیشنهاد می‌کند. ما آمار کلان داده مبتنی بر مکان را در واحدهای شبکه‌های هم اندازه پیاده‌سازی می‌کنیم و طبقه‌بندی چگالی را بر روی شبکه‌های توزیع یکنواخت با تبدیل موجک گسسته انجام می‌دهیم. یک الگوریتم خوشه‌بندی شبکه‌ای از پایین به بالا برای اجرا بر روی شبکه‌های خالی و یکنواخت با سطح چگالی یکسان بر اساس شباهت همسایگی طراحی شده است. نویز لاپلاسی با توجه به مدل حریم خصوصی دیفرانسیل در نتایج خوشه بندی گنجانده شده است تا آمار منتشر شده را تشکیل دهد.

کلید واژه ها:

انتشار آماری داده های بزرگ ؛ حریم خصوصی مکان ؛ حریم خصوصی دیفرانسیل ; حریم خصوصی تجزیه فضایی ; خوشه بندی شبکه ای

1. مقدمه

با گسترش سریع فناوری‌های نوظهور مانند اینترنت موبایل و اینترنت اشیا، خدمات داده‌های بزرگ مبتنی بر مکان متعدد به طور فزاینده‌ای در زمینه‌های مختلف، از جمله، اما نه محدود به، آمار توزیع جمعیت [ 1 ]، برنامه‌ریزی و مدیریت شهری محبوب می‌شوند. [ 2 ]، برنامه ریزی هوشمند ترافیک [ 3 ]، و کنترل همه گیر بیماری [ 4 ]]. به ویژه، در دوره بحرانی کنونی همه‌گیری کووید-19، مجموعه‌ای از برنامه‌های کاربردی داده‌های بزرگ مبتنی بر مکان (به عنوان مثال، کدهای سلامت، کارت‌های سفر ارتباطی، و روش‌های خودآزمایی با تماس نزدیک) راحتی زیادی را برای پیشگیری و کنترل همه‌گیری فراهم می‌کنند. بررسی های اپیدمیولوژیک، توزیع اپیدمی و تجزیه و تحلیل آماری، برنامه ریزی پرسنل و مواد و غیره.

اطلاعات مکان ارتباط زیادی با حریم خصوصی شخصی دارد. انتشار نامناسب یا تجزیه و تحلیل استدلال معکوس [ 5 ، 6 ، 7 ] آمار کلان داده مبتنی بر مکان می تواند به راحتی منجر به افشای حریم خصوصی یک مکان خاص کاربر، مسیر حرکت، عادات زندگی، وضعیت سلامت، سرگرمی ها، شرایط اقتصادی و غیره شود. .، و حتی ممکن است دارایی و جان کاربر را به خطر بیندازد [ 8 ]. بنابراین، پرداختن به مسائل حفاظت از حریم خصوصی ذکر شده در بالا در طول انتشار و استفاده از آمار کلان داده مبتنی بر مکان، یک کار ضروری باقی مانده است و به عنوان یک گلوگاه قابل توجه در توسعه صنعت کلان داده عمل می کند.

روش پارتیشن و انتشار آماری به طور گسترده در خدمات داده های بزرگ مبتنی بر مکان استفاده می شود. این می تواند آمار دقیق و به موقع ترافیک را در اختیار کاربران قرار دهد، مردم را برای برنامه ریزی زمان ها و مسیرهای معقول سفر تسهیل کند و خدمات مبتنی بر مکان (LBS) با دقت بالا را دریافت کند. هنگامی که با مدل حریم خصوصی دیفرانسیل ترکیب شود و هنگامی که اختلال نویز در آمار داده های بزرگ مبتنی بر مکان گنجانده شود، می تواند خطر نشت حریم خصوصی کاربران را در عین حفظ ویژگی های آماری داده های منتشر شده کاهش دهد. در طول همه‌گیری کووید-19، داده‌های بزرگ مکان مکانی، آمار مورد، تجزیه و تحلیل توزیع، و تخمین مسیر را برای پیشگیری و کنترل همه‌گیری فراهم می‌کرد و متعاقباً به از سرگیری اجتماعی کار و تولید کمک می‌کرد.شکل 1 نمونه معمولی از انتشار آماری داده های بزرگ مبتنی بر مکان است که توزیع فضایی آلوده کننده های COVID-19 را در استان هوبی در 31 مارس 2020 نشان می دهد [ 9 ]. شکل 2 نتیجه RAPPOR است، یک روش ناشناس حفظ حریم خصوصی داده های آماری جمع سپاری شده بر اساس حریم خصوصی تفاضلی، که در آن توزیع نمونه واقعی به رنگ سیاه نشان داده شده است، و سبز روشن توزیع تخمین زده شده را بر اساس رمزگشایی شده تصادفی انباشته شده ترتیبی حفظ حریم خصوصی نشان می دهد. گزارش های پاسخ (RAPPOR) [ 10 ]. همانطور که از مشاهده می شود شکل 2 مشاهده می شودهنگامی که تعداد گزارش‌های کاربران به یک میلیون می‌رسد، نتایج آماری گزارش‌شده بر اساس گزارش RAPPOR، توزیع آماری داده‌های واقعی را از نزدیک دنبال می‌کند، که بر در دسترس بودن نتایج آماری کلان داده‌های منتشر شده تأثیری ندارد.

روش انتشار آماری کلان داده مبتنی بر مدل حریم خصوصی دیفرانسیل، از حریم خصوصی هر کاربر تحت فرض اطمینان از در دسترس بودن داده ها با افزودن یک نویز تصادفی خاص به نتایج انتشار آماری محافظت می کند. ساختار پارتیشن اطلاعات مکان مکانی و معرفی نویز حریم خصوصی دیفرانسیل منجر به ایجاد خطا بین نتایج آمار کلان داده منتشر شده و نتایج آماری واقعی می شود. این ممکن است در دسترس بودن داده های منتشر شده را کاهش دهد. به عنوان مثال، یک کاربر تعداد تاکسی های موجود در 1 کیلومتری موقعیت مکانی خود را پرس و جو می کند و نتایج آمار پر سر و صدا که توسط سیستم LBS برگردانده می شود 11 است. با این حال، وضعیت واقعی این است که تنها دو تاکسی در محدوده درخواست کاربر وجود دارد. از این رو، چنین نتایج آماری منتشر شده احتمالاً کاربران را گمراه می کند تا برای مدت طولانی منتظر بمانند و در نتیجه منجر به یک تجربه خدمات LBS رضایت بخش می شود. به همین ترتیب، فرض کنید، مطابق با اطلاعات موقعیت مکانی بیماران تایید شده COVID-19 در یک منطقه خاص، تعداد تماس های نزدیک حدود 12000 نفر باشد. با این حال، نتیجه آماری منتشر شده پس از گنجاندن صدای حریم خصوصی دیفرانسیل 8700 است. بنابراین این امر می تواند تامین تجهیزات کمک پزشکی و سایر مواد پیشگیری از بیماری همه گیر را مختل کند، زیرا آنها نمی توانند نیازهای این منطقه را برآورده کنند و در نتیجه به تأخیر می افتند. درمان به موقع بیماران بنابراین، بهبود دقت نتایج آماری کلان داده مبتنی بر مکان با فرض اطمینان از حفظ حریم خصوصی مکان یک موضوع مهم برای خدمات کلان داده است. در نتیجه منجر به یک تجربه خدمات LBS رضایت بخش می شود. به همین ترتیب، فرض کنید، مطابق با اطلاعات موقعیت مکانی بیماران تایید شده COVID-19 در یک منطقه خاص، تعداد تماس های نزدیک حدود 12000 نفر باشد. با این حال، نتیجه آماری منتشر شده پس از گنجاندن صدای حریم خصوصی دیفرانسیل 8700 است. بنابراین این امر می تواند تامین تجهیزات کمک پزشکی و سایر مواد پیشگیری از بیماری همه گیر را مختل کند، زیرا آنها نمی توانند نیازهای این منطقه را برآورده کنند و در نتیجه به تأخیر می افتند. درمان به موقع بیماران بنابراین، بهبود دقت نتایج آماری کلان داده مبتنی بر مکان با فرض اطمینان از حفظ حریم خصوصی مکان یک موضوع مهم برای خدمات کلان داده است. در نتیجه منجر به یک تجربه خدمات LBS رضایت بخش می شود. به همین ترتیب، فرض کنید، مطابق با اطلاعات موقعیت مکانی بیماران تایید شده COVID-19 در یک منطقه خاص، تعداد تماس های نزدیک حدود 12000 نفر باشد. با این حال، نتیجه آماری منتشر شده پس از گنجاندن صدای حریم خصوصی دیفرانسیل 8700 است. بنابراین این امر می تواند تامین تجهیزات کمک پزشکی و سایر مواد پیشگیری از بیماری همه گیر را مختل کند، زیرا آنها نمی توانند نیازهای این منطقه را برآورده کنند و در نتیجه به تأخیر می افتند. درمان به موقع بیماران بنابراین، بهبود دقت نتایج آماری کلان داده مبتنی بر مکان با فرض اطمینان از حفظ حریم خصوصی مکان یک موضوع مهم برای خدمات کلان داده است. مطابق با اطلاعات مکان بیماران COVID-19 تایید شده در یک منطقه خاص، تعداد تماس های نزدیک حدود 12000 است. با این حال، نتیجه آماری منتشر شده پس از گنجاندن صدای حریم خصوصی دیفرانسیل 8700 است. بنابراین این امر می تواند تامین تجهیزات کمک پزشکی و سایر مواد پیشگیری از بیماری همه گیر را مختل کند، زیرا آنها نمی توانند نیازهای این منطقه را برآورده کنند و در نتیجه به تأخیر می افتند. درمان به موقع بیماران بنابراین، بهبود دقت نتایج آماری کلان داده مبتنی بر مکان با فرض اطمینان از حفظ حریم خصوصی مکان یک موضوع مهم برای خدمات کلان داده است. مطابق با اطلاعات مکان بیماران COVID-19 تایید شده در یک منطقه خاص، تعداد تماس های نزدیک حدود 12000 است. با این وجود، نتیجه آماری منتشر شده پس از تلفیق نویز حریم خصوصی دیفرانسیل 8700 است. بنابراین این امر می تواند تامین تجهیزات کمک پزشکی و سایر مواد پیشگیری از بیماری همه گیر را مختل کند، زیرا آنها نمی توانند نیازهای این منطقه را برآورده کنند و در نتیجه به تأخیر می افتند. درمان به موقع بیماران بنابراین، بهبود دقت نتایج آماری کلان داده مبتنی بر مکان با فرض اطمینان از حفظ حریم خصوصی مکان یک موضوع مهم برای خدمات کلان داده است. نتیجه آماری منتشر شده پس از گنجاندن صدای حریم خصوصی دیفرانسیل 8700 است. بنابراین این امر می تواند تامین تجهیزات کمک پزشکی و سایر مواد پیشگیری از بیماری همه گیر را مختل کند، زیرا آنها نمی توانند نیازهای این منطقه را برآورده کنند و در نتیجه زمان به موقع را به تاخیر می اندازند. درمان بیماران بنابراین، بهبود دقت نتایج آماری کلان داده مبتنی بر مکان با فرض اطمینان از حفظ حریم خصوصی مکان یک موضوع مهم برای خدمات کلان داده است. نتیجه آماری منتشر شده پس از گنجاندن صدای حریم خصوصی دیفرانسیل 8700 است. بنابراین این امر می تواند تامین تجهیزات کمک پزشکی و سایر مواد پیشگیری از بیماری همه گیر را مختل کند، زیرا آنها نمی توانند نیازهای این منطقه را برآورده کنند و در نتیجه زمان به موقع را به تاخیر می اندازند. درمان بیماران بنابراین، بهبود دقت نتایج آماری کلان داده مبتنی بر مکان با فرض اطمینان از حفظ حریم خصوصی مکان یک موضوع مهم برای خدمات کلان داده است.

به منظور کاهش تأثیر ساختار پارتیشن فضایی و نویز حریم خصوصی دیفرانسیل بر در دسترس بودن داده‌های منتشر شده، این مقاله بدینوسیله یک الگوریتم خوشه‌بندی شبکه از پایین به بالا و یک الگوریتم انتشار داده حفظ حریم خصوصی دیفرانسیل را پیشنهاد می‌کند. خطاهای پرس و جو شمارش محدوده کاهش می یابد و در دسترس بودن نتایج آماری منتشر شده بهبود می یابد.

بقیه مقاله به شرح زیر سازماندهی شده است: بخش 2 به بررسی پیشرفته ترین روش های تجزیه فضایی خصوصی می پردازد. بخش 3 مدل حریم خصوصی متمایز مورد استفاده برای انتشار اطلاعات آماری کلان داده مبتنی بر مکان را تعریف می کند. بخش 4 مشکلات تجزیه فضایی حریم خصوصی سنتی را تحلیل می‌کند و الگوریتم خوشه‌بندی شبکه پیشنهادی را معرفی می‌کند. بخش 5 ، انتشار آماری پیشنهادی و الگوریتم‌های حفاظت از حریم خصوصی متفاوت را شرح می‌دهد. در نهایت، بخش 6 مجموعه ای از مطالعات تجربی را گزارش می کند، در حالی که بخش 7 مقاله را به پایان می رساند و محدودیت ها و کارهای آتی تحقیق را ترسیم می کند.

2. کارهای مرتبط

تجزیه فضایی حریم خصوصی یکی از ابزارهای مهم برای تحقق کاربرد انتشار آماری کلان داده مبتنی بر مکان است. انتشار آماری و اختلال افتراقی اطلاعات مبتنی بر مکان در منطقه پارتیشن و نمایه سازی، کاهش خطر حریم خصوصی مکان کاربران را تسهیل می کند. روش‌های سنتی تجزیه فضایی حریم خصوصی، فضای دوبعدی را از بالا به پایین تقسیم می‌کنند و مناطق پارتیشن را بر اساس شبکه مستقل مکان یا ساختار درختی یا برخی ساختارهای سلسله مراتبی مبتنی بر مکان فهرست‌بندی می‌کنند.

ساختار پارتیشن و نمایه سازی مبتنی بر شبکه رایج ترین روش های تجزیه حریم خصوصی است که در آن روش شبکه یکنواخت (UG) و روش شبکه تطبیقی (AG) نمایندگان معمولی هستند [ 11 ]. اولی فضای دو بعدی را به شبکه هایی با اندازه مساوی جدا می کند و نتیجه آماری را در واحدهای شبکه محاسبه می کند. دومی پارتیشن شبکه ای بیشتری را بر روی مناطق متراکم بر اساس روش UG انجام می دهد. در [ 12 ]، نویسندگان از نقشه های کانتور برای توصیف توزیع نقاط مکان در خدمات جمع سپاری فضایی و تقسیم ناحیه فضایی به واحدهای منفصل برای محافظت از حریم خصوصی مکان کارگران استفاده می کنند. روش پارتیشن پیشنهادی در [ 13] ابتدا پارتیشن شبکه تطبیقی با چگالی اولیه را با قضاوت در مورد توزیع اطلاعات مبتنی بر مکان در جهت طول و عرض جغرافیایی بدست می‌آورد و متعاقباً برای صرفه‌جویی در فرآیند پارتیشن غیر ضروری و کاهش خطاهای انتشار، پارتیشن شبکه تطبیقی بر روی شبکه‌های متراکم انجام شد. در [ 14 ]، نویسندگان یک روش پارتیشن شبکه تطبیقی سه لایه مبتنی بر فناوری نمونه‌گیری تصادفی برنولی را پیشنهاد کردند که از مکانیسم نمایی و فناوری فیلتر بالا گذر برای فیلتر کردن شبکه‌های کوچکتر از آستانه از پیش تعریف شده در لایه دوم ساختار پارتیشن استفاده می‌کند. اما به پارتیشن بندی شبکه بزرگتر از آستانه از پیش تعریف شده ادامه می دهد. طرح حفاظت از حریم خصوصی مکان پیشنهاد شده در [ 15] از یک ساختار شبکه تطبیقی سه لایه و یک الگوریتم شبکه کاملا هرمی بر اساس حریم خصوصی دیفرانسیل استفاده می کند. در [ 16 ]، نویسندگان از اطلاعات آماری توزیع ذرات برای استخراج تجزیه فضایی بهینه استفاده می کنند تا هر واحد حاوی ذرات با توزیع فضایی یکنواخت باشد. یک مشکل رایج در روش پارتیشن مبتنی بر شبکه، متعادل کردن خطای نویز با خطای فرض یکنواخت دشوار است، که بر دقت نتایج آماری منتشر شده تأثیر می گذارد.

ساختار درختی ویژگی های سلسله مراتبی بهتری دارد و می تواند خدمات جستجوی محدوده فضایی راحت تری را ارائه دهد. الگوریتم Quad-opt [ 17 ] فضای دو بعدی را با استفاده از یک ساختار کامل چهار درختی جدا می‌کند و یک روش پس از تنظیم را طراحی می‌کند که دقت جستجوی شمارش محدوده را تا حدی بهبود می‌بخشد. با این حال، ساختار چهاردرختی کامل، توزیع داده ها را در نظر نمی گیرد، در نتیجه منجر به یک خطای فرضی یکنواخت بزرگ می شود. در [ 18 ]، نتایج کامل پارتیشن چهاردرختی مطابق با شرایط یکنواختی به منظور کاهش خطای فرض یکنواختی تنظیم و از پایین به بالا ادغام می شوند. در [ 19]، نویسندگان کل منطقه را به چهار واحد فرعی با اندازه‌های مختلف جدا می‌کنند و به صورت بازگشتی همان فرآیند پارتیشن را فراخوانی می‌کنند تا یک ساختار فضایی معقول به دست آید. در [ 20 ]، نویسندگان یک روش پارتیشن چهاردرختی نامتعادل را بر اساس یکنواختی منطقه ای پیشنهاد می کنند که زیردرخت را طبق استراتژی اول عمق طی می کند و به طور تطبیقی تقسیم بندی را بر اساس یکنواختی انجام می دهد. با این حال، روش های پارتیشن مبتنی بر درخت به عملیات بازگشتی بیشتری نیاز دارند و بنابراین، کارایی اجرای پارتیشن و الگوریتم انتشار به پایین کشیده می شود. برخی از روش های تجزیه فضایی حریم خصوصی به طور ارگانیک ساختارهای مبتنی بر شبکه و مبتنی بر درخت را برای تشکیل ساختارهای پارتیشن هیبریدی ترکیب می کنند [ 21 , 22]، در نتیجه دقت خدمات جستجوی شمارش محدوده را بهبود می بخشد.

تجزیه و تحلیل خوشه بندی نقش مهمی در فرآیند داده کاوی برای مدت طولانی ایفا می کند. رکوردهای داده های خوشه ای که از نظر مکانی به یکدیگر در یک منطقه نزدیک هستند، نه تنها بهبود دقت داده های آماری منتشر شده را تسهیل می کند، بلکه از اطلاعات مکان مربوط به یک رکورد واحد نیز محافظت می کند. این نوع الگوریتم خوشه بندی مبتنی بر شبکه یا مبتنی بر چگالی [ 23 ، 24 ، 25 ، 26 ، 27 ] می تواند برای طبقه بندی داده ها از هر شکلی استفاده شود. از آنجایی که فقط به محاسبات کمتری مربوط به فاصله بین تعداد کمی از گره های شبکه نیاز دارد، الگوریتم خوشه بندی دارای سطح بالایی از کارایی است. در [ 28]، نویسندگان یک الگوریتم خوشه‌بندی کلان داده مبتنی بر مکان را بر اساس چگالی و پارتیشن شبکه پیشنهاد می‌کنند. مدل تجزیه و تحلیل فاصله سلولی پیشنهادی، محاسبه فاصله و پیمایش نقاط مکان را بسیار کاهش داد. در [ 29 ]، نویسندگان یک روش خوشه‌بندی جریان داده آنلاین را بر اساس شبکه‌های چگالی پیشنهاد کردند. روش مبتنی بر شبکه برای کاهش تعداد تماس‌های تابع فاصله و در نتیجه بهبود کیفیت خوشه‌بندی استفاده می‌شود. که در [ 30]، نویسندگان یک الگوریتم خوشه بندی شبکه ای قوی برای پردازش موازی خوشه بندی بر اساس MapReduce پیشنهاد می کنند. خوشه های شبکه با اتصال قوی با محاسبه ماتریس وزن اتصال ادغام می شوند تا خوشه بندی کارآمد داده های مکان را محقق کنند. با بهبود روش‌های یادگیری ماشین، خوشه‌بندی شبکه با کارایی بالا و الگوریتم‌های خوشه‌بندی چگالی به تدریج در حال افزایش هستند. ترکیب الگوریتم‌های خوشه‌بندی فوق با انتشار اطلاعات آماری مبتنی بر مکان می‌تواند دسترسی به داده‌های منتشر شده را بر اساس استفاده کامل از ویژگی‌های توزیع داده‌های مبتنی بر مکان بهبود بخشد. تحقیقات در این زمینه فضای کاربردی بسیار گسترده ای دارد.

3. حریم خصوصی دیفرانسیل

تعریف 1

( $ϵ$ -حریم خصوصی دیفرانسیل [ 31 ، 32 ]). برای یک جفت مجموعه داده همسایه $T_{1}$ و $T_{2}$ با $‖ T_{1} - T_{2} ‖_{1} \leq 1$ ، یک الگوریتم تصادفی K با دامنه N به طور افتراقی خصوصی است اگر برای همه $S \subseteq R a n g e (K)$ ، وجود دارد:

پ r [ک (تی 1) \in اس] \leq ه ϵ \times پ r [ک (تی 2) \in اس]

(1)

پارامتر

ϵ

در فرمول (1) به عنوان بودجه حفظ حریم خصوصی گفته می شود. هر چه ارزش آن کمتر باشد

ϵ

، درجه حفاظت از حریم خصوصی ارائه شده توسط الگوریتم K بالاتر است . حتی اگر یک مهاجم تمام داده ها را به جز یک رکورد هدف خاص به دست آورد، مهاجم هنوز نمی تواند تعیین کند که آیا رکوردهای مربوط به یک هدف در مجموعه داده اصلی وجود دارد یا خیر، در نتیجه حفاظت از حریم خصوصی را درک می کند.

تعریف 2

(حساسیت [ 33 ]). برای یک تابع نگاشت پرس و جو داده شده f، حساسیت $▵ f$ به عنوان حداکثر تعریف شده است $L_{1}$ فاصله هنجار بین خروجی تابع نگاشت پرس و جو در مجموعه داده های همسایه $T_{1}$ و $T_{2}$ :

△ f = حداکثر تی 1 ، تی 2 ∥ f (تی 1) - f (تی 2) ∥ 1

(2)

تعریف 3

(مکانیسم لاپلاس [ 33 ]). برای پرس و جوهای عددی، مکانیسم لاپلاس با ترکیب مقدار کمی نویز مستقل در خروجی تابع نگاشت پرس و جو f به حفاظت از حریم خصوصی تفاضلی دست می یابد. اجازه دهید $f (T)$ نمایش نتیجه به دست آمده توسط تابع نگاشت پرس و جو f در مجموعه داده اصلی T. سپس، نتیجه پرس و جو که توسط مکانیسم لاپلاس برگردانده می شود را می توان به صورت بیان کرد $K (T) = f (T) + η$ ، که در آن η یک متغیر تصادفی پیوسته است که توزیع لاپلاس (در مرکز 0) را با مقیاس b برآورده می کند و تابع چگالی احتمال آن را می توان به صورت زیر بیان کرد:

پ r [η = x] = 1 2 ب ه - | x | ب

(3)

همراه با تعریف حساسیت، نویز مستقل گنجانده شده یک توزیع لاپلاس متوسط صفر را برآورده می کند.

b = \frac{▵ f}{ϵ}

قضیه 1

(ویژگی های ترکیب سریال [ 34 ]). برای مجموعه ای از الگوریتم های تصادفی

{K_{1}, K_{2}, \dots, K_{n}}

در همان مجموعه داده T، که در آن

K_{i}

هست یک

ϵ_{i}

-الگوریتم خصوصی متفاوت

(1 \leq i \leq n)

. سپس، ترکیب آنها

{K_{1}, K_{2}, \dots, K_{n}}

است

\sum_{i = 1}^{n} ϵ_{i}

خصوصی متفاوت

قضیه 2

(ویژگی های ترکیب موازی [ 34 ]). اگر مجموعه داده T از مجموعه ای از زیرمجموعه های مستقل و مجزا تشکیل شده باشد

{T_{1}, T_{2}, \dots, T_{n}}

، مجموعه ای از الگوریتم های تصادفی

{K_{1}, K_{2}, \dots, K_{n}}

هستند

ϵ_{i}

به ترتیب خصوصی متفاوت؛ سپس، ترکیب آنها

{K_{1}, K_{2}, \dots, K_{n}}

است

m a x {ϵ_{i}}

خصوصی متفاوت

تعریف 4

(خطای نویز). برای هر محدوده پرس و جو Q، خطای بین نتایج آماری منتشر شده و نتایج آماری اصلی پس از پردازش حفاظت از حریم خصوصی به عنوان خطای نویز گفته می شود:

ن o i s e_E r r o r (Q) = | سی o u n t (Q) - C o u n تی * (س) |

(4)

که در آن $C o u n t (Q)$ نشان دهنده نتیجه آماری اطلاعات مبتنی بر مکان اصلی در محدوده پرس و جو Q و $C o u n t^{*} (Q)$ نتیجه آماری داده های منتشر شده را در همان منطقه نشان می دهد.

تعریف 5

(خطای فرض یکنواخت). از آنجایی که فضای دو بعدی را نمی توان به طور دقیق به یک نقطه تقسیم کرد، الگوریتم های پارتیشن و انتشار اغلب فرض می کنند که اطلاعات مبتنی بر مکان در کوچکترین ناحیه پارتیشن به طور یکنواخت توزیع شده است. خطای پرس و جو شمارش محدوده که در نتیجه تخمین فرض یکنواخت رخ می دهد، خطای فرض یکنواخت نامیده می شود:

U n i_E r r o r (Q) = | \sum i = 1 متر r من \cdot سی اوه تو (__پ من) - سی o u n t (Q) |

(5)

که در آن $P_{i}$ $(i = 1, 2, \dots, m)$ ناحیه پارتیشنی را نشان می دهد که با محدوده پرس و جو Q قطع می شود و برآورده می شود $\underset{1 \leq i, j \leq m ⋀ i \neq j}{P_{i} \cap P_{j}} = \emptyset$ . $r_{i}$ $(i = 1, 2, \dots, m)$ نسبت تقاطع محدوده پرس و جو Q و ناحیه پارتیشن است و $C o u n t (Q)$ نشان دهنده نتیجه آماری اطلاعات مبتنی بر مکان اصلی در محدوده پرس و جو است.

4. الگوریتم خوشه بندی شبکه ای برای اطلاعات آماری کلان داده مبتنی بر مکان

4.1. مشکلات تجزیه فضایی حریم خصوصی سنتی

ساختار پارتیشن نامعقول احتمالاً خطاهای انتشار را برای اطلاعات آماری کلان داده مبتنی بر مکان افزایش می دهد. خطاها عمدتاً شامل خطای نویز حریم خصوصی دیفرانسیل و خطای فرض یکنواخت هستند. اگر توزیع محلی داده های بزرگ مبتنی بر مکان دارای مشخصه پراکنده باشد همانطور که در شکل 3 a نشان داده شده است، مقدار آماری دقیق در محدوده پرس و جو

Q_{1}

، به عنوان مثال، جعبه نقطه قرمز 1 است. نتیجه پرس و جو برگشتی پس از ترکیب نویز حریم خصوصی دیفرانسیل مطابق با تعریف 3 حدود است.

(3 + 2.6) \times \frac{4}{9} \approx 2.5

و به نتیجه آماری واقعی نزدیکتر است. نتیجه پارتیشن و حفاظت از حریم خصوصی دیفرانسیل توزیع محلی داده های بزرگ مبتنی بر مکان در شکل 3 ب نشان داده شده است. نتیجه پرس و جو برگشتی در همان محدوده

Q_{1}

در مورد است

1 + 6.3 = 7.3

(که در آن 6.3 خطای نویز است). از این مثال، می‌توانیم مشاهده کنیم که اگر یک ساختار پارتیشن دارای تعداد زیادی گره خالی باشد، به عنوان مثال، شبکه‌هایی بدون اطلاعات مبتنی بر مکان، ترکیب نویز حریم خصوصی دیفرانسیل، خطای نویز بزرگی را ایجاد می‌کند و دقت پرس و جو نتایج منتشر شده را کاهش می‌دهد.

اگر توزیع محلی داده های بزرگ مبتنی بر مکان دارای ویژگی یکنواختی باشد که در شکل 4 a نشان داده شده است، مقدار آماری دقیق در محدوده پرس و جو

Q_{2}

یعنی کادر آبی رنگ 16 است.

(148 - 7.6) \times \frac{1}{9} \approx 15.6

و همچنین به نتایج آماری واقعی نزدیکتر است. با این حال، برای پارتیشن و نتیجه حفاظت از حریم خصوصی دیفرانسیل توزیع مربوطه نشان داده شده در شکل 4 ب، نتیجه پرس و جو برگشتی در همان محدوده

Q_{2}

است

16 - 6.9 = 9.1

(که در آن 6.9 خطای نویز است). بنابراین، پارتیشن بندی بیش از حد مناطق با توزیع فضایی نسبتا یکنواخت نیز منجر به کاهش دقت جستجوهای شمارش محدوده می شود.

اگر توزیع محلی داده های بزرگ مبتنی بر مکان دارای ویژگی های غیریکنواختی باشد که در شکل 5 الف نشان داده شده است، مقدار آماری دقیق در محدوده پرس و جو

Q_{3}

، یعنی کادر سبز نقطه چین 3 است و نتیجه پرس و جو برگشتی پس از ترکیب نویز حریم خصوصی دیفرانسیل است

(101 + 11.6) \times \frac{1}{9} \approx 12.5

. خطای انتشار بین نتایج آماری منتشر شده و واقعی نسبتاً زیاد است. با این حال، برای پارتیشن و نتیجه حفاظت از حریم خصوصی دیفرانسیل توزیع مربوطه نشان داده شده در شکل 5 ب، نتیجه پرس و جو برگشتی در همان محدوده

Q_{3}

است

3 + 1.1 = 4.1

(که در آن 1.1 خطای نویز است). می توان مشاهده کرد که برای مناطقی با توزیع فضایی غیریکنواخت، پارتیشن بندی کمتر باعث خطای فرض یکنواخت بزرگ تری می شود و بر دقت پرس و جوهای شمارش محدوده تأثیر می گذارد.

4.2. روش پیشنهادی

به منظور غلبه بر مشکلات ذکر شده در بالا در طول تجزیه فضایی حریم خصوصی، ما یک الگوریتم خوشه‌بندی شبکه‌ای برای اطلاعات آماری کلان داده مبتنی بر مکان پیشنهاد می‌کنیم. در مرحله اول، فضای دوبعدی تحت پوشش اطلاعات مکان به شبکه های یکنواخت مطابق با حداقل اندازه سرویس جستجوی شمارش محدوده داده های بزرگ مبتنی بر مکان تقسیم می شود. تعداد نقاط مکان در هر شبکه شمارش شده و به عنوان تراکم شبکه استفاده می شود. در بسیاری از کاربردهای عملی، از جمله اما نه محدود به، آمار جمعیت، آمار ترافیک و خدمات مبتنی بر مکان، آمار با استفاده از شمارش محدوده منتشر می شود [ 35 ، 36 ]]. بنابراین، پارتیشن شبکه اولیه و روش آماری ما در راستای سناریوهای کاربردی عملی است. ثانیا، شرایط قضاوت توزیع یکنواخت برای مناطق شبکه در تلاش برای تعیین ویژگی های توزیع شبکه های غیر خالی طراحی شده است. چگالی شبکه از طریق تبدیل موجک گسسته درجه‌بندی می‌شود که بنابراین، دستیابی به خوشه‌بندی درشت نتایج آماری داده‌های بزرگ مبتنی بر مکان را تسهیل می‌کند. در نهایت، یک الگوریتم خوشه بندی شبکه از پایین به بالا پیشنهاد شده است. شبکه یکنواخت و شبکه خالی متعلق به همان سطح چگالی خوشه‌بندی شده و بر اساس شباهت همسایگی ادغام می‌شوند. بنابراین، خطای نویز و خطای فرض یکنواخت در نتایج آماری منتشر شده کاهش می‌یابد.

تعریف 6

(یکنواختی شبکه). برای یک شبکه G با چگالی $D e n (G)$ ، اجازه دهید $D e n (D_{1}),$ $D e n (D_{2})$ ,…, $D e n (D_{i})$ چگالی مناطق فرعی شبکه G باشد که از جهات افقی، عمودی، مورب و سایر جهات تقسیم شده اند. اگر بردار ردیف $V = {D e n (D_{1}), D e n (D_{2}), \dots,$ $D e n (D_{i})}$ ساخته می شود، سپس یکنواختی توزیع شبکه G را می توان با واریانس نشان داد $V a r (V)$ از بردار V. اگر فرمول (6) زیر برآورده شود، شبکه G به عنوان یک شبکه توزیع یکنواخت گفته می شود:

| L F C - log 10 (D e n ( G ) i) 2 | \leq θ

(6)

که در آن $L F C = l o g_{10} (V a r (V))$ ، i تعداد زیرمنطقه های بعد از تقسیم بندی چند جهته و θ آستانه است.

تعریف 7

(شبکه محله). اجازه دهید $C_{i}$ مرکز شبکه باشد $G_{i}$ و فاصله بین هر دو شبکه با لبه مجاور مشترک 1 باشد. اگر فاصله بین شبکه ها باشد $G_{i}$ و $G_{j}$ فرمول (7) زیر را برآورده می کند $G_{j}$ به عنوان شبکه همسایگی شبکه شناخته می شود $G_{i}$ (همانطور که در شکل 6 نشان داده شده است ).

d i s (C i, C j) \leq 2 -\sqrt

(7)

مناطقی با یکنواختی یکسان اما از نظر تراکم دارای تفاوت های زیاد برای ادغام مستقیم مناسب نیستند. بنابراین، ما از تبدیل موجک گسسته (DWT) استفاده می کنیم تا ماتریس تشکیل شده از طریق چگالی شبکه ها را طبقه بندی کنیم. متعاقباً، شبکه‌های سطوح مختلف با توجه به شباهت همسایگی ادغام می‌شوند تا ساختار انتشار نهایی را تشکیل دهند. DWT می تواند سیگنال را به زیر باندهای مختلف با اطلاعات فرکانس و زمان تجزیه کند تا تجزیه و تحلیل محلی و دقیق زمان یا مکان را انجام دهد. فرآیند تجزیه DWT در شکل 7 نشان داده شده است . سیگنال ورودی

X (n)

ابتدا با پایین گذر محاسبه می شود (با علامت گذاری شده به عنوان

f_l (n)

) و بالا گذر (با علامت گذاری شده است

f_h (n)

) به ترتیب افقی فیلتر می شود و سپس با ضریب 2 نمونه برداری می شود. متعاقباً خروجی ها

L_{1}

H_{1}

توسط فیلترهای عمودی پایین گذر و بالاگذر به طور جداگانه پردازش می شوند و دوباره نمونه برداری می شوند. در صورت لزوم، تجزیه DWT سطح بعدی را می توان بر روی ضرایب فرکانس پایین انجام داد.

L L_{1}

) از لایه قبلی DWT طبق همین روش. ضرایب فرکانس پایین تبدیل DWT بیشتر انرژی یک سیگنال را شامل می شود. بنابراین، ضرایب فرکانس پایین ماتریس چگالی پس از تبدیل DWT برای انجام طبقه‌بندی چگالی شبکه در این مقاله انتخاب شدند.

تعریف 8

(Grid Density Grading). اجازه دهید $L L$ به ضرایب فرکانس پایین ماتریس چگالی شبکه اصلی پس از تبدیل 2 بعدی DWT مراجعه کنید. با توجه به دو آستانه، $T_{1} = \frac{1}{3} \bar{L L}$ و $T_{2} = \frac{2}{3} \bar{L L}$ ، ماتریس چگالی شبکه اصلی را می توان به سه سطح طبقه بندی کرد:

C l a s s (i, j) = ⎧⎩⎨⎪⎪ 123 i f i f i f L L (i, j) \leq T 1 T 1 < L L (i, j) \leq T 2 T 2 \leq L L (i, j)

(8)

الگوریتم 1 مکانیسم پیاده سازی دقیق الگوریتم خوشه بندی شبکه ارائه شده در این مقاله را تشریح می کند. خطوط 1-18 آمار پارتیشن شبکه و چگالی یکنواخت را در فضای دوبعدی تحت پوشش مجموعه داده مکان انجام می دهند. فضای اولیه با قضاوت یکنواختی به شبکه های خالی (پرچم = 0)، شبکه های یکنواخت (پرچم = 1) و شبکه های غیر یکنواخت (پرچم = 2) تفکیک می شود. شبکه های یکنواخت بیشتر از طریق چگالی آنها درجه بندی می شوند. خطوط 19-34 انواع مختلف خوشه بندی شبکه را کامل می کند: برای شبکه های یکنواخت با پرچم = 1، شبکه های همسایگی با طبقه بندی چگالی یکسان برای تشکیل یک خوشه یکپارچه می شوند. برای شبکه های خالی با پرچم = 0، خوشه بندی و ادغام مشابه در شبکه های خالی مجاور انجام می شود. عملیات فوق در کاهش الحاق نویز لاپلاس و جلوگیری از تجمع بیش از حد خطاهای نویز را تسهیل می کند.بخش 4.1 ، ترکیبی از این نوع ناحیه باعث خطاهای بزرگ فرضی یکنواخت می شود. بنابراین، ما این نوع شبکه ها را از طریق الگوریتم پیشنهادی خود خوشه بندی نمی کنیم. خطوط 35-36 ماتریس ساختار خوشه نهایی را برمی گرداند. شکل 8 نتایج الگوریتم خوشه بندی شبکه پیشنهادی را با در نظر گرفتن مجموعه داده مکان، Storage، به عنوان مثال نشان می دهد (از رنگ های مختلف برای نمایش خوشه های مختلف استفاده می شود).

الگوریتم 1 الگوریتم خوشه بندی شبکه ای.

نیاز: مجموعه داده مبتنی بر مکان D ; دانه بندی پارتیشن m ; آستانه یکنواختی

θ

; آستانه درجه بندی چگالی

T_{1}

T_{2}

;
اطمینان حاصل کنید: ماتریس ساختار خوشه

C S M

; ماتریس چگالی شبکه

D e n

;

1:: فضای دوبعدی مجموعه داده مبتنی بر مکان D را به قسمت تقسیم کنید $m \times m$ شبکه های یکنواخت
2:: $D e n (i, j)$ =0، $f l a g (i, j)$ =0، $C l a s s (i, j)$ =0، $u n i_G (i, j)$ =0، $n u l l_G (i, j)$ =0، $(i, j = 1, 2, \dots, m)$
3:: برای هر شبکه انجام دهید
4:: $D e n (i, j) ⟵$ چگالی شبکه جریان را محاسبه کنید
5:: اگر $D e n (i, j) = 0$ سپس
6:: $f l a g (i, j) = 0$
7:: دیگر
8:: اگر یکنواختی شبکه جاری فرمول (6) را برآورده کند، آنگاه
9:: $f l a g (i, j) = 1$
10:: دیگر
11:: $f l a g (i, j) = 2$
12:: پایان اگر
13:: پایان اگر
14:: پایان برای
15:: $c A ⟵$ تبدیل کامل DWT روشن است $D e n$ و ضرایب فرکانس پایین را بدست آورید
16:: برای هر شبکه با $f l a g$ = 1 انجام
17:: $C l a s s (i, j) ⟵$ درجه بندی چگالی شبکه طبق فرمول (8)
18:: پایان برای
19:: برای هر شبکه یکنواخت با $f l a g$ = 1 انجام
20:: برای هر کلاس در فرمول (8) انجام دهید
21:: اگر شبکه همسایگی شبکه فعلی تعریف (7) را برآورده کند
22:: $u n i_G ⟵$ شبکه متصل را با برچسب شبکه فعلی تنظیم کنید
23:: دیگر
24:: $u n i_G ⟵$ شبکه فعلی را به عنوان یک شماره دنباله جدید علامت گذاری کنید
25:: پایان اگر
26:: پایان برای
27:: پایان برای
28:: برای هر شبکه خالی با $f l a g$ = 0 انجام دهید
29:: اگر شبکه همسایگی شبکه فعلی تعریف (7) را برآورده کند
30:: $n u l l_G ⟵$ شبکه متصل را با برچسب شبکه فعلی تنظیم کنید
31:: دیگر
32:: $n u l l_G ⟵$ شبکه فعلی را به عنوان یک شماره دنباله جدید علامت گذاری کنید
33:: پایان اگر
34:: پایان برای
35:: $C S M ⟵$ ماتریس را ادغام کنید $u n i_G$ و $n u l l_G$
36:: برگشت $C S M$ ، $D e n$

5. انتشار آماری و الگوریتم حفاظت از حریم خصوصی

به منظور تحقق حفاظت از حریم خصوصی داده های بزرگ مبتنی بر مکان منتشر شده، لازم است بودجه حریم خصوصی متفاوت با توجه به ساختار نمایه سازی فضایی تخصیص داده شود و نویز اختلال در نتایج آماری هر منطقه فضایی گنجانده شود. الگوریتم 2، حفظ حریم خصوصی متمایز فرآیند انتشار داده های بزرگ مبتنی بر مکان را به تصویر می کشد. ابتدا طبق الگوریتم 1، ساختار توزیع کل فضا به دست می آید. سپس، نتایج آماری در هر خوشه محاسبه می‌شود و نویز لاپلاسی با بودجه حفظ حریم خصوصی $ϵ$ در نتایج آماری هر خوشه گنجانده شده است. در نهایت، نتایج آماری پر سر و صدا به طور مساوی به هر منطقه شبکه با توجه به تعداد شبکه‌های درون خوشه تخصیص داده می‌شود تا خطای نویز و خطای فرض یکنواخت را متعادل کرده و قابلیت استفاده نتایج آماری منتشر شده را بهبود بخشد. شکل 9 شماتیک ساختار پارتیشن شبکه و فرآیند خوشه بندی را نشان می دهد که در آن شکل 9a نوع شبکه زیرین را با اعداد قرمز نشان می دهد (یعنی flag = 0 مربوط به شبکه های خالی است، flag = 1 نشان دهنده شبکه های یکنواخت، و flag = 2 مخفف شبکه های غیر یکنواخت است). فقط شبکه‌های خالی مجاور یا شبکه‌های یکنواخت با سطح چگالی یکسان می‌توانند برای تشکیل خوشه‌های شبکه یکپارچه شوند. از این رو، نه شبکه های غیریکنواخت و نه شبکه های یکنواخت با سطوح چگالی متفاوت را نمی توان برای کاهش خطای فرض یکنواختی ادغام کرد.

الگوریتم 2 الگوریتم انتشار حفظ حریم خصوصی دیفرانسیل.

نیاز: ماتریس ساختار خوشه

C S M

; ماتریس چگالی شبکه

D e n

; بودجه حریم خصوصی

ϵ

; حساسیت S ;
اطمینان حاصل کنید: نتایج آماری را بر اساس شبکه منتشر کنید

D e n^{*}

;

1:: $D e n^{*} (i, j)$ =0
2:: $n ⟵$ تعداد خوشه ها را بر اساس محاسبه کنید $C S M$
3:: برای هر خوشه انجام دهید
4:: $u ⟵$ تعداد شبکه های موجود در خوشه فعلی را محاسبه کنید
5:: $s u m_D e n ⟵$ چگالی شبکه های u را بر اساس جمع کنید $D e n$
6:: $n o i s y_s u m = s u m_D e n + L a p l a c e (\frac{S}{ϵ})$
7:: $D e n^{*} (i, j) = n o i s y_s u m / u$
8:: پایان برای
9:: برگشت $D e n^{*}$

نتیجه 1.

الگوریتم 2 می تواند حفاظت از حریم خصوصی ϵ-دیفرانسیلی را برای نتایج آماری کلان داده مبتنی بر مکان منتشر شده فراهم کند.

اثبات

برای هر محدوده پرس و جو Q ارسال شده توسط کاربر، پرس و جو شمارش محدوده دارای موارد استفاده زیر است:

(1) محدوده پرس و جو Q در منطقه تحت پوشش یک خوشه خاص قرار دارد که در شکل 10 a نشان داده شده است. با توجه به الگوریتم خوشه بندی شبکه 1 پیشنهاد شده در این مقاله، محدوده پرس و جو Q ممکن است در یک شبکه زیربنایی منفرد یا در یک منطقه ادغام شده توسط چندین شبکه زیربنایی گنجانده شود. در وضعیت قبلی، می توان نتیجه گرفت که این شبکه زیربنایی یک شبکه غیریکنواخت است و به تنهایی یک خوشه را تشکیل می دهد. بنابراین، الگوریتم 2 نویز لاپلاس را در این شبکه با بودجه حریم خصوصی تفاضلی ترکیب می کند.

ϵ

. در وضعیت دوم، الگوریتم 2 نویز لاپلاس را در منطقه ادغام شده با بودجه حریم خصوصی متفاوت از

ϵ

. با توجه به ویژگی های ترکیبی موازی مدل حریم خصوصی دیفرانسیل که در قضیه 2 توضیح داده شده است، هر شبکه ای که در منطقه ادغام شده قرار می گیرد، حفاظت از حریم خصوصی دیفرانسیل را برآورده می کند.

m a x {ϵ_{i}} = ϵ

(2) محدوده پرس و جو Q شامل ناحیه تحت پوشش A (

A \geq 1

) خوشه های کامل همانطور که در شکل 10 ب نشان داده شده است. در این مورد، هر خوشه با اولین مورد استفاده که در بالا توضیح داده شد مطابقت دارد. بنابراین، با توجه به ویژگی های ترکیبی موازی مدل حریم خصوصی دیفرانسیل که در قضیه 2 توضیح داده شده است، تمام خوشه های A کامل موجود در محدوده پرس و جو Q می توانند حفاظت از حریم خصوصی دیفرانسیل را فراهم کنند.

m a x {ϵ_{i}} = ϵ

(3) محدوده پرس و جو Q شامل ناحیه تحت پوشش B (

B \geq 1

) خوشه های متقاطع همانطور که در شکل 10 نشان داده شده است. در این حالت، هر یک از مناطق متقاطع مطابق با مورد (1) است و همچنین می تواند حفاظت از حریم خصوصی متفاوت را با قدرتی از

ϵ

(4) محدوده پرس و جو Q شامل منطقه تحت پوشش A (

A \geq 1

) خوشه های کامل و B (

B \geq 1

) خوشه های متقاطع، همانطور که در شکل 10 d نشان داده شده است. برای خوشه های کاملی که در محدوده پرس و جو Q قرار می گیرند، هر خوشه می تواند ارائه دهد

ϵ

حفاظت از حریم خصوصی دیفرانسیل مشابه مورد استفاده (2). برای خوشه هایی که با محدوده پرس و جو Q قطع شده اند، منطقه متقاطع با حالت استفاده (3) مطابقت دارد و ارائه می کند

ϵ

حفاظت از حریم خصوصی دیفرانسیل بنابراین، می تواند حفاظت از حریم خصوصی متفاوتی را نیز ارائه دهد

ϵ

با توجه به ویژگی های ترکیبی موازی مدل حریم خصوصی دیفرانسیل.

بر اساس موارد استفاده فوق، می‌توان نتیجه گرفت که الگوریتم 2 می‌تواند حفاظت از حریم خصوصی متفاوتی را فراهم کند.

ϵ

برای نتایج آماری کلان داده مبتنی بر مکان منتشر شده است. □

6. آزمایش ها و تجزیه و تحلیل

به منظور ارزیابی جامع الگوریتم انتشار خوشه‌بندی شبکه و حفاظت از حریم خصوصی افتراقی (GCDPP) برای اطلاعات آماری کلان داده مبتنی بر مکان، ما الگوریتم پیشنهادی را با تعدادی از الگوریتم‌های کلاسیک تجزیه فضایی حریم خصوصی از نظر در دسترس بودن اطلاعات منتشر شده مقایسه و تجزیه و تحلیل می‌کنیم. نتایج آماری کلان داده مبتنی بر مکان، کارایی الگوریتم انتشار حفاظت از حریم خصوصی، و تأثیرات دانه بندی پارتیشن. روش‌های پایه شامل، اما نه محدود به، روش تقسیم شبکه یکنواخت (UG) [ 11 ]، روش پارتیشن شبکه تطبیقی (AG) [ 11 ]، الگوریتم تجزیه شبکه تطبیقی شعاع دایره انحراف استاندارد (SDCAG) [ 14 ]، پارتیشن چهار درختی روش (چهار گزینه ای) [17 ]، روش پارتیشن چهاردرختی مبتنی بر چگالی (DBP) [ 19 ]، و روش پارتیشن چهاردرختی نامتعادل (چهاردرخت نامتعادل) [ 20 ].

مجموعه داده‌های مبتنی بر مکان آزمایشی شامل مجموعه داده‌های اطلاعات موقعیت مکانی، Storage https://www.infochimps.com/datasets/storage-facilities-by-neighborhood-2 ، قابل دسترسی در 1 ژانویه 2022، و Landmark https://www.infochimps است. .com/datasets/storage-facilities-by- Landmarks، قابل دسترسی در 1 ژانویه 2022، ارائه شده توسط Infochimps؛ اعلام حضور https://snap.stanford.edu/data/loc-gowalla.html ، در 1 ژانویه 2022، که اطلاعات موقعیت مکانی را از سایت شبکه اجتماعی Gowalla ارائه می دهد. و مجموعه داده رکورد تاکسی، Yellow_trip (2009–2016) https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page، در 1 ژانویه 2022، توسط کمیته مدیریت تاکسی شهر نیویورک ارائه شده است. پلتفرم آزمایشی Alibaba Cloud Server ECS (ecs.r6.2xlarge: CPU 8 هسته ای، حافظه 64 گیگابایتی، 100 گیگابایت دیسک ابری ESSD، Windows Server 2019 Data Center Edition 64 بیتی) را انتخاب می کند و همه الگوریتم ها در MATLAB برنامه ریزی شده اند. .

6.1. تجزیه و تحلیل در دسترس بودن نتایج آماری کلان داده مبتنی بر مکان منتشر شده

با توجه به سناریوهای کاربردی داده های بزرگ مبتنی بر مکان، دقت جستجوی شمارش دامنه برای اطمینان از در دسترس بودن نتایج انتشار آماری کلان داده مبتنی بر مکان استفاده شده است. پرس و جوهای شمارش دامنه در اندازه های مختلف بر روی نتایج منتشر شده پیاده سازی شده و با روش های پایه مقایسه می شوند.

برای تنظیمات پارامترهای الگوریتم های خط پایه، به ادبیات مربوط به آنها مراجعه می کنیم. به طور خاص، برای $S t o r a g e$ مجموعه داده، الگوریتم UG پارامتر ثابت c = 10 را تنظیم می کند، الگوریتم AG و SDCAG از نسبت تخصیص حریم خصوصی استفاده می کنند. $α = 0.5$ ، الگوریتم Quad-opt عمق پارتیشن h = 6 را اتخاذ می کند، الگوریتم DBP حداکثر اختلاف چگالی را تنظیم می کند. $β = 5$ و الگوریتم چهار درخت نامتعادل از آستانه قضاوت یکنواختی استفاده می کند $θ = 0.01$ . حساسیت پرس و جو شمارش محدوده ناشی از ترکیب نویز حریم خصوصی دیفرانسیل است $S = 1$ . برای سه مجموعه داده بزرگ دیگر، پارامتر ثابت برای الگوریتم UG روی 1000 c ، برای الگوریتم Quad-opt بر روی h = 8 تنظیم شد و سایر پارامترها بدون تغییر باقی ماندند. اطلاعات مربوط به پرس و جوهای شمارش محدوده در اندازه های مختلف در جدول 1 نشان داده شده است . مدل حریم خصوصی دیفرانسیل نویز لاپلاس را با بودجه حریم خصوصی ترکیب می‌کند $ϵ = 0.01, ϵ = 0.1$ ، و $ϵ = 1$ . هر نوع پرس و جو به صورت تصادفی برای 1000 بار ایجاد شد تا میانگین خطای نسبی بین نتایج آماری اصلی و منتشر شده مشخص شود. تعریف خطای نسبی در فرمول (9) ارائه شده است، که در آن Q محدوده پرس و جو را نشان می دهد. $C o u n t (Q)$ نتیجه آماری به دست آمده در محدوده پرس و جو در مجموعه داده های مبتنی بر مکان اصلی را برمی گرداند و $C o u n t^{*} (Q)$ نتیجه آماری پر سر و صدایی است که روی مجموعه داده منتشر شده در همان محدوده Q به دست آمده است. برای اینکه مخرج صفر نشود، تنظیم می کنیم $ρ = 0.001 \times | T |$ طبق الگوریتم UG [ 11 ]، که در آن $| T |$ اندازه مجموعه داده مبتنی بر مکان را نشان می دهد.

R E (Q) = | C o u n t * ( Q ) - C o u n t ( Q ) | m a x { C o u n t ( Q ) , ρ }

(9)

شکل 11 ، شکل 12 ، شکل 13 و شکل 14 مقایسه دقت پرس و جو را نشان می دهد، به عنوان مثال، از نظر خطای نسبی، در مجموعه داده های مختلف و بودجه های حریم خصوصی. در همان مجموعه داده تجربی، خطای نسبی همه الگوریتم‌ها به تدریج با افزایش بودجه حفظ حریم خصوصی کاهش می‌یابد.

ϵ

. دلیل اصلی این است که افزایش بودجه حفظ حریم خصوصی

ϵ

نویز لاپلاس گنجانیده شده را کاهش می دهد، در نتیجه خطا بین نتیجه منتشر شده و مقدار آماری واقعی را کاهش می دهد. برای همه مجموعه داده ها، با افزایش دامنه پرس و جو از کوچک به بزرگ، خطای نسبی ابتدا افزایش می یابد و سپس کاهش می یابد. این عمدتاً به این دلیل است که وقتی محدوده پرس و جو کوچک است (مثلاً اندازه

q_{1}

q_{2}

، نواحی گنجانده شده فقط شامل برخی از شبکه های زیرین یا مناطق خوشه ای ادغام شده هستند، و بنابراین، تداخل نویز انباشته شده اندک است، در نتیجه خطای پرس و جو را نسبتاً کم می کند. هنگامی که محدوده پرس و جو بزرگ است (به عنوان مثال، اندازه

q_{5}

q_{6}

، نواحی شامل نواحی بیشتری هستند که به خوشه های مختلف تعلق دارند، و بنابراین، خطای فرض یکنواختی کوچک است، در نتیجه خطای کلی پرس و جو را نسبتاً کم می کند.

هنگامی که خطاهای نسبی الگوریتم‌های مختلف انتشار حفظ حریم خصوصی را در یک مجموعه داده مقایسه می‌کنیم، می‌توان مشاهده کرد که الگوریتم UG و Quad-opt در مقایسه با سایرین تحت بودجه‌های مختلف حریم خصوصی، خطاهای نسبی بالاتری دارند. دلیل آن این است که فرآیند پارتیشن فضایی این دو الگوریتم هیچ ارتباطی با توزیع فضایی اطلاعات مبتنی بر مکان ندارد، که نه تنها گره‌های خالی و خطاهای نویز بیشتری تولید می‌کند، بلکه به دلیل توزیع غیر یکنواخت، خطای فرضی یکنواخت‌تری را ایجاد می‌کند. از گره ها الگوریتم AG یک پارتیشن ریزدانه اضافی را برای شبکه های متراکم بر اساس الگوریتم UG انجام می دهد. با این حال، هنوز نمی تواند بر تعداد زیادی از خطاهای نویز ناشی از گره های خالی در مناطق با توزیع مکان پراکنده غلبه کند. از این رو، خطای نسبی الگوریتم AG زمانی که محدوده پرس و جو کوچک است کم است و زمانی که محدوده پرس و جو بزرگ است، مقدار بدتر می شود. در الگوریتم SDCAG از فیلترینگ و باکتینگ برای کاهش خطای نویز استفاده می شود. بنابراین، دقت بهتری در پرس و جو شمارش محدوده نسبت به الگوریتم AG ارائه می دهد. الگوریتم چهار درخت DBP و Unbalanced یک پارتیشن چهاردرخت اکتشافی را با توجه به یکنواختی توزیع مکان پیاده سازی می کند، در نتیجه خطای فرض یکنواختی و خطای نویز ناشی از گره های خالی را تا حد معینی جبران می کند. الگوریتم GCDPP پیشنهادی استراتژی خوشه‌بندی محله از پایین به بالا را اتخاذ می‌کند. پارتیشن شبکه یکنواخت اولیه نیاز به خدمات جستجوی شمارش در مقیاس کوچک را در نظر می گیرد و دقت بهتری در خدمات مکان حفظ می کند. خوشه بندی شبکه همسایگی از پایین به بالا، تقسیم بیش از حد مناطق پراکنده را کاهش می دهد و خطاهای نویز بیش از حد را سرکوب می کند. علاوه بر این، ادغام مناطق یکنواخت با همان تراکم را تسهیل می کند و نویز حریم خصوصی متفاوت را تقسیم می کند. بنابراین، الگوریتم پیشنهادی در مقایسه با سایر الگوریتم‌ها تحت مجموعه داده‌های مختلف و بودجه‌های مختلف حریم خصوصی، دقت پرس و جو بهتری را به دست می‌آورد.

6.2. تحلیل کارایی الگوریتم انتشار حفاظت از حریم خصوصی

جدول 2 پیچیدگی زمانی الگوریتم GCDPP پیشنهادی را با روش های پایه مقایسه می کند. برای مجموعه داده ای که n رکورد را در بر می گیرد، در حالی که الگوریتم UG، AG و SDCAG دارای پیچیدگی زمانی یکسانی هستند.

O (n)

، فرآیند پارتیشن الگوریتم UG فقط داده های ورودی را برای یک بار اسکن می کند، در حالی که الگوریتم AG و SDCAG داده های ورودی را حداقل دو بار اسکن می کند تا یک پارتیشن شبکه تطبیقی دو لایه تشکیل شود. الگوریتم Quad-opt یک پارتیشن چهاردرخت بازگشتی را روی مجموعه داده ورودی انجام می دهد. پیچیدگی کلی زمانی حدود است

O (n log (n))

. فرآیند پارتیشن بندی الگوریتم چهار درختی DBP و Unbalanced با توزیع خاص مجموعه داده مبتنی بر مکان و عمق پارتیشن چهاردرخت مرتبط است. در بدترین سناریو، برای یک مجموعه داده مبتنی بر مکان با n رکورد و h عمق پارتیشن، پیچیدگی زمانی این دو الگوریتم خواهد بود.

O (h n)

. الگوریتم پیشنهادی GCDPP ابتدا پارتیشن مشابه الگوریتم UG را انجام می‌دهد و سپس شبکه‌های همسایگی از همان نوع و درجه چگالی را برای تشکیل خوشه‌ها ادغام می‌کند. پیچیدگی زمانی آن در حدود است

O (n + n) \approx O (n)

شکل 15 مقایسه در زمان اجرای همه الگوریتم های حفاظت از حریم خصوصی در مجموعه داده های مبتنی بر مکان واقعی را نشان می دهد. تنظیمات پارامتر این الگوریتم‌ها مانند تنظیمات بخش 6.1 است. از آنجایی که قدرت بودجه حریم خصوصی تفاوت معنی داری بر زمان اجرای الگوریتم های انتشار آماری ندارد، ما می گیریم

ϵ = 1

به عنوان نمونه ای برای انجام مقایسه های تجربی بر روی مجموعه داده های مبتنی بر مکان واقعی در مقیاس های مختلف. از دیدگاه کلان، زمان اجرای کلی همه الگوریتم ها با اندازه مجموعه داده افزایش می یابد. به طور خاص، الگوریتم UG کمترین زمان اجرا را دارد و به سختی تحت تأثیر اندازه مجموعه داده قرار می گیرد. الگوریتم AG و SDCAG یک دور اضافی از پارتیشن شبکه را بر اساس الگوریتم UG انجام می دهند و بنابراین زمان بسیار بیشتری را می گیرند. به منظور کاهش خطای نویز، الگوریتم SDCAG شبکه‌ها را با تعداد خام صفر فیلتر می‌کند و شبکه‌های مشابه را در یک سطل تخصیص می‌دهد. بنابراین، زمان اجرای کلی کمی بیشتر از الگوریتم AG است. اگرچه فرآیند پارتیشن الگوریتم Quad-opt وضعیت توزیع خاص اطلاعات مکان را در نظر نمی گیرد، فرآیند تکراری مبتنی بر درخت با استفاده از پیمایش اول عمق عمدتاً تحت تأثیر اندازه مجموعه داده است. بنابراین، زمان اجرای کلی الگوریتم Quad-opt به طور قابل توجهی بیشتر از سایر الگوریتم ها است. فرآیند پارتیشن بندی الگوریتم چهار درختی DBP و Unbalanced باید با توزیع خاص اطلاعات مکان ترکیب شود. در مناطقی که توزیع مکان به خصوص پراکنده یا متراکم است، می‌توانند از تقسیم‌بندی غیرضروری اجتناب کنند. بنابراین، آنها عملکرد بهتری در مجموعه داده پراکنده دریافت کردند فرآیند پارتیشن بندی الگوریتم چهار درختی DBP و Unbalanced باید با توزیع خاص اطلاعات مکان ترکیب شود. در مناطقی که توزیع مکان به خصوص پراکنده یا متراکم است، می‌توانند از تقسیم‌بندی غیرضروری اجتناب کنند. بنابراین، آنها عملکرد بهتری در مجموعه داده پراکنده دریافت کردند فرآیند پارتیشن بندی الگوریتم چهار درختی DBP و Unbalanced باید با توزیع خاص اطلاعات مکان ترکیب شود. در مناطقی که توزیع مکان به خصوص پراکنده یا متراکم است، می‌توانند از تقسیم‌بندی غیرضروری اجتناب کنند. بنابراین، آنها عملکرد بهتری در مجموعه داده پراکنده دریافت کردندذخیره سازی و مجموعه داده متراکم Yellow_trip . الگوریتم پیشنهادی GCDPP ابتدا مرحله پارتیشن شبکه یکنواخت را پیاده سازی می کند و سپس خوشه بندی شبکه همسایگی از پایین به بالا را انجام می دهد. خوشه‌بندی مبتنی بر شبکه، ادغام مناطق فضایی را تسریع می‌کند و در مقایسه با فرآیند پارتیشن و فیلتر شبکه تطبیقی در زمان صرفه‌جویی می‌کند. بنابراین، زمان اجرای الگوریتم GCDPP تنها ثانویه به الگوریتم UG است. می توان انتظار داشت که با افزایش اندازه مجموعه داده، مزیت الگوریتم پیشنهادی GCDPP آشکارتر شود.

6.3. تأثیرات دانه بندی پارتیشن

همانطور که در بخش 4.1 مورد بحث قرار گرفت ، روش‌های سنتی تجزیه فضایی حریم خصوصی به راحتی تحت تأثیر دانه‌بندی پارتیشن قرار می‌گیرند، که منجر به مشکلات پارتیشن‌بندی بیش از حد یا کم‌پارتیشن‌بندی می‌شود که نه تنها در دسترس بودن داده‌های منتشر شده را مختل می‌کند، بلکه ممکن است کارایی کل الگوریتم انتشار داده را نیز کاهش دهد. . این بخش روابط بین تنظیم دانه بندی پارتیشن، دقت نتایج منتشر شده و کارایی الگوریتم انتشار را تجزیه و تحلیل می کند. از آنجایی که قدرت بودجه حریم خصوصی هیچ تأثیر آشکاری بر تنظیم دانه بندی پارتیشن ندارد، ما می گیریم $ϵ = 1$ به عنوان مثالی برای تجزیه و تحلیل میانگین خطای نتایج آماری منتشر شده با دانه بندی های مختلف پارتیشن. برای رعایت انصاف، ما دانه بندی اولیه پارتیشن همه الگوریتم های مقایسه را اساساً یکسان نگه می داریم. میانگین خطای نتایج آماری منتشر شده را می توان به صورت زیر بیان کرد:

A E = \sum N i = 1 ∣∣ D e n * i - D e n i ∣∣ | T |

(10)

که در آن N دانه بندی پارتیشن اولیه مجموعه داده مبتنی بر مکان است، و $| T |$ اندازه مجموعه داده را نشان می دهد. $D e n_{i}$ مخفف چگالی اصلی grid i است، در حالی که $D e n_{i}^{*}$ چگالی منتشر شده ناحیه مربوطه را برمی گرداند.

شکل 16میانگین خطای همه الگوریتم ها را تحت دانه بندی پارتیشن های مختلف نشان می دهد. می توان مشاهده کرد که با افزایش دانه بندی پارتیشن، میانگین خطای الگوریتم های پارتیشن مبتنی بر درخت به تدریج افزایش می یابد، در حالی که میانگین خطای الگوریتم های پارتیشن مبتنی بر شبکه به وضوح تغییر نمی کند. دلیل اصلی این است که وقتی دانه بندی پارتیشن کوچک است، منطقه پوشش یک شبکه بزرگ خواهد بود و نتیجه آماری منتشر شده ممکن است حاوی خطاهای فرضی غیر یکنواخت بیشتری به دلیل توزیع ناهمگن داده ها در منطقه باشد. با این وجود، خطای نویز معرفی شده به دلیل تعداد کمتر شبکه های خالی کوچک خواهد بود. با افزایش دانه بندی پارتیشن، سطح پوشش هر شبکه کاهش می یابد. خطای فرض غیر یکنواخت برای ناحیه شبکه کاهش می یابد، در حالی که خطای کل نویز افزایش می یابد زیرا ممکن است تعداد شبکه های خالی افزایش یابد. الگوریتم پیشنهادی به کمترین میانگین خطا در تقریباً تمام مجموعه‌های داده تجربی دست می‌یابد که مزیت الگوریتم پیشنهادی را در در دسترس بودن نتایج آماری منتشر شده نشان می‌دهد.

به طور شهودی، زمان اجرای الگوریتم های پارتیشن با اندازه مجموعه داده ها و دانه بندی پارتیشن افزایش می یابد. شکل 17زمان اجرای همه الگوریتم ها را تحت دانه بندی پارتیشن های مختلف نشان می دهد. پیشرفت پارتیشن الگوریتم UG مستقل از توزیع مجموعه داده است، بنابراین همیشه کمترین زمان اجرا را حفظ می کند و به سختی با تغییر دانه بندی پارتیشن تغییر می کند. برای سایر الگوریتم ها، زمان اجرا با دانه بندی پارتیشن به طور قابل توجهی افزایش می یابد. زمان اجرای الگوریتم های AG و SDCAG کمی بیشتر از الگوریتم UG است. با افزایش مقیاس مجموعه داده و پیچیدگی توزیع، کارایی این دو الگوریتم به تدریج بدتر می شود، به ویژه برای بزرگترین و پیچیده ترین مجموعه داده ها.

Y e l l o w_t r i p

. برای الگوریتم های پارتیشن مبتنی بر درخت، افزایش پارتیشن به تدریج باعث عملیات بازگشتی بیشتر و قضاوت یکنواختی می شود. بنابراین، زمان اجرای این الگوریتم ها به طور قابل توجهی آسیب می بیند. در حالی که الگوریتم GCDPP پیشنهادی پارتیشن شبکه مستقل را درست مانند الگوریتم UG حفظ می کند، فرآیند خوشه بندی شبکه از پایین به بالا بر عملیات بازگشتی بیش از حد غلبه می کند. بنابراین، با افزایش دانه بندی پارتیشن، الگوریتم پیشنهادی همچنان بهتر از الگوریتم های دیگر است. قابل پیش بینی است که مزایای الگوریتم پیشنهادی در مورد مجموعه داده های مبتنی بر مکان با مقیاس بزرگتر و توزیع پیچیده تر آشکارتر خواهد بود.

7. نتیجه گیری

توسعه سریع فناوری کلان داده و رواج گسترده پایانه های هوشمند سیار، خدمات مختلف مبتنی بر مکان را بسیار مرتبط با کار و زندگی کاربران کرده است. بر این اساس، مسائل مربوط به نشت حریم خصوصی مکان ناشی از انتشار آمار کلان داده مبتنی بر مکان توجه گسترده ای را به خود جلب کرده است. دستیابی به انتشار آمار اطلاعات مبتنی بر مکان از طریق روش تجزیه فضایی و مدل حفاظت از حریم خصوصی افتراقی می‌تواند به طور موثری از خطرات مختلف ناشی از نشت حریم خصوصی مکان با فرض اطمینان از در دسترس بودن داده جلوگیری کند. به منظور کاهش از دست دادن در دسترس بودن داده ها ناشی از پارتیشن بندی بیش از حد و کم پارتیشن بندی در روش سنتی تجزیه فضایی از بالا به پایین، این مقاله یک روش خوشه‌بندی شبکه‌ای از پایین به بالا و روش انتشار حفاظت از حریم خصوصی متفاوت را پیشنهاد می‌کند. دقت خدمات مبتنی بر مکان از طریق آمار پارتیشن شبکه و چگالی یکنواخت برآورده می شود. حفاظت از حریم خصوصی داده های منتشر شده با ترکیب نویز لاپلاس به آمار کلان داده مبتنی بر مکان مطابق با مدل حریم خصوصی دیفرانسیل به دست می آید. ادغام نواحی خالی و نواحی توزیع یکنواخت توسط خوشه بندی شبکه همسایگی به منظور کاهش خطای نویز و خطای فرض یکنواخت محقق شده است. آزمایش‌ها و تجزیه و تحلیل بر روی مجموعه داده‌های مبتنی بر مکان واقعی ثابت می‌کند که روش خوشه‌بندی شبکه پیشنهادی و انتشار حریم خصوصی افتراقی مزایای آشکاری در بهبود دقت جستجوی محدوده و کارایی عملیاتی دارد. دقت خدمات مبتنی بر مکان از طریق آمار پارتیشن شبکه و چگالی یکنواخت برآورده می شود. حفاظت از حریم خصوصی داده های منتشر شده با ترکیب نویز لاپلاس به آمار کلان داده مبتنی بر مکان مطابق با مدل حریم خصوصی دیفرانسیل به دست می آید. ادغام نواحی خالی و نواحی توزیع یکنواخت توسط خوشه بندی شبکه همسایگی به منظور کاهش خطای نویز و خطای فرض یکنواخت محقق شده است. آزمایش‌ها و تجزیه و تحلیل بر روی مجموعه داده‌های مبتنی بر مکان واقعی ثابت می‌کند که روش خوشه‌بندی شبکه پیشنهادی و انتشار حریم خصوصی افتراقی مزایای آشکاری در بهبود دقت جستجوی محدوده و کارایی عملیاتی دارد. دقت خدمات مبتنی بر مکان از طریق آمار پارتیشن شبکه و چگالی یکنواخت برآورده می شود. حفاظت از حریم خصوصی داده های منتشر شده با ترکیب نویز لاپلاس به آمار کلان داده مبتنی بر مکان مطابق با مدل حریم خصوصی دیفرانسیل به دست می آید. ادغام نواحی خالی و نواحی توزیع یکنواخت توسط خوشه بندی شبکه همسایگی به منظور کاهش خطای نویز و خطای فرض یکنواخت محقق شده است. آزمایش‌ها و تجزیه و تحلیل بر روی مجموعه داده‌های مبتنی بر مکان واقعی ثابت می‌کند که روش خوشه‌بندی شبکه پیشنهادی و انتشار حریم خصوصی افتراقی مزایای آشکاری در بهبود دقت جستجوی محدوده و کارایی عملیاتی دارد. حفاظت از حریم خصوصی داده های منتشر شده با ترکیب نویز لاپلاس به آمار کلان داده مبتنی بر مکان مطابق با مدل حریم خصوصی دیفرانسیل به دست می آید. ادغام نواحی خالی و نواحی توزیع یکنواخت توسط خوشه بندی شبکه همسایگی به منظور کاهش خطای نویز و خطای فرض یکنواخت محقق شده است. آزمایش‌ها و تجزیه و تحلیل بر روی مجموعه داده‌های مبتنی بر مکان واقعی ثابت می‌کند که روش خوشه‌بندی شبکه پیشنهادی و انتشار حریم خصوصی افتراقی مزایای آشکاری در بهبود دقت جستجوی محدوده و کارایی عملیاتی دارد. حفاظت از حریم خصوصی داده های منتشر شده با ترکیب نویز لاپلاس به آمار کلان داده مبتنی بر مکان مطابق با مدل حریم خصوصی دیفرانسیل به دست می آید. ادغام نواحی خالی و نواحی توزیع یکنواخت توسط خوشه بندی شبکه همسایگی به منظور کاهش خطای نویز و خطای فرض یکنواخت محقق شده است. آزمایش‌ها و تجزیه و تحلیل بر روی مجموعه داده‌های مبتنی بر مکان واقعی ثابت می‌کند که روش خوشه‌بندی شبکه پیشنهادی و انتشار حریم خصوصی افتراقی مزایای آشکاری در بهبود دقت جستجوی محدوده و کارایی عملیاتی دارد. ادغام نواحی خالی و نواحی توزیع یکنواخت توسط خوشه بندی شبکه همسایگی به منظور کاهش خطای نویز و خطای فرض یکنواخت محقق شده است. آزمایش‌ها و تجزیه و تحلیل بر روی مجموعه داده‌های مبتنی بر مکان واقعی ثابت می‌کند که روش خوشه‌بندی شبکه پیشنهادی و انتشار حریم خصوصی افتراقی مزایای آشکاری در بهبود دقت جستجوی محدوده و کارایی عملیاتی دارد. ادغام نواحی خالی و نواحی توزیع یکنواخت توسط خوشه بندی شبکه همسایگی به منظور کاهش خطای نویز و خطای فرض یکنواخت محقق شده است. آزمایش‌ها و تجزیه و تحلیل بر روی مجموعه داده‌های مبتنی بر مکان واقعی ثابت می‌کند که روش خوشه‌بندی شبکه پیشنهادی و انتشار حریم خصوصی افتراقی مزایای آشکاری در بهبود دقت جستجوی محدوده و کارایی عملیاتی دارد.

با این حال، این تحقیق هنوز محدودیت هایی دارد. اولاً، اکثر روش‌های پارتیشن فضایی موجود داده‌های بزرگ مبتنی بر شبکه یا ساختار درختی هستند. با این حال، مناطقی که انسان واقعاً در آن کار می‌کند و زندگی می‌کند، عمدتاً به توزیع زیرساخت‌ها مرتبط است و نمی‌توان آن‌ها را به خوبی با شبکه‌ها یا ساختارهای درختی نشان داد. روش‌های تقسیم‌بندی جغرافیایی مانند ساختارهای شبکه جاده‌ای روش‌های شاخص مؤثری ندارند و نمی‌توانند به خدمات جستجوی کارآمد برای داده‌های بزرگ مبتنی بر مکان دست یابند. بنابراین، نحوه طراحی روش پارتیشن دقیق تر و انعطاف پذیرتر همراه با ساختار شاخص کارآمد، بهبود دسترسی به نتایج منتشر شده را تسهیل می کند و یکی از کارهای آینده ما است. ثانیاً این مقاله تنها بر تقسیم بندی آماری و انتشار داده های بزرگ مبتنی بر مکان ایستا تمرکز دارد. با این حال، مکان یک کاربر به طور مداوم و تصادفی در طول زمان تغییر می کند. تغییرات دینامیکی مکان تعداد زیادی از کاربران باعث می شود که ساختار پارتیشن فضایی زمان انتشار آماری قبلی برای زمان انتشار بعدی قابل اجرا نباشد. بنابراین، چگونگی طراحی پارتیشن آماری و روش انتشار همراه با تغییر پویای داده‌های بزرگ مکان، و افزایش به‌موقع بودن و عملی بودن نتایج آماری منتشر شده با فرض اطمینان از حفظ حریم خصوصی کاربران، یک جهت تحقیقاتی بیشتر خواهد بود. در نهایت، این مقاله روش انتشار آماری داده‌های بزرگ مبتنی بر مکان را بر اساس مدل حریم خصوصی دیفرانسیل متمرکز مورد بحث قرار می‌دهد. فرض این است که مکان های کاربران از طریق یک شخص ثالث قابل اعتماد جمع آوری و به صورت آماری منتشر می شود. با این حال، هیچ پلت فرم کاملا قابل اعتمادی در کاربردهای عملی وجود ندارد. مشکلاتی مانند نقص فنی، نشت ابرکاربر و حملات هکری، مکان اصلی کاربران را در معرض خطر قرار می دهد. بنابراین، انتقال فرآیند حفاظت از حریم خصوصی مکان های کاربران به پایانه های آنها و تحقق حفاظت از حریم خصوصی متفاوت محلی در سال های اخیر به کانون تحقیقاتی تبدیل شده است.

منابع

لیو، ز. کیان، جی ال. Du، YY; وانگ، ن. یی، JW; Sun، YR; ما، تی. پی، تی. ژو، CH مدل تخمین توزیع فضایی چند سطحی جمعیت مهاجر بین منطقه ای با استفاده از داده های بزرگ فضایی-زمانی چند منبعی: مطالعه موردی مهاجران از ووهان در طول گسترش COVID-19. J.-Geo-Inf. علمی 2020 ، 22 ، 147-160. [ Google Scholar ]
وو، اچ. گی، ز. یانگ، ز. داده های بزرگ جغرافیایی برای برنامه ریزی شهری و مدیریت شهری. ژئو اسپات. Inf. علمی 2020 ، 23 ، 273-274. [ Google Scholar ] [ CrossRef ]
محمد، س. عرب نیا، منابع انسانی; Qu، X. ژانگ، دی. کیم، تی. Zhao, J. IEEE دسترسی به بخش ویژه سرمقاله: فناوری داده های بزرگ و برنامه های کاربردی در حمل و نقل هوشمند. IEEE Access 2020 ، 8 ، 201331–201344. [ Google Scholar ] [ CrossRef ]
ژو، سی. سو، اف. پی، تی. ژانگ، ا. دو، ی. لو، بی. کائو، زد. وانگ، جی ال. یوان، دبلیو. زو، YQ; و همکاران COVID-19: چالش های GIS با داده های بزرگ. Geogr. حفظ کنید. 2020 ، 1 ، 77-87. [ Google Scholar ] [ CrossRef ]
گروشکا، ن. ماوروئیدیس، وی. ویشی، ک. جنسن، ام. مسائل مربوط به حریم خصوصی و حفاظت از داده ها در داده های بزرگ: تجزیه و تحلیل مطالعه موردی تحت GDPR. در مجموعه مقالات کنفرانس بین المللی IEEE 2018 در مورد داده های بزرگ، سیاتل، WA، ایالات متحده، 10-13 دسامبر 2018؛ ص 5027–5033. [ Google Scholar ]
تکبیری، ن. هومنصدر، ع. گوکل، دی ال. پیشرو نیک، ح. حریم خصوصی در برابر تطبیق آماری: همبستگی بین کاربر. در مجموعه مقالات سمپوزیوم بین المللی IEEE 2018 در نظریه اطلاعات، Vail، CO، ایالات متحده آمریکا، 17-22 ژوئن 2018؛ ص 1036-1040. [ Google Scholar ]
پریمولت، وی. بوته، ا. مختار، س.ب. برونی، ال. راه طولانی برای حریم خصوصی مکان محاسباتی: یک نظرسنجی. IEEE Commun. Surv. معلم خصوصی 2018 ، 21 ، 2772-2793. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
یان، ی. عیلهکو، ق. محمود، ع. لی، جی. دونگ، ز. Xu, F. حفظ حریم خصوصی انتشار داده های پویا در برابر پیوند مترادف بر اساس ریزانجماد. علمی Rep. 2022 , 12 , 1-22. [ Google Scholar ] [ CrossRef ]
لی، دی. شائو، ز. یو، دبلیو. زو، ایکس. ژو، اس. خدمات پیشگیری و کنترل همه گیر عمومی بر اساس داده های کلان مکان مکانی-زمانی شهرها را هوشمندتر می کند. Geomat. Inf. علمی دانشگاه ووهان 2020 ، 45 ، 475-487. [ Google Scholar ]
ارلینگسون، او. پیهور، وی. Korolova، A. Rappor: پاسخ ترتیبی با حفظ حریم خصوصی جمع‌آوری‌شده تصادفی. در مجموعه مقالات کنفرانس ACM SIGSAC 2014 در مورد امنیت رایانه و ارتباطات، اسکاتسدیل، AZ، ایالات متحده آمریکا، 3 تا 7 نوامبر 2014. صص 1054-1067. [ Google Scholar ]
قرداجی، دبلیو. یانگ، دبلیو. Li، N. شبکه های خصوصی متفاوت برای داده های مکانی. در مجموعه مقالات بیست و نهمین کنفرانس بین المللی مهندسی داده IEEE 2013، بریزبن، QLD، استرالیا، 8 تا 12 آوریل 2013. صص 757-768. [ Google Scholar ]
Xiong، P. ژانگ، ال. زو، تی. جمع سپاری فضایی مبتنی بر پاداش با حفظ حریم خصوصی متفاوت. Enterp. Inf. سیستم 2017 ، 11 ، 1500-1517. [ Google Scholar ] [ CrossRef ]
یان، ی. الگوریتم پارتیشن بندی حریم خصوصی دیفرانسیل Hao، XH بر اساس شبکه های چگالی تطبیقی. J. شاندونگ دانشگاه. (Nat. Sci.) 2018 ، 53 ، 12-22. [ Google Scholar ]
ژو، جی. تانگ، ایکس. Qin, S. الگوریتم تجزیه شبکه تطبیقی بر اساس شعاع دایره انحراف استاندارد. بین المللی J. اجرا کنید. مهندس 2019 ، 15 ، 2145–2152. [ Google Scholar ]
وی، جی. لین، ی. یائو، ایکس. Zhang, J. حفاظت از مکان مبتنی بر حریم خصوصی متفاوت در جمع سپاری فضایی. IEEE Trans. خدمت محاسبه کنید. 2022 ، 15 ، 45-58. [ Google Scholar ] [ CrossRef ]
رودریگز، KM; رئیس، م. مفتی، ر. شکرفروش، س. Henry, C. روش جدید تجزیه فضایی برای پیش بینی تراکم دقیق و مستقل از مش در جریان های مملو از ذرات. Appl. ریاضی. مدل. 2021 ، 90 ، 582-614. [ Google Scholar ] [ CrossRef ]
کورمود، جی. پروکوپیوک، سی. سریواستاوا، دی. شن، ای. Yu, T. تفکیک خصوصی فضایی. در مجموعه مقالات بیست و هشتمین کنفرانس بین المللی مهندسی داده IEEE در سال 2012، آرلینگتون، ویرجینیا، ایالات متحده آمریکا، 1 تا 5 آوریل 2012. ص 20-31. [ Google Scholar ]
وو، ی. لو، کیو. کای، جی. Wang, X. الگوریتم انتشار پارتیشن بندی داده های دو بعدی حریم خصوصی دیفرانسیل بر اساس درخت چهارگانه. J. Huazhong Univ. علمی تکنولوژی (Nat. Sci. Ed.) 2016 ، 44 ، 99-104. [ Google Scholar ]
یانگ، م. زو، تی. شیانگ، ی. ژو، دبلیو. حفظ مکان مبتنی بر تراکم برای سنجش جمعیت موبایل با حریم خصوصی متفاوت. دسترسی IEEE 2018 ، 6 ، 14779–14789. [ Google Scholar ] [ CrossRef ]
یان، ی. گائو، ایکس. محمود، ع. فنگ، تی. Xie، P. تجزیه فضایی خصوصی دیفرانسیل و انتشار مکان بر اساس الگوریتم پارتیشن چهاردرخت نامتعادل. دسترسی IEEE 2020 ، 8 ، 104775–104787. [ Google Scholar ] [ CrossRef ]
هوانگ، اس. چن، تی. لو، کیو. وو، ی. بله، S. الگوریتم انتشار پارتیشن بندی مجموعه داده دو بعدی حریم خصوصی متفاوت بر اساس kd-tree. J. شاندونگ دانشگاه. (Eng. Sci.) 2015 ، 45 ، 24-29. [ Google Scholar ]
یان، ی. هائو، ایکس. Zhang, L. الگوریتم تجزیه ترکیبی حریم خصوصی تفاضلی سلسله مراتبی برای داده های بزرگ مکان. خوشه. محاسبه کنید. 2019 ، 22 ، 9269–9280. [ Google Scholar ] [ CrossRef ]
اوحدی، ن. کمندی، ع. شعبانخواه، م. فاطمی، س.م. حسینی، س.م. محمودی، ع. Sw-dbscan: یک الگوریتم dbscan مبتنی بر شبکه برای مجموعه داده های بزرگ. در مجموعه مقالات ششمین کنفرانس بین المللی تحقیقات وب 2020، تهران، ایران، 22 تا 23 آوریل 2020؛ صص 139-145. [ Google Scholar ]
Suo، ML; ژو، دی. An، RM; خوشه بندی شبکه چگالی Li، SL و کاربردهای آن. J. Tsinghua Univ. (Sci. Technol.) 2018 ، 58 ، 732-739. [ Google Scholar ]
وو، بی. Wilamowski، BM یک روش خوشه‌بندی مبتنی بر شبکه و چگالی سریع برای داده‌ها با اشکال و نویز دلخواه. IEEE Trans. Ind. اطلاع رسانی. 2017 ، 13 ، 1620-1628. [ Google Scholar ] [ CrossRef ]
خو، اچ. یائو، اس. لی، کیو. بله، Z. یک الگوریتم خوشه بندی k-means بهبودیافته. در مجموعه مقالات پنجمین سمپوزیوم بین المللی IEEE 2020 در مورد سیستم های هوشمند و بی سیم در کنفرانس های جمع آوری داده های هوشمند و سیستم های محاسباتی پیشرفته (IDAACS-SWS)، دورتموند، آلمان، 17 تا 18 سپتامبر 2020؛ صص 1-5. [ Google Scholar ]
زو، س. تانگ، ایکس. Liu, Z. اصلاح الگوریتم خوشه‌بندی dbscan بر اساس شبکه دوگانه. علاوه بر این، در مجموعه مقالات کنترل چینی 2020، کنفرانس تصمیم گیری (CCDC)، هفی، چین، 22 تا 24 اوت 2020؛ صص 3461–3466. [ Google Scholar ]
یو، ی. جیا، ز. کائو، ال. ژائو، جی دی. لیو، ZW; Liu, JL الگوریتم خوشه‌بندی مبتنی بر چگالی سریع برای داده‌های بزرگ مکان. جی. سافتو. 2018 ، 29 ، 2470-2484. [ Google Scholar ]
طارق، م. ساندارراجان، EA; محد، م. Sani، NS خوشه‌بندی آنلاین جریان‌های داده در حال تکامل با استفاده از روش مبتنی بر شبکه چگالی. دسترسی IEEE 2020 ، 8 ، 166472–166490. [ Google Scholar ] [ CrossRef ]
هو، YS; الگوریتم خوشه‌بندی سلولی Lu، YH بر اساس MapReduce و Strongly Connected Fusion. محاسبه کنید. علمی 2019 ، 46 ، 204–207+215. [ Google Scholar ]
Dwork، C. حریم خصوصی دیفرانسیل. در مجموعه مقالات سی و سومین کنفرانس بین المللی اتوماتا، ونیز، ایتالیا، 10 تا 14 ژوئیه 2006; صص 1-12. [ Google Scholar ]
Dwork، C. حریم خصوصی متفاوت: بررسی نتایج. در مجموعه مقالات کنفرانس بین المللی نظریه و کاربردهای مدل های محاسبات، شیان، چین، 25-29 آوریل 2008. صص 1-19. [ Google Scholar ]
Dwork، C. کالیبره کردن نویز به حساسیت در تجزیه و تحلیل داده های خصوصی. لکت. یادداشت ها محاسبه. علمی 2012 ، 3876 ، 265-284. [ Google Scholar ]
دیورک، سی. راث، الف. مبانی الگوریتمی حریم خصوصی دیفرانسیل. پیدا شد. نظریه روندها. محاسبه کنید. علمی 2014 ، 9 ، 211-407. [ Google Scholar ] [ CrossRef ]
Losada-Rojas، LL; Gkritza، K. ویژگی های فردی و مبتنی بر مکان مرتبط با پذیرش خودروی خودمختار در منطقه شهری شیکاگو: پیامدها برای سلامت عمومی. J. Transp. Health 2021 , 22 , 101232. [ Google Scholar ] [ CrossRef ]
هارا، ی. یاماگوچی، اچ. روندها و تغییر رفتار سفر ژاپنی تحت اعلام وضعیت اضطراری COVID-19: مشاهده در سراسر کشور توسط داده های مکان تلفن همراه. ترانسپ Res. بین رشته ای. چشم انداز 2021 ، 9 ، 100288. [ Google Scholar ] [ CrossRef ]

شکل 1. توزیع فضایی COVID-19.

شکل 2. توزیع نرمال با استفاده از RAPPOR.

شکل 3. رابطه توزیع داده های پراکنده و ساختار پارتیشن. ( الف ) مثالی از توزیع پراکنده؛ ( ب ) پرس و جوی پارتیشن و محدوده مربوطه.

شکل 4. رابطه توزیع یکنواخت داده و ساختار پارتیشن. ( الف ) نمونه ای از توزیع یکنواخت؛ ( ب ) پرس و جوی پارتیشن و محدوده مربوطه.

شکل 5. رابطه توزیع غیر یکنواخت داده و ساختار پارتیشن. ( الف ) نمونه ای از توزیع غیر یکنواخت؛ ( ب ) پرس و جوی پارتیشن و محدوده مربوطه.

شکل 6. شبکه های همسایگی.

شکل 7. فرآیند تجزیه DWT.

شکل 8. فرآیند پارتیشن شبکه و خوشه بندی مجموعه داده های ذخیره سازی. ( الف ) پارتیشن شبکه. ( ب ) ماتریس چگالی. ( ج ) ماتریس ضریب بعد از DWT. ( د ) نتیجه خوشه بندی شبکه ای.

شکل 9. تصویری از نتیجه خوشه بندی شبکه و ساختار نمایه سازی فضایی. ( الف ) نتیجه خوشه‌بندی شبکه‌ای فرضی؛ ( ب ) ساختار نمایه سازی فضایی متناظر.

شکل 10. سه مورد استفاده از محدوده پرس و جو Q. ( الف ) مورد استفاده (1); ( ب ) مورد استفاده (2)؛ ( ج ) مورد استفاده (3); ( د ) مورد استفاده (4).

شکل 11. مقایسه دقت پرس و جو در مجموعه داده Storage. ( الف ) مجموعه داده های ذخیره سازی،

ϵ = 0.01

; ( ب ) مجموعه داده های ذخیره سازی،

ϵ = 0.1

; ( ج ) مجموعه داده های ذخیره سازی،

ϵ = 1

شکل 12. مقایسه دقت پرس و جو در مجموعه داده Landmark. ( الف ) مجموعه داده شاخص،

ϵ = 0.01

; ( ب ) مجموعه داده شاخص،

ϵ = 0.1

; ( ج ) مجموعه داده شاخص،

ϵ = 1

شکل 13. مقایسه دقت پرس و جو در مجموعه داده Checkin. ( الف ) مجموعه داده اعلام حضور،

ϵ = 0.01

; ( ب ) مجموعه داده اعلام حضور،

ϵ = 0.1

; ( ج ) مجموعه داده اعلام حضور،

ϵ = 1

شکل 14. مقایسه دقت پرس و جو در مجموعه داده Yellow_trip. ( الف ) مجموعه داده Yellow_trip،

ϵ = 0.01

; ( ب ) مجموعه داده Yellow_trip،

ϵ = 0.1

; ( ج ) مجموعه داده Yellow_trip،

ϵ = 1

شکل 15. مقایسه بازده عملیاتی الگوریتم های مختلف تحت مجموعه داده های مختلف. ( الف ) مجموعه داده های ذخیره سازی،

ϵ = 1

; ( ب ) مجموعه داده شاخص،

ϵ = 1

; ( ج ) مجموعه داده اعلام حضور،

ϵ = 1

; ( د ) مجموعه داده Yellow_trip،

ϵ = 1

شکل 16. دانه بندی پارتیشن در مقابل خطای متوسط. ( الف ) مجموعه داده های ذخیره سازی،

ϵ = 1

; ( ب ) مجموعه داده شاخص،

ϵ = 1

; ( ج ) مجموعه داده اعلام حضور،

ϵ = 1

; ( د ) مجموعه داده Yellow_trip،

ϵ = 1

شکل 17. دانه بندی پارتیشن در مقابل زمان اجرا. ( الف ) مجموعه داده های ذخیره سازی،

ϵ = 1

; ( ب ) مجموعه داده شاخص،

ϵ = 1

; ( ج ) مجموعه داده اعلام حضور،

ϵ = 1

; ( د ) مجموعه داده Yellow_trip،

ϵ = 1

مقالات داخلی و بین المللی

8 نظرات

دیدگاهتان را بنویسید لغو پاسخ

برای نوشتن دیدگاه باید وارد بشوید.

مشاورین هوش پیروزی

کلید واژه ها:

1. مقدمه

2. کارهای مرتبط

3. حریم خصوصی دیفرانسیل

4. الگوریتم خوشه بندی شبکه ای برای اطلاعات آماری کلان داده مبتنی بر مکان

4.1. مشکلات تجزیه فضایی حریم خصوصی سنتی

4.2. روش پیشنهادی

5. انتشار آماری و الگوریتم حفاظت از حریم خصوصی

6. آزمایش ها و تجزیه و تحلیل

6.1. تجزیه و تحلیل در دسترس بودن نتایج آماری کلان داده مبتنی بر مکان منتشر شده

6.2. تحلیل کارایی الگوریتم انتشار حفاظت از حریم خصوصی

6.3. تأثیرات دانه بندی پارتیشن

7. نتیجه گیری

منابع

قبلیپورتال چند منظوره GIS برای مدیریت، تحقیق و آموزش جنگل

بعدیاستخراج دقیق اجسام زمینی از تصویر سنجش از دور بر اساس فرآیند نقطه خوشه بندی علامت گذاری

مطالب مرتبط ...

آموزش مقاله نویسی در رشته ادبیات فارسی

تأثیر همسایگی درونیابی DEM بر عوامل زمین

رگرسیون وزنی جغرافیایی تطبیقی غیر منفی برای تخمین تراکم جمعیت بر اساس نور شب

8 نظرات

دیدگاهتان را بنویسید لغو پاسخ

درباره سرزمین فناوری مکانی GISLAND

دسترسی سریع

اطلاعات

خبرنامه

خبرنامه

درباره سرزمین فناوری مکانی GISLAND

دسترسی سریع

اطلاعات

دسترسی سریع

مشاورین هوش پیروزی

دستیابی به انتشار حریم خصوصی متفاوت داده های آماری مبتنی بر مکان با استفاده از خوشه بندی شبکه

کلید واژه ها:

1. مقدمه

2. کارهای مرتبط

3. حریم خصوصی دیفرانسیل

4. الگوریتم خوشه بندی شبکه ای برای اطلاعات آماری کلان داده مبتنی بر مکان

4.1. مشکلات تجزیه فضایی حریم خصوصی سنتی

4.2. روش پیشنهادی

5. انتشار آماری و الگوریتم حفاظت از حریم خصوصی

6. آزمایش ها و تجزیه و تحلیل

6.1. تجزیه و تحلیل در دسترس بودن نتایج آماری کلان داده مبتنی بر مکان منتشر شده

6.2. تحلیل کارایی الگوریتم انتشار حفاظت از حریم خصوصی

6.3. تأثیرات دانه بندی پارتیشن

7. نتیجه گیری

منابع

قبلیپورتال چند منظوره GIS برای مدیریت، تحقیق و آموزش جنگل

بعدیاستخراج دقیق اجسام زمینی از تصویر سنجش از دور بر اساس فرآیند نقطه خوشه بندی علامت گذاری

مطالب مرتبط ...

آموزش مقاله نویسی در رشته ادبیات فارسی

تأثیر همسایگی درونیابی DEM بر عوامل زمین

رگرسیون وزنی جغرافیایی تطبیقی ​​غیر منفی برای تخمین تراکم جمعیت بر اساس نور شب

8 نظرات

دیدگاهتان را بنویسید لغو پاسخ

درباره سرزمین فناوری مکانی GISLAND

دسترسی سریع

اطلاعات

خبرنامه

خبرنامه

درباره سرزمین فناوری مکانی GISLAND

دسترسی سریع

اطلاعات

دسترسی سریع

رگرسیون وزنی جغرافیایی تطبیقی غیر منفی برای تخمین تراکم جمعیت بر اساس نور شب