چالش تشخیص کاربران در دیوار طی مسابقات ACM ICPC

در حاشیه مسابقات ACM ICPC در دانشگاه شریف، کارگاه تشخیص کاربر در دیوار ارائه و به چالش‌های پیرامون این مسئله‌ و راه‌حل آن پرداخته شد.

تبلیغات

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

هدف از این ارائه « شکل الگوریتم‌های برنامه‌نویسی در محیط‌های صنعتی و تجاری» اعلام شد. محمدامین خشخاشی مقدم درباره‌ی سرویس دیوار گفت: «دیوار یک پلتفرم خرید و فروش کالا است که در وب و اندروید در دسترس کاربران است. فروشنده کالایی را در دیوار ثبت می‌کند و خریداران آن را می‌بینند و برای بازدید کالا یا خرید با وی تماس می‌گیرند.»

دیوار

مدیر تیم دیتای دیوار ادامه داد: «آگهی گذاشتن در دیوار راحت است. هر کاربر مشخصات خودش را در آگهی وارد می‌کند و نیازی به ثبت‌نام و ورود ندارد. ما بخشی داریم که وظیفه‌ی آن جمع‌آوری داده‌های محصولات و کاربران و تحلیل این داده‌ها است. دیوار ۱۵ میلیون کاربر دارد و تصمیمات ما باید کاربر محور باشد. با استفاده از این داده‌ها و تحلیل‌ها می‌توانیم خدماتی از قبیل نمایش کالاهای مشابه را به‌درستی در اختیار کاربران قرار دهیم. به‌عنوان مثال اگر کسی به دنبال خرید فرش است، به او پیشنهادات مرتبط داده شود.»

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

خشخاشی - دیوار

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

او در مورد سختی این کار گفت:‌ «در بازه‌ای ۶ ماهه‌، ۲۵ میلیون آگهی در دیوار ثبت شده بود و باید روی آن‌ها این گراف را اجرا می‌کردیم. برای طراحی این گراف باید ابتدا یال گذاری این ۲۵ میلیون رأس را انجام می‌دادیم. برای یال‌گذاری راه‌حل‌های مختلفی را امتحان کردیم. در ابتدا ۲ میلیارد و ۴۵۵ میلیون یال برای گراف‌ها ایجاد شد. کار کردن روی بیش از ۲ میلیارد گراف بسیار مشکل است. برای کاهش تعداد یال‌ها باید از مؤلفه‌های هم‌بندی کمک می‌‌گرفتیم. بیش از ۲ میلیارد یال کار را برای دریافت مؤلفه‌های هم‌بندی سخت می‌کرد. ما از ایده‌ی اولیه خودمان تعداد یال‌های تکراری بین هر گراف را حذف کردیم تا نهایتا به تعداد رأس‌ها یعنی ۲۵ میلیون عدد برسند. اما ما به درجه رأس‌ها نیاز داشتیم. پس این راه حل درست نبود.»

خشخاشی مقدم راه‌حل اسپارک (Spark) را چاره‌ای برای کوتاه کردن یال‌ها همراه با مؤلفه‌های هم‌بندی عنوان کرد و افزود:‌ «مشکل بعدی که به آن برخوردیم جاینت کامپوننت‌ها بودند که از اسپم‌ها به وجود می‌آمدند. به‌عنوان مثال به رأسی برخوردیم که مؤلفه‌ی هم‌بندی آن ۵ میلیون بود. با توجه به قانون حداکثر ۳ پست در روز، متوجه شدیم این کاربر واقعی نیست.»

خشخاشی - دیوار

او در مورد راه حل آنالیز و تشخیص اسپم‌ها گفت: «ما مؤلفه‌های هم‌بندی را در ابتدا خرد کردیم تا به ۳۰۰ هزار پست برسیم. برای حل مشکل باید ویژوالایز می‌کردیم که برای این حجم از داده کار زمان‌بر و سختی بود. به همین خاطر بخشی از گراف را ویژوالایز کردیم. برای این کار از الگوریتم‌های لیوت و یال و فنر استفاده کردیم و برای ویژوالایز کردن گراف نیز از نرم‌افزار Gephi کمک گرفتیم. مشکلی که در این گراف هم‌بند وجود داشت، ایمیل‌های یکسان بود. این ایمیل‌های یکسان همان اسپم‌ها بودند. اما همین ایمیل‌ها با شماره‌ تلفن‌های متفاوت وارد شده بودند. به همین خاطر موقع تحلیل و جداسازی شماره‌ تلفن‌های یکسان یک ایمیل بود.»

او در مورد الگوریتمی که بعد از آن استفاده کرده‌اند، گفت: «ما در این مرحله از الگوریتم ضریب خوشگی کمک گرفتیم تا بر اساس آن گراف را آنالیز کنیم. در نهایت توانستیم این گراف را ویژوالایز و تحلیل کنیم. نتیجه این ویژوالایز، حل باگ‌ها و مشکلات موجود در داده‌های ما بود. ما همچنین در حال کار روی تجارت‌های موجود در دیوار هستیم. می‌خواهیم در این مرحله که شروع شده است، روی تحلیل تجارت‌ها و کسب‌وکارهای موجود در دیوار کار کنیم.»

خشخاشی مقدم در جمع‌بندی بحث خود گفت:‌ «نکته‌ی مهم دیگر این است که گراف تنها برای ACM و مسابقات نیست؛ ۱۰ به توان ۹ نیز تنها برای این مسابقات نیست. همه‌ی موارد موجود در مسابقات ACM را می‌توان در تجارت و کسب‌وکار استفاده کرد. باید دانست که تنها زبان‌های برنامه‌نویسی برای حل مشکلات نرم‌افزارها و اپلیکیشن‌ها کافی نیست.»

منبع زومیت

مقاله های مرتبط

  دیدگاه
کاراکتر باقی مانده