Branch-and-Bound Applications in Combinatorial Data Analysis

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

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

Dr. بروسکو استاد بازاریابی و تحقیقات عملیاتی در دانشگاه ایالتی فلوریدا، عضو هیئت تحریریه مجله طبقه بندی و عضو هیئت مدیره انجمن طبقه بندی آمریکای شمالی است. استفانی استال نویسنده و محققی با سالها تجربه در زمینه نوشتن، ویرایش و تحقیقات کمی روانشناسی است.

There are a variety of combinatorial optimization problems that are relevant to the examination of statistical data. Combinatorial problems arise in the clustering of a collection of objects, the seriation (sequencing or ordering) of objects, and the selection of variables for subsequent multivariate statistical analysis such as regression. The options for choosing a solution strategy in combinatorial data analysis can be overwhelming. Because some problems are too large or intractable for an optimal solution strategy, many researchers develop an over-reliance on heuristic methods to solve all combinatorial problems. However, with increasingly accessible computer power and ever-improving methodologies, optimal solution strategies have gained popularity for their ability to reduce unnecessary uncertainty. In this monograph, optimality is attained for nontrivially sized problems via the branch-and-bound paradigm.

For many combinatorial problems, branch-and-bound approaches have been proposed and/or developed. However, until now, there has not been a single resource in statistical data analysis to summarize and illustrate available methods for applying the branch-and-bound process. This monograph provides clear explanatory text, illustrative mathematics and algorithms, demonstrations of the iterative process, psuedocode, and well-developed examples for applications of the branch-and-bound paradigm to important problems in combinatorial data analysis. Supplementary material, such as computer programs, are provided on the world wide web.

Dr. Brusco is a Professor of Marketing and Operations Research at Florida State University, an editorial board member for the Journal of Classification, and a member of the Board of Directors for the Classification Society of North America. Stephanie Stahl is an author and researcher with years of experience in writing, editing, and quantitative psychology research.