TUM Course – “Artificial Intelligence in Automotive Technology” – Lecture 5

TUM Course – “Artificial Intelligence in Automotive Technology” – Lecture 5


dann auch ein hallo von meiner seite erst mal das ist es laut genug von hinten doch okay johannes hat schon gesagt heute der volle oder der letzte termin was das klassische machine learning angeht heute geht es um clustering feedback habt ihr bekommen und wir starten wie immer mit den punkten die ihr aus dem heutigen termin mitnehmen sollte ich sollte verstehen was heißt überhaupt clustering was hat es mit dem mit der mustererkennung zu tun wie es das einzuordnen mit den anderen methoden die wir kennen gelernt haben der regression der klassifikation dann sollt ihr verstehen können was ist die qualität eines clusters wie messe ich diese und wenn ihr ein cluster bekommt der sie analysieren könnt ist es jetzt gut reicht mir dieses cluster für meinen anwendungsfall oder muss sich eine andere methode nehmen eine andere parametrisierung verwenden ihr werdet den begriff des anzugs learning heute kennenlernen im vergleich zum super weiß learning gibt es dort keine geregelten trainingsdaten und sie sollte auch dort verstehen was ist der workflow wie sind anzuweisen learning probleme aufgebaut wenn es um clustering geht lernen wir natürlich auch verschiedene klassischen methoden kennen es wird einmal eigentlich reich isches cluster sein termins und ein density oder ein lichter basiertes cluster verfahren und durch die übung sollte auch lernen diese methoden anwenden zu können und als letztes sollt ihr wenn ihr aus dieser vorlesung heraus geht auch im täglichen leben oder im studium wo immer ihr seid erkennen können dieses problem ist es ein problem dass ich eher mit reaktionen angehe ist es ein problem der klassifikation des clusters oder vielleicht eine kombination verschiedener methoden dann geht es los mit einem überblick über clustering wieder eine textbuch definition hier ruping aufs zimmer jüngst bei der close to gather sometimes surrounding something es geht also um dinge die irgendwie ähnlich sind irgendwie dicht beieinander und die wollen wir in klassen packen oder in gruppen packen also ähnliche sachen in ein klasse andere sachen in eine andere klasse jetzt ist ein bild von euch das ist mein blick auf euch und letztes mal habe ich euch ja schon ein bisschen kennen gelernt ich habe euch klasse klassifiziert als studentin ich wusste wir sind hier in einer universität wir sind im vorlesungssaal ihr hört mir zu deshalb habe ich euch als studentin klassifiziert jetzt will ich euch näher kennenlernen aber sie ungefähr 100 studenten so viel zeit habe ich nicht jetzt zu jedem hinzugehen ich habe mir auch gar nicht alles merken wenn ich jetzt mit jedem sprechen trotzdem will ich irgendwie mehr informationen über euch clustering bietet da eine möglichkeit und das erste was ich mache ist dass sich die features von euch extrahieren ich nehme die position von euch und legt mir das als punkte in den 23 das heißt ich hätte hier jetzt die reihe nach oben und den sitzplatz und jeder punkt repräsentiert eine person der mensch mit einer gut mustererkennung sie direkt hier irgendwelche zusammenhänge also hier ist ein zusammenhang zwischen den punkten die gehören auch irgendwie zusammen aber vielleicht ist es hier auch dass es zwei kleine sind und hier auch also wir kennen zwar zusammenhängen aber wir sind oder ich bin mir nicht ganz sicher wie gehört es jetzt zusammen nehme ich jetzt mal an dass ich mit dieser einordnung in vier gruppen zufrieden bin dann könnte ich jetzt zu einem hingehen und ihn fragen erzählt etwas über dich und dann würde ich zum beispiel kennenlernen oder erfahren dass er ein sportler ist und weil er da in dieser gruppe mit diesen drei anderen sitzt nämlich von da an alles klar das trifft auch auf die anderen elemente dieses clusters zu und wenn wir bin ich erst so weitergehen würde dann hätte ich für jede dieser cluster 1 stereotypen wenig darauf alle anderen elemente dieses clusters anwenden kann es ist also eine kombination aus clustering und klassifizierung erst bilden gruppen danach frage ich ein aus der gruppen- oder eine teilmenge der gruppe nach mehr information und diese information wenn ich dann auf alle anderen elemente dieser gruppe an so kann ich wenn ich nur vier elemente hier näher untersuchen informationen über alle elemente entziehen wie ist das jetzt einzuordnen in den gesamtzusammenhang unserer vorlesung wir sind immer noch im bereich der mustererkennung letztes mal hatten wir oder vorletztes mal hat mir die regression nochmal zusammengefasst was war das wir bilden bei der regression einen kontinuierlichen ausgabewert und es ist eine super weist learning methode das heißt wir haben geregelte trainingsdaten und wir als beispiel die wir wieder die wohnungspreise wir haben eine größe der wohnung wollen den preis bestimmen und können dann mit der regression auch für vorher unbekannte werte den entsprechenden preis ermitteln bei der klassifikation ging es um diskrete ausgabe werte und wieder war es mit geregelten trainingsdaten das beispiel dass sich ihr letztes mal hatte war wieder mit häusern wir wollen wissen ob das haus teuer oder günstig ist wenn wir also ein die features von einem haus eintragen den die größe und den preis können wir anhand der klassen grenze sehen dieses haus ist teuer oder günstig wie sie jetzt mit dem clustering aus wir haben wieder diskrete ausgabe werte aber der unterschied ist ist es an zu beweist was genau das ist erkläre ich nachher noch aber erstmal heißt es wir haben keine gelernten trainingsdaten wir wissen also gar nicht so viel über diese elemente die wir clustern wollen sondern wir schmeißen eine große menge an daten einfach dem algorithmus hin und sagen findet man zusammenhänge findet malgruppen darin findet struktur da drin und so könnten wir zum beispiel wenn wir jetzt auf der suche nach einer neuen wohnung sind cluster bilden mit wohnung die uns interessieren oder die wir eher uninteressant finden wenn wir also die wohnung in verschiedene bereiche eingeteilt haben zb hier ein cluster mit zwei zimmer wohnung hier ein cluster mit fünf zimmer wohnungen und wir haben ein elemente heraus angeschaut und finde es gut dann können wir darauf schließen dass wir wahrscheinlich auch die anderen elemente dieses clusters gut finden und so können wir unsere suche beim wohnungskauf einschränken auf die cluster auf die gruppen von wohnungen die uns wirklich interessieren paar beispiele zu der regression auch wir hatten die hauspreise gerade die verkaufszahlen oder dieses gewicht einer größe das gewicht einer person in abhängigkeit von der größe war der klassifikation aus der fahrzeugtechnik die objekterkennung mit kameras spam erkennung aus dem alltag oder die tumor detektion also ist ein tumor gutartig oder bösartig beim clustering jetzt neu erst mal gen sequenzen wir können also anhand einer gen sequenz verschiedene lebewesen kategorien es ist ein säugetier ist es ein reptil zum beispiel bei google news können wir themen zu einem bestimmten zu einer bestimmten schlagzeile in gruppen geliefert bekommen oder bei aus der fahrzeugtechnik bei laserscannern können wir die punktwolken die wir die wir bekommen auch clustern und damit die elemente der fahrzeuge die wir erkennen kombinieren wie läuft es ab mit dem platz training wir haben erstmal unser daten z wir haben nicht ein element und wir haben ein ganzes set eine menge wieder mit featuren diese feature schmeißen wir in den clustering algorithmus und er baut cluster raus also verschiedenen gruppen bei den google news zum beispiel sind die wörter features es geht darum was ist ähnlich zueinander und wir bekommen cluster raus bei den gegen sequenzen ist genauso es geht wieder um ähnlichkeiten zwischen gen sequenzen und bei punktwolken vom leader ist es auch wieder es geht um ähnlichkeiten und es werden cluster erzeugt das prinzip sollte also klar sein beispiel aus der fahrzeugtechnik hier haben wir vier felder wir haben einmal oben links ein kamerabild oben rechts haben wir die punktwolken des leaders und links klassifizierte bereiche aus der aus dem videostream und unten rechts eine kombination aus klassifizierten elementen oder bei klassifizierten bereichen aus dem video und den punktwolken unten seht ihr ein workflow erst können punkte oder punktwolken beim leader klassifiziert werden dann kann eine teilmenge dieser punkte über das videobild klassifiziert werden und sodann die objekt eigenschaft auf das gesamte cluster der punkt wolke übertragen werden so kann man dann deutlich effizienter die objekte der diktieren da nicht mehr alle punkte klassifiziert werden müssen sondern nur noch teilmengen der cluster wenn ihr nach clustering sucht werdet ihr oft auf den begriff segmentation stoßen beide wörter könnt ihr analog verwenden das glas trinkt kommt er aus dem statistischen hintergrund wo es um methodik geht bei segmenten wird oft im business bereich gesprochen wo es eine sagt marktsegmentierung zum beispiel gibt also mitklatschen könnt ihr cluster erzeugen oder gleich bedeuten auch segmente und mit der segmentierung könnt ihr auch cluster erzeugen also beide wörter könnt ihr gleich verwenden hier in der vorlesung wird er das wort clustering benutzt dann gehen wir jetzt mehr auf das training oder die genauere bedeutung des castings ein erstmal eine formelle die funktion wir haben unsere menge der elemente diese wollen wir ein cluster aufteilen natürlich können wir kein cluster bilden das irgendwie aus unserer elemente menge heraus ragt das heißt unsere cluster befinden sich alle in unserer elemente menge und wenn wir so wie hier zwei cluster in dieser menge bilden gibt es immer noch elemente die daneben liegen hier in diesem beispiel das heißt hier würden alle elemente die nicht in den beiden klassen liegen zur einen dritten cluster zugeordnet werden dass wir zum beispiel dann rauschen nennen könnten also einen rausch cluster was aber wichtig ist dass am ende alle elemente der der unseres also alle elemente unseres raumes einem cluster zugeordnet sind und dass kein element zwei clustern gleichzeitig zugeordnet ist es darf also keine sich überschneidenden cluster geben dann hat jedes cluster einen repräsentanten ein element das stereo typisch für all die anderen elemente in diesem cluster steht dafür können wir den mittelwerten oder um dieses element zu berechnen können wir ein mittelwert berechnen was bei distanzen zum beispiel sehr leicht ist jedes cluster wird auch definiert durch die oder bewertet durch die variabilität das ist die distanz aller elemente eines clusters zudem repräsentanten wenn ich also hier sechs punkte habe wer mein repräsentant des clusters der punkt in der mitte und die variabilität wäre der abstand aufsummiert von allen punkten des clusters zu diesem repräsentanten was klassisches bedeutet ist dass wir die summe der variabilität über alle cluster minimieren wollen es ist eigentlich ganz leicht ist ob die musik optimierungs problem was ist denn die kleinste variabilität die ein cluster bekommen kann also was ist der wir wollen dass sie minimieren also was ist der kleinste wert erst mal den wir hier erzielen können ja wohl richtig distanzen sind meistens positiv manche metriken erlauben negative aber selbst dann wird es hier noch quadrat weshalb hier bei der variabilität als minimalsten wert eine null bekommen wann ist der wert oder wann ist die variabilität eines clusters 0 was müsste dafür gelten also wie können wir jetzt ein ganz leichtes cluster aufbauen um eben hier diesen tag zu minimieren wie müssten wir die repräsentanten zu unseren punkten lägen genau also wenn wir unsere repräsentanten immer genau auf unseren daten punkt legen also nicht so wie hier sondern dass wir für jedes element ein eigenes cluster haben haben wir die variabilität auf null damit haben wir auch die summe hier auf 0 und damit hätten wir das perfekte cluster also clustering heißt nicht nur dass wir diese summe minimieren wollen sondern wir brauchen eine einschränkung und genau da wird clustering es spannend was könnte eine einschränkung sein wir könnten oder wir werden die anzahl an clustern beschränken also wir wollen nicht hier in diesem fall sechs cluster sondern wir minimieren das mit k dass unsere menge der cluster ist festgesetzt auf zum beispiel 3 das würde hier bedeuten dass wir drei cluster bilden müssen zum beispiel so und dieses kann richtig zu wählen und zu wissen alles klar mit dieser anzahl an gruppen oder mit dieser anzahl an clustern kann ich meine daten richtig repräsentieren das ist die schwierigkeit beim clustering hier ist die distanz erwähnt deshalb einmal ganz kurz das heißt überhaupt distanz wie setzt lässt sich distanz berechnen gibt es drei häufig benutzte metriken einmal die manhattan metrik die von der straßenaufbau in manhattan kommt wo man durch die durch das straßenraster nicht einfach diagonal gehen kann sondern man immer ums eck gehen muss das heißt um zu diesem punkt zu kommen hätte ich eine distanz von 2 während ich hier einst habe die kritische distanz so wie wir sie alle kennen hier können wir diagonal gehen wie bei kago was hätten wir dann wurzel 2 zu diesen wieder eins und djs distanz die nur die maximale verschiebung in eine achse betrachtet wodurch hier die distanz zu jedem benachbarten feld eins wären was wir häufig benutzten werden ist die quadrate kritische distanz quartiert ist daraus oder quartiert ist es keine richtige metrik mehr aber da wir nur abstände zwischen zwei punkten und keine addition von verschiedenen distanzen oder kombination haben können wir auch quartieren und sparen uns dadurch eine wurzel berechnung in der kalkulation unseres clusters wir sind also effizienter dann kommen ganz kurz noch zur klassifikation wir hatten gelernt klassifikation wir haben gläubige trainingsdaten ist es zu beweisen und wir haben feste klassen wir wissen also hier vorne bei einer dartscheibe wir haben eine klasse bei der wir drei punkte bekommen eine klasse bei der bbe ein punkt zwei punkte bekommen und ein klasse bei der wir nur einen punkt bekommen beim clustering fallen diese klassen erst mal weg wir wollen daten die dann nach ähnlichkeit sortieren wir wissen aber nichts über diese daten erst mal wollen wir also irgendwelche gruppen bilden klasse bilden und wir wollen dass die elemente die in einem cluster sind sich sehr ähnlich sind und dass zwei elemente aus verschiedenen clustern sich stark unterscheiden noch mal der große unterschied zur klassifikation dabei ist dass wir nicht wissen wie viele klassen wir haben nicht wissen welche klassen wir haben und wo wird es genutzt wir hatten eben schon ein paar beispiele allgemein kann man sagen das clustering häufig ein vorprozess ist für eine weitere datenverarbeitung wenn man sehr große datenmengen hat ist es schwierig alle daten zu bewältigen und durch clustering kann man sich eben teilmengen daraus extrahieren die trotzdem generalisiert das wissen über die gesamte menge darbieten hier vorne bei dem beispiel mit den dort fallen können wie zum beispiel jetzt drei cluster erkennen und wenn wir jetzt wüssten wie wir diese pfeile geschossen haben nämlich zwei pfeile oder an zwei teile normal andere teile mit geschlossenen augen und andere teile mit der linken hand könnten wir hier dann anschließend nach der clusterbildung einzelne stadtteile untersuchungen und würden dann zum beispiel erfahren dieser darf wurde mit links geworfen und deshalb nehmen wir an dass auch wir die anderen teile aus diesem cluster mit links geworfen wurden wir können also nachträglich wenn wir ein cluster haben das genau analysieren kurzer recap nochmals zum super weiß learning wir haben gelüste trainingsdaten extrahieren oder teils auf in einem trainings at geben dies dem klassifiziert oder es kann auch regression sein je nachdem was für ein superbes learning problem wir haben und passen damit die klassengrenzen oder die parameter an und danach evaluieren wir das mit einem test an super weiß learning sieht etwas anders aus wir haben unsere unsortierten unbekannten daten natürlich wieder mit feature live extrahieren kann und wir schmeißen sie dem clustering algorithmus zu und sagen mach mal wir können nichts mehr wirklich vergleichen haben keine label wir wissen zu wenig über diese daten aber trotzdem können wir mit dem oder mit den clustern immer noch überlegen wie gut sind diese cluster sind wir damit zufrieden also dieser ganze schritt mitgeteilt diese daten auf fällt weg und wir haben keine label wie beurteile ich jetzt ob ein cluster gut ist oder schlecht wenn wir überlegen wir berechnen distanzen dann wäre es ja praktisch wenn wir einfach die distanz zu unseren repräsentanten immer minimieren also dass die abstände innerhalb eines clusters sehr klein sind wenn wir das überlegen wenn neben k einfach sehr groß fast jeder fast jedes element hat jetzt ein eigenes cluster wir haben also insgesamt sehr geringe distanzen die wir berechnen wunderbar aber wir lernen nichts daraus wir passen uns damit einfach nur unseren trainings daten an analog zu dem zur klassifikation als zur regression wäre das over fitting wir spezialisieren uns zu sehr auf unsere trainings daten so dass wir kein allgemeines bild kein wissen mehr aus diesen daten extrahieren können weiß ja das eigentliche ziel von machine learning ist dass wir aus daten wissen generieren auf der anderen seite wenn wir ganz klein wählen gleich eins nur ein großes klasse haben sind zu stark generalisiert also die wahl von k bewirkt ob man sich zu sehr richtung ufer fitting oder zu sehr generalisierung oder zusätze generalisierung bewegt die distanz alleine ist also kein richtig gutes qualitäts maß für uns wir hatten eben schon die ähnlichkeit angesprochen die ähnlichkeit der elemente in einem cluster nehmen wir vorne an wir haben zwei cluster die ähnlichkeit ist die durchschnittliche distanz der elemente in einem cluster ja ich möchte also die ähnlichkeit für dieses element bestimmen und berechnet die durchschnittliche distanz von diesem element zu allen anderen elementen innerhalb des clusters und dabei wollen wir möglichst kleine werte bekommen also ein kleiner wert hier ist gut dann gibt es noch das gegenteil nämlich den unterschied hier wollen wir die distanz wieder die durchschnittliche durch distanz von einem element zu allen anderen elementen des nächst nehren clusters bestimmen die in diesem fall ist es leicht weil wir haben nur zwei cluster das ist klar welches dann am nächsten ist also wenn ihr das für dieses element hier bestimmen wollen müssen wir von hier die distanz zu allen elementen ist anderen clusters berechnen wenn wir diese beiden parameter haben dann können wir den silhouetten koeffizienten des clusters bestimmen hier haben wir das verhältnis zwischen der ähnlichkeit und des unterschiedes zwischen den elementen zweier cluster und das können wir für jedes einzelne element bestimmen und wenn wir das über alle elemente eines clusters mitteln bekommen wir die silhouette des clusters und wir können es natürlich auch über unsere gesamte menge berechnen und haben dadurch dann ein qualitäts maß für einzelne elemente wie gut ist dieses element den gegebenen clustern zugeordnet wie gut ist ein cluster selbst und wie gut ist die menge an unserer elemente geclustert diese silhouette ist immer zwischen minus eins und eins und wenn wir einen sehr großen unterschied haben oder der unterschied der cluster deutlich größer ist als die ähnlichkeit dann geht unsere silhouette gegen eins das ist gut wir wollen möglichst dicht an der einst sein wenn die werte in etwa gleich sind dann geht die suhler silhouette gegen null und wenn der unterschied deutlich größer ist als die ähnlichkeit dann gehen wir gegen -1 und da wo wir nicht hin als richtwert kann man sagen das werden die silhouette größer 0,7 ist können wir zufrieden sein mit unserem cluster jetzt haben wir erstmal genug zu der qualität und dem clustering allgemein schauen wir uns den ersten clustering algorithmus an die das hierarchische clustering es läuft so ab dass erst mal alle allen elementen ein eigenes cluster zugeordnet wird dann fängt man an die cluster zu suchen die am ähnlichsten sind und kombiniert die so geht man einfach alle elemente durch bis dann alle elemente schließlich in einem großen pflaster liegen hier vorne sind a und b erst mal am dichtesten zusammen dann sehen wir das c und d auch dich zusammen sind dann ist der abstand da ist unsere jetzige situation der abstand zwischen diesen beiden clustern kleiner als zwischen diesen clustern weshalb wir hier kombinieren und schließlich bleibt nur noch die kombination der beiden übrigen cluster jetzt haben wir alle elemente in einem großen pflaster aber da wollten wir ja nicht hin wir wollten ja entweder oder wir hatten gesagt wenn wir gleich 1 wählen dann haben wir es zu stark generalisiert wenn wir zu klein wählen also hier sind sind wir zu spezialisiert was hat uns das also gebracht wenn wir uns das so aufzeichnen können wir an der hierarchie erkennen wo es vielleicht eine gute ebene um das zu trennen wir müssen also wir müssen selber dann entscheiden welches kbw das irakische clustering bietet und es erst mal nur eine visuelle natürlich auch numerische angabe darüber was vielleicht empfehlenswert ist es hilft uns eigentlich nur zu entscheiden wie wählen wir jetzt unser k wenn wir hier distanzen bestimmen bestimmt nicht mehr distanzen zwischen zwei punkten sondern wir bestimmen distanzen zwischen zwei clustern und das müssen wir es auch noch vor anschauen da gibt es drei möglichkeiten einmal single link wo die kürzeste distanz zwischen zwei elemente aus den beiden clustern gewählt wird als distanz das wäre dann hier vorne complete link wo die größtmögliche distanz zwischen den beiden clustern gewählt wird also die beiden punkte die am weitesten voneinander wegfliegen das wäre dann also überdeutlichen das sind die beiden cluster und david link wo die durchschnittliche distanz zu allen anderen elementen des anderen clusters herangezogen wird also drei verschiedene möglichkeiten um zwei oder die distanz zwischen zwei clustern zu bestimmen am häufigsten werden wir das single link verwenden was ich eben schon aufgezeichnet habe mit der kombination der verschiedenen clustern nennt sich denn programm da haben wir unsere wurzeln mit einem cluster in dem alle elemente enthalten sind unten haben wir jeweils cluster die nur ein element haben und durch die kanten kombinieren wir zwei cluster zusammen immer nur zwei cluster und durch die durch die länge der kanten können wir denn dass die distanz zwischen der beiden cluster erkennen hier sehen wir also dass wir hier eine sehr große distanz haben das heißt es wäre praktisch hier vorne unser cut zu machen unser car zu wählen und dann mit zwei clustern herauszugehen das ist eine klasse enthält damit die 78 und die 9 und das andere cluster die restlichen daten denn programm habt ihr vielleicht auch schon mal so gesehen hier aus der tierwelt um hunde darzustellen oder die verwandtschaft zwischen hunden es geht hier oben los mit drei clustern einmal die kojoten die wölfe und die hunde und so wird es immer weiter aufgesplittet hierarchisches clustern funktioniert nicht immer so gut hier vorne sehen wir eine punkt wolke und wollen die cluster wenn wir da jetzt mit hierarchischen clustern herangehen bekommen wir diese aufteilung dieses programm und es ist immer genau dieses bereiches clustern ist also deterministisch es ist nichts zufälliges es gibt keine parameter die wir irgendein stellen es kommt immer genau diese aufteilung heraus und vorne haben wir unseren silhouetten koeffizienten für jedes element in diesem cluster hier haben wir null hier haben wir 1 -1 werden hier hier der kath mit elementen die blau sind und hier unten die darunter die andere klasse und wir sehen dass unser koeffizient relativ schlecht ist für viele elemente sogar negativ ist wir sehen also diese aufteilung an elementen in diese zwei cluster ist schlecht sehen wir vorne auch ist auch eine schwierig aufzuteilen eine menge hier und sieht schon ganz anders aus ein denn programm wo wir hier einen großen abstand haben was wieder heißt wir haben zwei cluster gut voneinander getrennt und den silhouetten koeffizient sehr hoch also fasst bei 1 für einige elemente und natürlich gibt es auch hier wieder elemente die nicht so gut bewertet sind das werden dann elemente die genau zwischen den clustern liegen die zu beiden klassen ähnlichkeiten haben aber insgesamt hat hier die zuordnung sehr gut funktioniert und wir haben einmal die optische rückmeldung durch das programm also hier einen großen abstand und wir haben die numerische rückmeldung dass eben der südsee letten koeffizient für diese cluster sehr hoch ist und können damit dieses cluster als qualitativ hochwertig bewerten gehen wir mal ein beispiel mit städten durch wir haben zum beispiel eine flotte selbstfahrende fahrzeuge und wir wollen diese besser auf den auf die städte aufgeteilt haben als wir wollen zwei cluster bilden und die fahrzeuge fahren immer nur zu stätten aus dem eigenen cluster wenn wir hier wieder ein programm bauen wollen schreiben wir erst mal unsere städte auf also wir sehen in dieser tabelle die abstände zwischen den verschiedenen städten der abstand zwischen boston und new york zum beispiel 206 kilometer und wir sehen auch direkt das ist der kleinste abstand den wir in dieser tabelle haben wir würden also anfang boston und new york in ein cluster zulegen als nächstes das haben wir auch den stift wieder dabei werden also ein cluster mit boston und new york was ist der nächste kleinere abstand welche städte könnten wir noch kommune oder welche cluster können wir noch kombinieren wir hatten hier die 206 zwischen boston und new york dadurch hier schon ein cluster und die nächst kleinere distanz zu einem anderen cluster wer hier chicago mit 802 kilometer wir würden also diese beiden cluster kombinieren als nächstes haben wir san francisco und seattle mit 808 kilometern distanz also kombinieren wir hier san francisco und seattle jetzt ist die frage was mir denn wir machen denn war hat zum einen ein kleiner abstand zu chicago wenn wir also nach dem single ding prinz prinzip clustern würden müssten wir denn war mit unserem boston new york chicago cluster kombinieren wenn wir aber komplett link betrachten und nach dem größten abstand der beiden cluster sortieren dann sehen wir hier das denn wahr einen großen abstand zu boston hat der abstand zu ostern francisco und seattle aber kleiner ist das heißt nach complete link müssten wir denn war san francisco und seattle zu ordnen das heißt es macht also einen unterschied nach welchem kriterium man cluster vergleicht ich habe gesagt wir bleiben bei single link deshalb sieht unser finalisten programm so aus dieser schritt am ende wo wir alle kombinieren ist natürlich ein bisschen überflüssig wir können auch einfach vorher schon aufhören und damit die 1 fahrzeuge in diesem cluster fahren lassen und die rest den rest der flotte nur zwischen diesen städten zur bewertung des griechischen clustering es ist genetisch wir haben keine parameter die wir ändern müssen wir müssen nur unsere elemente haben wir müssen ein maß für die distanz bestimmen und ansonsten gibt es nichts was wir irgendwie noch anpassen müssten es ist oder es bringt eine schöne visualisierung und zusammenhänge zwischen verschiedenen klassen und es ist deterministisch das heißt es bringt immer den gleichen das gleiche cluster und wir müssen uns keine sorgen machen dass wir zufällig irgendwie mal was schlechtes getroffen haben sondern wir kommen immer das gleiche klasse mit der gleichen qualität nicht so gut beim griechischen clustering ist die laufzeit mit von n3 sind wir relativ ineffizient und wie schon gesagt es bietet das bringt am ende alle elemente in ein cluster und wir müssen selber wählen wo auf dem weg dahin machen wir den cut wohl sagen wir diese aufteilung die cluster finden wir gut das heißt wir müssen am ende nochmal selbst drauf schauen und das finale clustering auswählen bevor wir zu den nicks methoden gehen machen wir jetzt eine kleine pause und in fünf minuten machen wir weiter okay machen wir langsam weiter mit dem hierarchischen clustering sind wir durch wir gehen zunächst methode und zwar kamins erst mal die idee hinter der methode wir wollen die variabilität innerhalb eines clusters minimieren und wir wollen die summe der variabilität über alle cluster auch minimieren das ist jetzt die formelle definition vom anfang noch mal einfach in worte gefasst also wenn wir eine große summe habe ist es klasse ring schlecht wenn wir eine kleine summe haben haben wir es gut geklappt hat und dabei natürlich wieder mit einem fixen kam also mit einer bestimmten anzahl an klassen clustern in die wir die menge aufteilen wollen das ganze ist sehr rechenintensive hier steht np hart sagt euch np hat was also ist eine komplexität klasse es gibt vielleicht habt ihr schon mal von dem gleich mp problem gehört beides komplexität klassen als eselsbrücke das p sind die klassen die man zum beispiel in nok lösen kann mp probleme sind probleme die er so aussehen also exponentielle laufzeit benötigen nicht mehr in poley nominal zeit laufen wir können so was also rechnerisch nicht einfach umsetzen und nutzen aber es gibt neue ristic es gibt ein algorithmus der uns dahin bringen kann er findet nicht immer das globale optimum und ist ein greedy algorithmus der lokale optimal findet und das heißt wir müssen dann noch bestimmte richtig nutzen damit wir nicht in einem kleinen lokalen optimum hängen bleiben sondern dass wir immer eine möglichst optimale lösung finden wie läuft es also ab gegeben haben wir unsere daten und die anzahl an klassen die wir daraus generieren wollen dann fangen wir mit einer initialisierung an und wählen für jede klasse einen repräsentanten zufällig aus unsere menge heraus hier fangen wir einfach mal an und wählen unsere drei repräsentanten im nächsten schritt weisen wir die elemente der menge immer dem nächstgelegenen repräsentanten zu also hier wird einfach die distanz berechnet und wir ordnen die elemente den klassen zu im nächsten schritt berechnen wir für jedes cluster einen neuen repräsentanten und zwar den mini den mittelwert deshalb heißt es auch so aus diesem cluster das heißt unsere repräsentanten hier würden sich in die mitte des clusters verschieben das sind dann keine elemente mehr aus unserem raum zu beginn sondern sind einfach gemittelte werte also es muss nicht mehr genau auf einen anderen punkt treffen sondern es kann auch daneben liegen und so hätten wir dann für jedes cluster 1 repräsentanten und haben hier eine ganz klare trennung war bei dem beispiel ist jetzt jetzt erreicht und sehen wir später auch war eine sehr schöne wahl wie wir zufällig unsere ersten elemente gewählt haben wie sieht es aus wenn es ein bisschen komplexer ist hier haben wir wieder eine menge auf den ersten blick sieht der mensch schon ja hier und da da könnte man cluster machen wir fangen hier einfach mal an und wählen gleich vier wir wollen vier cluster innerhalb dieser menge bestimmen und der erste schritt ist wir wählen zufällig elemente aus dieser menge als repräsentanten hier sind jetzt vier repräsentanten gewählt und die elemente den clustern oder die elemente den repräsentanten zugeordnet das sieht natürlich noch nicht so gut aus der nächste schritt ist für jedes cluster wieder den neuen repräsentanten zu bestimmen wieder den mittelwert aus allen elementen dieses clusters zu bilden für die drei roten punkte wird das zum beispiel bedeuten dass der mittelwert er nach da wandert für dieses cluster müsste der mittelwert oder der repräsentant nach dort beim blauen etwa nach da der schwarze bewegt sich auch näher zu mitte dadurch dass wir die repräsentanten verschoben haben verschiebt sich natürlich auch die zuordnung der elemente zu den klassen hier ist jetzt dieser rote punkt neu zu der roten class hinzugekommen wenn wir jetzt wieder die neuen repräsentanten für diese klasse bestimmen heißt es also dass hier dadurch dass wir einen neuen punkt bekommen haben sich der mittelwert weiter verschiebt und auch hier da habe ich das ein element zu einer anderen klasse gegangen ist nicht der repräsentant auch wieder weiter zum mit dem verschiebt im nächsten schritt ist wieder ein neues element dazu kommen in der roten klasse der rote repräsentant wandert also immer weiter nach oben während hier unten der schwarze zum beispiel schon relativ festes dort wird nichts mehr passieren jetzt ist dieser ehemals rote punkt zum blauen cluster über gewandert das heißt das blaue cluster wird sich auch wieder verschieben der rote wird weiter nach oben wandern weil wieder ein neuer roter punkt dazu gekommen ist und jetzt sehen wir schon dass wir deutlich bessere aufteilung haben wir sehen dass die elemente farblich gut sortiert sind wir machen noch einen schritt und wenn wir jetzt oder wir haben gesehen dass ich jetzt keine zuordnung mehr zu in clustern verändert hat das heißt wenn wir jetzt das gleiche nochmal machen würden würden wir immer den gleichen repräsentanten bekommen weil die zuordnung die cluster sind jetzt stabil und an dieser stelle können wir dann aufhören also wenn wir diesen kreis immer weiter durchlaufen und irgendwann merken alles klar unsere repräsentanten bewegen sich nicht mehr dann brechen wir es ab und haben hier unseren finale oder unsere vier finalen cluster jetzt was hier relativ leicht einfach zu sagen mit dem k gleich vier aber wie wählt man jetzt klar wenn man die daten nicht so gut kennt ein ansatz ist immer man weiß es einfach man hat irgend experte der experte sagt hier wir brauchen wir brauchen vier cluster wenn wir das nicht haben dann haben wir zwei ansätze wir können einmal einfach brutal alle cast durch probieren und schauen was der beste ist oder mit welchen k wie die beste silhouette bekommen oder wir geben uns ein bisschen cleverer an und nehmen eine teilmenge unsere elemente live klassifizieren wollen werden darauf zum beispiel das hierarchische clustern und generieren uns da raus so ein bisschen dieses expertenwissen dass wir an der teilmenge erkennen alles klar hier wäre eine klasse größe von ungefähr vier gut und dann kann man nachher immer noch von 4 3 und 5 die cluster bestimmen also dann geht man nicht mehr brutal alles durch sondern grenzt den suchbereich schon mal etwas ein statt nämlich reichlichen clustering könnte man natürlich auch die teilmenge mit kamins schon mal vor clustern schauen wir uns das an wie man’s macht wenn wir einfach brutal durchgehen hier haben wir rechts unsere daten wir haben hier gleich zwei gleich eins ist trivial da hätten wir nur einen cluster und auf der linken seite haben wir die silhouette für alle elemente und wir sehen schon hier oben dieses cluster bei sieht eigentlich ganz gut aus also hier das cluster kann man einen schon zu lassen aber hier unten vor allem in diesem bereich sind einige elemente nicht wirklich gut zugeordnet was machen wir wir gehen einfach weiter erhöhen kam auf dieses cluster hier vorne bleibt unverändert ist wieder genau das gleiche geworden aber wir sehen dass hier bei dem dunklen cluster einige elemente sogar negativ eine negative julia haben das sind dann wahrscheinlich elemente in diesem bereich die sehr ähnlich zu dem hellen cluster sind also der unterschied zu diesem cluster sehr gering ist obwohl wir einen großen unterschied zu einem anderen klasse haben wollen und die ähnlichkeit oder distanz zu klassischen elementen innerhalb des eigenen clusters sehr hoch ist also gleich drei ist er auf jeden fall keine gute wahl gleich vier sieht schon ganz anders aus wir haben kein klasse mehr dass irgendwelche negativen bereiche hat wir sind hier also überall positiv wir haben immer noch das klasse vom anfang unverändert und wir haben ein paar bereiche wo einzelne elemente nicht wieder so ganz gut zugeordnet sind also solche randbereiche erhöhen wir das kann einfach weiter auf 5 sehen wir es deutlich schlechter geworden wieder elemente mit negativen zigaretten deutlich kleinere silhouetten insgesamt von den clustern und gehen wir noch weiter auf 6 sehen wir dass insgesamt also wir waren vor in bereichen hier vorne mit manchen clustern dass wir insgesamt viel schlechter geworden sind von den silhouetten kann man jetzt also abschätzen was ist hier unser richtiges k man können sie einmal sagen ich möchte gleich zwei wm ist ein solides cluster aber dadurch sind wir vielleicht etwas zu generalisiert wenn wir gleich vier wählen haben wir ähnliche ergebnisse nur halt in diesem randbereichen etwas schwierig zuzuordnende elemente aber auf jeden fall können wir hier unsere klasse mit drei und fünf oder auch größer ausschließen jetzt haben wir bei dem car show oder bei dem termin schon mal geklärt wie das kwf aber wir initialisieren haben anfang zufällige elemente als repräsentanten und immer wenn irgendwas zufällig ist kann uns das auch auf schlechte wege leiten wie gehen wir also damit um dass irgendwas zufällig ist oder warum kann überhaupt dadurch irgendetwas schlechtes passieren wenn wir einzelne elemente am anfang als repräsentanten wählen könnte es passieren dass wir unsere repräsentanten sowie hier wählen wir haben hier unten zwei repräsentanten ziemlich dicht beieinander und wenn wir das jetzt so weiterführen dann wird der schwarze repräsentant etwas weiter zur mitte wandern des schwarzen clusters hier wird es sich auch weiter zur mitte bewegen und hier wird der rote sich auch weiter richtung mitte des roten clusters bewegen und der blaue hat keine wahl er muss auch da unten bleiben es wird also nie ein es wird nie einer dieser repräsentanten den weg nach oben schaffen wo wir ihn eigentlich benötigen würden wir haben gesehen mit k gleich wie ist es eigentlich schön pasteurisiert war aber dadurch dass wir hier ungünstig unserer repräsentanz zu beginn gewählt haben werden wir nie auf das gleiche optimum kommen mit auf dass wir eben gekommen sind und werden immer hier ein sehr großes cluster haben das im vergleich zu den beiden kleinen die wir vorhatten deutlich schlechter ist wie können wir das also verhindern wir könnten anfangen in dem wir wieder eine teilmenge unsere elemente nehmen und diese teilmenge clustern das entstandene cluster oder von dem entstandenen cluster können wir dann die repräsentanten nehmen und als unsere stadt repräsentanten annehmen das heißt wir hätten schon mal verhindert dass irgendwelche repräsentanten ganz dicht beieinander gewählt werden und dass sie schon mal in einer teilmenge zumindest das cluster gut treffe oder die menge gut repräsentiert haben wir können ein bisschen weitergehen noch und sagen wir machen nicht nur eine teilmenge sollen wir machen m teilmengen gehen diese teilmengen durch bilden verschiedene repräsentanten zu wählen von diesen dann wieder die den besten repräsentanten aus und den nehmen wir dann an unserer gesamtmenge als unseren staat wehrt was heißt das zusammengefasst wir haben irgendwas zufällig und wenn wir was zu verlegen haben dann hilft es uns oft etwas ganz oft einfach zu wiederholen und immer das beste zu speichern und damit das alles effizient läuft wiederholen wir das nicht an der gesamtmenge sondern wir nehmen eine teilmenge wo wir deutlich schneller sind und können dadurch dann deutlich besser initial werte für unsere richtige für unser richtiges cluster bestimmen jetzt kommt ein video wie keynes angewandt wird auf ja also hier haben wir oben die anzahl aller elemente nennt gleich 1000 verändert sich gleich auch noch darunter k unsere anzahl an cluster in die wir die menge ein teilen wollen oben links sehen wir die integration also wie häufig der algorithmus durchläuft und was ihr gesehen habt ist dass es sich immer cluster der gleichen form gebildet haben ist man immer es waren immer mehr ecke konvexe form es wird immer es werden immer alle elemente die am dichtesten an einem cluster repräsentanten dran sind diesen cluster zugeordnet dh ein cluster ein repräsentant spricht für eine bestimmte fläche und diese fläche sieht immer so aus dass sie eine konvexe form ist und wir können sich hier relativ leicht konstruieren wir nehmen den abstand zwischen zwei punkten aber zwischen zweiter präsenten und teilen ihnen in der mitte durch ziehen also die mittel senkrechte und wissen alle elemente darüber gehören zu diesem cluster alle elemente darunter gehören zu diesem cluster wenn wir das für jedes für jeden repräsentanten machen also immer die mittel senkrechten aus dem abstand ziehen bekommen wir solche konvexen form die die elemente des clusters umfasst häufig haben wir aber probleme wo wir nicht immer solche komplexen formen haben sondern viel komplexere formen das ist einer der nachteile von kevins das eben die form der elemente die geclustert werden können sehr begrenzt ist und immer genau solche formen darstellt gehen wir mal noch mal kurz auf die vorteile ein termins ist durch diese heuristik sehr effizient wir sind also nicht mehr im exponentiellen oder nicht den exponentiellen laufzeiten sondern wir sind sehr schnell mit in unserer anzahl an elementen und da unsere anzahl an clustern t unserer wiederholung die wir den algorithmus durchlaufen mussten und in dem video auch wenn es kurz war vielleicht hat jemand oben gesehen wie viele integration ist auch bei 5.000 elementen war es wurde nie dreistellig also das waren iteration im bereich von 40 wiederholungen das heißt der kleine zahlen es ist sehr leicht anwendbar aber dadurch dass wir immer ein mini bestimmen müssen immer ein mittelwert muss es diesen auch geben hier sind wir bei numerischen daten also die position lässt sich ja leicht numerisch darstellen wenn es sich um daten handelt die wir nicht nur mährisch so repräsentieren können kann es sein dass wir überhaupt kein mittelwert bilden können wir sind relativ anfällig gegenüber von rauschen und wir müssen das ganz klar definieren wir müssen also von vornherein wissen wir werden so viele klasse benötigen und dadurch dass wir am anfang zufällig etwas initialisieren können wir dort auch in probleme laufen und müssen eben die eben genannte touristik anwenden hier seht ihr noch mal wieder an so ein cluster aussehen könnte mit queens wo eben einem repräsentanten immer eine bestimmte fläche zugeordnet wird nennt man dann wohl nie modelle oder wohnflächen und wenn unsere daten die wir clustern wollen so aufgeteilt sind funktioniert es wunderbar aber wenn wir komplexe reformen haben bekommen wir eben probleme es gibt noch varianten des kamins es gibt kein idiot und comedian dabei wird zum einen das problem angenommen oder angriffen dass es diese mittelwerte nicht immer geben kann also wenn wir kein mittelwert bilden kann dann nehmen wir eben das element das am dichtesten in der mitte unserer menge ist wir wählen also ein element aus der tatsächlichen menge raus wir bilden kein künstliches and element wenn wir neben ein element aus unserer menge als repräsentanten der eben unsere unser cluster am besten darstellt oder wenn wir sortierte features haben von den elementen können wir auch den media nehmen als repräsentanten unserer cluster dabei kann man dann auch statt der quadriga ist als die normale distanz verwenden also einfach so kritische distanz dadurch dass wir das quadrat weglassen sind große abstände nicht wieder potenziert so und dadurch werden die ausreisser nicht so stark gewichtet also wenn ein element weit weg ist und wir den abstand dann noch quartieren hat es natürlich noch größere auswirkungen wenn wir den abstand nicht quartieren einfach normal lassen ist diese auswirkung des abstands nicht mehr so und bei diesen zwei methoden ist die grundidee gleich wir wollen wieder die distanz zwischen den clustern zu ihrem repräsentanten minimieren kleiner überblick hier kamins besonders gut für numerische daten wo wir eben diesen mittelwert bilden kann können wenn das nicht der fall ist dann ist amy die heute oder medien besser wir sind mit kamins und median sehr schnell dabei während bei comedia dadurch dass wir unsere element sind nach einem element durchgehen müssen dass das cluster gut repräsentiert er bei einer schlechten effizienz und haben aber dadurch dass wir hier nicht den quadraten abstand nehmen eine bessere sensitivität gegen ausreißern ansonsten bleiben die vor und nachteile gleich es ist einfach zu nutzen aber wir bleiben bei den konvexen form wir bleiben dabei dass wir die anzahl der klassen kennen müssen und wir sind immer noch bei einem credit algorithmus wir haben eine zufällige ins initialisierung das heißt wir können in lokalen minimal laufen ein weiterer oder eine weitere methode zur clustering ist die wie scannen dabei handelt es sich um eine dichte basierte methode den special clustering applications also irgendwas hat das auch noch mit neues zu tun und wir brauchen zwei parameter dafür einmal brauchen wir den ypsilon radius das ist der radius um den wir den bereich um ein element untersuchen und zwar suchen wir in diesem bereich nach der anzahl an punkten und das ist unser zweiter parameter die minimale anzahl an punkten die in einem bereich definiert oder dies in einem bereich um das element von sein muss der arbeit zählt das element selbst auch dazu das heißt hier vorne hätten wir an elementen in unserem app see und radios 1 schauen wir uns das hier unten an unser epson radius mit 1 2 3 4 5 elementen in unserem radius und wenn wir hier unsere unseren parameter auf 5 wählen dann würde das für dieses element in der mitte bedeuten dass wir dieses element zu einem chor element machen also wir schauen uns ein element an zählen wie viele elemente im umkreis des ersten parameters liegen wenn diese zahl größer gleich unserer minimalen anzahl an punkten ist dann wird es ein chor element überprüfen dass für den nächsten punkt hier vorne wie ziehen den epson radius die 10 12 elemente dadurch kann es kein chor element werden aber ein border element denn wir haben ein chor element in unserem radius aber nicht genug um selber ein ko element zu werden deshalb wird es ein border element und wir haben eine dritte klasse an elementen zwar die ausleiher das sind die elemente in deren radius nicht diese mindestens fünf punkte liegen aber auch kein anderes chor element das heißt hier dieses element wird zu einem outlaw was euch jetzt vielleicht hier schon aufgefallen ist es gibt kein parameter k gibt kein parameter der uns sagt mit dem wir sagen wir benötigen hier drei cluster vier cluster sondern diese methode wie die anzahl an clustern selber bestimmen schauen wir dass hier in dem beispiel mal an wir wählen unsere unseren parameter der minimalen punkte mit vier apps i lon wählen wir eins und fangen einfach mal an hier kreise zu ziehen mit abstand 1 oder mit radius 1 dann sehen wir dass wir hier ein chor element haben mit unseren vier elementen im umkreis hier fordern wir auch ein ko allem and und so handeln wir uns durch die elemente durch untersuchen auch die anderen elemente die aber dann border elemente bleiben da nicht genug da nicht genug elemente im umkreis sind aber immerhin ein anderes chor element so hätten wir jetzt hier ein cluster erstellt denn alle elemente die density rippel sind bilden ein cluster das heißt also wenn ich einen punkt haben wir in diesem chor punkt und ich von diesem chor punkt über andere chor punkte ein element erreichen kann gehört es zum gleichen cluster der abstand hier ist so groß deshalb hier vorne das nicht mehr zu unserem cluster zählt wir schauen handelt sich um ein eigenes cluster ist es ein chor element im umkreis ist nur ein anderes element das heißt nein es ist kein chor element das andere element im umkreis ist auch selbst kein ko alam and wir haben also kein border element das heißt wir haben nichts sind out leier wir sind einfach nur rauschen also diese daten hier würden in ein großes cluster und rauschen aufgeteilt werden damit lassen sich dann auch komplexe formen wie hier darstellen indem hier einfach durchgegangen wird mit gleich drei wer hier das erste chor element und so können auch komplexe form gebildet werden und das ganze rauschen können dabei außer acht lassen wir werden wir das noch wir haben beliebige formen wir müssen unsere anzahl an cluster vorher nicht definieren und wir sind nicht mehr anfällig gegenüber rauschen oder ausreißern das ganze kriegen wie sogar einigermaßen effizient hin der nachteil ist dass es relativ schwierig zu parametrisieren ist wir müssen einen abstand wir müssen eine anzahl an elementen wählen und nur kleine veränderungen dort können große veränderungen auf unser cluster bewirken das heißt man muss mit sehr viel feingefühl einstellen jetzt haben wir drei methoden betrachtet kommen wir zu ihren anwendungen wo kann man clustering gebrauchen am anfang habe ich schon mal google news erwähnt oder die gen sequenzen bei google-news werden schlagzahl zu einem oder werden berichte zu einer schlagzeile zusammengefasst aber ohne zu wissen welche schlagzeile ist es eigentlich es werden erstmal nur ähnliche neuigkeiten zusammengefasst und anschließend klassifiziert welche schlagzeile würde jetzt zu diesem bereich passen dann gibt es auch noch krasser zum beispiel in rechenzentren wo module oder rechner die viel miteinander kommunizieren müssen eine schnellere verbindung bekommen als die elemente mit denen sie nur selten kommunizieren einfach um die effizienz innerhalb der rechner gruppe zu erhöhen in sozialen netzwerken kennt ihr cluster wo freunde von freunden vorgestellt werden also wieder gruppen mit ähnlichkeiten geburt werden und natürlich im marketingbereich wo gezielt auf einzelne nutzer eingang wird was nur dadurch erreichbar ist dass diese nutzer bestimmten clustern zugeordnet werden und man weiß was dieses cluster haben möchte bei amazon zum beispiel gibt es produktvorschläge ihr schaut euch vor irgendwelche produkte an und dadurch dass es schon unzählige gesamte daten amazon gibt wissen sie die leute die sich vor diese produkte angeschaut haben schauen sich auch gerne diese anderen produkte an ohne genau zu wissen was das produkt jetzt genau ist es geht einfach nur um ähnlichkeiten wer sich das angeschaut hat schaut sich auch das an bei netflix genauso die vorschläge weil ihr das geschaut habt kommt jetzt das für euch oder ihr top pick genau für dich netflix hatte 2006 eine challenge für oder um eine million dollar wo sie gesagt haben die die einen besseren algorithmus für die film vorschläge programmieren kriegen eine million dollar das heißt sieg verdienen oder durch dieses clustering verdient netflix so viel dass sie einfach mal eine million euro als preisgeld ausschreiben können also clustering ist bei marktsegmentierung markt clustering wo es darum geht persönliche werbung persönliche vorschläge für den kunden zu bringen sehr sehr wichtig aber natürlich braucht man clustering auch im automobilbereich wenn wir viele mobilitäts daten haben können wir die dann zusammen fassen können eine verkehrsanalyse machen können bestimmte gewohnheiten erkennen zb pendler oder bereiche die besonders gern befahren werden daraus können wir dann verallgemeinerte verkehrsfluss generieren deutlich reduziert wir brauchen nicht mehr die unmengen an daten anschauen sondern können unsere repräsentanten anschauen die eben für diese große menge an daten sprechen und wir können daraus wissen extrahieren dass wir dann zum beispiel bei der planung von neuen straßen verwenden können auch bei der objekterkennung kann man clustering nutzen wenn wir hier ein laserscanner und ein kamerabild haben dann ist der konventionelle weg wir stellen erst mal eine objekt liste aus den laser daten also wir haben eine ein objekt und wissen die distanz vielleicht die relativ geschwindigkeit und wir haben durch die kamera eine klassifizierung von objekten also das ist ein fußgänger das ist ein fahrzeug und wenn wir diese objekte listen haben fusionieren wir sie zu einer kombinierten objekt liste bei der objekt fusion arbeiten wir dann aber auch schon bereits verarbeiteten daten das heißt wir haben schon einen kleinen informationsverlust ein weg mit clustering wäre dass man die punktwolken und das bild der kamera direkt kombiniert also auf die punkte des leaders den farb wert aus der kamera legt dafür müssen natürlich beide sensoren so kalibriert sein dass man eben diesen übertrag schafft und dann in dieser punkt wolke cluster findet wenn ich mein fahrzeug ab und nach vorne ein laser ausgerichtet habe dann sehe ich zum beispiel fahrzeuge als solche ecken also der laserstrahl wird reflektiert und solche ecken werden dann zurückgeworfen sowas ist super leicht zu klasse oder aus so was kann man sehr leicht cluster bilden also hätten wir hier und da fahrzeuge oder objekte und klassifiziert werden sie dann anschließend durch eben die farbe auf diesen punkten die wir aus der kamera haben und so kann man eine viel tiefgreifendere objekt fusion erstellen hier nochmal als bild wo ihr die die laser daten seht und ich denke es macht noch mal klar dass wirklich einzelne cluster von fahrzeugen viel oder sehr leicht zu erkennen sind und wenn man dann sich noch mal das video von anfang an schaut wo wir eben genau das haben das videobild für die klassifizierung und dass die punktwolken um die klasse zu bilden dann haben wir da die möglichkeit durch dieses clustern sehr effizient und noch besser als konventionell objekte zu erkennen fassen wir das alles jetzt noch mal zusammen wir haben jetzt den abschluss unseres pattern recognition bereichs wir haben die muster oder wir schließen die mustererkennung ab mit den drei großen gruppen der regression der klassifikation des castings bei der regression haben wir kontinuierlich ein output und super weiß learning genauso wie beim klassifizieren wo wir allerdings diskrete werte haben und das clustering wo wir auch diskrete werte haben aber ein anzug weißes learning was haben wir heute gelernt beim clustering geht es darum gruppen elena elemente in gruppen einzuteilen ist ein optimierungs problem und wir wollen dass elemente innerhalb einer gruppe sehr ähnlich sind und die elemente zu anderen gruppen sehr unterschiedlich die distanz ist ein sehr gutes maß um ähnlichkeit auszudrücken und im vergleich zu dem problem vor so sind wir jetzt an zucker weiß unterwegs wir haben also keine geregelten trainingsdaten mehr die silhouette ist ein gutes qualitäts maß um die qualität eines clusters zu beurteilen segmentierung und clustering können analog als begriffe benutzt werden die methoden waren das hierarchische clustern kamins und die wie scan durch das reichliche clustering lassen sich denn programme erstellen die uns gut visualisieren wie die cluster aufgebaut sind und wir anschließend aber selber noch entscheiden müssen welche klasse wählen dann hatten wir kamins der sehr schnell als greedy algorithmus cluster bestimmt wird dort aber die anzahl an cluster for definieren müssen und gefahr laufen in lokale minima zu laufen wir haben auch nur konvexe bereiche die wir damit klassifizieren können aber dieses problem konnten wir lösen oder wir haben eine andere methode noch kennen gelernt nämlich die wie scan die in der lage ist auch komplexe reform zu klassifizieren dabei können wir sogar rauschen ausschließen oder wir können mit rauschen umgehen indem wir rauschen als autor definieren während wir die elemente eines clusters als chor oder border elemente klassifizieren da mal lassen sich dann auch komplett komplizierte formen bilden und clustering hat viele anwendungen aber ist oft ein schritt der vorverarbeitung um dann eben die klassifizierung oder ein experten daten auswerten zu lassen und damit sind wir am ende der vorlesung und staaten nach einer pause mit der übung durch okay machen wir langsam weiter mit der übung wir haben in der übung jetzt zwei computer notebooks die wir durchgehend erstmal schauen wir uns caymans an mit einer zufälligen punkte wolke wie verhält sich der algorithmus star wie werden da die repräsentanten gebildet und danach schauen wir uns noch ein anderes problem an wo wir aus gps daten eine busroute extrahieren wollen bei dem ersten jupiter notebook ihr könnt euch das auch auf jeden fall das zweite könnt ihr euch schon auf der modellseite runterladen wenn du das jetzt macht dann habt ihr es gleich wenn wir da sind auch vielleicht schon bereit also hier geht’s erst mal los mit ein paar standard import export kein export sachen import sachen also dabei natürlich wir haben jetzt nicht die sky kittel höheren bibliothek dabei weil wir den algorithmus hier selber schreiben das heißt sie brauchen wir nicht und wirklich los geht es dann hier wo wir unsere zufälligen daten erstellen wir stellen erst mal unsere drei zentren um die wir dann rauschen legen also zufällige punkte um diese drei zentren legen und dann verbinden wir das alles und haben dann ein punkt oder ein eine menge an zufälligen punkten und die schauen wir uns auch erst mal die sieht so aus also drei für uns ganz klare cluster aber ob der algorithmus das gleich auch als cluster erkennen kann ist die frage der nächste schritt ist dass wir uns die die initialen zentren für den caymans algorithmus auswählen da haben wir wie schon eben gesehen in der vorlesung irgend etwas zufälliges und zwar wird hier kein element gewählt also hier an dieser stelle wo wir einen cent zentrum haben oder einen repräsentanten haben liegt kein tatsächliches element aus unserem bereich sondern es ist ein eigenes element des gebaut haben und da wird der gesamte bereich genommen und daraus irgendwo drei zufällige punkte also es wird kein element kein bestehendes element genommen sondern ein eigenes element für diesen repräsentanten gebildet sodass ist also unsere ausgangssituation wir haben die die daten und wollen jetzt diesen drei oder diese drei zentren sowie dass sie diese daten gut repräsentieren den texte oder den kot gehen wir gar nicht genau durch weil das auch ein teil der hausaufgabe sein wird wenn alles richtig läuft dann sieht es hier so aus wir haben hier wunderbar unsere repräsentanten in den mitten unserer cluster was wir jetzt ein bisschen machen wir spielen mit den clustern rum wir haben kam auf drei gesetzen wollen drei cluster wenn wir jetzt aber ein eine weitere klasse menge hinzufügen wählen wir dafür mal 4 und -2 generieren die punkte dazu und verbinden den wird natürlich auch in unsere große punkt wolke da sieht es so aus für uns wieder ganz klar zu erkennen hier haben wir vier cluster aber wir haben den algorithmus gesagt wir wollen nur drei haben gleich drei schauen wir einmal was er daraus macht live demos gehen wir mal von vorne durch dann gucken wir uns erst noch einen anderen effekt an der hoffentlich funktioniert also was sie hätten sehen sollen ist dass der algorithmus natürlich diese vier klaren cluster nicht aufteilen kann auf 3 und dadurch ein klasse entsteht das sehr auch dass zwei dieser punktwolken beinhaltet aber dadurch dass diese punktwolken zu dicht aneinander liegen es nicht richtig funktioniert heute sind wir wieder an der ursprung situation unsere drei punktwolken mit den drei clustern wir erhöhen jetzt mal da die größe also wie weit ein cluster sich ausbreitet also den radius eines clusters sehen jetzt hier vorne dieses cluster oder diese punkt wolke ist deutlich auseinander gezogen und schauen wie sich das auswirkt funktioniert noch ganz gut also wir haben eine klare trennung noch innerhalb dieser drei punktwolken erzielt schieben wir jetzt noch mal ein zweites cluster etwas auf bekommen wir als mensch jetzt schon probleme dauernd irgendwas zuzuordnen und wir sehen zwar es ist immer noch diese aufteilung dort aber wenn wir hier vorne diese elemente betrachten wissen wir dass solche elemente natürlich auch hier vorne liegen also elemente die eigentlich von diesem zentrum erstellt wurden vermischen sich mit dem anderen cluster oder mit dem man mit der anderen punkt wolke ich probe jetzt nochmal eine weitere punkt hinzuzufügen weil das eigentlich der schönere effekt ist so hier haben wir jetzt die vier punkt wollten auch geclustert verschieben wir die jetzt auch mal etwas weiter weg so ist haben wir hier sie ganz klar getrennt aber immer noch nur drei cluster die wir den zuordnen wollen und wenn wir das jetzt termins machen lassen sehen wir hier das wir einen repräsentanten haben der zwischen zwei clustern sitzt er repräsentiert also nicht wirklich die klasse sondern eigentlich würde dieser repräsentant diesen bereichen klassik repräsentieren er liegt also genau dazwischen was ihm besonders schlecht macht und da sehen wir dass wenn wir bei kamins nicht die richtige anzahl an cluster wählen die wir benötigen repräsentanten bekommen die in bereichen liegen wo vielleicht überhaupt keine elemente sind und dadurch halt falsche informationen oder zu wenig informationen aus diesen aussichten datensatz extrahiert werden kann das notebook ist auch auf moodle für die hausaufgabe dort werdet ihr selber in dem kamin scott ein paar coach sein hinzufügen um ihn zum laufen zu bringen wir schauen uns jetzt das zweite beispiel an wo es darum geht gps position von einem bus zu einer route zu verbinden also wir haben am anfang ein paar definition schauen uns gleich an und wir beginnen damit unsere trainingsdaten einzulesen die sind so aus dass es einfach nur position sind davon 5000 stück und hier sind mal die ersten zehn aufgeschrieben damit können wir erst mal nicht so viel anfangen aber wenn wir das visualisieren und die punkte auf einer karte darstellen erkennen wir viel besser worum es sich handelt wir haben also für jeden punkt jetzt ein blauen kreis gezeichnet und wenn wir da mal langsam sehen wir dass diese punkte teilweise sehr dicht aneinander liegen also hier haben wir zum beispiel auf der straße ist der bus entlang gefahren und wir haben hier einen punkt wolke während wir vorne überhaupt keine daten punkt haben sie sind also nicht gleich verteilt über die gesamte strecke aber wir können schon ja alles klar das sind punkte die irgendwie immer auf seiner straße liegen also plus/minus 20 meter wenn wir noch mal raus suchen und uns einmal die gesamte route anschauen dann sehen wir hier vorne ist ein weg das sind zwei punkte aber die dichte dort ist viel geringer also da ist also ein bus fährt jeden tag diese strecke aber dann war irgendwann mal hier eine baustelle und er muss den umweg fahren wir haben also rauschen in unserem trainingsdaten satz und was wir hier raus bekommen wollen ist die tatsächliche route die der bus normalerweise fährt und wir wollen diese route nicht als 5.000 punkte die irgendwie aneinander hängen sondern wir wollen eine repräsentation dieser route mit nur wenigen mit weniger als 100 punkten weil mit 5.000 punkten hat gesehen wie lange es geladen hat das zu zeichnen lässt es sich einfach schwierig zu schwierig arbeiten wenn wir diesen informationsgehalt also reduzieren können auf 100 punkte können wir damit deutlich besser arbeiten dafür nutzen wir die scan und initialisieren das hier erst mal wir bestimmen unsere cluster zentren und dafür müssen wir einmal nach oben scrollen wo das gemacht wird hier haben wir unsere vier definition in denen das clustering eigentlich abläuft wir haben unsere daten wir haben das y also den radius in dem wir suchen und wir haben unseren parameter der uns sagt wie viele objekte brauchen wir damit wir ein element als chor element klassifizieren das kennen wir unsere daten nach den clustern dafür müssen wir erst mal die feature richtig extrahieren unsere position sind in grad angegeben wir wächst wollen das aber noch umwandeln damit wir besser damit arbeiten können machen hier also eine konvertierung und haben dann unseren bb ascon algorithmus wo wir noch mal diese parameter eingeben und sebs i lon unsere anzahl an mindestens objekten und dann noch hier zwei algorithmen die uns helfen dass wir die distanz auf der erde bestimmen also wir sind auf einem großen ball und wollen nicht die distanz durch den ball einfach nehmen indem wir die kürzeste distanz zwischen diesen zwei punkten nehmen sondern wir wollen die tatsächliche distanz auf der erdoberfläche berechnen also müssen um diesen ball herum gehen und so werden hier die klasse gebildet und dann zurückgegeben und die wiso visualisieren wir uns jetzt einfach mal also mit unserem der einstellung hier wir suchen im umkreis von 50 metern und wir wollen mindestens zwei elemente in unserer umgebung dass wir ein keule mensch haben bekommen wir vorhin die cluster das sieht jetzt nicht nach dem aus was wir wirklich haben wollten wir wollten ja dass dieses rauschen hier auf dem umweg irgendwie verschwindet aber damit jetzt ganz viele cluster wir wollten dass wir hier auf dem weg eigentlich eine schöne repräsentation haben aber teilweise sind sie dich zusammen teilweise haben wir wieder größere lücken und was mich am meisten stört ist noch hier diese diese ganzen klasse auf dem umweg ein roter kreis hier bedeutet dass dort ein zentrum eines clusters ist es bedeutet nicht dass alle elemente die in diesem kreis sind diesem cluster zu gehören und alle elemente außerhalb nicht sondern einfach nur dass dort ein zentrum des clusters ist wir haben hier also 32 cluster aber wir wollen eine route irgendwie haben also warum haben wir jetzt so viele klasse warum haben wir nicht nur ein cluster hier nutzen wir das pflastern um die daten zu komprimieren wie komprimieren abschnitte der strecke immer in einem cluster und nutzen das als repräsentativen punkt für diesen abschnitt das heißt am ende wollen wir cluster die über die gesamte straße verteilt sind aber nicht auf dem umweg wir müssen also irgendwie noch an unseren parametern spielen damit wir eine bessere repräsentation des pfades bekommen dafür habe ich hier sonst leider eingebaut mit dem wir die distanz im äther beeinflussen können und die punkte die wir mindestens erwarten nehmen wir mal an wir erwarten mindestens 25 elemente 26 wollte ich und 102 meter dann bekommen wir jetzt ohne die eigentlichen blauen elemente eben geplättet diese acht cluster jetzt ist es zu wenig unser umweg ist zwar aus aber wir brauchen noch mehr informationen zwischendurch reduzieren wir das also wieder ein bisschen und gehen wir mal auf mindestens zehn punkte und 50 meter sieht es schon besser aus das könnten wir noch ein bisschen weiter herum spielen jetzt haben wir hier schon eine relativ gute repräsentation man kann jetzt noch ein bisschen feintuning mache ein bisschen weiter an den stellhebeln spielen aber hier ist für uns relativ klar zu erkennen wo diese route entlang ging und wir haben das rauschen den umweg komplett herausgefiltert wir haben jetzt also die 5.000 punkte die wir am anfang für diese route haben reduziert auf 40 punkte die uns diese route eigentlich relativ gut darstellen du hast mir jetzt noch machen können ist diese punkte verbinden die wir eine route durch legen und so jetzt die route die wir oder die route die der bus gefahren ist relativ gut darstellen können aber an so kurven sehen wir dass es nicht mehr über die straße geht sondern einfach durch die häuser jetzt müssen wir abwägen wollen wir eine wollen wir es noch weiter generalisieren um die punkte noch weiter zu reduzieren um den die größe unserer datenmenge klein zu haben oder wollen wir jetzt vielleicht doch wieder ein paar mehr cluster haben ein paar mehr elemente damit wir solche stellen vermeiden also hier voll zum beispiel wenn wir hier noch ein cluster hätten dann wären wir schon wieder relativ dicht an der straße also jetzt ist ein trade off zwischen informationen und daten oder datengröße wir können mehr cluster haben haben den weg genauer oder wir haben weniger cluster und dafür nur noch eine annäherung an den tatsächlichen weg was wir aber auf jeden fall geschafft haben ist mit dem clustering die 5000 elemente relativ leicht zu reduzieren auf hier in diesem fall nur 40 cluster bei gleichen oder sehr ähnliche informationsgehalt wir wissen jetzt wo der bus her fährt die haben das rauschen herausgefiltert und könnten mit diesen daten jetzt weiterarbeiten ist könnten wir noch andere busrouten so clustern und die routen extrahieren wir könnten so dann zur städteplanung gehen und überlegen wo macht es sinn irgendwelche straßen anders zu legen die verkehrsführung zu ändern wo sind vielleicht relativ viele cluster von verkehrs- oder von busrouten übereinander und können so also das wissen aus diesen 5.000 punkten relativ leicht hier nutzen habt ihr fragen zu diesem notebook oder zudem davor ok dann können wir jetzt da könnt ihr diese evaluierung machen sind also soweit am ende wenn ihr aber nochmal ein oder wenn ihr noch mal die hausaufgabe von der letzten woche hier durchrechnen wollt dann könnt ihr noch hier bleiben dann können wir das hier noch eben durchgehen ansonsten sind wir mit der übung ist auch durch und ich freue mich auf eure bewertung und dann geht es nächste woche weiter mit lennart und den pathfinder algorithmen


Leave a Reply

Your email address will not be published. Required fields are marked *