Бүлэглэх арга гэдэг нь нэг бүлэгт багтсан объектуудыг бусад салбарын объектуудтай харьцуулахад бие биетэйгээ илүү төстэй байхаар бүлэглэх даалгавар юм. Энэ нь өгөгдөл олборлох үндсэн ажил бөгөөд машин сурах, хэв маягийг таних, зураг таних, мэдээлэл хайх, өгөгдөл шахах, компьютерийн график зэрэг олон салбарт хэрэглэгддэг ерөнхий статистик шинжилгээний арга юм.
Оновчлолын асуудал
Кластер хийх арга нь өөрөө тодорхой нэг алгоритм биш, харин шийдвэрлэх шаардлагатай ерөнхий даалгавар юм. Бүлэг гэж юу болох, түүнийг хэрхэн үр ашигтайгаар олохыг ойлгоход ихээхэн ялгаатай янз бүрийн алгоритмуудын тусламжтайгаар үүнийг хийж болно. Метасубъект үүсгэхэд кластерын аргыг ашиглах нь бүлгийн хэрэглээг агуулдаггишүүдийн хоорондох жижиг зай, орон зайн нягт бүс нутаг, интервал эсвэл тодорхой статистик тархалт. Тиймээс кластерчлалыг олон зорилготой оновчлолын асуудал гэж томъёолж болно.
Тохирох арга, параметрийн тохиргоо (үүнд ашиглах зайны функц, нягтын босго эсвэл хүлээгдэж буй кластерын тоо зэрэг) нь өгөгдлийн багц болон үр дүнгийн зориулалтаас хамаарна. Дүн шинжилгээ хийх нь автомат ажил биш, харин мэдлэгийг олж илрүүлэх эсвэл интерактив олон зорилготой оновчлолын давтагдах үйл явц юм. Энэ кластерын арга нь туршилт, алдааны оролдлогуудыг агуулдаг. Үр дүн нь хүссэн шинж чанарт хүрэх хүртэл өгөгдлийн урьдчилсан боловсруулалт болон загварын параметрүүдийг өөрчлөх шаардлагатай байдаг.
"Бүлэглэх" гэсэн нэр томъёоноос гадна автомат ангилал, тоон ангилал зүй, хоёрриологи, хэв зүйн шинжилгээ зэрэг ижил утгатай үг олон байдаг. Метасубъектийн харилцааг бий болгохын тулд кластерын аргыг ашиглахад нарийн ялгаа байдаг. Өгөгдөл задлах явцад үүссэн бүлгүүд нь сонирхолтой байдаг бол автомат ангилалд эдгээр функцийг гүйцэтгэдэг ялгаварлан гадуурхах хүч аль хэдийн байдаг.
Кластерын шинжилгээг 1932 онд Кроберын олон бүтээл дээр үндэслэсэн. Үүнийг 1938 онд Зубин, 1939 онд Роберт Трён нар сэтгэл зүйд нэвтрүүлсэн. Мөн эдгээр бүтээлийг Кэттелл 1943 оноос хойш кластерын аргуудын ангиллыг онолын хувьд зааж өгөхөд ашиглаж ирсэн.
Хугацаа
"Кластер" гэсэн ойлголтыг нарийн тодорхойлох боломжгүй. Энэ нь бөөгнөрөх олон аргууд байдгийн нэг шалтгаан юм. Нийтлэг хуваагч байдаг: өгөгдлийн объектуудын бүлэг. Гэсэн хэдий ч өөр өөр судлаачид өөр өөр загвар ашигладаг. Мөн кластерын аргуудын эдгээр хэрэглээ бүр нь өөр өөр өгөгдлийг агуулдаг. Төрөл бүрийн алгоритмаар олсон ойлголт нь шинж чанараараа эрс ялгаатай.
Кластерын аргыг ашиглах нь зааврын ялгааг ойлгох түлхүүр юм. Ердийн кластерын загварт:
- Centroid s. Энэ нь жишээ нь, k-тэдгээрийн бөөгнөрөл нь кластер бүрийг нэг дундаж вектороор илэрхийлдэг.
- Холболтын загвар s. Энэ нь жишээлбэл, зайн холболт дээр суурилсан загваруудыг бий болгодог шаталсан кластер юм.
- Түгээлтийн загвар s. Энэ тохиолдолд кластеруудыг кластерын аргыг ашиглан загварчилж, мета субьектийн статистикийн тархалтыг бүрдүүлдэг. Хүлээлтийг нэмэгдүүлэх алгоритмд хамаарах олон хувьсагчийн хэвийн тусгаарлалт гэх мэт.
- Нягтын загвар s. Эдгээр нь жишээлбэл, DBSCAN (Шуугиантай орон зайн кластерын алгоритм) болон OPTICS (Бүтэц илрүүлэх захиалгын цэгүүд) бөгөөд кластеруудыг өгөгдлийн орон зайд холбогдсон нягт бүс гэж тодорхойлдог.
- Дэд сансрын загвар c. Хоёр бөөгнөрөлд (хамтран кластер эсвэл хоёр горим гэж нэрлэдэг) бүлгүүдийг аль алинаар нь элемент болон тохирох шинж чанаруудаар загварчилдаг.
- Загвар s. Зарим алгоритмд тийм бишмета-сэдвийн үр дүнг гаргаж, зүгээр л мэдээллийн бүлэглэлээр хангах кластерын аргын хувьд боловсронгуй харилцаа.
- График дээр суурилсан загвар. Клик буюу захын хэсгийн хоёр холболт бүрийг кластер хэлбэрийн загвар гэж үзэж болохуйц зангилааны дэд хэсэг. Нийт эрэлтийн сулралыг бараг бүлэглэл гэж нэрлэдэг. HCS кластерын алгоритмд яг ижил нэрийг харуулав.
- Мэдрэлийн загварууд. Хамгийн алдартай хяналтгүй сүлжээ бол өөрийгөө зохион байгуулах газрын зураг юм. Эдгээр загварууд нь мета-субъектийн үр дүнг бий болгохын тулд дээрх нэг буюу хэд хэдэн кластерийн аргуудтай төстэй гэж тодорхойлж болно. Үүнд мэдрэлийн сүлжээ нь үндсэн эсвэл бие даасан бүрэлдэхүүн хэсгүүдийн шинжилгээний шаардлагатай хэлбэрийг хэрэгжүүлэх үед дэд сансрын системийг багтаадаг.
Энэ нэр томъёо нь үнэндээ өгөгдлийн кластерын аргын багц дахь бүх объектыг агуулсан ийм бүлгүүдийн багц юм. Нэмж дурдахад энэ нь кластеруудын харилцан хамаарлыг, тухайлбал, бие биендээ суурилуулсан системүүдийн шатлалыг илэрхийлж болно. Бүлэглэлийг дараах хэсгүүдэд хувааж болно:
- Хатуу төвтэй кластер хийх арга. Энд объект бүр бүлэгт харьяалагддаг эсвэл түүний гадна байдаг.
- Зөөлөн эсвэл бүдэг систем. Энэ үед объект бүр аль хэдийн тодорхой хэмжээгээр аль ч кластерт харьяалагддаг. Үүнийг мөн c-means тодорхой бус кластерын арга гэж нэрлэдэг.
Мөн илүү нарийн ялгааг гаргах боломжтой. Жишээ нь:
- Хатуу хуваах кластер. Эндобъект бүр яг нэг бүлэгт хамаарна.
- Зөрчлийн үзүүлэлт бүхий хатуу хуваалтын кластер. Энэ тохиолдолд объектууд нь ямар ч кластерт хамаарахгүй бөгөөд шаардлагагүй гэж үзэж болно.
- Давхардсан бөөгнөрөл (мөн олон үзэлттэй хувилбар). Энд объектууд нэгээс олон салбаруудад хамаарах боломжтой. Ихэвчлэн хатуу кластерууд оролцдог.
- Шаталсан кластерын аргууд. Хүүхдийн бүлэгт хамаарах объектууд мөн эцэг эхийн дэд системд хамаарна.
- Дэд орон зай үүсэх. Хэдийгээр давхцаж буй кластеруудтай төстэй боловч өвөрмөц тодорхойлогдсон системийн хүрээнд харилцан бүлгүүд давхцаж болохгүй.
Заавар
Дээр дурдсанчлан кластерийн алгоритмуудыг кластер загварт үндэслэн ангилж болно. Дараах тоймд эдгээр зааврын хамгийн тод жишээг л жагсаах болно. Нийтлэгдсэн 100 гаруй алгоритм байж болох тул бүгдээрээ кластертаа загвар өгдөггүй тул амархан ангилах боломжгүй.
Объектив зөв кластер хийх алгоритм алга. Гэхдээ дээр дурдсанчлан заавар нь үргэлж ажиглагчийн харах талбарт байдаг. Нэг загварыг нөгөөгөөсөө илүүд үзэх математикийн шалтгаан байхгүй бол тодорхой асуудалд хамгийн тохиромжтой кластерийн алгоритмыг туршилтаар сонгох шаардлагатай болдог. Нэг төрөлд зориулагдсан алгоритм нь ихэвчлэн ажиллахгүй гэдгийг тэмдэглэх нь зүйтэйэрс өөр сэдвийг агуулсан өгөгдлийн багц. Жишээ нь, k-дундууд нь гүдгэр бус бүлгүүдийг олох боломжгүй.
Холболтод суурилсан кластер
Энэ нэгдэл нь шаталсан загвар гэсэн нэрээрээ ч алдартай. Энэ нь объектууд хол байгаа хэсгүүдээс илүү хөрш зэргэлдээ хэсгүүдтэй илүү холбоотой байдаг гэсэн ердийн санаан дээр суурилдаг. Эдгээр алгоритмууд нь объектуудыг холбодог бөгөөд тэдгээрийн зайнаас хамааран өөр өөр кластер үүсгэдэг. Бүлгийг голчлон кластерын өөр өөр хэсгүүдийг холбоход шаардагдах хамгийн их зайгаар тодорхойлж болно. Боломжит бүх зайд бусад бүлгүүд үүсэх бөгөөд тэдгээрийг дендрограмм ашиглан дүрсэлж болно. Энэ нь "шаталсан кластер" гэсэн нийтлэг нэр хаанаас гаралтай болохыг тайлбарладаг. Өөрөөр хэлбэл, эдгээр алгоритмууд нь өгөгдлийн багцын нэг хуваалтыг өгдөггүй, харин өргөн хүрээний эрх мэдлийн дарааллыг өгдөг. Тодорхой зайд бие биентэйгээ ус зайлуулах хоолой байдаг нь түүний ачаар юм. Дендрограммд y тэнхлэг нь бөөгнөрөл нийлэх зайг илэрхийлдэг. Мөн бүлгүүдийг холихгүйн тулд объектуудыг X шугамын дагуу байрлуулсан байна.
Холболтод суурилсан кластер нь зайг тооцоолох арга барилаараа ялгаатай аргуудын бүхэл бүтэн гэр бүл юм. Зайны функцүүдийн ердийн сонголтоос гадна хэрэглэгч холболтын шалгуурыг шийдэх хэрэгтэй. Кластер нь хэд хэдэн объектоос бүрддэг тул түүнийг тооцоолох олон сонголт байдаг. Алдартай сонголтыг нэг хөшүүргийн бүлэг гэж нэрлэдэг бөгөөд энэ бол арга юмUPGMA эсвэл WPGMA (арифметик дундажтай жингүй эсвэл жигнэсэн хосуудын нэгдэл, мөн дундаж холбоосын кластер гэж нэрлэдэг) агуулсан бүрэн холбоос. Түүнчлэн, шаталсан систем нь бөөгнөрөл (тус тусдаа элементүүдээс эхэлж, тэдгээрийг бүлэг болгон нэгтгэх) эсвэл хуваах (бүрэн өгөгдлийн багцаас эхэлж, хэсэг болгон хуваах) байж болно.
Тархсан кластер
Эдгээр загвар нь хуваалт дээр үндэслэсэн статистиктай хамгийн нягт холбоотой. Кластерууд нь ижил тархалтад хамаарах объектууд гэж хялбархан тодорхойлж болно. Энэ аргын ашигтай шинж чанар нь хиймэл өгөгдлийн багц үүсгэх аргатай маш төстэй юм. Тархалтаас санамсаргүй объектыг түүвэрлэх замаар.
Эдгээр аргуудын онолын үндэс нь маш сайн боловч загварын нарийн төвөгтэй байдалд хязгаарлалт тавихгүй бол хэт тохируулга гэх нэг гол асуудал тулгардаг. Илүү том холбоо нь өгөгдлийг илүү сайн тайлбарлаж, зөв аргыг сонгоход хэцүү болгодог.
Гаусын хольцын загвар
Энэ арга нь хүлээлтийг нэмэгдүүлэх бүх төрлийн алгоритмуудыг ашигладаг. Энд өгөгдлийн багцыг ихэвчлэн санамсаргүй байдлаар эхлүүлсэн, өгөгдлийн багцад илүү сайн нийцүүлэхийн тулд параметрүүдийг нь давталттайгаар оновчтой болгосон Гауссын тархалтын тогтмол тоогоор загварчлагддаг. Энэ систем нь орон нутгийн оновчтой байдалд ойртох болно. Тийм ч учраас хэд хэдэн гүйлт өгөх боломжтойөөр үр дүн. Хамгийн нягт кластерийг авахын тулд шинж чанаруудыг ихэвчлэн хамаарах Гауссын тархалтад хуваарилдаг. Мөн зөөлөн бүлгүүдийн хувьд энэ шаардлагагүй.
Түгээлтэд суурилсан кластер нь эцсийн эцэст шинж чанаруудын хоорондын хамаарал, хамаарлыг тогтоох цогц загваруудыг бий болгодог. Гэсэн хэдий ч эдгээр алгоритмууд нь хэрэглэгчдэд нэмэлт ачаалал өгдөг. Бодит ертөнцийн олон мэдээллийн багцын хувьд товч тодорхойлогдсон математик загвар байхгүй байж болно (жишээ нь, Гауссын тархалтыг нэлээд хүчтэй таамаглал гэж үзвэл).
Нягт суурилсан кластер
Энэ жишээнд бүлгүүдийг үндсэндээ бусад өгөгдлийн багцаас илүү ус үл нэвтрэх хэсэг гэж тодорхойлсон. Эдгээр ховор хэсгүүдийн бүх бүрэлдэхүүн хэсгүүдийг салгахад шаардлагатай объектуудыг ихэвчлэн дуу чимээ, ирмэгийн цэг гэж үздэг.
Хамгийн алдартай нягтралд суурилсан кластер хийх арга бол DBSCAN (Орон зайн дуу чимээний кластерын алгоритм) юм. Олон шинэ аргуудаас ялгаатай нь "нягт хүрэх чадвар" гэж нэрлэгддэг сайн тодорхойлсон кластерийн бүрэлдэхүүн хэсэгтэй. Холбоос дээр суурилсан кластер хийхтэй адил энэ нь тодорхой зайны босгон доторх холболтын цэгүүд дээр суурилдаг. Гэхдээ энэ арга нь зөвхөн нягтын шалгуурыг хангасан зүйлсийг цуглуулдаг. Энэ радиус дахь бусад объектын хамгийн бага тоо гэж тодорхойлсон анхны хувилбарт кластер нь бүх зүйлээс бүрдэнэ.нягтралтай холбоотой зүйлс (бусад олон аргуудаас ялгаатай нь чөлөөт хэлбэрийн бүлэг үүсгэж болно) болон зөвшөөрөгдсөн хязгаарт байгаа бүх объект.
DBSCAN-ийн өөр нэг сонирхолтой шинж чанар бол түүний нарийн төвөгтэй байдал нь маш бага бөгөөд мэдээллийн сангийн эсрэг шугаман тооны хүрээний асуулга шаарддаг. Мөн ер бусын зүйл бол гүйлт бүрт үндсэндээ ижил үр дүнг олох болно (энэ нь үндсэн болон дуу чимээний цэгүүдийн хувьд тодорхойлогддог, гэхдээ хилийн элементүүдийн хувьд биш). Тиймээс үүнийг олон удаа ажиллуулах шаардлагагүй.
DBSCAN болон OPTICS-ийн гол сул тал нь кластерын хил хязгаарыг илрүүлэхийн тулд нягтрал бага зэрэг буурдагт оршино. Жишээлбэл, хиймэл объектын нийтлэг хэрэглээ болох Гауссын тархалт давхцсан өгөгдлийн багцад эдгээр алгоритмаар үүсгэгдсэн кластерын хил хязгаар нь ихэвчлэн дур зоргоороо харагддаг. Энэ нь бүлгүүдийн нягтрал тасралтгүй буурч байгаатай холбоотой юм. Гауссын хольцын өгөгдлийн багцад эдгээр алгоритмууд нь эдгээр төрлийн системийг нарийн загварчлах чадвартай EM кластер хийх гэх мэт аргуудаас бараг үргэлж давж гардаг.
Дундаж нүүлгэн шилжүүлэлт нь бүх цөмийн тооцоонд үндэслэн объект бүр хөрш зэргэлдээх хамгийн нягт хэсэг рүү шилждэг бөөгнөрөлийн арга юм. Эцсийн эцэст объектууд орон нутгийн үл нэвтрэх дээд цэгт нийлдэг. k-тэдгээрийн бөөгнөрөлтэй адил эдгээр "нягт татагч" нь өгөгдлийн багцын төлөөлөгч болж чаддаг. Гэхдээ дундаж өөрчлөлтDBSCAN-тай төстэй дурын хэлбэртэй кластеруудыг илрүүлж чадна. Өндөр үнэтэй давталттай процедур ба нягтын тооцооллын улмаас дундаж шилжилт нь DBSCAN эсвэл k-Means-аас удаан байдаг. Нэмж дурдахад, цөмийн нягтын тооцоолол нь жигд бус үйлдлээс болж, кластерын сүүлийг хэт их хэмжээгээр хуваахад хүргэдэг тул өндөр хэмжээст өгөгдөлд ердийн ээлжийн алгоритмыг хэрэглэхэд хэцүү байдаг.
Үнэлгээ
Кластерын үр дүнг шалгах нь өөрөө кластер хийхтэй адил хэцүү. Түгээмэл хандлагад "дотоод" оноо (системийг чанарын нэг хэмжүүр болгон бууруулсан) ба мэдээж "гадаад" оноо (бүлэглэлийг одоо байгаа "үндсэн үнэн" ангилалтай харьцуулах) орно. Мөн хүний шинжээчийн гарын авлагын оноо болон шууд бус оноог төлөвлөсөн хэрэглээнд кластер хийх ашиг тустай эсэхийг шалгаснаар олно.
Дотоод далбааны хэмжүүрүүд нь өөрсдийгөө кластерын зорилт гэж үзэж болох онцлогуудыг төлөөлдөг тул асуудалтай тулгардаг. Жишээлбэл, Silhouette коэффициентээр өгөгдсөн өгөгдлийг бүлэглэх боломжтой, гэхдээ үүнийг хийх үр дүнтэй алгоритм байхгүй. Ийм дотоод хэмжүүрийг үнэлгээнд ашигласнаар оновчлолын асуудлуудын ижил төстэй байдлыг харьцуулах нь дээр.
Гадна тэмдэгт ижил төстэй асуудал байна. Хэрэв "үндсэн үнэн" гэсэн шошго байгаа бол бөөгнөрөх шаардлагагүй болно. Мөн практик хэрэглээнд ихэвчлэн ийм ойлголт байдаггүй. Нөгөөтэйгүүр, шошго нь өгөгдлийн багцын зөвхөн нэг боломжит хуваалтыг тусгасан бөгөөд энэ нь гэсэн үг биш юмөөр (магадгүй илүү сайн) кластер байхгүй байна.
Тиймээс эдгээр аргуудын аль нь ч эцсийн дүндээ бодит чанарыг дүгнэж чадахгүй. Гэхдээ энэ нь хүний үнэлгээг шаарддаг бөгөөд энэ нь маш субъектив юм. Гэсэн хэдий ч ийм статистик нь муу кластеруудыг тодорхойлоход мэдээлэл өгч чадна. Гэхдээ хүний талаарх субьектив үнэлгээг үгүйсгэх ёсгүй.
Дотоод тэмдэг
Кластерын үр дүнг өөрөө бүлэглэсэн өгөгдөл дээр үндэслэн үнэлэх үед үүнийг энэ нэр томъёо гэж нэрлэдэг. Эдгээр аргууд нь ерөнхийдөө хамгийн сайн үр дүнг бүлгүүдийн дотор ижил төстэй, бага бүлэг үүсгэдэг алгоритмд өгдөг. Кластерийн үнэлгээнд дотоод шалгуурыг ашигласны нэг сул тал нь өндөр оноо авсан нь мэдээлэл хайхад үр дүнтэй хэрэглүүр гаргах шаардлагагүй юм. Түүнчлэн, энэ оноо нь ижил загварыг ашигладаг алгоритмуудад чиглэсэн байна. Жишээлбэл, k- бөөгнөрөл нь онцлогийн зайг оновчтой болгодог гэсэн үг бөгөөд түүн дээр үндэслэсэн дотоод шалгуур нь үүссэн кластерийг хэтрүүлэн үнэлэх магадлалтай.
Тиймээс эдгээр үнэлгээний арга хэмжээ нь нэг алгоритм нөгөөгөөсөө илүү сайн ажилладаг нөхцөл байдлын талаар ойлголт авахад хамгийн тохиромжтой. Гэхдээ энэ нь мэдээлэл бүр бусдаас илүү найдвартай үр дүнг өгдөг гэсэн үг биш юм. Ийм индексээр хэмжигдэх хүчинтэй байх хугацаа нь өгөгдлийн багцад бүтэц байгаа гэсэн нотолгооноос хамаарна. Зарим төрлүүдэд зориулж боловсруулсан алгоритм нь хэрэв олонлог радикал агуулсан байвал ямар ч боломж байхгүйөөр найрлагатай эсвэл үнэлгээ нь өөр өөр шалгуурыг хэмждэг бол. Жишээлбэл, k-дундаж кластер нь зөвхөн гүдгэр кластеруудыг олох боломжтой бөгөөд олон онооны индексүүд ижил форматтай байна. Гүдгэр бус загвар бүхий өгөгдлийн багцад k-дунд болон ердийн үнэлгээний шалгуурыг ашиглах нь тохиромжгүй.
Гадаад үнэлгээ
Ийм төрлийн бөмбөлөгөөр бүлэглэхдээ ашиглаагүй өгөгдөл дээр үндэслэн кластерын үр дүнг үнэлдэг. Энэ нь мэдэгдэж буй ангийн шошго, гадаад тест гэх мэт. Ийм асуултууд нь урьдчилан ангилагдсан зүйлсийн багцаас бүрддэг бөгөөд ихэвчлэн шинжээчид (хүн) бий болгодог. Иймээс лавлагааны иж бүрдлийг үнэлгээний алтан стандарт гэж үзэж болно. Эдгээр төрлийн онооны аргууд нь өгөгдсөн лавлагааны ангиудтай кластержилт хэр ойрхон байгааг хэмждэг. Гэсэн хэдий ч энэ нь бодит өгөгдөлд хангалттай юу эсвэл зөвхөн бодит үнэнтэй нийлэг багцад хангалттай юу гэдгийг саяхан хэлэлцэж байна. Ангиуд нь дотоод бүтцийг агуулж болох тул одоо байгаа шинж чанарууд нь кластеруудыг салгах боломжгүй байж болно. Түүнчлэн, мэдлэгийг нээх үүднээс мэдэгдэж буй баримтуудыг хуулбарлах нь хүлээгдэж буй үр дүнг өгөх шаардлагагүй байж магадгүй юм. Бүлэглэх явцад мета мэдээлэл (ангиллын шошго гэх мэт) аль хэдийн ашиглагдаж байгаа тусгай хязгаарлагдмал кластерийн хувилбарт үнэлгээний зорилгоор бүх мэдээллийг хадгалах нь тийм ч чухал биш юм.
Одоо кластерын аргад юу хамаарахгүй, эдгээр зорилгоор ямар загвар ашигласан нь тодорхой боллоо.
