الگوریتم یافتن مشابهت اسناد — راهنمای مقدماتی

۵۳۷ بازدید
آخرین به‌روزرسانی: ۳۰ اردیبهشت ۱۴۰۲
زمان مطالعه: ۵ دقیقه
الگوریتم یافتن مشابهت اسناد — راهنمای مقدماتی

در این مقاله با روش کدنویسی و همچنین مبانی ریاضیاتی فاصله اقلیدسی، مشابهت کسینوسی و همبستگی پیرسون به عنوان سه الگوریتم یافتن مشابهت اسناد برای طراحی موتورهای «پیشنهاد موارد مشابه» آشنا خواهیم شد. امروزه سیستم‌های پیشنهاد محتوا اهمیت زیادی در حوزه‌های گوناگون دارند. هسته اصلی سیستم‌های پیشنهادی مفهوم «پالایش گروهی» (Collaborative Filtering) است و در هسته اصلی پالایش گروهی نیز بحث «مشابهت سند» (Document Similarity) قرار دارد.

در ادامه 3 الگوریتم برای محاسبه مشابهت اسناد معرفی می‌کنیم:

  • فاصله اقلیدسی
  • مشابهت کسینوسی
  • ضریب همبستگی پیرسون

حتی یک شهود کلی در مورد شیوه کار این الگوریتم‌ها موجب می‌شود که ابزار صحیحی برای ساخت یک موتور هوشمندتر مورد استفاده قرار دهیم.

وجه اشتراک الگوریتم‌ها

در زمان بررسی الگوریتم‌ها همواره این مفاهیم را در پس‌زمینه ذهن خود داشته باشید.

  1. محاسبات روی بازنمایی‌های بُرداری اشیا اعمال می‌شوند.
  2. مشابهت/فاصله هر زمان بین یک جفت منفرد از بردارها محاسبه می‌شود.
  3. صرف نظر از الگوریتم، انتخاب قابلیت تأثیر عمده‌ای روی نتایج دارد.

فاصله اقلیدسی

فاصله اقلیدسی به طور خلاصه به مسافت بین 2 نقطه در یک فضای چندبعدی گفته می‌شود.

الگوریتم یافتن مشابهت اسناد

به این ترتیب نقاط نزدیک‌تر، به همدیگر شباهت بیشتری دارند. نقاط دورتر از همدیگر تفاوت بیشتری دارند. از این رو در نمودار فوق ماریو و کارلوس شباهت بیشتری نسبت به جفت کارلوس و جنی دارند.

در نمودار فوق فضای دوبعدی (ویژگی‌های ثروت و دوستان) ‌عامدانه انتخاب شده تا رسم نمودار ساده‌تر باشد. اما می‌توان فاصله را در فضای فراتر از 2 بعد نیز محاسبه کرد، گرچه به فرمول خاصی نیاز دارد.

به طور شهودی این روش برای اندازه‌گیری مسافت معنی‌دار است. ما سندها را به صورت نقاطی رسم می‌کنیم که به طور عملی امکان اندازه‌گیری فاصله بین آن‌ها با استفاده از خط‌کش وجود دارد.

مقایسه شهرها با فاصله اقلیدسی

در این بخش مثالی از مقایسه سه شهر نیویورک، تورنتو و پاریس را بررسی می‌کنیم.

  • تورنتو = [3,7]
  • نیویورک = [7,8]
  • پاریس = [2,10]

بردار ویژگی شامل 2 خصوصیت به صورت [population, temperature] است. جمعیت بر حسب میلیون و دما با مقیاس سانتی‌متر است. اکنون از آنجا که این مسئله را نیز به صورت 2 بعدی طراحی کرده‌ایم، می‌توانیم مسافت بین نقاط را با خط‌کش اندازه‌گیری کنیم، اما به جای آن باید از فرمول بهره بگیریم.

الگوریتم یافتن مشابهت اسناد

این فرمول چه 2 و چه 1000 بُعد وجود داشته باشد، کار می‌کند.

پیاده‌سازی فاصله اقلیدسی در پایتون

فرمول ریاضی فاصله اقلیدسی به صورت زیر است:

الگوریتم یافتن مشابهت اسناد

در ادامه تابعی می‌نویسیم که آن را پیاده‌سازی کرده و مسافت بین دو نقطه را محاسبه می‌کند:

