Кластерлеу әдісі – объектілер жиынын бір топтағылар басқа салалардағы объектілерге қарағанда бір-біріне көбірек ұқсайтындай етіп топтастыру міндеті. Бұл деректерді іздеудің негізгі міндеті және машиналық оқыту, үлгіні тану, кескінді тану, ақпаратты іздеу, деректерді қысу және компьютерлік графиканы қоса, көптеген салаларда қолданылатын жалпы статистикалық талдау әдісі.
Оңтайландыру мәселесі
Кластерлеу әдісінің өзі бір нақты алгоритм емес, шешуді қажет ететін жалпы тапсырма. Бұған топты нені құрайтынын және оны қалай тиімді табуға болатынын түсінуде айтарлықтай ерекшеленетін әртүрлі алгоритмдер арқылы қол жеткізуге болады. Метасубъектілерді қалыптастыру үшін кластерлеу әдісін қолдану тобын қолдануды қамтидымүшелер арасындағы шағын қашықтық, кеңістіктің тығыз аймақтары, интервалдар немесе белгілі бір статистикалық үлестірім. Сондықтан кластерлеуді көп мақсатты оңтайландыру мәселесі ретінде тұжырымдауға болады.
Сәйкес әдіс пен параметр параметрлері (пайдаланылатын қашықтық функциясы, тығыздық шегі немесе күтілетін кластерлердің саны сияқты элементтерді қоса) жеке деректер жинағына және нәтижелерді мақсатты пайдалануға байланысты. Талдау автоматты тапсырма емес, білімді ашудың немесе интерактивті көп мақсатты оңтайландырудың итерациялық процесі. Бұл кластерлеу әдісі сынақ және қате әрекеттерін қамтиды. Нәтиже қалаған қасиеттерге жеткенше деректерді алдын ала өңдеу мен үлгі параметрлерін өзгерту жиі қажет.
«Кластерлеу» терминінен басқа, автоматты жіктеу, сандық таксономия, ботриология және типологиялық талдау сияқты мағыналары жақын сөздер қатары бар. Жіңішке айырмашылықтар көбінесе метасубъектілік қатынастарды қалыптастыру үшін кластерлеу әдісін қолдануда жатыр. Деректерді шығару кезінде алынған топтар қызығушылық тудырса, автоматты жіктеуде бұл функцияларды орындайтын кемсітушілік күш болып табылады.
Кластерлік талдау 1932 жылы Кробердің көптеген жұмыстарына негізделген. Оны психологияға 1938 жылы Зубин және 1939 жылы Роберт Трайон енгізді. Және бұл жұмыстарды Кэтелл 1943 жылдан бастап теорияда кластерлеу әдістерінің жіктелуін көрсету үшін қолданып келеді.
Мерзім
«Кластер» ұғымына нақты анықтама беру мүмкін емес. Бұл кластерлеу әдістерінің көп болуының бір себебі. Ортақ бөлгіш бар: деректер объектілерінің тобы. Дегенмен, әртүрлі зерттеушілер әртүрлі модельдерді пайдаланады. Кластерлеу әдістерін қолданудың әрқайсысы әртүрлі деректерді қамтиды. Әртүрлі алгоритмдер арқылы табылған ұғым өзінің қасиеттерінде айтарлықтай ерекшеленеді.
Кластерлеу әдісін пайдалану нұсқаулар арасындағы айырмашылықтарды түсінудің кілті болып табылады. Әдеттегі кластер үлгілеріне мыналар жатады:
- Centroid с. Бұл, мысалы, k-орташа кластерлеу әрбір кластерді бір орташа вектормен көрсететін кезде.
- Қосылу үлгісі s. Бұл, мысалы, қашықтық байланысына негізделген үлгілерді құрастыратын иерархиялық кластерлеу.
- Тарату үлгісі s. Бұл жағдайда кластерлер метапәннің статистикалық үлестірімдерін қалыптастыру үшін кластерлеу әдісі арқылы модельденеді. Күтуді максимизациялау алгоритміне қолданылатын көп айнымалы қалыпты бөлу сияқты.
- Тығыздық үлгісі s. Бұл, мысалы, DBSCAN (Шу бар кеңістіктік кластерлеу алгоритмі) және OPTICS (Құрылымды анықтауға арналған тапсырыс нүктелері), олар кластерлерді деректер кеңістігіндегі қосылған тығыз аймақтар ретінде анықтайды.
- Ішкі кеңістік үлгісі c. Қос кластерлеуде (бірлескен кластерлеу немесе екі режим ретінде де белгілі) топтар екі элементпен және сәйкес атрибуттармен модельденеді.
- Модельдер. Кейбір алгоритмдерде жоқмета-тақырып нәтижелерін жасау және жай ғана ақпаратты топтастыруды қамтамасыз ету үшін олардың кластерлеу әдісі үшін нақтыланған қарым-қатынас.
- С графикасына негізделген үлгі. Клик, яғни жиек бөлігіндегі әрбір екі қосылымды кластер пішінінің прототипі ретінде қарастыруға болатындай түйіндердің ішкі жиыны. Жалпы сұраныстың әлсіреуі квази-кликтер деп аталады. Дәл осындай атау HCS кластерлеу алгоритмінде берілген.
- Нейрондық модельдер s. Ең танымал бақыланбайтын желі - өзін-өзі ұйымдастыру картасы. Дәл осы модельдерді әдетте мета-пән нәтижелерін қалыптастыру үшін жоғарыда аталған кластерлеу әдістерінің біріне немесе бірнешеуіне ұқсас деп сипаттауға болады. Ол нейрондық желілер негізгі немесе тәуелсіз құрамдас талдаудың қажетті түрін жүзеге асырған кезде қосалқы кеңістік жүйелерін қамтиды.
Бұл термин, шын мәнінде, әдетте деректерді кластерлеу әдістерінің жиынындағы барлық нысандарды қамтитын осындай топтардың жиынтығы. Сонымен қатар, ол бір-біріне кіріктірілген жүйелер иерархиясы сияқты кластерлердің өзара байланысын көрсете алады. Топтауды келесі аспектілерге бөлуге болады:
- Қатты центроидты кластерлеу әдісі. Мұнда әрбір нысан топқа жатады немесе одан тыс.
- Жұмсақ немесе анық емес жүйе. Бұл кезде әрбір нысан белгілі бір дәрежеде кез келген кластерге жатады. Оны c-ортасының анық емес кластерлеу әдісі деп те атайды.
Және басқа да нәзік айырмашылықтар болуы мүмкін. Мысалы:
- Қатаң бөлу кластері. Мұндаәрбір нысан дәл бір топқа жатады.
- Шеше мәндері бар қатаң бөлу кластері. Бұл жағдайда нысандар да ешқандай кластерге жатпайды және қажет емес деп саналуы мүмкін.
- Қайталас кластерлеу (сонымен қатар баламалы, бірнеше көріністермен). Мұнда нысандар бірнеше тармақтарға тиесілі болуы мүмкін. Әдетте тұтас кластерлерді қамтиды.
- Иерархиялық кластерлеу әдістері. Еншілес топқа жататын нысандар да негізгі ішкі жүйеге жатады.
- Ішкі кеңістіктің қалыптасуы. Бірегей анықталған жүйеде қабаттасатын кластерлерге ұқсас болғанымен, өзара топтар бір-біріне сәйкес келмеуі керек.
Нұсқаулар
Жоғарыда айтылғандай, кластерлеу алгоритмдерін кластер үлгісіне қарай жіктеуге болады. Келесі шолуда осы нұсқаулардың ең көрнекті мысалдары ғана берілген. 100-ден астам жарияланған алгоритмдер болуы мүмкін болғандықтан, олардың барлығы кластерлері үшін үлгілерді қамтамасыз ете бермейді, сондықтан оларды оңай жіктеуге болмайды.
Объективті дұрыс кластерлеу алгоритмі жоқ. Бірақ, жоғарыда айтылғандай, нұсқау әрқашан бақылаушының көру аймағында болады. Белгілі бір мәселе үшін ең қолайлы кластерлеу алгоритмі, егер бір модельді екіншісінен артықшылыққа ие болу үшін математикалық себеп болмаса, көбінесе эксперименталды түрде таңдалуы керек. Айта кету керек, бір типке арналған алгоритм әдетте жұмыс істемейдітүбегейлі басқа тақырыпты қамтитын деректер жинағы. Мысалы, k-орталары дөңес емес топтарды таба алмайды.
Қосылымға негізделген кластерлеу
Бұл одақ өз атымен де белгілі, иерархиялық модель. Ол объектілердің әлдеқайда алыстағы бөліктерге қарағанда көрші бөліктермен көбірек байланысатыны туралы типтік идеяға негізделген. Бұл алгоритмдер объектілерді олардың қашықтығына байланысты әртүрлі кластерлер құра отырып, байланыстырады. Топты негізінен кластердің әртүрлі бөліктерін қосу үшін қажетті максималды қашықтықпен сипаттауға болады. Барлық мүмкін қашықтықтарда дендрограмма арқылы көрсетуге болатын басқа топтар құрылады. Бұл «иерархиялық кластерлеу» жалпы атауының қайдан шыққанын түсіндіреді. Яғни, бұл алгоритмдер деректер жиынының бір бөлігін қамтамасыз етпейді, керісінше, өкілеттіктің кең тәртібін қамтамасыз етеді. Оның арқасында белгілі бір қашықтықта бір-бірімен дренаж бар. Дендрограммада у осі кластерлердің біріккен қашықтығын білдіреді. Ал нысандар топтар араласпауы үшін X сызығы бойынша орналастырылған.
Байланысқа негізделген кластерлеу - қашықтықтарды есептеу тәсілімен ерекшеленетін әдістердің тұтас тобы. Қашықтық функцияларын әдеттегі таңдаудан басқа, пайдаланушы қосылу критерийін де шешуі керек. Кластер бірнеше объектілерден тұратындықтан, оны есептеудің көптеген нұсқалары бар. Танымал таңдау бір тұтқалы топтау ретінде белгілі, бұл әдістолық сілтеме, құрамында UPGMA немесе WPGMA (орташа арифметикалық бар жұптардың өлшенбеген немесе өлшенген ансамблі, сондай-ақ орташа сілтеме кластері ретінде белгілі). Сонымен қатар, иерархиялық жүйе агломеративті (жеке элементтерден басталып, оларды топтарға біріктіру) немесе бөлуші (толық деректер жинағынан басталып, оны бөлімдерге бөлу) болуы мүмкін.
Таратылған кластерлеу
Бұл үлгілер бөлуге негізделген статистикамен ең тығыз байланысты. Кластерлерді бірдей таратуға жататын нысандар ретінде оңай анықтауға болады. Бұл тәсілдің ыңғайлы ерекшелігі оның жасанды деректер жиынын жасау тәсіліне өте ұқсас болуы. Бөлуден кездейсоқ нысандарды таңдау арқылы.
Бұл әдістердің теориялық негізі тамаша болғанымен, модельдің күрделілігіне шектеулер қойылмаса, олар шамадан тыс орнату деп аталатын бір негізгі мәселеден зардап шегеді. Үлкенірек байланыс әдетте деректерді жақсырақ түсіндіреді, бұл дұрыс әдісті таңдауды қиындатады.
Гаусс қоспасы үлгісі
Бұл әдіс күтуді барынша арттыру алгоритмдерінің барлық түрлерін пайдаланады. Мұнда деректер жинағы әдетте кездейсоқ түрде инициализацияланған және деректер жиынына жақсырақ сәйкестендіру үшін параметрлері итеративті түрде оңтайландырылған Гаусс үлестірімдерінің тіркелген санымен (алмасуды болдырмау үшін) модельденеді. Бұл жүйе жергілікті оптимумға жақындайды. Сондықтан бірнеше жүгіріс бере аладыәртүрлі нәтижелер. Ең тығыз кластерлеуді алу үшін мүмкіндіктер көбінесе тиесілі болуы мүмкін Гаусс үлестіріміне тағайындалады. Ал жұмсақ топтар үшін бұл қажет емес.
Таратуға негізделген кластерлеу ең соңында атрибуттар арасындағы корреляция мен тәуелділікті анықтай алатын күрделі үлгілерді жасайды. Дегенмен, бұл алгоритмдер пайдаланушыға қосымша ауыртпалық түсіреді. Көптеген нақты дүние деректер жиындары үшін қысқаша анықталған математикалық модель болмауы мүмкін (мысалы, Гаусс үлестірімі өте күшті болжам деп есептесек).
Тығыздыққа негізделген кластерлеу
Бұл мысалда топтар негізінен деректер жинағының қалған бөлігіне қарағанда өткізбейтіндігі жоғары аймақтар ретінде анықталған. Барлық құрамдастарды бөлу үшін қажет осы сирек бөліктердегі нысандар әдетте шу және шеткі нүктелер болып саналады.
Тығыздыққа негізделген кластерлеудің ең танымал әдісі DBSCAN (кеңістіктік шудың кластерлеу алгоритмі) болып табылады. Көптеген жаңа әдістерден айырмашылығы, оның «тығыздыққа жету мүмкіндігі» деп аталатын жақсы анықталған кластер құрамдас бөлігі бар. Байланысқа негізделген кластерлеуге ұқсас, ол белгілі бір қашықтық шегіндегі қосылым нүктелеріне негізделген. Дегенмен, бұл әдіс тығыздық критерийін қанағаттандыратын элементтерді ғана жинайды. Осы радиуста басқа нысандардың ең аз саны ретінде анықталған бастапқы нұсқада кластер барлығынан тұрады.тығыздыққа қатысты элементтер (көптеген басқа әдістерге қарағанда еркін пішінді топ құра алады) және рұқсат етілген ауқымдағы барлық нысандар.
DBSCAN-тың тағы бір қызықты қасиеті оның күрделілігі өте төмен – ол дерекқорға қарсы диапазон сұрауларының сызықтық санын талап етеді. Сондай-ақ әдеттен тыс нәрсе, ол әрбір жұмыста бірдей нәтижелерді табады (бұл негізгі және шу нүктелері үшін детерминирленген, бірақ шекаралық элементтер үшін емес). Сондықтан оны бірнеше рет іске қосудың қажеті жоқ.
DBSCAN және OPTICS негізгі кемшілігі кластер шекараларын анықтау үшін тығыздықтың біршама төмендеуін күтуінде. Мысалы, Гаусс таралымдары қабаттасатын деректер жиындарында - жасанды нысандар үшін жалпы пайдалану жағдайы - осы алгоритмдер арқылы жасалған кластер шекаралары жиі ерікті болып көрінеді. Бұл топтардың тығыздығы үздіксіз төмендейтіндіктен орын алады. Гаусс қоспасының деректер жинағында бұл алгоритмдер жүйелердің осы түрлерін дәл модельдеуге қабілетті EM кластерлеу сияқты әдістерден әрқашан дерлік асып түседі.
Орташа орын ауыстыру – әрбір нысан бүкіл ядроны бағалау негізінде көршілес ең тығыз аймаққа жылжитын кластерлік тәсіл. Соңында объектілер жергілікті өтпеушілік максимумдарына жақындайды. k-құрылғысын кластерлеуге ұқсас, бұл «тығыздық аттракторлары» деректер жиынының өкілдері ретінде қызмет ете алады. Бірақ орташа ауысуDBSCAN-ға ұқсас ерікті пішінді кластерлерді анықтай алады. Қымбат итерациялық процедура мен тығыздықты бағалаудың арқасында орташа ығысу әдетте DBSCAN немесе k-Орташаларына қарағанда баяу болады. Сонымен қатар, типтік ауысу алгоритмін жоғары өлшемді деректерге қолдану ядро тығыздығын бағалаудың біркелкі емес әрекетіне байланысты қиын, бұл кластер ағындарының шамадан тыс фрагментациясына әкеледі.
Рейтинг
Кластерлеу нәтижелерін тексеру кластерлеудің өзі сияқты қиын. Танымал тәсілдерге «ішкі» балл қою (жүйе сапаның бір өлшеміне дейін төмендетілген) және, әрине, «сыртқы» балл қою (бұл жерде кластерлеу бар «негізгі ақиқат» классификациясымен салыстырылады) жатады. Ал адам сарапшысының қолмен берген ұпайы мен жанама ұпайы жоспарланған қолданбадағы кластерлеудің пайдалылығын тексеру арқылы табылады.
Ішкі жалауша өлшемдері өздерін кластерлік мақсат деп санауға болатын мүмкіндіктерді көрсететін мәселеге байланысты. Мысалы, Silhouette коэффициентімен берілген деректерді топтастыруға болады, тек мұны істеу үшін белгілі тиімді алгоритм жоқ. Бағалау үшін осындай ішкі өлшемді пайдалану арқылы оңтайландыру мәселелерінің ұқсастығын салыстырған дұрыс.
Сыртқы белгіде ұқсас мәселелер бар. Егер мұндай «негізгі шындық» белгілері болса, онда кластерлеудің қажеті жоқ. Ал практикалық қолданбаларда әдетте мұндай ұғымдар болмайды. Екінші жағынан, белгілер деректер жиынының бір ғана ықтимал бөлімін көрсетеді, бұл білдірмейдібасқа (мүмкін одан да жақсы) кластерлеу жоқ.
Сондықтан бұл тәсілдердің ешқайсысы түпкілікті сапаны бағалай алмайды. Бірақ бұл адамның бағалауын талап етеді, бұл өте субъективті. Дегенмен, мұндай статистика нашар кластерлерді анықтауда ақпараттық болуы мүмкін. Бірақ адамның субъективті бағасын жоққа шығаруға болмайды.
Ішкі белгі
Кластерлеу нәтижесі өзі кластерленген деректер негізінде бағаланса, бұл осы термин деп аталады. Бұл әдістер, әдетте, ең жақсы нәтижені топтар ішінде ұқсастығы жоғары және топтар арасында төмен топтар жасайтын алгоритмге тағайындайды. Кластерлік бағалауда ішкі критерийлерді пайдаланудың кемшіліктерінің бірі жоғары ұпайлар тиімді ақпаратты іздеу қолданбаларына әкелмейді. Сондай-ақ, бұл ұпай бірдей үлгіні пайдаланатын алгоритмдерге бағытталған. Мысалы, k-кластерлеу мүмкіндіктер қашықтығын табиғи түрде оңтайландыратынын білдіреді және оған негізделген ішкі критерий нәтижесінде кластерлеуді асыра бағалауы мүмкін.
Сондықтан, бұл бағалау шаралары бір алгоритм екіншісіне қарағанда жақсырақ орындалатын жағдайлар туралы түсінік алу үшін қолайлы. Бірақ бұл әрбір ақпарат басқаларға қарағанда сенімдірек нәтиже береді дегенді білдірмейді. Мұндай индекспен өлшенетін жарамдылық мерзімі құрылымның деректер жинағында бар екендігін бекітуге байланысты. Кейбір түрлер үшін әзірленген алгоритм, егер жиында түбегейлі болса, ешқандай мүмкіндік болмайдықұрамы әртүрлі немесе бағалау әртүрлі критерийлерді өлшейтін болса. Мысалы, k-орталарды кластерлеу тек дөңес кластерлерді таба алады және көптеген ұпай индекстері бірдей пішімді қабылдайды. Дөңес емес үлгілері бар деректер жинағында k-орталарды және типтік бағалау критерийлерін пайдалану орынсыз.
Сыртқы бағалау
Осындай шарлау арқылы кластерлеу нәтижелері топтау үшін пайдаланылмаған деректер негізінде бағаланады. Яғни, белгілі сынып белгілері және сыртқы сынақтар сияқты. Мұндай сұрақтар алдын ала жіктелген элементтердің жиынтығынан тұрады және оны көбінесе сарапшылар (адамдар) жасайды. Осылайша, анықтамалық жинақтарды бағалаудың алтын стандарты ретінде қарастыруға болады. Бұл бағалау әдістерінің түрлері кластерлеудің берілген анықтамалық сыныптарға қаншалықты жақын екенін өлшейді. Дегенмен, бұл нақты деректер үшін жеткілікті ме, әлде нақты ақиқатқа ие синтетикалық жиынтықтар үшін ғана сәйкес пе деген мәселе жақында талқыланды. Өйткені сыныптар ішкі құрылымды қамтуы мүмкін және бар атрибуттар кластерлерді бөлуге мүмкіндік бермеуі мүмкін. Сондай-ақ, білімді ашу тұрғысынан белгілі фактілерді жаңғырту міндетті түрде күтілетін нәтиже бермеуі мүмкін. Топтау процесінде мета-ақпарат (сынып белгілері сияқты) бұрыннан қолданылған арнайы шектеулі кластерлік сценарийде бағалау мақсатында барлық ақпаратты сақтау маңызды емес.
Енді кластерлеу әдістеріне не қолданылмайтыны және бұл мақсаттар үшін қандай үлгілер қолданылатыны белгілі болды.
