معیار normalized Discounted Cumulative Gain یا به اختصار nDCG یک معیار (metric) رایج جهت ارزیابی خروجی یک موتور جستجوگر یا هر سیستم رنکینگ دیگر است. مقدار این متریک عددی بین صفر و یک است که از جمله ویژگی‌های آن، اندازه‌گیری میزان درستی در مرتب‌سازی نتایج می‌باشد.

این معیار نرمالایز شده‌ی معیار DCG می‌باشد. برای محاسبه‌ی DCG از رابطه‌ی زیر استفاده می‌شود:

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

در رابطه‌ی بالا IDCG برابر است با مقدار DCG برای حالت ایده‌آل مرتب‌سازی:

برای اطلاعات بیشتر درباره‌ی این متریک می‌توانید اینجا کلیک کنید.

ما در دیجی‌کالا برای محاسبه این متریک از داده‌ی کلیک کاربران به روی نتایج موتور جستجوگر استفاده می‌کنیم. فرض کنید جدول زیر موجود باشد. در این جدول هر سطر نشانگر تعداد کلیک بروی نتیجه‌ی سرچ یک کوئری در پوزیشنِ مربوطه است.

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

دریافت نمونه فایل دادگان (demo_testset.zip)

در این فایل دیتابیس 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 استفاده شده است.