بخشی از مقاله
چکیده
با توجه به افزایش روزافزون حجم اطلاعات وگذر از اقتصاد سنتی و از میان رفتن مرزهای جغرافیایی برای کسب و کار و به تبع آن شدت یافتن رقابت، منجر به یافتن راه حلهای جدید به منظور افزایش رضایتمندی مشتریان شده است. در این مقاله تلاش میشود که براساس جریان کلیکهای مشتریان، این امر محقق گردد.حجم بسیار زیادی از اطلاعات در حیطه خدمات الکترونیک از طریق تجزیه و تحلیل کلیکها بدست میآید.
جریان کلیکها به معنای ذخیره کردن رفتار کاربران در هنگام استفاده از وبسایت است و شامل مواردی همچون محصولات خریداری شده، تاریخ و زمان، زمان سپری شده در صفحات و... میباشد. هر کاربری که از سایت بازدید میکند، ترجیهات و تمایلات به خصوصی دارد. کاربران با علاقهمندیهای مشابه، رفتارهای مروری مشابهای را به نمایش می گذارند.
از این رو در این مقاله تلاش میشود تا الگوریتم جدیدی از خوشه بندی ارائه گردد که به کمک آن بتوان کاربران با علاقه مندیهای مشابه در فضای دادههای بزرگ شناسایی گردند. با بررسی مجموعه دادهها و انجام عملیات پیش پردازش روی دادههای خام از توالی صفحات وب و تجمیع کل دادهها، آرایهای استخراج میشود سپس الگوریتم خوشه بندی ارائه شده با معیار شباهت جدید برروی آن اعمال میگردد و بهبود کیفیت آن نسبت به مدلهای دیگر خوشه بندی مانند کامینز و کامدویدز بررسی میگردد، همچنین سرعت این الگوریتم در قالب مپ ردیوس نسبت به حالت عادی آن، نیز ارزیابی میشود.
-1 مقدمه
امروزه، پراکندگی پایگاههای داده و عدم تحلیل مناسب دادهها، تصمیم گیری بهینه در خصوص مشتریان را با مشکل مواجه کرده است. سازمانهایی که علاقه مند به بهبود کیفیت تصمیم گیری و ارائه خدمات با کیفیت بهتر به مشتریان خود هستند، باید به سوی توسعه مدل هایی جهت دسته بندی مشتریان و شناسائی مشتریان هدف حرکت نمایند، زیرا از این طریق می توانند از رویکردی واقع گرایانه برای عملیاتهای کسب و کار، مشتریان، تامین کنندگان و غیره سود ببرند.
امروزه سازمان-ها در تلاشند تا مشتریان را به صورت فردی درک نمایند و از این شناخت برای تسهیل تجارت خود استفاده کنند. از این رو با استفاده از تجزیه و تحلیل کلیک های کاربران و خوشه بندی کردن آنها میتوان کاربران با رفتار های مشابه را مشخص نمود و با پیش بینی علاقه مندی مشتریان، رضایتمندی آنها را فراهم ساخت .
ایده clickstreams این است که محققان میتوانند اطلاعات زیادی در مورد فعالیت های کاربران از جمله تاریخ، زمان، شناسه کاربر، مرورگر استفاده شده توسط کاربر ، زمان سپری شده در صفحات، کشور و... فراهم کنند. این نوع از اطلاعات یک دنباله تصویری از رفتار کاربران با بازخورد دقیق فراهم میکند و با تحلیل اطلاعات استخراج شده میتوان کمک شایانی در افزایش خدمات الکترونیک فراهم نمود. هدف ما از مقاله ارائه الگوریتمی با معیار تشابه جدید میباشد که به واسطه آن مشتریان با رفتار یا علاقهمندیهای مشترک در مجموعه داده موجود، بهتر از معیارهای قبلی خوشه بندی گردند و سرعت آن در قالب mapreduce نسبت به حالت عادی افزایش یابد.
-2 پیشینه تحقیق
در مقاله[1] سعی شده است مدل جدیدی برای دسته بندی داده های کلیک استریم ارائه گردد که سه فاز پردازش داده بر روی آن اعمال می شود و صحت آن توسط آزمونهایی تصدیق میگردد. اجزای آنلاین، داده های خلاصه شده را به جای استفاده از یک سیستم ذخیره، در حافظه موقت ذخیره میکنند. به علاوه این اجزا میکروکلاسترها را تولید نمی-کنند اما یک ماتریس با اندازه ثابت جهت قطعی نمودن دادههای وبلاگ تولید مینمایند. اجزای آفلاین میتوانند شامل الگوریتمهای دسته بندی متفاوتی باشند که به صورت موازی کار میکنند و به طور مستقل شامل گروههای متنوعی از کلاسترها با ویژگیهای مشخصی میباشند. در این روش آزمایشی ابتدا خوشه بندی اعمال شد و بعد از آن عملیات پیش پردازش و سپس فرآیند متاکلاسترینگ صورت گرفت.
ایده اصلی تقسیم پروسه کلاسترینگ در سه فاز جداگانه می باشد: - الف - یک جز آنلاین که به صورت اتوماتیک دادههای دنباله دار را به روش فشرده در حافظه ذخیره میکند. - ب - یک مجموعه از اجزای آفلاین که به کمک این دادههای فشرده شده کلاسترها را تولید می کنند. - ج - یک فرایند متاکلاسترینگ که کلاسترهایی با ویژگی دسته بندی بلند مدت تولید مینمایند. جریان های ورودی که در مدل ما بکار برده میشوند، کلیک استریم های وب از وب سرور یک سایت پشتیبان میباشد.
در مقاله [2] ابتدا سعی شده است وابستگی بین تعداد زیادی از دامنه ها که بوسیله دادههای جریان کلیکها اندازه گیری شده، نمایش داده شود. در مرحله بعد فضای دادههای جمع آوری شده در وب مورد تجزیه و تحلیل قرار گرفت و در انتها طراحان وب به درک عمیق تری از توپوگرافی و اینکه مرورگران به چه چیزهایی علاقه مندی بیشتر دارند، دست یافتند.
در [3] به اهمیت ساختار سیستم مپ ردیوس و هدوپ در تجزیه و تحلیل دادههای بزرگ اشاره شده و از موفقیتهای بدست آمده برای سرویس دهندگان وب و سایتهای اجتماعی گغته شده و اهمیت عملیات روزانه جریان کلیکها در فضای وب را نشان داده است.
در [4] به سه مولفه مغناطیسی، چابکی و عمق تجزیه و تحلیل داده به عنوان اصول ورود به دنیای هوش کسب و کار و دادههای بزرگ پرداخته شده است. ابتدا متادولوژیهای طراحی پایگاه داده که با سرعت تجزیه و تحلیل این تنظیمات را پشتیبانی میکنند مورد تشریح قرار گرفت و در مرحله بعدی الگوریتمهای موازی روشهای آماری پیچیده بیان گردید و در نهایت تنوع مکانیسمهای حافظه که از اس کیو ال و مپ ردیوس استفاده میکنند بیان گردید.
در [5] سعی شده است دادههای بزرگ جمع آوری گردد و جهت فازهای مدیریت و نظارت، واکاوی گردند. با توجه به پروفایل قبلی کاربر که چه رفتاری در وب داشته و از کجاها بیشتر بازدید نموده است، اطلاعات مرتبط با پیشنه کاربر نمایش داده میشود.
سیستم رفتار کاربر را رصد میکند و برای هر کاربر پروفایل جداگانه ای تشکیل میدهد. به عنوان مثال پروفایل میتواند شامل صفحات مرور شده کاربر و جستجوی کلمات خاص در یک محدوده زمانی باشد که این پروفایل همراه با فعالیت کلیک یا کلیک نکردنهای کاربر میباشد. در این روش دادههای متنوعی در محدوده زمانی به خصوصی، تولید گشت که اطلاعات پروفایل و کلیکهای هرکاربر به صورت جداگانه ذخیره شد.
تمرکز مقاله [6] بر سبکهای شناختی مدل سازی کاربر بر پایه تکنیکهای وب کاور کاربرد بر الگوهای شناختی کاربر و دادههای جریان کلیک میباشد. هدف اصلی رسیدگی به چگونگی تکنیکهای ویژه خوشه بندی گروههای کاربران بر اساس تستهای روان شناختی و رفتارهای مرور مفهوم محور میباشد. افزایش فهم ما نسبت به رفتار مرور کاربران نسبت روشهای شناختی آنان به وسیله مطالعه فعل و انفعالات در محیطهای وب با استفاده از تکنیکهای خوشه بندی ویژه از دیگر اهداف مهم این مقاله می باشد.
-3 خوشه بندی
داده و الگو یکی از شاخصهای بسیار مهم در دنیای اطلاعات هستند. خوشه بندی، یکی از بهترین روشهایی است که برای کار با دادهها ارائه شده است. قابلیت آن در ورود به فضای داده و تشخیص ساختار آنها، خوشه بندی را یکی از ایده ال ترین مکانیزمها برای کار با دنیای عظیم دادهها کرده است. هر خوشه توسط خصوصیات مشترک موجودیتهایی که درون آن قرار میگیرند تعریف میشود.
خوشه، یک مجموعه از دادهها با شرایط زیر می باشد :
· دادههای موجود در یک خوشه شبیه یکدیگر هستند.
· دادههای موجود در خوشههای مختلف به یکدیگر شبیه نیستند.
-1-3 معرفی الگوریتم های خوشه بندی
خوشه بندی :K-Means در این روش ابتدا به تعداد خوشههای مورد نیاز نقاطی به صورت تصادفی انتخاب میشود. سپس در دادهها با توجه با میزان نزدیکی - شباهت - به یکی از این خوشهها نسبت داده میشوند
و بدین ترتیب خوشههای جدیدی حاصل میشود. با تکرار همین روال میتوان در هر تکرار با میانگینگیری از دادهها مراکز جدیدی برای آنها محاسبه کرد و مجدادأ دادهها را به خوشههای جدید نسبت داد. این روند تا زمانی ادامه پیدا میکند که دیگر تغییری در دادهها حاصل نشود.
خوشه بندی :K-Medoids در این الگوریتم برخی از اشیاء داده به عنوان مرکز خوشه در نظر گرفته میشود که به آنها medoids می-گویند. پس این الگوریتم مشابه k-means با k عدد medoids شروع میشود. و در هر مرحله در صورتی که مجموع فاصلهها درون خوشه بهبود یابد، یک شی داده medoids با یک شی داده non-medoids تعویض میشود.
خوشه بندی فازی: ایده بنیادین در خوشه بندی فازی به این ترتیب است که فرض کنیم هر خوشه مجموعه ای از عناصر است . سپس با تغییر در تعریف عضویت عناصر در این مجموعه از حالتی که یک عنصر فقط بتواند عضو یک خوشه باشد، به حالتی که هر عنصر میتواند با درجه عضویتهای مختلف داخل چندین خوشه قرار بگیرد، دسته بندی هایی که انطباق بیشتری با واقعیت دارند ارائه کنیم.
خوشهبندی سلسله مراتبی و خوشهبندی مسطح: در روش خوشه بندی سلسله مراتبی، به خوشههای نهایی بر اساس میزان عمومیت آنها ساختاری سلسله مراتبی نسبت داده میشود. ولی در خوشهبندی مسطح تمامی خوشههای نهایی دارای یک میزان عمومیت هستند به ساختار سلسله مراتبی حاصل از روشهای خوشهبندی سلسله مراتبی دندوگرام گفته میشود.
-4 شاخصهای علاقه مندی کاربران
ترتیب بازدید، فرکانس بازدیدها و مدت زمان سپری شده در هر صفحه محصول به عنوان سه جز اصلی اندازه گیری علاقه مندی کاربر به کار گرفته میشود که بسته به توانایی وبسایتها در ذخیره کلیک استریمها میتواند این شاخص ها کمتر و یا بیشتر گردند.
-5 جمع آوری و پاکسازی دادهها
مجموعه داده مورداستفاده در این مقاله، مجموعه استاندارد مسابقات KDD CUP 2000 میباشد.[7] که شامل 59601 دنباله کلیک استریم و بسایت تجاری میباشد و دارای 497 عضو متمایز است. طول میانگین دنباله ها 2,42 جز با یک انحراف استاندارد از 3,22 میباشد. در این مجموعه داده دنباله هایی با طول بسیار زیادی نیز وجود دارد، به عنوان مثال 318 دنباله بیش از 20 عضو دارند. نمونه مجموعه دادهها در جدول - 1 - نمایش داده شده است.
جدول - 1 - توالی صفحات وب از داده های KDD2000
مجموعه دادههای موجود دارای تعداد زیادی توالیهای کلیک در صفحات وب میباشد. هر صفحهی وب با یک id نشان داده شده است که برای آن صفحه منحصر به فرد میباشد. پس در هر سطر تعدادی id در ادامهی هم آمده اند که -1 نشان دهندهی اتمام کار صفحهی کلیک شده است. در پایان هر توالی -2 آمده است که نشانهی بستن browser و اتمام کار است.
با توجه به حجم بالای دادهها و نمونههای موجود از صفحات وب، خواندن همه ی این دادهها در یک مرحله امکان پذیر نیست. از این رو، در الگوریتم پیشنهادی جدید، با استفاده از تکنولوژی hadoop و بهره گیری از الگوریتم MapReduce دادهها به صورت تکه تکه خوانده شده و وارد حافظه میشوند. MapReduce یک مدل برنامه نویسی پردازش داده میباشد و برنامههای نوشته شده تحت MapReduceذاتاً بصورت موازی طراحی و پیاده سازی میشوند.
زبان انتخاب شده جهت نوشتن برنامه در این مقاله Matlab 2014b میباشد. الگوریتم MapReduce از دو فاز map و reduce بهره میگیرد که در فاز map به صورت موازی پردازش بر روی هر تکه انجام میشود و نتایج میانی ذخیره میگردند. در فاز reduce نتایج میانی به دست آمده از فازهای map با هم ادغام میشوند و نتایج نهایی حاصل میگردد. در واقع برنامه در دو تابع نگاشت - - map و کاهش - reduce - نوشته میشود که هر کدام از آنها نگاشتی از یک مجموعه "Key & Value" ایجاد میکند.
این توابع مستقل از حجم داده و یا محدوده کلاستر پردازش کننده، نوشته میشوند. بنابراین بدون هیچ گونه تغییری میتوانند با هر میزان داده - کم و یا زیاد - به اجرا درآیند. مهمتر آنکه، اگر حجم داده ورودی را دو برابر کنیم، منطقی است که سرعت پردازش دو برابر افزایش یابد. اما اگر در کنار آن اندازه کلاستر را هم دو برابر کنیم، سرعت پردازش مثل حالت اول خواهد شد.
در این حالت ابتدا دادهها به عنوان ورودی به چندین قطعه معین تقسیم میشود سپس هر یک از قطعه ها به صورت کاملا مستقل مورد پردازش قرار میگیرند. بنابراین به ازای هر قطعه یک نتیجه وجود خواهد