1from math import sqrt
2def euclidean_dist(doc1, doc2):
3    '''
4    For every (x,y) pair, square the difference
5    Then take the square root of the sum
6    '''
7    pre_square_sum = 0
8    for idx,_ in enumerate(doc1):
9        pre_square_sum += (doc1[idx] - doc2[idx]) ** 2
10    
11    return sqrt(pre_square_sum)
12
13toronto = [3,7]
14new_york = [7,8]
15
16euclidean_dist(toronto, new_york)
17#=> 4.123105625617661

به این ترتیب می‌بینیم که مسافت بین نیویورک و تورنتو برابر با 4.12 است.

محاسبه فاصله اقلیدسی با Sklearn

تابعی که در بخش فوق نوشتیم کمی ناکافی است. Sklearn یک نسخه سریع‌تر را با استفاده از Numpy پیاده‌سازی می‌کند. در بخش پروداکشن فقط از این نسخه باید استفاده کنیم:

1toronto = [3,7]
2new_york = [7,8]
3import numpy as np
4from sklearn.metrics.pairwise import euclidean_distances
5t = np.array(toronto).reshape(1,-1)
6n = np.array(new_york).reshape(1,-1)
7euclidean_distances(t, n)[0][0]
8#=> 4.123105625617661

توجه کنید که این نسخه به عنوان ورودی به جای لیست از آرایه استفاده می‌کند، اما نتیجه مشابهی به دست می‌‌آید.

مشابهت کسینوسی

مشابهت کسینوسی به طور خلاصه به کسینوس زاویه بین دو نقطه در یک فضای چندبُعدی گفته می‌شود.

به این ترتیب نقاط با زوایای کمتر، مشابهت بیشتری دارند و نقاط با زوایای بزرگ‌تر از همدیگر متفاوت‌تر هستند.

الگوریتم یافتن مشابهت اسناد
تعداد دفعات اشاره به کلمات پخت و رستوران در مقاله

در نمودار فوق، سه سند را بر اساس تعداد دفعاتی که به کلمات Cooking و Restaurant اشاره شده است مورد بررسی قرار داده‌ایم.

فاصله اقلیدسی به ما اعلام می‌کند که بلاگ و مجله مشابهت بیشتری نسبت به بلاگ و روزنامه دارند، اما این نتیجه می‌تواند گمراه‌کننده باشد، چون بلاگ و روزنامه می‌توانند محتوای مشابه بیشتری داشته باشند، اما فاصله اقلیدسی بیشتری دارند، زیرا مطالب روزنامه طولانی‌تر است و شامل کلمات بیشتری است.

در عمل هر دو آن‌ها شامل کلمات Restaurant و Cooking بیشتری هستند و احتمالاً مشابهت بیشتری نسبت به هم دارند. مشابهت کسینوسی موجب می‌شود در این دام نیفتیم.

مقایسه کتاب‌ها و مقالات با مشابهت کسینوسی

در این بخش روی مثال قبلی کار می‌کنیم و به مقایسه اسناد بر اساس تعداد کلمات خاص می‌پردازیم.

1magazine_article = [7,1]
2blog_post = [2,10]
3newspaper_article = [2,20]

الگوریتم یافتن مشابهت اسناد

به جای این که مسافت بین هر نقطه را محاسبه کنیم، کسینوس زاویه بین آن‌ها را از مبدأ مختصات در نظر می‌گیریم. اکنون حتی با یک نگاه مختصر نیز می‌بینیم که بلاگ و روزنامه مشابهت بیشتری دارند.

پیاده‌سازی مشابهت کسینوسی در پایتون

توجه کنید که مشابهت کسینوسی به خود زاویه مربوط نیست، بلکه کسینوس زاویه در نظر گرفته می‌شود. بنابراین زاویه‌های کمتر (زیر 90 درجه) مشابهت بیشتری دارند.

الگوریتم یافتن مشابهت اسناد

در ادامه یک تابع برای محاسبه مشابهت کسینوسی پیاده‌سازی می‌کنیم:

1import numpy as np
2from math import sqrt
3def my_cosine_similarity(A, B):
4    numerator = np.dot(A,B)
5    denominator = sqrt(A.dot(A)) * sqrt(B.dot(B))
6    return numerator / denominator
7    
8    
9magazine_article = [7,1]
10blog_post = [2,10]
11newspaper_article = [2,20]
12m = np.array(magazine_article)
13b = np.array(blog_post)
14n = np.array(newspaper_article)
15    
16print( my_cosine_similarity(m,b) ) #=> 0.3328201177351375
17print( my_cosine_similarity(b,n) ) #=> 0.9952285251199801
18print( my_cosine_similarity(n,m) ) #=> 0.2392231652082992

