بخشی از مقاله
چکیده
گرافکاوی یکی از روشهای دادهکاوی است که امروزه به جهت امکان نمایش داده در کاربردهایی نظیر شبکههای اجتماعی، وب، دادههای شیمیایی، ژنوم و حتی کسب و کار و بورس به مبحثی داغ تبدیل شده است. در واقع ایده اصلی موضوع گرافکاوی، استخراج زیر گرافهایی است که به نوعی بیانگر خصوصیات مهم گراف اصلی است؛ لذا در این مقاله پس از بررسی مطالعات اخیر در زمینه گرافکاوی، سیستمی مبتنی بر گراف برای کاوش مشتریان وفادار طراحی شده است.
مبنای کار این سیستم بدین گونه است که ابتدا گراف مشتریان بر اساس دادههای مشتریان سازمان ساخته شود. سپس عمل خوشهبندی مشتریان را با استفاده از مفهوم درخت پوشای مینیمم انجام داده و پس از بدست آمدن خوشهها، خوشهی مشتریان وفادار را شناسایی کند.
-1 مقدمه
بیشک میتوان گفت مهمترین دارایی اغلب سازمانها مشتریان آنها هستند. مشتریان به خاطر ارتباط مستقیمی که با اقدامات یک سازمان دارند، منبع ارزشمندی برای فرصتها، تهدیدات و سؤالات عملیاتی مرتبط با صنعت مربوطه میباشند. در روندهای کسب و کاری جدید، به دست آوردن رضایت مشتریان جایگاهی مهم و حیاتی در اهداف شرکتها به خود اختصاص داده است. از سوی دیگر نمیتوان گفت همه مشتریان به یک اندازه در موفقیت شرکت نقش دارند. بنابراین جلب رضایت مشتریان وفادار، حساسیت بیشتری خواهد داشت. بدین منظور، تعیین معیاری برای کشف مشتریان وفادار، از جمله مسائل اساسی در سیستم مدیریت روابط مشتریان است.
امروزه گرافها به طور گسترده در بسیاری از حوزهها، برای مدلسازی و کار با دادهها استفاده میشوند؛ نرمافزار، شبکه، وب، شیمی، زیست، ژنتیک و حتی مخابرات و جامعهشناسی تنها نمونههایی از این حوزهها میباشند. این استفاده از دادهها سبب شده است که الگوریتمهای گرافکاوی1 به موضوعی داغ تبدیل شود. این الگوریتمها، گرافهای بزرگ را به گرافهای کوچکتر و قابل فهمتری تبدیل میکنند که در عین سادگی، خصوصیات مهم گراف اولیه و نیز اطلاعات مورد نیاز کاربران را در خود دارند.
یادا و همکاران2 درباره چگونگی بهکارگیری سیستم گرافکاوی در مجموعه دادهی تبادلات فروش به منظور درک رفتار مشتری صحبت میکنند .[5] بوگینسکی و همکاران3 به تحلیل آماری توزیع درجه گراف بازار پرداختند و نشان دادند که مدل power-law در شبکههای مالی نیز معتبر است .[6] کاویک و همکاران4، تحلیل سبد بازار را به مسأله یافتن گراف با ماکزیمم وزن تبدیل میکنند.
پیچیدگی زمانی الگوریتم اصلی Apriori به تعداد آیتمها، تعداد تراکنشها و اندازه سبد بازار وابسته است، در حالی که، الگوریتم پیشنهادی Similis تنها به تعداد آیتمها - گرههای گراف - وابسته میباشد .[7] ژانگ5، یک سیستم سلسله مراتبی با ارزیابی شاخص اقتصادی برای شبکههای توزیع پیشنهاد میکند. این سیستم از شاخصهای گوناگون شبکههای توزیع و همبستگی میان آنها برای ایجاد گراف مورد نظر خود بهره میگیرد .[8] لین و همکاران6 از مجموعه راف 7 و گراف جریان شبکه8 برای پیشبینی الگوی رفتاری وفاداری مشتریان در بانک تجاری تایوان استفاده کردند
در بررسی مقالات به این نکته پی بردیم که با توجه کاربرد های تئوری گراف در زمینه های مختلف از این موضوع برای بررسی رفتار مشتریان بسیار کم و صرفاً در حد یک نمایش گرافیکی برای نشان دادن قوانین انجمنی که با استفاده از تکنیکهای دیگر بدست آمدهاند [1]، و یا تحلیل بازار سهام استفاده شده است
اولین گام در پیدا کردن الگوهای کلیدی، ردیابی رفتار مشتریان کلیدی بنگاه است که برای تحقق این موضوع ابتدا نیاز است تا مشتریان را خوشه بندی نموده تا خوشه مشتریان با رفتارهای مشابه شناسایی شود و طبق پارامتری معین تأثیرگذارترین مشتریان هر خوشه را تعیین گردد، پس از شناسایی مشتریان وفادار آن خوشه و الگوی خرید آنها، میتوان از این الگوها در جهت حفظ و نگهداری مشتریانی که رفتاری مشابه مشتریان وفادار دارند، استفاده نمود؛ لذا در این مقاله سعی شد تا از میان تکنیکهای مختلف خوشهبندی مبتنی بر مقالات، مناسبترین روش انتخاب شده و پس از خوشهبندی و انتخاب مشتری وفادار، نتایج را با نتایج الگوریتم DBSCAN مقایسه نموده و صحت متدولوژی خود را اثبات کنیم.
-2 خوشهبندی
اخراًی توجهات بر روی روشهای خوشهبندی مبتنی بر گراف بیشتر شدهاند. بر اساس اینکه نمایش گراف دادهها، امکان درک مستقیم و مؤثر را فراهم میسازد، لذا گرافها در بسیاری از روشهای خوشهبندی مورد استفاده قرار گرفتهاند. وظیفه اصلی این روشها شامل ساخت یک گراف مناسب و بخشبندی مؤثر این گراف است. بیشتر روشهای خوشهبندی گرافی، گراف اولیه را به وسیله روش KNN میسازند.
کریپس1 و همکارانش در CHAMELEON یک مجموعه داده را با گراف نزدیکترین همسایگی نشان میدهند و از اتصال داخلی نسبی و نزدیکی نسبی برای بخشبندی گراف استفاده نموده و نهاتاًی بخشها را ادغام میکنند؛ لذا میتوانند خوشههای متصل و شکلیافتهی اختیاری را تشخیص دهد . اما فرانتای2 و همکارانش نمایش گراف خود را اینگونه تعریف کردهاند، که هر رأس نمایانگر یک خوشه باشد تا فرآیند خوشهبندی نسبی را سرعت بخشند
ژائودی هؤانگ و همکارانش3 از ماتریس شباهت میان گرههای رئوس را، بر اساس معیار جدیدی از شباهت استفاده میکنند. از مزایای این روش میتوان به عدم نیاز به لایهی اولیه گراف، تخمین تعداد خوشهها بر اساس توزیع درجه گرهها و ارائهی معیاری استاندارد برای شباهت میان گرهها نام برد .[12] تامینللو و همکاران4، دو روش فیلترینگ ماتریس همبستگی که با روشهای خوشهبندی سلسله مراتبی انجام شده است را بیان میکند.
روشهای مورد بررسی تحلیل خوشهی پیوندی منفرد - SLCA - 5 و تحلیل خوشهی پیوندی میانگین - ALCA - 6 است. در حقیقت ALCA از ضریب همبستگی استفاده میکند، در حالی که SLCA از همبستگی ماکزیمال .[13] طباطبایی و همکاران7، الگوریتم خوشهبندی 8GANC را به منظور مینیمم کردن معیار برش نرمال خوشهبندی گرافها پیشنهاد کردند. خوشهبندی گرافهایی با میلیونها رأس و یال از قابلیتهای اصلی این الگوریتم میباشد. زمان اجرایی الگوریتم برای گرافی با n رأس و O - n - یال از مرتبه زمانی O - n log2n - است. که در مقایسه با الگوریتمهای طیفی با مدت زمان اجرایی O - n3 - بهبود قابل مقایسهای دیده میشود. این الگوریتم از سه جزء اصلی تشکیل شده است: -1 روش خوشهبندی حریصانه تجمعی سلسله مراتبی -2 مدل انتخاب سفارش و -3 پالایش محلی
دیگر روشها از درخت پوشای مینیمم برای نمایش مجموعه داده استفاده میکنند. ژو9 و همکارانش سه دیدگاه در این زمینه ارائه میکنند که شامل خوشهبندی از طریق حذف یالهای طویل درخت پوشای مینیمم10، الگوریتم مکرر خوشهبندی و الگوریتم بهینه کلی است
اما در مقایسه با الگوریتمهای خوشهبندی KNN، الگوریتمهای خوشهبندی مبتنی بر MST دو مشکل دارند: -1 تنها اطلاعات مربوط به یالهای MST برای بخشبندی گراف استفاده میشود. -2 با حذف هر یال دو زیرگراف حاصل میشود.
لذا این دو مشکل منجر به بخشبندی بدون شواهد کافی میشد؛ لذا در جهت حل مشکل MST دو مرحلهای پیشنهاد شد. که ما نیز برای انجام خوشهبندی مسأله خود، از این روش استفاده کردیم .
-3 متدولوژی تحقیق
مبنای کار این سیستم بدین گونه است که ابتدا گراف مشتریان را بر اساس دادههای جمعآوری شده توسط فروشگاه میسازد. سپس عمل خوشهبندی مشتریان را با استفاده از مفهوم درخت پوشای مینیمم انجام داده و پس از بدست آمدن خوشهها، مشتری وفادار را شناسایی میکند. در ادامه، متدولوژی تحقیق را مرحله به مرحله بیان میکنیم.
-1-3 جمع آوری مشتریان و پالایش مجموعه داده
در این مقاله، چون ما میخواستیم از مجموعه داده های واقعی استفاده کنیم و نیز دسترسی به داده های واقعی مهیا نبود، لذا از مجموعه داده یک صرافی اینترنتی استفاده کردیم که داده های آن واقعی بود. بازهی انتخابی ما بین سالهای 2009 تا 2011 میباشد که در این بین 304 مشتری از فروشگاه خرید کرده بودند، اما اطلاعات آنها ناقص بود که پس از پالایش دادهها جمعاً 133 مشتری شناسایی شد که اطلاعات آنها به طور کامل ثبت گردیده بود. این اطلاعات شامل نام مشتری، شماره شناسایی مشتری، میزان خرید، کالاهای خریداری شده در روزهای مختلف، آدرس و ایمیل اشخاص میباشد.
-2-3 ساخت گراف وزندار مشتریان
در این مقاله، هدف اصلی ما از ساخت گراف وزندار مشتریان، خوشهبندی آن و نیز شناسایی مشتریان وفادار بنگاه است. گراف وزندار مشتریان طی مراحل زیر ساخته میشود.
1. هر مشتری را به عنوان یک رأس در نظر میگیریم.
2. دادهها را بر اساس واحد زمانی تقسیم نموده و Yi - t - را که میزان خرید مشتری i در سال t میباشد، محاسبه میکنیم.
3. حال میزان همبستگی دو مشتری به هم طبق رابطه کوواریانس به صورت زیر تعریف میشود:
که E - Yi - = 1n ∑nt=1 Y - i - t میانگین میزان خرید مشتری i در n دوره میباشد.
لذا میان مشتری i و j یک یال قرار میگیرد، اگر ij ≥ باشد.
Pij، معرف میزان همبستگی میان دو مشتری i و j است. که این معیار در بازه 1] و [-1 تغییر میکند. این بدان معنی است که اگر P ij = 1 باشد، دو مشتری مشابه هم رفتار میکنند و در صورتی که Pij = -1 ، یعنی دو مشتری i و j خلاف هم رفتار میکنند. قصد ما از طراحی گراف مشتریان، خوشهبندی مشتریان و شناسایی مشتریانی با رفتارهای مشابه است؛ لذا مقدار آستانه 0/1 را برای Pij انتخاب میکنیم. بنابراین میان دو مشتری i و j یالی وجود خواهد داشت، هرگاه Pij ≥ 0/1 باشد.
پس از طی نمودن مراحل بالا، گراف حاصل دارای رئوس ایزوله متعددی بود. این امر امکان ساخت درخت پوشای مینیمم را غیر ممکن میساخت؛ لذا در جهت فائق آمدن بر این مشکل، دادهها را دوباره بر اساس واحد زمانی نیم سال مرتب کردیم. نتیجه گرافی همراه با یک رأس ایزوله بود. با در نظر گرفتن آن رأس به عنوان نویز، گراف مشتریان طبق شکل - 1 - ساخته شد.
وقتی گراف تشکیل شد، نوبت به وزندهی یالهای آن میرسد. باید دقت شود که مفهوم وزن باید در برگیرنده میزان همبستگی میان دو مشتری باشد؛ لذا از معیار فاصله اقلیدسی = √2 - 1 − - برای این مفهوم استفاده شد. این معیار بدین معنی است که هر چه فاصله دو مشتری کمتر باشد، آن دو مشتری بهم وابستهتر بوده و بالطبع پیروی آن دو از یکدیگر در الگوی خرید بیشتر خواهد بود. حال نوبت به خوشهبندی گراف ایجاد شده میرسد.
شکل -1 گراف وزندار مشتری
-3-3 ایجاد درخت پوشای مینیمم گراف اولیه
برای ساخت MST از الگوریتم کراسکال استفاده میشود. در الگوریتم کراسکال یالهای گراف را به ترتیب صعودی مرتب میکنیم. از اولین - کوچکترین - یال شروع کرده و هر یال را به گراف اضافه میکنیم به شرط اینکه دور در گراف ایجاد نگردد. این روال را آنقدر ادامه میدهیم تا درخت پوشای بهینه تشکیل گردد - شکل . - 2
شکل -2 مینیمم درخت پوشای گراف مشتریان - MST1 -
-4-3 ترسیم MST2
برای ساخت MST2، ابتدا کلیهی یالهای MST1 را از گراف اولیه حذف میکنیم. اگر بعد از حذف یالهای MST1 از گراف اصلی، گره تنها و ایزولهای حاصل شود، باید از میان یالهای این گره در گراف اصلی، یال با کمترین وزن به MST2 اضافه شود تا بتوان MST2 را ایجاد کرد. بعد از این نوبت آن میرسد تا درخت پوشای مینیمم گراف حاصله را بسازیم که این کار طبق مرحله قبل توسط الگوریتم کراسکال انجام میشود.
-5-3 ایجاد درخت پوشای مینیمم ثانویه - 2-MST -
در این مرحله، دو درخت MST1 و MST2 با هم ترکیب میشوند تا 2-MST بدست آید. حال نوبت به وزندهی یالهای گراف 2-MST میرسد. در وزندهی یالهای 2-MST ، اگر dij = 0 باشد، وزن یال صفر نظر گرفته شده، در غیر این صورت طبق معادله پایین یالها وزندهی میشوند
