Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
015 clustering kmeans
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 117 Zeilen
- abschließend für das kapitel informationssuche und data mining noch ganz kurzen thema clustering dass auch ein elementares problem ist im data
- 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
- basierend auf den eigenschaften der objekte und in diesem fall haben wir einen 3d koordinatensystem und die eigenschaften die objekte inspektor drei
- eigenschaften nämlich ein wert pro dimension man sieht hier dem in dem einfachen beispiel dass sich hier drei cluster
- 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
- 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
- den raum airplus also die positiven realen zahlen was nichts anderes ist als die distanz zwischen zwei objekten
- 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
- 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
- hier reden wir von der intel cluster distanz wo wir die distanz zwischen zwei cluster eben betrachten und das ist so das ziel
- osmani hat es gibt verschiedene varianten des clustering problems man kann betrachten das cluster des jungs sind
- man kann betrachten das objekt in mehreren lastern drin liegen können man kann betrachten dass objekte mit wahrscheinlichkeiten zu den einzelnen
- klassen zugewiesen werden und so weiter setzt ist eine vielzahl von verschiedenen techniken die hier möglich sind wir betrachten relativ einfaches
- 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
- techno technologien oder algorithmen vorgestellt werden wir betrachten diese folgen wie gesagt ein relativ einfaches clustering
- 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
- 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
- bilden mit den elementen dort drin erhalten wir natürlich unsere ursprüngliche menge diese cluster sind paarweise des jungen
- dh ein radweg gehört wirklich nur zu einem cluster wenn wir so einen klasse betrachten zum beispiel c i write laster von punkten
- also eine menge punkte drin dann können wir für dieses laster einen so genannten prototypen berechnen oder auch schwerpunktzentrum oder mittelbar
- durchschnitt genannt wird ihren dem fall durch dieses mühe beschrieben das können zum beispiel hier sehr punkt sein
- der punkt kann muss aber nicht unbedingt ein echter punkt sein und dieser prototyp beschreibt das cluster die qualität eines clustering durchlass der
- 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
- 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
- diese qualität ist castings wird berechnet oder in der regel berechnet durch den quadratischen fehler zwischen den objekten der einzelnen cluster um
- 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
- quadratischen fehler zwischen in diesem mix unter dem durchschnitt oder eine prototypen dieses clusters
- 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
- reden oder von punkten im dimensionalen raum beben die berechnung von der distanz nichts anderes als die summe die summe der quadratischen fehler zwischen
- leben objekt und dem objekt dass dieses objekt repräsentiert ihm sind wir von diesen prototypen
- 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
- 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
- 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
- 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
- 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
- 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
- spezifizieren sondern verschiedene cluster berechnen die am ende wo das kann eine variable ist mit dem man die daten anschauen kann
- 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
- aus folgenden drei schritten wir berechnen wir generieren alle möglichen cluster rings eins nach dem anderen nochmal das ganze wirklich deutlich zu
- 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
- 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
- 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
- verschiedene cluster zu fassen also wir betrachten die ersten schritt alle möglichen cluster rings aber alle möglichen möglichkeiten cluster über
- diese punkte zulegen und wir betrachten eins nach dem anderen brechen immer diesen quadratischen feder der zuvor definiert war und wählen dann das
- 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
- 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
- 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
- einige von den clustern leer sein können das sieht harmlos aus ist allerdings nicht harmlos 450 objekte haben und drei cluster pro
- clustering betrachten möchten haben wir drei hoch 50 verschiedene clustering also verschiedene möglichkeiten die daten zu pflastern
- 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
- problemstellungen wie 50 objekte und drei cluster pro cluster also das ist vollkommen unmöglich dieses clustering problem so naiv zu lösen
- das kann man auch das ganze einschränkt noch ein bisschen weiteren sagen na ja das darf keine leeren pflaster geben ok
- 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
- zweiten art die cool aussehende definition sehen sie runden das hat mich wichtig dass ich die definition der gri merken
- 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
- 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
- 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
- diese kleine problemstellung eben zu berechnen der kamins clustering algorithmus löst das problem von diesen sehr hob vielen cluster rings die
- angeschraubt werden müssten durch einen credit ansatz credit ansatz bedeutet dass wir hier von einer initialen auswahl von clustern beginnen und diese
- cluster nach und nach besser machen die erste beobachtung hier ist dass jedes cluster durch einen mittelpunkt in
- sohland android oder prototypen repräsentiert wird das hatten wir vorher schon so definiert dass innovation cluster und hier seht ihr wie eben der
- dezentral und hier sind anderes kaster noch ein cluster und hat dieses cluster mit den zehen treten und wenn wir jetzt hergehen brachten
- einen raum von datenpunkten das ist unser also schon zwei dimensionalen eine menge von punkten was muss jetzt macht ist er
- 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
- 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
- offensichtlich dieses objekt hier diesem zentrum zu weisen ebenfalls dieses objekt und vermutlich auch dieses objekt und dieses objekt auch bei diesem hier
- 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
- man das zweite gast um diesen centro eaton herum wurde aus genau hinschauen aus diesem punkt ganz sicher bestehen
- 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
- 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
- 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
- gemacht wird im nächsten schritt berechnet für jedes dieser cluster einen neuen zentrum zum beispiel würde man sagen gut dem
- 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
- 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
- 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
- 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
- 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
- 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
- abgesehen davon dass der punkt sich unten natürlich verschoben hat dessen hätte dann so etwas und so etwas
- 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
- 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
- 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
- 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
- hier dargestellt zufällige auswahl von pacentro eaton usw zuordnung der objekte zu den nächstgelegenen neuberechnung der der
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- konnten wir die idee der algorithmus konvergiert wenn sich die klasse nicht mehr ändern
- es gibt es noch ein bisschen weiter wenn wir die gleiche schritt immer immer neue berechnungen der centro ettenberg
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- oder einfach an kranke verbessern kann in dem einfachen algorithmus noch mal ganz kurz das übersicht die initialen zentrierten wird nun
- 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
- wir berechnen den centro iten als mittelwert im englischen daherkommen wärme distanz maß würde öffentlicher weise die kritische distanz benutzt
- werden der algorithmus konvergiert kann man zeigen die ersten operationen sind natürlich die stärksten integration wo
- 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
- die komplexität des algorithmus angegeben inflation ja das ist auch das ende des kapitels informationssuche und daytime einigen
- nochmal einen algorithmus herausgegriffen der sehr bekannte ist der kamin algorithmus denke es nicht sehr schwierig zu verstehen
- 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
- 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
- gibt viele andere clustering algorithmen es gibt viele anderen themen zur informationssuche und ich habe schon zwei mal angesprochen
- 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
- 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
- wir auf die betrieblichen datenbanksystemen oder betriebliche informationssysteme spezielle datenbank systeme im detail ein
Zum Nachlesen
K-Means-AlgorithmusEin k-Means-Algorithmus ist ein Verfahren zur Vektorquantisierung, das auch zur Clusteranalyse verwendet wird. Dabei wird aus einer Menge von ähnlichen …
ClusteranalyseUnter Clusteranalyse (Clustering-Algorithmus, gelegentlich auch: Ballungsanalyse) versteht man ein Verfahren zur Entdeckung von Ähnlichkeitsstrukturen in …
Cluster (Datenanalyse)Als Cluster (gelegentlich auch Ballungen) bezeichnet man in der Informatik und Statistik eine Gruppe von Datenobjekten mit ähnlichen Eigenschaften.
Fuzzy-c-Means-AlgorithmusIn der Informatik ist der Fuzzy-c-Means-Algorithmus, auch Algorithmus der c unscharfen Mittelwerte, ein unüberwachter Clustering-Algorithmus, der eine …