Кластерлөө ыкмасы – бул объекттердин жыйындысын башка тармактардагы объектилерге караганда, алар бир топко киргендер бири-бирине көбүрөөк окшоштургудай кылып топтоо милдети. Бул маалыматтарды казып алуунун негизги милдети жана машина үйрөнүү, үлгү таануу, сүрөт таануу, маалыматты издөө, маалыматтарды кысуу жана компьютердик графика сыяктуу көптөгөн тармактарда колдонулган жалпы статистикалык талдоо ыкмасы.
Оптималдаштыруу маселеси
Кластерлөө ыкмасынын өзү бир конкреттүү алгоритм эмес, бирок чечилиши керек болгон жалпы маселе. Буга топту эмнеден түзөрүн жана аны кантип натыйжалуу табуу керектигин түшүнүүдө бир топ айырмаланган ар кандай алгоритмдер менен жетишүүгө болот. Метасубъекттерди түзүү үчүн кластердик ыкманы колдонуу менен топту колдонуу киретмүчөлөрүнүн ортосундагы кичинекей аралыктар, мейкиндиктин жыш аймактары, интервалдар же белгилүү бир статистикалык бөлүштүрүү. Ошондуктан, кластерлөө көп максаттуу оптималдаштыруу маселеси катары түзүлүшү мүмкүн.
Тийиштүү ыкма жана параметр жөндөөлөрү (анын ичинде колдонула турган аралык функциясы, тыгыздык босогосу же күтүлгөн кластерлердин саны сыяктуу нерселер) жеке маалымат топтомуна жана натыйжалардын максаттуу колдонулушуна жараша болот. Талдоо бул автоматтык тапшырма эмес, билимди ачуунун же интерактивдүү көп максаттуу оптималдаштыруунун кайталануучу процесси. Бул кластерлөө ыкмасы сыноо жана ката аракеттерин камтыйт. Көбүнчө натыйжа керектүү касиеттерге жеткенге чейин маалыматтарды алдын ала иштетүүнү жана моделдин параметрлерин өзгөртүү керек.
"Кластерлөө" термининен тышкары, автоматтык классификация, сандык таксономия, ботриология жана типологиялык анализди камтыган окшош маанидеги бир катар сөздөр бар. Тымызын айырмачылыктар көбүнчө метасубъекттик мамилелерди түзүү үчүн кластерлөө ыкмасын колдонууда болот. Маалыматтарды алууда пайда болгон топтор кызыгуу жаратса, автоматтык классификацияда бул функцияларды аткарган дискриминациялык күч.
Кластердик анализ 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-Means караганда жайыраак болот. Мындан тышкары, типтүү жылдыруу алгоритминин жогорку өлчөмдүү маалыматтарга колдонулушу ядронун тыгыздыгын баалоонун бирдей эмес жүрүм-турумунан улам кыйын, бул кластердин куйруктарынын ашыкча фрагменттелишине алып келет.
Рейтинг
Кластерлөөнүн натыйжаларын текшерүү кластерлөө сыяктуу эле кыйын. Популярдуу ыкмаларга “ички” балл коюу (бул жерде система сапаттын бир өлчөмүнө чейин төмөндөтүлгөн) жана, албетте, “тышкы” баалоону (мында кластерлөө учурдагы “негизги чындык” классификациясы менен салыштырылган) кирет. Ал эми адамдык эксперттин кол менен упайы жана кыйыр упай топтолуунун максаттуу колдонмодо пайдалуулугун текшерүү аркылуу табылат.
Ички желекчелер өздөрүн кластердик максаттар деп эсептей турган өзгөчөлүктөрдү чагылдырган көйгөйдөн жабыркайт. Мисалы, Силуэт коэффициенти менен берилген маалыматтарды топтоого болот, бирок муну жасоо үчүн белгилүү эффективдүү алгоритм жок. Баалоо үчүн мындай ички өлчөнү колдонуу менен оптималдаштыруу көйгөйлөрүнүн окшоштугун салыштыруу жакшы.
Сырткы белгиде ушундай көйгөйлөр бар. Андай “негизги чындык” деген жарлыктар болсо, анда кластерлердин кереги жок. Ал эми практикалык колдонмолордо, адатта, мындай түшүнүктөр жок. Башка жагынан алып караганда, энбелгилер маалымат топтомунун бир гана мүмкүн болгон бөлүгүн чагылдырат, бул дегенди билдирбейтбашка (балким андан да жакшыраак) кластерлик жок.
Ошентип, бул ыкмалардын бири да түпкү сапатка баа бере албайт. Бирок бул адамдык баа берүүнү талап кылат, бул өтө субъективдүү. Ошентсе да, мындай статистика жаман кластерлерди аныктоодо маалымат болушу мүмкүн. Бирок адамдын субъективдүү баасын жокко чыгарбаш керек.
Ички белги
Кластерлөөнүн натыйжасы өзү кластерленген маалыматтардын негизинде бааланганда, бул термин деп аталат. Бул ыкмалар жалпысынан эң жакшы натыйжаны топтордун ичинде окшоштуктары жогору жана топтордун ортосунда төмөн түзгөн алгоритмдерге ыйгарышат. Кластердик баалоодо ички критерийлерди колдонуунун кемчиликтеринин бири – бул жогорку упайлар сөзсүз түрдө эффективдүү маалымат издөө тиркемелерине алып келбейт. Ошондой эле, бул упай бир эле моделди колдонгон алгоритмдерге бир жактуу. Мисалы, k-кластерлөө функциялардын аралыктарын табигый түрдө оптималдаштырууну билдирет жана ага негизделген ички критерий натыйжада топтолууну ашыкча баалашы мүмкүн.
Ошондуктан, бул баалоо чаралары бир алгоритм экинчисине караганда жакшыраак иштеген жагдайлар жөнүндө түшүнүк алуу үчүн эң ылайыктуу. Бирок бул ар бир маалымат башкаларга караганда ишенимдүү натыйжаларды берет дегенди билдирбейт. Мындай индекс менен өлчөнгөн жарактуу мөөнөтү структура маалымат топтомунда бар экенин ырастоого көз каранды. Кээ бир түрлөрү үчүн иштелип чыккан алгоритм, эгерде топтом радикалдуу камтыса, эч кандай мүмкүнчүлүк жокар кандай курамы же эгерде баа ар кандай критерийлерди өлчөйт. Мисалы, k-кластерлөө томпок кластерлерди гана таба алат жана көптөгөн баллдык индекстер бирдей форматты кабыл алат. Томпок эмес моделдери бар берилиштер топтомунда k-каражатты жана типтүү баалоо критерийлерин колдонуу орунсуз.
Тышкы баалоо
Мындай топтоо менен кластерлөө натыйжалары топтоо үчүн колдонулбаган маалыматтардын негизинде бааланат. Башкача айтканда, белгилүү класс энбелгилери жана тышкы тесттер. Мындай суроолор алдын ала классификацияланган нерселердин жыйындысынан турат жана көбүнчө эксперттер (адамдар) тарабынан түзүлөт. Ошентип, маалымдама топтомдору баа берүүнүн алтын стандарты катары каралышы мүмкүн. Упай коюу ыкмаларынын бул түрлөрү кластерлөө берилген шилтеме класстарга канчалык жакын экендигин өлчөйт. Бирок, жакында эле бул реалдуу маалыматтар үчүн адекваттуубу же чыныгы негиздүү чындыкка ээ болгон синтетикалык топтомдор үчүн гана талкууланды. Класстар ички структураны камтышы мүмкүн болгондуктан, бар болгон атрибуттар кластерлердин бөлүнүшүнө жол бербеши мүмкүн. Ошондой эле, билимди ачуу көз карашынан алганда, белгилүү фактыларды кайра чыгаруу сөзсүз эле күтүлгөн натыйжаны бербеши мүмкүн. Топтоо процессинде мета-маалымат (мисалы, класс энбелгилери) мурунтан эле колдонулган өзгөчө чектелген кластерлөө сценарийинде баалоо максатында бардык маалыматты сактап калуу маанилүү эмес.
Эми кластердик методдорго эмнелер тиешеси жок экени жана бул максаттарда кандай моделдер колдонулары айкын болду.
