so das ist das letzte mal dass man mit grafen befassen in dieser woche und es

geht wieder mal um clustering na ja also mit grafen da bildet sich wirklich an

dass man viel über clustering spricht weil die struktur von grafen irgendwie

nahelegt dass man was machen kann wie das in den gruppen zu zerteilen und jetzt

schauen wir uns einen algorithmus für clustering an der originär auf

ungerichteten grafen funktioniert wir haben gesehen wir das auf gerichteten

grafen machen kann mit hilfe von max und mit katten und weiter

wir haben es geschafft es auf ungerichtete grafen zu übertragen in

dem wir diesen etwas urständlichen hack gemacht haben mit alle ungerichteten

kanten in die richtung der kanten umwandel extra knoten einfügen wir keine

antiparallel kanten haben und schließlich dieses problem mit der

quelle der senke lösen aber jetzt schauen wir uns an was einfach so auf

ungerichteten grafen funktioniert was wirklich fundamentales

fundamentales verfahren ist ich bin auf der falschen seite gelandet

bei mincut wir sind natürlich jetzt hier diesem thema und das thema ist

spectral clustering

bald oder gleich darum gehen wird dass wir uns die das spektrum einer matrix

anschauen die eigenwerte und die eigenwerte

das ist auch was relativ moderne ist also die ersten gängigen verfahren

spektrum klasse die gibt es 20 jahren das sind nicht einerseits alt aber

andererseits in der magne für die magmatik ist es nicht sehr alt 20 jahre

wirklich modernes verfahren und es gibt immer noch aktuelle forschung auf diesem

gebiet das heißt es ist wirklich was sehr spannendes das setting ist ein

ungerichteter gewichteter graf mit kanten e und knoten v mit gewichten w und

diese gewichte w und da war ich vielleicht in den letzten wochen nicht

ausdrücklich genug gesprochen wie interpretiert man in diesem

kontext von clustering als eine ähnlichkeit zwischen das heißt ein

hohes gewicht zwischen zwei knoten heißt eine enge verwandtschaft und wenn

w ungefähr gleich nur ist oder klein ist fast nur oder wenn es gleich nur ist

dass diese knoten entweder nicht zusammenhängen oder sehr schwarz

zusammenhängen das ist natürlich jetzt irgendwie so genau das umgekehrte wie das

was man im kopf hat wenn man über über kürze wegen grafen nachdenkt ja also

immer über drei gestern gesprochen haben und solche sachen da war das gewicht

zwischen zwei knoten ein abstand zwischen zwei knoten das heißt ein

großes gewicht ein großer abstand zwischen zwei knoten das heißt dass es

hier genau begehrt wenn ein gewicht groß ist dann ist in diesem kontext von

clustering meinen damit zwei eng verwandte knoten und das auch gewisser

hinsicht stetig in wie gegen nur ja wenn wie klein ist dann sollen die kaum

verwandt sein wie gleich nur ist dann sollen die nicht verknüpft sein ja

hängen die nicht zusammen okay also das ist noch mal als

integration wie wie groß oder klein zu verstehen ist und in diesem kontext

eben so gesetzt ansteht

der graf ist ungerecht das heißt die kante uv ist auch die kante vu das ist

genau das gleiche und auch die gewichte sind gleich wie uv ist genau das gleiche

wie von vu weil das ja wirklich das gleiche kantenobjekt ist es nummerieren

die knotenmenge so mit v1 bis vm das heißt wir haben m knoten und wir

definieren jetzt erstmal wieder ein paar dinge nämlich erstens die

adiazenzmatrix die adiazenzmatrix haben wir schon mal am anfang gehabt bei diesen

grafen die beinhaltet die kantengewichte das heißt also w ist jetzt hier so eine

matrix und weiter und hier ist i und da ist j das ist das hier wie ij und wie ij