بخشی از مقاله
چکیده
- با توجه به افزایش منابع تولید دادههای جریانی، حجم انبوهی از اطلاعات، روزانه تولید میشود که نگهداری این اطلاعات در عمل ممکن نیست. استخراج مدل از میان این اطلاعات خام، برای رسیدن به دانشی مفید، امری ضروری محسوب میشود. هدف ما در این تحقیق، ارائه روشی جدید برای خوشهبندی دادههای جریانی، به نام DSCBF، با توجه به مشکل عدمقطعیت موجود در دادهها است. در روش پیشنهادی، برای حل مشکل عدمقطعیت و ابهام در دادهها، از تابع باور استفاده شده است. تابع باور، به منظور خوشهبندی دادهها در خوشههای تکی و یا مجموعهای از خوشهها و تعیین ساختار دادهها، مورد استفاده قرار میگیرد. علاوه بر آن، استفاده از روش پنجره لغزان و وزندهی به مراکز با در نظر گرفتن زمان، موجب غلبه بر ویژگیهای خاص دادههای جریانی میشود. نتایج آزمایشها روی مجموعه دادههای واقعی، نشاندهنده برتری روش پیشنهادی، از نظر نرخ خطا، نرخ ابهام و خلوص، نسبت به سایر روشهای مطرح مرز دانش است.
کلید واژه- خوشهبندی، دادههای جریانی، تابع باور.
-1 مقدمه
در دهه اخیر، با رشد روزافزون دادهها و همچنین نیاز سازمانها به کسب اطلاعات ارزشمند از دادههای خام، دادهکاوی بهعنوان روشی مهم و پرکاربرد، برای استخراج مدل و اطلاعات مفید از دادهها، مطرح شده است.یکی از پرکاربردترین روشهای دادهکاوی، خوشهبندی است. فرآیند گروهبندی مجموعهای از دادهها و قرار دادن آنها در گروههایی متفاوت از نمونههای مشابه، خوشهبندی نامیده میشود .[1] از ایده خوشهبندی در زمینه کاهش دادهها نیز استفاده شده است .[2]در سالهای اخیر، پیشرفت تکنولوژی باعث ضبط روزانه دادهها با سرعت بالا شده است. این فرآیند مقدار زیادی اطلاعات برخط تولید میکند که این اطلاعات با نرخ بالا رشد میکنند. به این نوع از دادهها که طی زمان نیز تغییر میکنند، دادههای جریانی گفته میشود.
ذخیرهسازی کامل و دسترسی به دادهها، فرآیندی پرهزینه به لحاظ حافظه و زمان است. لذا باید الگوریتمهای جدیدی برای مقابله با این نوع از دادهها توسعه یابند .[1]عدمقطعیت در دادهها یکی از مسائل مهم در تصمیمگیری است که باید مورد بررسی قرار گیرد. مسئله فوق به دو گروه تصادفی - - Aleatory و ذهنی - - Epistemic تقسیم میشود.عدمقطعیت تصادفی مربوط به تصادفی بودن مشاهدات در طبیعت و عدمقطعیت ذهنی مربوط به وضعیت دانش سیستم وتوانایی در مدلسازی است. بررسی و حل مشکل عدمقطعیت ذهنی، باعث بهدست آوردن تفسیر دقیقتری از دادهها میشود.[3]در این مقاله، الگوریتمی جدید برای خوشهبندی دادههایجریانی، به نام DSCBF، - Data Stream Clustering usingBelief Function - ارائه شده است.
هدف از ارائه این الگوریتم، مقابله با سه مشکل عدمقطعیت ذهنی، حافظه کم و تغییر طی زمان است. برای حل مشکل عدمقطعیت ذهنی، زمانی که دادهها نزدیک به مجموعهای از خوشهها است، از تابع باور استفاده شده است. برای حل مشکل حافظه برای دادههای جریانی، از روش خوشهبندی تکگذر با پنجره لغزان استفاده شده است. برای حل مشکل تغییر طی زمان نیز تابع محو مورد استفاده قرار گرفته است. درنهایت، در این الگوریتم روشی متفاوت برای محاسبه فاصله دادهها تا خوشههای جمعی نیز استفاده شده است.ساختار ادامه مقاله به شرح زیر است: در بخش دوم کارهای مرتبط مورد بررسی قرار گرفته است. بخش سوم شامل معرفی تابع باور است. در بخش چهارم روش پیشنهادی بیان شده است. بخش پنجم شامل آزمایشها و مقایسه روش پیشنهادی با سایر روشهای خوشهبندی است. درنهایت، بخش آخر شامل نتیجهگیری و کارهای آینده است.
-2 مروری بر کارهای پیشین
در سال 2008، برای بررسی عدمقطعیت ذهنی، الگوریتم[4]ECM معرفی شد. این الگوریتم علاوه بر بررسی عضویت هر داده در هر خوشه، عضویت آن را در مجموعههایی از خوشهها نیز بررسی مینماید. در سال 2012، الگوریتم [5]CECM، بهعنوان نسخهای دیگر از الگوریتم ECM، با در نظر گرفتن اطلاعات پیشین در مورد عضویت در خوشهها و فاصله ماهالانوبیس ارائه شد. یکی از نقاط ضعف این الگوریتمها عدم پشتیبانی از خوشهبندی دادههای جریانی است.روشهای بسیاری برای خوشهبندی دادههای جریانی ارائه شده است. الگوریتم [6]strWFCM، الگوریتمی برخط برای خوشهبندی فازی دادهها است. در این الگوریتم، پس از بررسی عضویت دادهها، درصورت عدم اختصاص آن به خوشهها، از یک حافظه موقتی برای ذخیره استفاده میشود و درنهایت، روی این حافظه خوشهبندی اعمال میشود.
الگوریتم [7]HSDC، از روش سلسله مراتبی، برای خوشهبندی دادههای جریانی با ابعاد بالا استفاده میکند. این الگوریتم توانایی تشخیص خوشهها با شکل دلخواه را نیز دارا است. الگوریتم [8]MuDi Stream، شامل دو مرحله برخط و برونخط است. در مرحله برخط، خوشههای اولیه ایجاد میشود و در مرحله برونخط، الگوریتم M-DBSCAN اعمال میشود. الگوریتم [9]ADStream نیز شامل دو مرحله برخط و برونخط برای خوشهبندی با استفاده از مفهوم تراکم است . این الگوریتم توانایی مقابله با دادههای جریانی در حال تغییر را نیز دارا است. در الگوریتم مبتنی بر شبکه [10]SCRP، زمانی که دادههای جریانی تغییر کرد، با ذخیره ساختار آن در یک درخت، اطلاعات آماری بهروزرسانی میشود. این الگوریتم دادههای پرت و تغییر طی زمان را نیز مورد بررسی قرار داده است. در این الگوریتمها عدمقطعیت موجود در دادهها در نظر گرفته نمیشود.
در زمینه عدمقطعیت دادههای جریانی، درسال 2012، الگوریتم [11]E2GK، بهعنوان بهبودی بر الگوریتم GK، برای دادههای جریانی ارائه شد. در این الگوریتم از تابع باور برای خوشهبندی مجموعه داده Pronostia، مربوط به لرزش و دمای بلبرینگ در طول عمر مفید آن، استفاده شده است. در سال بعد، الگوریتم [12]SPECM، برای خوشهبندی برخط از طریق تقسیم دادهها به قطعات و وزندهی به مراکز آن معرفی شده است. زمان و تغییرات طی آن، که از ویژگیهای مهم دادههای جریانی است، در این دو الگوریتم در نظر گرفته نشده است. در سال 2016، الگوریتم [13]SECM، بهعنوان روشی برای خوشهبندی دادههای جریانی با استفاده از تابع باور ارائه شده است. در این الگوریتم نیز تغییرات طی زمان، مورد بررسی قرار نگرفته است و به دلیل عدم استفاده از وزندهی، نتایج ضعیفتری را دارا است.
-3 معرفی تابع باور
نظریه دمپسترشافر از توابع باور، چارچوبی ریاضی برای نمایش و استدلال با عدمقطعیت و دانش مبهم است. فرض کنید Ω = { 1, … , } یک مجموعه متناهی از عناصر، به نام قاب تشخیص باشد. تابع جرم را با m مشخص میکنند که از نگاشت مجموعه توانی ، به بازه 1]،[0، با محدودیت زیر مشخص میشود:که m - A - >0 باشد، عنصرکانونی نامیده میشود. درصورتیکه تمام جرم، به یک زیرمجموعه تکی اختصاص یابد، به آن تابع جرم قطعی گفته میشود. جهل کامل نیز درصورت برقراری عبارت 1P - - رخ میدهد. دانش جزئی نشان داده شده توسط m، میتواند به صورت
معادل با تابع bel و یا pl نیز نمایش داده شود .[14]
-4 روش پیشنهادی
در این مقاله، یک روش خوشهبندی تکگذر با استفاده از روش پنجره لغزان ارائه شده است. این الگوریتم از دو بخش اصلی تشکیل شده است. بخش اول مربوط به وزندهی به مراکز و خلاصهسازی دادهها است و بخش دوم بهعنوان الگوریتم پایه، چرخه اصلی برای هر پنجره را نشان میدهد.
-1-4 بخش اول
هر مرکز با توجه به درجه عضویت یا همان جرم دادههای آن، یک وزن اولیه - ′ - ، طبق رابطه - 4 - ، دارا است.وزن اولیه دادهها برابر 1 در نظر گرفته شده است. k نشاندهنده تعداد خوشهها و n نشاندهنده تعداد دادهها است.زمان ورود دادهها و تغییر طی زمان باید مورد توجه قرار گیرد. لذا از تابع محو، رابطه - 5 - ، برای اعمال زمان بهعنوان وزن برای مراکز استفاده میشود. در این رابطه، بهعنوان متغیری برای کنترل تأثیر زمان استفاده شده است. وزن نهایی با استفاده از رابطه - 6 - بهدست میآید.که در آن t نشاندهنده زمان و w نشاندهنده وزن نهایی است. مقداردهی اولیه مراکز، در ابتدا، به صورت تصادفی انجام میگردد و در مراحل بعد، مراکز مرحله قبل، بهعنوان مراکز اولیه انتخاب میشوند. با دریافت هر پنجره، وزن هر داده برابر 1 قرار میگیرد. مراکز مرحله قبل به دادهها اضافه شده و وزن محاسبه شده آن نیز اعمال میگردد. این مراحل برای هر پنجره قبل از اعمال بخش دوم الگوریتم انجام میگردد و زمانی که تعداد مراکز ذخیره شده به حد خاصی رسید، خوشهبندی سطح دوم، با در نظر گرفتن مراکز، بهعنوان دادههای اولیه انجام میگردد. شبه کد بخش اول، در الگوریتم - 1 - نشان داده شده است.
-2-4 بخش دوم
برای حل مشکل عدمقطعیت و ابهام در دادهها، از تابع باور استفاده شده است. مجموعه داده = { 1, … , } و قاب تشخیصΩ = { 1, … , } را در نظر بگیرید. V = { 1, … , } مجموعه مراکز این خوشهها و = { 1, … , } مجموعهای از توابع جرم مربوط به دادهها است. به طور کلی، جرم باور هر داده به زیرمجموعههایی از Ω بررسی میشود. به مجموعههای دارای بیشتر از یک خوشه، خوشهجمعی گفته میشود. بهعنوان مثال برای دو خوشه اصلی و 4 داده، مقادیر جدول زیر را داریم:داده اول متعلق به زیرمجموعه ∅ است. در نتیجه بهعنوان داده پرت در نظر گرفته میشود. داده دوم، به طور همزمان با تمام خوشهها فاصله یکسانی دارد، در نتیجه مشخص کردن کلاس آن امکانپذیر نیست. داده سوم، به طور کامل متعلق به خوشه اول است و داده چهارم عضویت نسبی در خوشه اول و دوم دارد.
هر الگوریتم خوشهبندی شامل یک تابع هدف است. هدف اصلی در خوشهبندی، کمینهسازی این تابع است. تابع هدف از درجه عضویت دادهها به مراکز و فاصله آن محاسبه میشود. به دلیل وجود وزن برای هر داده، این وزن نیز در رابطه اعمال میگردد. در این بخش، روشی متفاوت برای محاسبه فاصله دادهها تا خوشههای جمعی ارائه شده است که علاوه بر در نظر گرفتن مرکز خوشهجمعی، مراکز خوشههای درگیر را نیز مورد بررسی قرار میدهد. درنهایت تابع هدف به صورت زیر درمیآید:که در آن β نشاندهنده شاخصی برای میزان تأثیر جرم دادهها است و برابر با کاردینالیتی هر خوشه است. پارامتر δ، آستانه دادههای پرت و پارامتر نیز آستانه برای تعیین تعداد دادههای مربوط به خوشههای جمعی است. برای محاسبه فاصله داده تا مرکز، از رابطه زیر استفاده شده است:
