ЎҚув материаллари

9-маъруза. Таксономия усуллари ва тажриба берилганларини бошланғич таҳлили


Кластерли таҳлил (cluster analysis) – берилганларни тўплаш, танлов объектлари ҳақидаги маълумотларни сақловчи ва уларни бир жинсли гуруҳларга нисбатан тартиблашни бажарувчи кўп ўлчамли статистик процедурадир. Кластеризация масалалари “ўқитувчисиз ўргатиш” масалалари синфига киради.

Кластерли таҳлил қуйидаги асосий вазифаларни бажаради:

• 
  Турларга ажратиш ёки классификацияни қайта ишлаш;
  
• 
  Объектларни гуруҳлаш учун фойдали концептуал схемалар тадқиқоти;
  
• 
  Берилганларни тадқиқ қилиш асосида гипотезалар топиш;
  
• 
  Гипотезаларни текшириш.
  

Кластеризациянинг мақсади:

• 
  Берилганларни кластерли структурасини аниқлаш орқали тушуниш.
  
• 
  Танловни ўхшаш объектлар гуруҳларига ажратиш кейинги қадамдаги берилганларни қайта ишлаш ва қарор қабул қилишни осонлаштиради. Яъни, ҳар бир кластерга мос таҳлил усули қўлланилади (“ажратиб ол ва ҳукмронлик қил” стратегияси).
  
• 
  Берилганларни камайтириш. Агар танлов керагидан ортиқ катта бўлса, ҳар бир кластердан 1 тадан, энг катта ўхшаш вакил қолдирилади.
  
• 
  Янгиликларни аниқлаш (novelty detection). Ҳеч қайси бир кластерга кирмайдиган гуруҳланмаган объектларни ажратиб олинади.
  

Биринчи ҳолда кластерлар сони камайтиришга ҳаракат қилинади.
Иккинчи ҳолда ҳар бир кластер ичида объектлар ўхшашлиги энг юқори даражада бўлиши муҳим, кластерлар сони истаганча бўлиши мумкин.
Учинчи ҳолатда энг катта эътибор ҳеч бир кластерга кирмайдиган объектларга қаратилади. Бу барча ҳолатда иерархик кластеризация қўллаш мумкин, яъни, катта кластерлар кичик кластерларга, кичик кластерлар ўз навбатида яна ҳам кичикроқ кластерларга ва ҳ.к. ажратилиши мумкин.
Бундай масалалар таксономия масалалари дейилади. Таксономиянинг натижаси дарахт кўринишидаги иерархик структура бўлади.
Гуруҳлаш усуллари. Гуруҳлаш (кластеризация) усулларининг умумий қабул қилинган синфланиши йўқ, лекин, бир нечта ёндашув гуруҳларга бўлиш мумкин:
1. Эҳтимолли ёндашув. Ҳар бир қаралаётган объект k синфдан бирига тегишли деб қаралади. Уларга қуйидагилар киради:

• 
  K-means;
  
• 
  K-medians;
  
• 
  EM-алгоритм (Expectation-maximization (EM) algorithm);
  
• 
  FOREL алгоритмлар оиласи;
  
• 
  Дискриминантли таҳлил.
  

2. Сунъий интеллект тизимларига асосланган ёндашув алгоритмлари:

• 
  C-means;
  
• 
  Кохонен нейрон тўри;
  
• 
  Генетик алгоритм.
  

3. Мантиқий ёндашув. Дендрограммаларни қуриш қарор дарахтлари ёрдамида амалга оширилади.
4. Назарий – графли ёндашув алгоритмларига гуруҳлашнинг графли алгоритмларини келтириш мумкин.
5. Иерархик ёндашув. Бу гуруҳ алгоритмлари агломератив (бирлаштирувчи) ва дивизив (ажратувчи) гуруҳларга ажралади. Аломатлар сонига қараб монотетик ва политетик классификация усулларига ажралади. Бунга иерархик дивизив гуруҳлаш ёки таксономия усулини келтириш мумкин.
6. Юқоридагилардан фарқли бошқа усуллар:

• 
  Кластеризациянинг статистик алгоритмлари;
  
• 
  Кластеризаторлар ансамбли;
  
• 
  KRAB алгоритмлар оиласи;
  
• 
  “Элаш” усули асосидаги алгоритм;
  
• 
  DBSCAN.
  

Санаб ўтилган усуллар ўртасида фарқлар бўлишига қарамасдан барчаси компактлик гипотезасига таянади, яъни, объектлар фазосида барча яқин объектлар бир кластерга, барча фарқли объектлар мос равишда турли кластерларга тегишли бўлишлари шарт.

K-means усули. K-means (k-ўртача) усули 1950 йилларда Гуго Штейнгауз ва Стюард Ллойдлар томонидан бир вақтда кашф қилинган кластеризациянинг энг машҳур усулидир. Алгоритмнинг мазмуни кластер нуқта (объект)ларининг шу кластер марказидан квадратик оғишининг йиғиндисини минимизация қилишга ҳаракат қилинади:

бу ерда k – кластерлар сони, - олинган кластерлар, ва - эса векторларнинг масса маркази.
Икки ўлчамли аломатлар фазосида алгоритм намойиши:

Берилган барча нуқталар ва тасодифий танланган бошланғич нуқталар

Бошланғич марказларга тегишли нуқталар. Текисликни Воронов диаграммасига ёрдамида бошланғич марказларга нисбатан бўлиш.

Кластерлар янги маркази ҳисобланади. (масса маркази изланади)

Марказлар силжимай қолгунча олдинги қадамлар такрорланади.

K-means усулининг камчиликлари:

• 
  квадратик оғишнинг йиғиндиси нинг глобал минимумга эришиши кафолатланмайди, фақат локал минимумлардан бирига эришади
  
• 
  натижа кластер бошланғич марказларини танлашга боғлиқ, уларни оптимал танлаш номаълум.
  
• 
  Кластерлар сонини олдиндан билиш керак.