Кластерли таҳлил

Кластеризация усуллари

Кластеризация усулларининг умумий қабул қилинган синфланиши йўқ, лекин, бир нечта ёндашув гуруҳларга бўлиш мумкин:
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 усулининг камчиликлари:

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