بطور کلی، دو نوع خوشه بندی می­تواند روی داده­های تراکنشی کاربرد وب انجام شود که عبارتند از خوشه بندی تراکنش ها (یا کاربران) و خوشه بندی مشاهده صفحه ها. هر یک از این رویکردها کاربردهای مختلفی دارند و بطور خاص، هر دو رویکرد را می­توان برای شخصی­سازی وب استفاده کرد. کارهای زیادی در زمینه­ی کاربردهای خوشه بندی در وب­کاوی کاربرد وب، بازاریابی اینترنتی و شخصی­سازی وب انجام گرفته است. به عنوان مثال الگوریتمی به نام PageGather را می­توان برای کشف گروه های باارزش از صفحات دسترسی شده در الگوهای کاربرد وب استفاده کرد. مبنای این الگوریتم، تکنیک خوشه بندی clique می­باشد. خوشه های حاصل را می­توان برای ترکیب خودکار صفحات اندیس ایستا در یک سایت بکار برد که هر یک علایق خاصی از کاربران را منعکس می­کنند. خوشه بندی رکوردهای رای کاربران نیز به عنوان یک مرحله پیش از فیلتر کردن جمعی به منظور کاهش مشکلات گسترش پذیری الگوریتم نزدیک ترین k همسایه استفاده شده است. هر دو رویکرد خوشه بندی را می­توان به عنوان یک بخش یکپارچه در چارچوب شخصی­سازی وب بر مبنای وب­کاوی کاربرد وب بکار برد.

فرض کنید که نگاشت تراکنش های کاربر به بردارهایی از مشاهده صفحات در فضای چندبعدی داده شده است. الگوریتم های استاندارد خوشه بندی مانند k-means معمولا این فضا را بر مبنای یک معیار شباهت یا فاصله به گروه هایی از تراکنش ها تقسیم می­کنند. خوشه های بدست آمده از این روش می­توانند گروه هایی از کاربران را بر مبنای رفتار گردشی آن­ها نمایندگی کنند. با این وجود، این خوشه های تراکنش ها به تنهایی یک ابزار درک دید تجمعی از الگوهای معمول نمی­باشند. هر خوشه از تراکنش ها می­تواند شامل هزاران تراکنش کاربر دربرگیرنده­ی صدها مشاهده صفحه باشد. هدف نهایی در خوشه­بندی تراکنش های کاربر فراهم کردن قابلیت تحلیل خوشه ها به منظور استخراج هوش تجاری یا استفاده از آن­ها برای اعمالی نظیر شخصی­سازی وب می­باشد.

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

به عنوان یک مثال، داده های تراکنشی شکل 2-8 را در نظر بگیرید. در این مورد، وزن های مشاهده صفحات در هر بردار تراکنش بصورت دودویی است. فرض می­کنیم که داده ها قبلا با استفاده از یک الگوریتم استاندارد خوشه بندی مانند k-means خوشه بندی شده اند و سه خوشه از تراکنش های کاربران حاصل شده است. جدول سمت راست شکل 2-8 پروفایل تجمعی متناظر با خوشه­ی1 را نشان می­دهد. وزن مشاهده صفحات نشان می­دهد که مشاهده صفحات B و F، باارزش ترین صفحات و نشان دهنده­ی علایق معمول کاربران این خوشه می­باشند. مشاهده صفحه­ی C فقط در یک تراکنش ظاهر شده است و می­تواند با استفاده از مقدار آستانه­ی بیش از 0.25 حذف شود.

 

F E D C B A
0 0 1 1 0 0 کاربر1
0 0 1 1 0 0 کاربر4
0 0 1 1 0 0 کاربر7
1 0 0 0 1 1 کاربر0
1 0 0 0 1 1 کاربر3
1 0 0 0 1 1 کاربر6
1 0 0 1 1 0 کاربر9
0 1 1 0 0 1 کاربر2
0 1 1 0 0 1 کاربر5
0 1 1 1 0 1 کاربر8
پروفایل تجمعی برای خوشه­ 1
مشاهده صفحه وزن
B 1.00
F 1.00
A 0.75
C 0.25
خوشه 0
خوشه2

 

 

 

 

 

 

 

 

 

 

 

 

شکل 2-8- مثالی از استخراج پروفایل های تجمعی کاربرد از خوشه های تراکنش ها

 

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

یک رویکرد که در این مورد بسیار موثر بوده است ARHP(Association Rule Hpergraph Partitioning) می­باشد. ARHP می­تواند بصورت کارا مجموعه داده های با ابعاد بالا را خوشه بندی کند. در ARHP ابتدا کاوش قواعد انجمنی برای کشف یک مجموعه از مجموعه اقلام مکرر I از میان مشاهده صفحات مورد استفاده قرار می­گیرد. این مجموعه اقلام سپس برای تشکیل یک ابرگراف H=<V,E> که به عنوان ابریال­ها استفاده می­شود. یک ابرگراف، یک گراف گسترش یافته است که در آن هر ابریال می­تواند بیش از دو راس را متصل کند. وزن­های مرتبط با هر ابریال را می­توان بر مبنای معیارهای گوناگونی محاسبه کرد، مانند اطمینان قواعد انجمنی مرتبط با اقلام موجود در مجموعه اقلام مکرر، پشتیبانی مجموعه اقلام و ….

ابرگراف H بصورت بازگشتی افراز می­شود تا این که یک شرط توقف برای هر قسمت بدست آید و به یک مجموعه از خوشه ها به نام C منجر شود. هر بخش برای فیلتر کردن راس هایی که خیلی به بقیه­ی راس های آن بخش متصل نیستند بررسی می­شود. قابلیت اتصال یک راس v (یک مشاهده صفحه­ی ظاهر شده در مجموعه اقلام مکرر) در یک خوشه c بصورت زیر تعریف می­شود:

(2-6)

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

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

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