Konceptuální shlukování je paradigma strojového učení pro klasifikaci bez dohledu, které bylo vyvinuto zejména v 80. letech 20. století. Od běžného shlukování dat se liší tím, že pro každou generovanou třídu generuje popis pojmu. Většina metod konceptuálního shlukování je schopna generovat hierarchické struktury kategorií; více informací o hierarchii naleznete v části Kategorizace. Konceptuální shlukování úzce souvisí s formální pojmovou analýzou, učením rozhodovacích stromů a učením směsných modelů.
Konceptuální shlukování vs. shlukování dat
Konceptuální shlukování samozřejmě úzce souvisí se shlukováním dat, nicméně při konceptuálním shlukování není hnací silou pro vytváření shluků pouze vlastní struktura dat, ale také jazyk popisu, který má žák k dispozici. Statisticky silné seskupení v datech tak nemusí být učícím se subjektem extrahováno, pokud převládající jazyk popisu pojmů není schopen tuto konkrétní pravidelnost popsat. Ve většině implementací byl jazyk popisu omezen na spojování příznaků, ačkoli v COBWEB (viz „COBWEB“ níže) je jazyk příznaků pravděpodobnostní.
Seznam zveřejněných algoritmů
Pro konceptuální shlukování bylo navrženo poměrně velké množství algoritmů. Některé příklady jsou uvedeny níže:
Obecnější diskuse a přehledy konceptuálního shlukování lze nalézt v následujících publikacích:
Příklad: Základní algoritmus konceptuálního shlukování
V této části jsou popsány základy konceptuálního shlukovacího algoritmu COBWEB. Existuje mnoho dalších algoritmů, které používají různé heuristiky a kritéria pro hodnocení „kvality kategorií“ nebo kategorií, ale COBWEB je jedním z nejznámějších. Čtenáře odkazujeme na bibliografii, kde jsou uvedeny další metody.
Datová struktura COBWEB je hierarchie (strom), kde každý uzel představuje daný koncept. Každý koncept představuje množinu (ve skutečnosti vícenásobnou množinu nebo pytel) objektů, přičemž každý objekt je reprezentován jako seznam vlastností s binární hodnotou. Údaje spojené s každým uzlem stromu (tj. konceptem) jsou celočíselné počty vlastností pro objekty v daném konceptu. Například (viz obrázek), nechť koncept obsahuje následující čtyři objekty (opakované objekty jsou povoleny).
Ukázka reprezentace znalostí COBWEB, pravděpodobnostní hierarchie pojmů. V modrých rámečcích jsou uvedeny skutečné objekty, ve fialových počty atributů. Podrobnosti viz text. Poznámka: Diagram má sloužit pouze jako ilustrace struktury dat COBWEB; nemusí nutně představovat „dobrý“ strom pojmů nebo strom, který by COBWEB skutečně zkonstruoval ze skutečných dat.
Tyto tři vlastnosti mohou být například [is_male, has_wings, is_nocturnal]. Pak je v tomto uzlu konceptu uložen počet vlastností [1 3 3], což znamená, že 1 z objektů v konceptu je samec, 3 z objektů mají křídla a 3 z objektů jsou noční. Popis konceptu je kategoriálně podmíněná pravděpodobnost (likelihood) vlastností v uzlu. Tedy vzhledem k tomu, že objekt je členem kategorie (konceptu) , pravděpodobnost, že je samec, je . Podobně pravděpodobnost, že objekt má křídla, a pravděpodobnost, že objekt je noční nebo obojí, je . Popis pojmu lze tedy jednoduše zadat jako [ .25 .75 .75], což odpovídá -podmíněné pravděpodobnosti rysu, tj.
Obrázek vpravo ukazuje strom pojmů s pěti pojmy. je kořenový pojem, který obsahuje všech deset objektů v datovém souboru. Koncepty a jsou potomky konceptu , z nichž první obsahuje čtyři objekty a druhý šest objektů. Koncept je také rodičem konceptů , , a , které obsahují tři, dva a jeden objekt. Všimněte si, že každý nadřazený uzel (relativní nadřazený koncept) obsahuje všechny objekty, které obsahují jeho podřízené uzly (relativní podřízené koncepty). Fisher (1987) v popisu COBWEB uvádí, že v uzlech jsou uloženy pouze celkové počty atributů (nikoli podmíněné pravděpodobnosti a nikoli seznamy objektů). Případné pravděpodobnosti se podle potřeby počítají z počtů atributů.
Popisný jazyk COBWEB je „jazykem“ pouze ve volném smyslu, protože je plně pravděpodobnostní a je schopen popsat jakýkoli koncept. Pokud se však na pravděpodobnostní rozsahy, které mohou pojmy představovat, uvalí omezení, získá se silnější jazyk. Například můžeme povolit pouze pojmy, u nichž se alespoň jedna pravděpodobnost liší od 0,5 o více než . Podle tohoto omezení by žák nemohl vytvořit pojem jako [.6 .5 .7]; pojem jako [.6 .5 .9] by však byl přístupný, protože alespoň jedna pravděpodobnost se liší od 0,5 o více než . Při takových omezeních tedy získáme něco jako tradiční pojmový jazyk. V omezujícím případě, kdy pro každý rys, a tedy i pro každou pravděpodobnost v pojmu musí být 0 nebo 1, je výsledkem rysový jazyk založený na konjunkci; to znamená, že každý pojem, který lze reprezentovat, lze pak popsat jako konjunkci rysů (a jejich negací), a pojmy, které takto popsat nelze, reprezentovat nelze.
Ve Fisherově (1987) popisu COBWEBu je měřítkem, které používá k hodnocení kvality hierarchie, Gluckova a Corterova (1985) míra kategoriální užitečnosti (CU), kterou ve svém článku znovu odvozuje. Motivace této míry je velmi podobná míře „informačního zisku“, kterou zavedl Quinlan pro učení rozhodovacích stromů. Již dříve bylo ukázáno, že CU pro klasifikaci založenou na příznacích je stejná jako vzájemná informace mezi proměnnými příznaků a proměnnou třídy (Gluck & Corter, 1985; Corter & Gluck, 1992), a protože tato míra je mnohem známější, vycházíme zde ze vzájemné informace jako míry „vhodnosti“ kategorie.
To, co chceme vyhodnotit, je celková užitečnost seskupení objektů do určité hierarchické kategorizační struktury. Máme-li k dispozici množinu možných klasifikačních struktur, potřebujeme určit, zda je jedna z nich lepší než jiná.