اینک می‌توانیم ببینیم که بلاگ و روزنامه در عمل مشابهت بیشتری نسبت به همدیگر دارند.

مشابهت کسینوسی با Sklearn

در محیط پروداکشن بهتر است پیاده‌سازی بسیار کارآمدتر Sklearn را ایمپورت کنیم:

1from sklearn.metrics.pairwise import cosine_similarity
2m = np.array(magazine_article).reshape(1,-1)
3b = np.array(blog_post).reshape(1,-1)
4n = np.array(newspaper_article).reshape(1,-1)
5print( cosine_similarity(m,b)[0,0] ) #=> 0.3328201177351375
6print( cosine_similarity(b,n)[0,0] ) #=> 0.9952285251199801
7print( cosine_similarity(n,m)[0,0] ) #=> 0.2392231652082992

چنان که می‌بینید مقادیر مشابهی به دست می‌آید.

همبستگی پیرسون

همبستگی پیرسون به طور معمول رابطه بین 2 متغیر را کمّی‌سازی می‌کند. در مثال زیر به بررسی همبستگی بین دو متغیر تحصیلات و درآمد می‌پردازیم.

الگوریتم یافتن مشابهت اسناد

از همبستگی پیرسون می‌توان برای اندازه‌گیری مشابهت بین دو سند نیز استفاده کرد. در این حالت سند اول به عنوان یک بردار مانند x و سند دوم به عنوان بردار y تصور می‌شود. از آنجا که ضریب همبستگی پیرسون (r) یک مقدار بین 1 و 1- بازگشت می‌دهد. فاصله پیرسون را می‌توان به صورت 1-r محاسبه کرد تا مقداری بین 0 و 2 بازگشت یابد.

پیاده‌سازی ضریب همبستگی پیرسون در پایتون

در این بخش فرمولی برای افزایش درک خودمان از طرز کار ضریب همبستگی پیرسون پیاده‌سازی می‌کنیم.

الگوریتم یافتن مشابهت اسناد

به منظور نمایش برخی افراد در مثال مورد نظر خود برخی داده‌های ساختگی تولید می‌کنیم. این افراد را بر اساس مشابهت بر مبنای یک بردار با سه ویژگی مورد بررسی قرار می‌دهیم.

1emily = [1,2,5]
2kartik = [1,3,5]
3todd = [5,3,5]

پیاده‌سازی ما به صورت زیر است:

1import numpy as np
2def pearsons_correlation_coef(x, y):
3    x = np.array(x)
4    y = np.array(y)
5    
6    x_mean = x.mean()
7    y_mean = y.mean()
8    x_less_mean = x - x_mean
9    y_less_mean = y - y_mean
10    
11    numerator = np.sum(xm * ym)
12    denominator = np.sqrt(
13        np.sum(xm**2) * np.sum(ym**2)
14    )
15    
16    return r_num / r_den
17pearsons_correlation_coef(emily,kartik)
18#=> 0.9607689228305226

چنان که می‌بینید امیلی و کارتیک کاملاً مشابه به نظر می‌رسند. ما هر سه این موارد را در ادامه با Scipy بررسی خواهیم کرد.

محاسبه ضریب همبستگی پیرسون با Scipy

پکیج Scipy یک نسخه بسیار کارآمدتر و پایدارتر را برای محاسبه ضریب همبستگی پیرسون پیاده‌سازی کرده است:

1emily = [1,2,5]
2kartik = [1,3,5]
3todd = [5,3,5]
4pearsonr2(emily,kartik)
5print( pearsonr2(emily, kartik) ) 
6#=> (0.9607689228305226, 0.1789123750220673)
7print( pearsonr2(kartik, todd) ) 
8#=> (0.0, 1.0)
9print( pearsonr2(todd, emily) ) 
10#=> (0.27735009811261446, 0.8210876249779328)

البته ما از اعداد تصادفی به عنوان نقاط داده خود استفاده کرد‌یم. بدین ترتیب می‌بینیم که امیلی و کاتریک مشابهت بیشتری نسبت به جفت امیلی و تاد دارند.

سخن پایانی

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

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

بر اساس رای ۴ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
towardsdatascience
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *