ریاضیات

14 آگوست 2015

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

روند اجرای آمار تاو-کندال ، با استفاده از کلاه مهندس نرم افزار من ، باعث شد تا اندکی در مورد چگونگی تعمیم آن فراتر از کاربرد سنتی رتبه بندی جفت های عددی تأمل کنم. در این پست من به کلیات تاو-کندال به داده های غیر عددی و همچنین تعمیم داده های کاملاً مرتب به ترتیب های جزئی بحث خواهم کرد.

مروری بر تاو کندال

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

دنباله ای از مشاهدات (n) را در نظر بگیرید که هر مشاهده یک جفت است (x، y) ، جایی که ما می خواهیم اندازه گیری کنیم که یک رتبه بندی با مقادیر x با یک رتبه بندی با مقادیر y چه اندازه موافق است. به طور غیررسمی ، کندو تاو (معروف به ضریب همبستگی رتبه کندال) تفاوت بین تعداد جفتهای مشاهده (در صورت تمایل جفتهای جفت) است که ترتیب آنها موافق است (جفتهای "مطابق") و تعداد جفتهایی که ترتیب آنها مخالف است (" ناسازگار "جفت). این اختلاف بر تعداد کل جفت های مشاهده تقسیم می شود.

فرمول معمول استفاده شده از Tau کندال ، آمار "Tau-B" است که برای جفت های مشاهده شده دارای مقادیر گره خورده در x یا y به عنوان نه سازگار و متناقض است:

شکل 1: کندلو Tau-B

فرمول فوق با توجه به اندازه داده (n) دارای پیچیدگی درجه دو است. تنظیم مجدد این محاسبات به روشی امکان پذیر است که بتواند در (n) log (n) زمان محاسبه شود [1]:

شکل 2: فرمول بندی (n) log (n) Kendall's Tau-B

جزئیات انجام این محاسبه را می توانید در [1] یا در ورودی ویکی پدیا پیدا کنید . برای اهداف من ، توجه خواهم کرد که به دو نوع (n) log (n) داده نیاز دارد که در زیر مربوط می شوند.

تعمیم به مقادیر غیر عددی

تعمیم Tau کندال به مقادیر غیر عددی عمدتاً فقط مشاهده این نکته است که تعریف جفت "سازگار" و "ناسازگار" صرفاً بر اساس مقایسه مقادیر x و مقادیر y است (و در (n) log (n) فرمول بندی ، انجام انواع بر روی داده ها). از منظر مهندس نرم افزار ، این بدان معناست که محاسبات روی هر نوع داده با رابطه ترتیب به خوبی تعریف شده است ، که شامل انواع عددی است اما همچنین کاراکترها ، رشته ها ، توالی هر عنصری که از یک سفارش پشتیبانی می کند و غیره. به طور قابل توجهی ، اکثر زبان های برنامه نویسی از این مفهوم پشتیبانی می کنند از تعریف روابط ترتیب بر روی انواع داده های دلخواه ، به این معنی که * Tau کندال ، در اصل ، می تواند به معنای واقعی کلمه از هر نوع ساختار داده ای محاسبه شود *، به شرطی که آن را با یک سفارش کاملاً مشخص تهیه کنید. علاوه بر این ، بررسی الگوریتم ها نشان می دهد که مقادیر x و y حتی از یک نوع نیستند و همچنین به ترتیب مشابه نیاز ندارند.

تعمیم به سفارشات جزئی

وقتی این مشاهدات را مطرح کردم ، همکارم ویل بنتون این س interesting ال بسیار جالب را مطرح کرد که آیا محاسبه تاو کندال روی اشیایی که فقط ترتیب جزئی دارند نیز امکان پذیر است ؟ به نظر می رسد که شما * می توانید Tau کندال را بر روی داده های جزئی مرتب شده تعریف کنید ، با تعریف حالت دو مقدار x غیرقابل مقایسه ، یا مقادیر y ، به عنوان نوع دیگری از کراوات.

نکته مهم با این تعریف این است که بهینه سازی (n) log (n) اعمال نمی شود. در مرحله اول ، الگوریتم بهینه شده به میزان زیادی به (n) log (n) مرتب سازی متکی است و هیچ نوع مرتب سازی کامل و منحصر به فردی از عناصر که فقط تا حدی مرتب شده اند وجود ندارد. ثانیاً ، تعریف فرمول از مقادیر n1 ، n2 و n3 بر این فرض استوار است که برابری عناصر انتقالی است. به همین دلیل است که می توانید تعدادی مقادیر گره خورده ، t را بشمارید و از t (t-1) / 2 به عنوان تعداد جفت گره خورده استفاده کنید. اما در یک سفارش جزئی ، این فرض نقض می شود. موردی را در نظر بگیرید که (a) <(b) ، اما (a) با (c) قابل مقایسه نیست و (b) نیز با (c) قابل مقایسه نیست. طبق تعریف ما ، (a) با (c) گره خورده است ، و (c) با (b) گره خورده است ، اما انتقال پذیری نقض می شود ، به عنوان (a) <(b).

بنابراین چگونه می توانیم Tau را در این حالت محاسبه کنیم؟ (n1) و (n2) را در شکل 1 در نظر بگیرید. این مقادیر به ترتیب تعداد جفت هایی است که به ترتیب wrt (x) و (y) گره خورده اند. ما نمی توانیم از فرمول های میانبر برای (n1) و (n2) استفاده کنیم ، اما می توانیم آنها را مستقیماً ، جفت به جفت ، به سادگی با انجام تکرار درجه دوم سنتی روی جفت ها ، و افزایش (n1) هر زمان که دو مقدار x غیرقابل مقایسه نیستند ، بشماریم. ، و هر زمان که دو مقدار y قابل مقایسه نباشند (n2) ، دقیقاً همانطور که (nc) و (nd) را برای شمردن جفت های سازگار و ناسازگار افزایش می دهیم. با استفاده از این اصلاح ، می توان فرمول موجود در شکل -1 را همانطور که هست اعمال کرد.

نتیجه گیری

من این مشاهدات را بدون در نظر گرفتن کاربرد خاصی انجام دادم. با این حال ، غرایز من به عنوان یک مهندس نرم افزار به من می گویند که ایجاد تعمیم در این روش ، اغلب زمینه ساز ایده های جدید می شود ، پس از در دسترس قرار دادن مفهوم تعمیم یافته. خوشبختانه ، این کار من یا کسی را ترغیب خواهد کرد که Tau کندال را به روشهای جدید جالب استفاده کنید.

منابع

[1] Knight، W. (1966). "یک روش رایانه ای برای محاسبه تاو کندال با داده های دسته بندی نشده". مجله انجمن آماری آمریكا 61 (314): 436–439. doi: 10.2307 / 2282833. JSTOR 2282833.

http://erikerlandson.github.io/blog/2015/08/14/generalizing-kendalls-tau/