015 clustering kmeans
dbislab
https://www.youtube.com/watch?v=Zq5w9l-QdJI

Transkript (automatisch erstellt)

0:00 abschließend für das kapitel informationssuche und data mining noch ganz kurzen thema clustering dass auch ein elementares problem ist im data
0:10 mining bereich wir haben eine menge von objekten gegeben und das ziel hier ist eine ein gutes clustering also eine gute gruppierung die objekte zu finden
0:19 basierend auf den eigenschaften der objekte und in diesem fall haben wir einen 3d koordinatensystem und die eigenschaften die objekte inspektor drei
0:29 eigenschaften nämlich ein wert pro dimension man sieht hier dem in dem einfachen beispiel dass sich hier drei cluster
0:38 ergeben würden von roten blauen und braunen punkten die hier zusammengefügt sind das heißt mathematisch ausgedrückt möchte man eine menge von objekten
0:55 betrachten wir reden hier von dem von der menge und wir haben eine distanz funktion de gegeben dts hd bildet partner von objekten ab in
1:05 den raum airplus also die positiven realen zahlen was nichts anderes ist als die distanz zwischen zwei objekten
1:14 dann besteht die aufgabe des castings und das wasserproblem daraus die objekte aus zu gruppieren und laster so dass die distanz zwischen den punkten eines
1:28 clusters also innerhalb eines gastes kleines und die distanz zwischen den einzelnen clustern groß ist ist das hier ist die in 3 cluster distanz hier und
1:40 hier reden wir von der intel cluster distanz wo wir die distanz zwischen zwei cluster eben betrachten und das ist so das ziel
1:51 osmani hat es gibt verschiedene varianten des clustering problems man kann betrachten das cluster des jungs sind
2:00 man kann betrachten das objekt in mehreren lastern drin liegen können man kann betrachten dass objekte mit wahrscheinlichkeiten zu den einzelnen
2:10 klassen zugewiesen werden und so weiter setzt ist eine vielzahl von verschiedenen techniken die hier möglich sind wir betrachten relativ einfaches
2:20 setup aber auch wenn sie interesse daran haben und diesem themengebiet wir bieten auch eine vorlesung an informationen triebel peter meining wo auch hier mehr
2:29 techno technologien oder algorithmen vorgestellt werden wir betrachten diese folgen wie gesagt ein relativ einfaches clustering
2:40 sogenannte exklusive clustering das heißt hier ist ein objekt genau einem cluster zugeordnet das heißt diese menge die wir betrachten der ursprünglichen
2:53 objekte dieser wert in einer anzahl von clustern überführt oder begeistert diese gestern in vc-1 bis ca und wenn wir die vereinigung von allen diesen cluster
3:06 bilden mit den elementen dort drin erhalten wir natürlich unsere ursprüngliche menge diese cluster sind paarweise des jungen
3:18 dh ein radweg gehört wirklich nur zu einem cluster wenn wir so einen klasse betrachten zum beispiel c i write laster von punkten
3:30 also eine menge punkte drin dann können wir für dieses laster einen so genannten prototypen berechnen oder auch schwerpunktzentrum oder mittelbar
3:42 durchschnitt genannt wird ihren dem fall durch dieses mühe beschrieben das können zum beispiel hier sehr punkt sein
3:51 der punkt kann muss aber nicht unbedingt ein echter punkt sein und dieser prototyp beschreibt das cluster die qualität eines clustering durchlass der
4:06 ring wäre eben die berechnungen der eine menge von clustern für eine menge uhr also ich habe jetzt diesen ruhe und habe jetzt eine menge von diesen clustern und
4:19 kann jetzt berechnen wie gut dieser cluster sind für meine menge und alle diese zusammengenommen diese mengen dass das was man als clustering bezeichnet
4:31 diese qualität ist castings wird berechnet oder in der regel berechnet durch den quadratischen fehler zwischen den objekten der einzelnen cluster um
4:43 den prototypen der cluster das heißt wir gehen her und berechnen können sie erstmal diesen teil an für alle iks aus dem cluster ci die quadratische distanz
5:00 quadratischen fehler zwischen in diesem mix unter dem durchschnitt oder eine prototypen dieses clusters
5:10 das machen wir für alle punkte xj aus diesem cluster ci und das machen wir auch für alle cluster von ii gleich 1 sk wenn wir von der dimension ahlen punkten
5:26 reden oder von punkten im dimensionalen raum beben die berechnung von der distanz nichts anderes als die summe die summe der quadratischen fehler zwischen
5:39 leben objekt und dem objekt dass dieses objekt repräsentiert ihm sind wir von diesen prototypen
5:56 dass der ring ist nicht immer eindeutig im allgemeinen nicht eindeutig denn wie sie hier sehen können wenn sie sich dieses beispiel der schwarzen punkte
6:05 betrachten und die frage stellen wie viele cluster sehen sie da es kann verschiedene antworten geben und die sind alle valide das nicht so dass eine
6:13 antwort schlechte wäre also eine andere oder unsinn liga wäre als der andere und konnten daher gehen und sagen ja wir haben zwei cluster 12 könnte auch sagen
6:22 wer nicht genau hinguckt sehe ich hier vier cluster 1234 oder eben hier oben rechts für den fall habe ich sogar sechs cluster die ich hier sehe das heißt man
6:35 kann nicht von vornherein sagen ich habe gleich fünf cluster aber der tat gleich sechs cluster visiten cluster man hat allerdings in einfachen rhythmen oft
6:43 diese vorgabe dass man k class der berechnen möchte es gibt auch ansätze geben diese parameter car der anzahl der klasse die man brechen möchte nicht
6:53 spezifizieren sondern verschiedene cluster berechnen die am ende wo das kann eine variable ist mit dem man die daten anschauen kann
7:04 aber das auch nicht auch nicht relevant für diese vorlesung hier betrachtet ja mal und schrank zu motivieren einen naiven brute force ansatz der besteht
7:19 aus folgenden drei schritten wir berechnen wir generieren alle möglichen cluster rings eins nach dem anderen nochmal das ganze wirklich deutlich zu
7:31 machen clustering so ein clustering ist wirklich die berechnung von clustern für die daten und ein cluster wer zb so ein c1 und c2 und c3 das mindeste cluster
7:49 und das ganze hier die 123 wäre ein glas der weg und konnten sich auch ein anderes clustering vorstellen wo vielleicht das c1 müssen anders
7:59 ausschaut und das tc2 bleibt wegen mir gleich und die hat man noch einen c3 dass wir ein anderes kasse eine andere möglichkeit diese punkte in
8:10 verschiedene cluster zu fassen also wir betrachten die ersten schritt alle möglichen cluster rings aber alle möglichen möglichkeiten cluster über
8:18 diese punkte zulegen und wir betrachten eins nach dem anderen brechen immer diesen quadratischen feder der zuvor definiert war und wählen dann das
8:28 clustering aus das ist ein clustering sein wählen das clustering aus mit den kleinsten fehler ja das clustering der erste fehler hier in den folien du weißt
8:42 dass dieser ansatz unbrauchbar denn es gibt viel zu viele klasse längst die ausprobiert werden müssten wenn wir kaká cluster erzeugen möchten und haben
8:52 in objekte dann haben wir kaum möglichkeiten diese klasse zu berechnen dass wir haben chaos enden viele cluster rings wenn wir davon ausgehen dass
9:04 einige von den clustern leer sein können das sieht harmlos aus ist allerdings nicht harmlos 450 objekte haben und drei cluster pro
9:19 clustering betrachten möchten haben wir drei hoch 50 verschiedene clustering also verschiedene möglichkeiten die daten zu pflastern
9:29 das ist diese zahl die ich jetzt hier nicht vorlesen möchte brauche sie sehen daran dass diese zahl recht groß ist recht groß auch für so einfache
9:39 problemstellungen wie 50 objekte und drei cluster pro cluster also das ist vollkommen unmöglich dieses clustering problem so naiv zu lösen
9:51 das kann man auch das ganze einschränkt noch ein bisschen weiteren sagen na ja das darf keine leeren pflaster geben ok
10:00 dann diese anzahl von cluster rings von möglichkeiten daten zu clustern wenn man keine leeren pflaster erlaubt wird ausgedrückt durch die sterling zahl der
10:09 zweiten art die cool aussehende definition sehen sie runden das hat mich wichtig dass ich die definition der gri merken
10:17 wichtig ist dass diese zahl mit anzahl der objekte und anzahl der clusters als cluster pro clustering eben diese zahl ist auch das müssen sie sich nicht
10:29 merken aber sie müssen sehen dass es auch sehr groß ist und auch diese einschränkung auf nicht leere cluster macht das problem nicht wirklich
10:35 einfacher denn auch das ist sehr hoch die sein sei viel zu hoch und das ganze wirklich für realistische problemstellungen oder auch nur für
10:43 diese kleine problemstellung eben zu berechnen der kamins clustering algorithmus löst das problem von diesen sehr hob vielen cluster rings die
10:58 angeschraubt werden müssten durch einen credit ansatz credit ansatz bedeutet dass wir hier von einer initialen auswahl von clustern beginnen und diese
11:12 cluster nach und nach besser machen die erste beobachtung hier ist dass jedes cluster durch einen mittelpunkt in
11:22 sohland android oder prototypen repräsentiert wird das hatten wir vorher schon so definiert dass innovation cluster und hier seht ihr wie eben der
11:32 dezentral und hier sind anderes kaster noch ein cluster und hat dieses cluster mit den zehen treten und wenn wir jetzt hergehen brachten
11:43 einen raum von datenpunkten das ist unser also schon zwei dimensionalen eine menge von punkten was muss jetzt macht ist er
11:58 wählt zufällig kam objekte von diesen blauen objekten aus und diese objekte dienen uns als centro etat zum beispiel würde man diesen punkt auswählen würde
12:10 diesen punkt auswählen und diesen punkt auswählen dann im nächsten schritt und jedes objekt dem centro zugewiesen der die geringste distanz hat also man würde
12:27 offensichtlich dieses objekt hier diesem zentrum zu weisen ebenfalls dieses objekt und vermutlich auch dieses objekt und dieses objekt auch bei diesem hier
12:42 das geschlecht zu sehen ich denke auch dass das hier noch dazu gehören würde das heißt man hätte so dass hier wäre schon mal das erste cluster dann sieht
12:51 man das zweite gast um diesen centro eaton herum wurde aus genau hinschauen aus diesem punkt ganz sicher bestehen
13:01 und auch aus diesem punkt und vielleicht sogar sagen wir mal dass dieser punkt nicht dazu gehören das heißt man hätte so ein cluster wie folgt dann ist das
13:15 eher für diesen zentren da steht eben was den anderen übrigen objekt das heißt man hätte schon so ein ideales kaster ringe gebe
13:23 mit drei klassen wie gewünscht wenn wir vier cluster hätten haben wollen dann würden wir eben vier in soziale zentren aussuchen und so weiter so was jetzt
13:32 gemacht wird im nächsten schritt berechnet für jedes dieser cluster einen neuen zentrum zum beispiel würde man sagen gut dem
13:44 beispiel wäre hier vielleicht dieses hier der bessere centro eat für das cluster dass auch anfragen der cluster dass man würde dann sagen naja dieser
13:54 naja das war zu viel dieser dieser punkt hier wird jetzt der neue centro eed und was macht man auch für die anderen pflaster im falle der
14:05 und entlaste sieht man aber auch dass diese zentrierten die schon gewählt wurden relativ gut ausschauen das würde sich hier würde nichts nichts
14:11 mehr passieren das heißt wir haben diese 433 pinkfarbenen centro eaton dahin hat sich geändert die anderen hat sich nicht geändert okay das löschen wir wieder die
14:22 cluster die wird zuvor gebildet haben und ordnung jetzt wieder diese einzelnen punkte den clustern sie zertreten zu wir sehen dass hier durch die änderung dass
14:33 er sich verschoben hat wie ein neues pflaster bekommen nehmen hieß es hier und die anderen beiden wurden jetzt in dem in dem beispiel gleich bleiben
14:42 abgesehen davon dass der punkt sich unten natürlich verschoben hat dessen hätte dann so etwas und so etwas
14:52 die farben haben jetzt geändert ist nicht so schlimm dass sie haben wir gesehen dass die initiale war zentrierten sich leicht geändert hat in
14:59 diesem orange farbenen fall und das ganze wiederholt beim jetzt weiter und weiter bis ich nichts mehr ändert das heißt sozialgeld manka zentren aus man
15:13 weist den objekten den nächstgelegenen android hinzu das ist dieses dieses bild einen clustering und dann bilden dann berechnet man für jedes für jedes
15:25 cluster den 19 treten und fügt dann und weiß dann wieder den objekten die die centro eaton zu die am nächsten dran liegen und so weiter deshalb muss es
15:34 hier dargestellt zufällige auswahl von pacentro eaton usw zuordnung der objekte zu den nächstgelegenen neuberechnung der der
15:44 centro iden und bissig nichts mehr ändern das heißt die zehen treten gleich bleiben wird der rhythmus ausgeführt und termine dann wenn eben sich nichts
15:53 geändert und wir haben dann das finale clustering und in der illustration hier oben könnte es tatsächlich so ausschauen dass dies hier unsere finales clustering
16:02 ist nach und einer integration ja so etwas ausführlichere animation des problems wir haben in dem fall fähig 14 treten sie sehen dass diese durch diese
16:17 iks schwarz nächste aber markiert sind und wir haben auch schon die punkte den einzelnen zentren zugewiesen wir haben hier im genau hinschaut hier so ein paar
16:29 rote punkte und dann die blauen punkte grün und orange haben punkte rechtecke weitergehen würden wir die centro eaton der cluster neu berechnen sie haben
16:43 gesehen dass sie das dx ist hier dass sich verschoben haben zumindest für das orangefarbene das blaue und das grüne cluster dann rechnen
16:51 wir neu die zuweisungen der objekt zu den clustern ja sehen hier dass ich hier gerade bei den roten bereich und auch was getan hat dann berechnen wir wieder
17:03 die neuen zentren weißen wieder ihre rechte zu und so weiter und wir machen das so lange bis sich die centro eaton nicht mehr ändern und das also die
17:17 konnten wir die idee der algorithmus konvergiert wenn sich die klasse nicht mehr ändern
17:25 es gibt es noch ein bisschen weiter wenn wir die gleiche schritt immer immer neue berechnungen der centro ettenberg
17:33 der cluster dann basierend auf den neuen zentren die zuteilung der daten auf die cluster auf die zehen treten und so weiter ebene sich nichts mehr tut
17:49 wir sehen hier das im letzten schritt sich nichts mehr geändert hat das heißt hier würde der kamins algorithmus eben diese determinieren und wir während
18:03 fertig und hätten unser clustering berechnet kamins der name kaminski ist klar dass die anzahl der cluster und wiens im englischen für durchschnitt das
18:14 ist es eben genau dann die aussage dass wir hier k centro edeka prototypen durchschnitt und so weiter berechnet das heißt er könnte auch k s android
18:23 algorithmus heißen heißt aber kamins sagt das gleiche aus in dem fall ein sehr einfacher algorithmus sie hat natürlich ein paar probleme
18:32 darüber nachdenken was hier passieren kann ist dass die auswahl von dem parameter kann natürlich eine rolle spielt nämlich vier nämlich fünf die
18:41 mich drei nämlich zehn nämlich 15 und so weiter dass die wahl von kmu sowie sind sinnvoll bekannt sein und zum anderen natürlich sollte die initiale
18:51 auswahl der k10 truiden er hat es braucht eine rolle und sollte dann eben eventuell ein paar mal durch probiert werden das heißt man würde die initialen
19:01 centro eaton oder würden algorithmus mit verschiedenen stadtzentren ausführen wurde dann in verschiedene klassen bekommen würde dann die die qualität der
19:11 cluster rings berechnen und dann am ende das darin zurück liefern das den besten fehler hatte die kleinsten fehler hat gewisse dinge die man hier ändern kann
19:21 oder einfach an kranke verbessern kann in dem einfachen algorithmus noch mal ganz kurz das übersicht die initialen zentrierten wird nun
19:34 zufällig ausgewählt das heißt die daten die auf den staaten gleich bleiben durch die zufällige auswahl kann das verschiedene cluster rings geben
19:43 wir berechnen den centro iten als mittelwert im englischen daherkommen wärme distanz maß würde öffentlicher weise die kritische distanz benutzt
19:55 werden der algorithmus konvergiert kann man zeigen die ersten operationen sind natürlich die stärksten integration wo
20:03 am meisten passiert und am ende wenn nichts mehr passiert oder nur sehr wenig passiert dann darf der rhythmus terminieren und hier sehen sie auch noch
20:10 die komplexität des algorithmus angegeben inflation ja das ist auch das ende des kapitels informationssuche und daytime einigen
20:22 nochmal einen algorithmus herausgegriffen der sehr bekannte ist der kamin algorithmus denke es nicht sehr schwierig zu verstehen
20:29 durch diese animation öffentliches klar wie der funktioniert natürlich muss man sich jetzt gedanken machen dass man auch in der klausur in der lage sind zu
20:38 beschreiben dass man den dollar code angeben könnte dass man die distanzen berechnen kann für so eine einfache ein einfaches beispiel und so weiter ja es
20:49 gibt viele andere clustering algorithmen es gibt viele anderen themen zur informationssuche und ich habe schon zwei mal angesprochen
20:54 mindestens dass wir auch eine vorlesung haben informationen und data mining die wir alle zwei jahre im sommer anbieten und wenn sie interesse haben an diesem
21:04 themengebiet dann würden wir uns freuen wenn sie da wieder sehen würden und da das markiert das ende des kapitels und dem kommentar titelt gehen
21:14 wir auf die betrieblichen datenbanksystemen oder betriebliche informationssysteme spezielle datenbank systeme im detail ein