معیار *normalized Discounted Cumulative Gain* یا به اختصار **nDCG** یک معیار (metric) رایج جهت ارزیابی خروجی یک موتور جستجوگر یا هر سیستم رنکینگ دیگر است. مقدار این متریک عددی بین صفر و یک است که از جمله ویژگیهای آن، اندازهگیری میزان درستی در مرتبسازی نتایج میباشد.
این معیار نرمالایز شدهی معیار *DCG* میباشد. برای محاسبهی *DCG* از رابطهی زیر استفاده میشود:
![توضیح تصویر](https://s6.uupload.ir/files/dcg_zsr.jpg)
همانطور که مشاهده میکنید این معیار میتواند برای کوئریهای مختلف، اسیکلهای مختلف داشته باشد. به همین دلیل معیار *nDCG* معرفی میشود که برای محاسبهی آن از رابطهی زیر استفاده میکنیم.
![توضیح تصویر](https://s6.uupload.ir/files/ndcg_nzqb.jpg)
در رابطهی بالا *IDCG* برابر است با مقدار *DCG* برای حالت ایدهآل مرتبسازی:
![توضیح تصویر](https://s6.uupload.ir/files/idcg_bmha.jpg)
برای اطلاعات بیشتر دربارهی این متریک میتوانید [**اینجا**](https://en.wikipedia.org/w/index.php?title=Discounted_cumulative_gain&oldid=1013040968) کلیک کنید.
ما در دیجیکالا برای محاسبه این متریک از دادهی کلیک کاربران به روی نتایج موتور جستجوگر استفاده میکنیم.
فرض کنید جدول زیر موجود باشد. در این جدول هر سطر نشانگر تعداد کلیک بروی نتیجهی سرچ یک کوئری در پوزیشنِ مربوطه است.
| query | click_count | position |
| ------ | ----------- | ---------- |
| pocox3 | 89 | 1 |
| pocox3 | 88 | 2 |
| iphone13 | 100 | 1 |
| ... | ... | ... |
در این مسئله شما باید با استفاده از این دادهها و طراحی یک کوئری sql مناسب، این متریک را برای دادگان کلیک کاربران محاسبه کنید. نمونه فایل دادگان و خروجی مورد نظر در ادامه آورده شده است:
[**دریافت نمونه فایل دادگان (demo_testset.zip)**](https://quera.org/contest/assignments/39253/download_problem_initial_project/132644/?noconvert=true)
در این فایل دیتابیس `sqlite` با نام `testset.sqlite` شامل جدولی با نام `dk_table` در اختیار شما قرار گرفته است. همچنین خروجیی که با اجرای درست کوئری تولید میشود نیز در فایلی به نام `testset_gt.csv` به شما داده شده است.
در این مسئله شما باید کوئری خود را در قالب یک فایل با فرمت *sql* (مانند *query.sql*) در سایت بارگذاری کنید.
## ساختار خروجی
خروجی شما باید شرایط زیر را داشته باشد:
1. تنها دو ستون داشته باشد.
2. یکی از ستونها `query` و دیگری `ndcg` نامیده شود.
3. نوع داده برای ستون `query` **رشته** و برای ستون `ndcg` **عدد اعشاری float** باشد.
4. هیچکدام از ستونها مقدار خالی نداشته باشند.
5. ستون `query` داپلیکت نداشته باشد.
6. معیار *nDCG* برای همه `query` ها محاسبه شده باشد.
## نحوهی ارزیابی:
خروجی کد *sql* شما با خروجی کد زیر مقایسه میشود:
de compute_ndcg_for_dataset(dataset):
df = dataset.groupby('query').agg({'click_count':lambda x: x.tolist(),'position':lambda x: x.tolist()})
df['ndcg'] = df.apply(lambda x: compute_ndcg_per_query(x['click_count'],x['position'])[0],axis=1)
return df[['query','ndcg']]
def compute_ndcg_per_query(clicks,position):
if len(clicks)!= len(position):
raise ValueError("clicks and positions len should be equal")
dcg_list = np.array(clicks)/np.log2(np.array(position)+1)
idcg_list = np.array(sorted(clicks,reverse=True))/np.log2(np.array(position)+1)
dcg = np.sum(dcg_list)
idcg = np.sum(idcg_list)
return dcg/idcg
## تابع لگاریتم در sqlite
برای داشتن تابع لگاریتم در *sqlite* میتوانید کانکشن را به صورت زیر بسازید:
def creaet_sqlite_conn(path):
conn = sqlite3.connect(path)
conn.create_function("log2", 1, np.log2)
return conn
**نکته:** در این سوال از ورژن **3.31** دیتابیس *sqlite* استفاده شده است.
محاسبه nDCG در موتور جستجو دیجیکالا