12 júna 2009

Medoid trojice bodov

Narýchlo len jeden príkladík; nič mimoriadne, ale aspoň že je môj vlastný :-) Napadol ma dnes pri skúšaní analýzy zhlukov na predmete "Viacrozmerné štatistické analýzy 2".

Majme trojuholník ABC s navzájom rôznymi dĺžkami strán. Z trojice vrcholov A,B,C nazveme medoidom ten, ktorý má minimálny súčet vzdialeností od zvyšných dvoch vrcholov. Je nutne medoid bližšie k ťažisku trojuholníka ABC než zvyšné dva vrcholy?

Poznámka 13.6.: V komentároch nájdete Peťove riešenie pomocou súradnicového systému, ale skoro by som sa stavil, že existuje aj nejaké veľmi jednoduché tvrdenie založené na klasickej geometrii :-) Nájdete ho?

Poznámka 14.6.: Zdá sa, že môže platiť aj nasledovné tvrdenie; vedeli by ste nájsť dôkaz?

Majme trojuholník ABC s navzájom rôznymi dĺžkami strán. Z trojice vrcholov A,B,C nazveme antimedoidom ten, ktorý má maximálny súčet vzdialeností od zvyšných dvoch vrcholov. Je nutne antimedoid vzdialenejší od ťažiska trojuholníka ABC než zvyšné dva vrcholy?

17 komentárov:

Peter Richtárik povedal(a)...

Anketa: mozno to bude tym ze ta stranka nefunguje ;-) [mne ten link nefrci...]

Radoslav Harman povedal(a)...

Mne ten link išiel, aj tak so ho však zmenil na mierne iný (ktorý mi osobne tiež ide). Inak tá stránka nemá bezpečnostný certifikát, takže možno to len Tvoj prehliadač odmieta Ťa na tú stránku pustiť, kým jej neudelíš výnimku.

Každopádne k zaujímavým výsledkom ankety sa človek dostane len s matfyzáckym ISICom, alebo ITICom (alebo z matfyzáckej IPčky).

Peter Richtárik povedal(a)...

Včera som sa nad problémom chvíľu zamýšľal, ale ten nápad nefungoval. Dnes som sa na to pozrel inak, a pomerne ľahko som dospel k záveru, že
skutočne, v ľubovoľnom trojuholníku je ťažisko najbližšie k vrcholu protiľahlému k najdlhšej strane, teda k medoidu.

Môj postup:

WLOG predpokladajme že najdlhšia strana má vrcholy v bodoch A=[1,0] a B=[0,1] v súr. sústave. Nech C=[a,b] je tretí vrchol.

Potom podmienka, že úsečka AB je najdlšia strana trojuholníka sa dá takmer okamžite napísať ako nerovnosť v neznámych a,b nasledovne:

a^2 + b^2 - 1 <= 2*min{a,b}.

Čuduj sa svete, rovnakú nerovnosť dostaneme ak zapíšeme podmienku, že |T-C| <= min{|T-A|,|T-A|}, pričom použijeme vzťah T=(A+B+C)/3.

Peter Richtárik povedal(a)...

Inak mal si pravdu, nevšimol som si, že musím povoliť certifikáciu.

Napriek tomu sa k výsledkom nedostanem keďže nie som študentom...

Radoslav Harman povedal(a)...

Peťo: Ja som ten príklad tiež počítal len tak, že som celý trojuholník vložil do súradného systému. Možno by niekto vedel nájsť aj dôkaz len povedzme na základe podobností trojuholníkov. Inak, nedalo by sa toto tvrdenie vhodne zovšeobecniť do priestoru všeobecnej dimenzie?

K tej ankete: Tento rok (v zimnom semestri; výsledky sú k dispozícii so značným oneskorením) sa študentskej ankety zúčastnilo menej ako 25 percent študentov. Pritom majú študenti na hlasovanie veľmi pekný www portál a súčasne organizátori robili ankete pomerne rozsiahlu propagáciu. Ako je možné, že tri štvrtiny študentov sa na študetskú anketu úplne vykašľalo? To nemajú záujem k výuke, ktorá tvorí tak podstatnú časť ich života, nič poznamenať? Samozrejme nemusia, ale aj tak by ma zaujímali myšlienkové pochody niektorého z tých troch troch štvrtín študentov...

Peter Richtárik povedal(a)...

Anketa: Celkom rád by som ju videl, aj keď nie som študent alebo vyučujúci... ale ako bývalý študent. Škoda, že to nie je verejne prístupné.

Úloha: Neviem celkom čo myslíš pod tým zovšeobecnením... Jediná interpretácia, ktorú si viem predstaviť, má jasnú odpoveď: áno. Trojuholník predsa leží v 2D afínnom podpriestore, a teda rovnaká argumentácia platí pre trojuholníky v ľubovoľnom vektorovom priestore so skalárnym súčinom.

Peter Richtárik povedal(a)...

Aha! Asi myslíš iné útvary ako trojuholníky vo vyšších dimenziách. Povedzme štvorsten v 3D a pod... Príliš rýchlo som odpovedal ;-)

Ako to inak celé súvisí so štatistikou?

Radoslav Harman povedal(a)...

Peťo: Anketa: Niekedy keď prídeš k nám na matfyz, tak si výsledky ankety môžeš popozerať.

Príklad: Áno; mal som na mysli nie trojuholníky v priestore všeobecnej dimenzie, ale simplexy. Napríklad (strelím nejakú hypotézu pre 3d): je spomedzi vrcholov simplexu najbližie k ťažisku ten, ktorý stojí oproti stene s najväčšou plochou?

Súvis so štatistikou: Učím a momentálne skúšam (vlastne už som doskúšal) predmet "Viacrozmerné štatistické analýzy 2", kde berieme aj rôzne často používané metódy, ktoré súvisia s dataminingom a takou, nazval by som to "inžinierskou" štatistikou. Tam patrí aj analýza zhlukov (cluster analysis CA). Dve najčastejšie používané metódy v CA sú kmeans a kmedoids. Pre skupinu bodov v mnohorozmernom priestore (súbor mnohorozmerných dát) je kmedoid ten z týchto bodov, ktorý podľa definície má najmenšiu priemernú vzdialenosť od ostatných bodov, alebo, ekvivalentne, najmenší súčet vzdialeností od ostatných bodov tejto skupiny. Moji študenti však na skúške viackrát povedali, že medoid je ten spomedzi daných bodov, ktorý je najbližšie k ťažisku celej skupiny bodov a otázka vyvstala, či sú tieto dve definície rovnaké. Zdá sa, že pre všeobecný počet bodov v skupine to pravda byť nemusí, ale pre tri body je to tak.

Peter Richtárik povedal(a)...

Troška som sa tým pohral v MATLABe a výsledok je taký, že naša 3D hypotéza neplatí.

Ťažisko štvorstena teda môže mať najbližšie k vrcholu, ktorého protiľahlá stena NIE JE stena s najväčším obsahom.

Takisto neplatí, že ťažisko má najbližšie k vrcholu, ktorého súčet vzdialeností od ostatných vrcholov je minimálny.

Mimochodom, pri (ako sa neskôr ukázalo neúspešnej) snahe aplikovať môj 2D prístup na túto 3D úlohu som prišiel na celkom zaujímavý dôkaz Herónoveho vzorca (pre výpočet obsahu trojuholníka z informácie o dĺžkach strán).

Radoslav Harman povedal(a)...

Ja som sa s tým tiež pár minút hral (v R-ku) a taktiež mi vyšlo, že tá moja 3D hypotéza neplatí. Možno však existuje iný spôsob zovšeobecnenia do 3D a vyšších dimenzií; ktovie.

Ak si našiel nejaký pekný spôsob odvodenia Heronovho vzorca, tak to by mohol byť námet na blogový príspevok, nie? :-)

Peter Richtárik povedal(a)...

Tiež mi to napadlo ;-)

Práve som jeden príspevok zverejnil, ako príprava na ten Heronov vzorec:

http://predbarakom.wordpress.com/2009/06/14/trojuholnik-na-suradnicovych-osiach/

Úloha #37 bude o tom ako pomocou #36 odvodiť Heronov vzorec.

katka povedal(a)...

Ulohou je vlastne dokazat, ze taznica na najdlhsiu stranu v trojuholniku je najkratsia a taznica na najkratsiu stranu je najdlhsia taznica. Nech a>=b>=c. Plati kosinusova veta: a^2=b^2+c^2-2bc.cos(alfa). Nech S_C je stred strany AB, aj v trojuholniku ACS_C plati kosinusova veta: t_c^2=b^2+(c^2)/4-bc.cos(alfa). Z prveho vztahu si vyjadrim bc.cos(alfa)=(b^2+c^2-a^2)/2, to dosadim do druheho vztahu a dostanem: t_c^2=(2b^2+2a^2-c^2)/4. Podobne t_a^2=(2b^2+2c^2-a^2)/4, t_b^2=(2a^2+2c^2-b^2)/4. Potom uz nie je tazke dlzky taznic porovnat, plati t_a<=t_b<=t_c.

Radoslav Harman povedal(a)...

katka: Ešte že s Peťom Ťa máme.

Inak Tebe aj ostatným prispievateľom na naše blogy, ktorých sa to týka (napr. Ondro, Ajka, Janka, Veronika, Rasťo, Lukáš...), držím palce na štátniciach!

Anonymný povedal(a)...

anketa:

1) dost vyrazne by som odlisoval ucast u Bc. vs Mgr. studia - v tom druhom uz maju studenti vacsinou asi omnoho blizsi vztah s vyucujucimi ako pocas prvych 3 rokov. teda aj tlak na ucast a spatnu vazbu od studentov by mal byt imho vacsi.

2) nizka ucast (cele sa to bude k viazat k Bc. studiu) - to je asi postojom vacsiny studentov k samotnemu studiu. zaroven mozno aj odraz pristupu niektorych vyucujucich pocas prvych rokov v style "hlavne ze si to oducim, ci aj nieco naucim je druhorade". takisto si to vela studentov odstuduje a tym to konci. tych par rokov predsa nejak preziju. dalej je dost predmetov, kt. su jednosemestralne a teda student po ich absolvovani vacsinou na ne akosi zabudne, prip. pri nespokojnosti si mozno radsej povie, ze nebude vytahovat stare zle spomienky a tak sa na to radsej vykasle. alebo len nechce byt prilis subjektivny a tak radsej anketu nevyplni.

dalej by sa mozno zislo tu anketu trochu prepracovat - od grafickej stranky (moderne weby vacsinou vyzeraju lakavejsie, aj ked tu ide zjavne v prvom rade o funkcionalitu) cez polozene otazky.

dalsia vec - preco sa anketa tyka zimneho semestra (resp je proklamovana najmna pri konci zimneho) a v lete nic?

a to asi najpodstatnejsie - vyvodzovanie dosledkov. ak by dostal vyucujuci 30% zlych hodnoteni, bude sa tym jeho nadriadeny zaoberat alebo je to len na voli daneho vyucujuceho k sebareflexii? a aj ked by sa tym niekto nadriadeny zaoberal, vyucujuci sa vacsinou poznaju (niektori viac, niektori menej, kazdopadne v ramci odboru urcite), hadam sa nebudu medzi sebou este nejak kritizovat apod. verim, ze mladsie rocniky (vid R.H.) by to este mozno dokazali, ale tie starsie, kt. je samozrejme nasobne viac, asi tazko. koho by bavilo vyplnat nieco, co si niekto precita a zalozi do suflika. mozno akurat tych < 25% (z toho este urcite bude dost prvakov, cize vyplnaju premierovo s vierou, ze nieco to zmeni) idealistov. tolko aspon v rychlosti k tejto teme.

Radoslav Harman povedal(a)...

Ďakujem za komentár k ankete.

Pár mojich poznámok: Medzi jednotlivými ročníkmi sú v účasti len veľmi malé rozdiely: Prváci, druháci a tretiaci bakalári aj prváci a druháci magistri majú všetci 25 až 29 percentnú účasť. (Málo percent je od štvrtákov a starších bakalárov, t.j. takých, ktorí opakujú ročník. Tým je celkový priemer účasti znížený na tých 24,9 percenta.) Takže ani prváci neoplývajú príliš veľkým entuziazmom čo sa týka vyplňovania ankety.

Účasť na ankete má jednoznačne klesajúci trend už niekoľko rokov, takže problém bude asi hlbší.

Ako píšeš, asi veľa študentov nemá o anketu záujem, lebo ich skoro jedinou motiváciou je nejako doštudovať a vyplnenie ankety im v tom nepomôže. Ak je väčšina takých, tak je to potom smutné a s tým je potom ťažké niečo robiť. V zásade je to ale veľmi sebecký postoj, lebo anketa môže reálne pomôcť mladším kolegom (napríklad sa môžu na jej základe študenti rozhodovať, čo si zapíšu, alebo vyučujúci môžu urobiť vo výuke zlepšenia).

Čo sa týka toho vyvodzovania dôsledkov: Nie je to len fraška a to z niekoľkých dôvodov.

Po prvé, výsledky ankety sú prístupné všetkým kolegom. Každému je jasné, že občas študenti prídu na anketu vrátiť vyučujúcemu pociťovanú krivdu, aj keď si povedzme to vyhodenie zo skúšky skutočne zaslúžili. Niektoré komentáre od študentov sú zjavné nezmysly, alebo drzé podpichovanie. Ale ak sa v zásade taká istá výhrada vyskytne zo strany veľa nezávisle hodnotiacich študentov, tak na tom už asi niečo bude. Pre dotknutých vyučujúcich to určite nie je veľmi príjemná vizitka pred kolegami a je veľká šanca, že sa do budúcnosti pokúsia o nápravu.

Po druhé, ak má nejaký vyučujúci veľmi zlé hodnotenie od veľa študentov, tak sa k tomu musí ten pedagóg vyjadriť z nariadenia dekana. Sám dekan skrátka má záujem na tom, aby sa výsledky ankety brali seriózne. A tam už určite nefunguje tolerancia z titulu známosti (ak, tak v malej miere). Nakoniec, fakulta má možno tak 400 vyučujúcich a osobne sa dekan pozná len so zlomkom z tohto počtu. Naviac, verím že by dekan dokázal zaujať rázne stanovisko aj v prípade, že by dotknutým pedagógom bol jeho známy.

A po tretie, anketa môže byť pre pedagógov nielen negatívnou, ale aj pozitívnou motiváciou. Ak vyučujúceho študenti pochvália, tak mu to veľmi dobre padne. Kvôli tomu som aj dal návrh na ten zoznam top 10 vyučujúcich, čo by pozitívnu motiváciu mohlo ešte trochu zvýšiť. (Hoci ako som si predbežne počítal, ja sám by som sa do top 10 nemal šancu dostať; nenavrhujem to preto :-)

Anonymný povedal(a)...

Reakcia

"Medzi jednotlivými ročníkmi sú v účasti len veľmi malé rozdiely..."

-> no ved to svojim sposobom tiez vyzdvihujem ako zaujimavost, cakal by som, ze starsi studenti budu mat k studiu predsalen blizsi vztah. alebo aspon to zaciatocne zapalanie prvakov. zial to tak nevyzera.

"Účasť na ankete má jednoznačne klesajúci trend už niekoľko rokov, takže problém bude asi hlbší."

-> suhlas, chcelo by to nejaku poriadnu viacrozmernu analyzu :) len kto ju spravi?

"Ale ak sa v zásade taká istá výhrada vyskytne zo strany veľa nezávisle hodnotiacich študentov, tak na tom už asi niečo bude."

-> toto by som akceptoval pri vyssej(nechcem povedat ze 100%nej) ucasti. anketu totiz asi nevyplnaju studenti vybrani podla nah. vyberu. povedal by som, ze pri 25%-nej ucasti je proste dost mozne, ze 'vyber vyplnajucich' je do istej miery vychyleny.

"Pre dotknutých vyučujúcich to určite nie je veľmi príjemná vizitka pred kolegami a je veľká šanca, že sa do budúcnosti pokúsia o nápravu."

-> viem si predstavit, ze su vyujuci, kt. si to k srdcu beru a zase aj dost takych, kt. je to ukradnute. mozno by stalo za to trosku 'spovinnit' aspon precitanie vysledkov. ale chapem, ze dekan si asi tazko najde cast prejst nazory s kazdym vyucujucim osobitne. boli by to take pekne konzultacie :)

"Po druhé, ak má nejaký vyučujúci veľmi zlé hodnotenie od veľa študentov, tak sa k tomu musí ten pedagóg vyjadriť z nariadenia dekana."

-> jedna vec je sa vyjadrit, druha nieco (chciet) realne zmenit.

"Sám dekan skrátka má záujem na tom, aby sa výsledky ankety brali seriózne. A tam už určite nefunguje tolerancia z titulu známosti (ak, tak v malej miere). Nakoniec, fakulta má možno tak 400 vyučujúcich a osobne sa dekan pozná len so zlomkom z tohto počtu. Naviac, verím že by dekan dokázal zaujať rázne stanovisko aj v prípade, že by dotknutým pedagógom bol jeho známy."

-> to velmi rad pocujem (ci skor citam) a budem sa snazit tomu aj verit.

"Kvôli tomu som aj dal návrh na ten zoznam top 10 vyučujúcich, čo by pozitívnu motiváciu mohlo ešte trochu zvýšiť."

-> vyborny napad a urcite by ste sa mali posnazit realizovat ho. nie kvoli tomu, ci by ste sa tam dostali, ale kvoli principu. navyse, netreba robit unahlene zavery ("...ja sám by som sa do top 10 nemal šancu dostať;"_, ako sa hovorieva: ked pan boh da, aj motyka vystreli ;)

p.s. co s tym, ze anketa je len v zime? je nejaky statisticky vyznamny dovod, ze bol vybrany prave zimny semester ako referencny?

ajka povedal(a)...

Zdravim,
páči sa mi diskusia o ankete, ale bohužiaľ prebiehala v predštátnicovom čase, takže som sa k nej nedostala keď bola aktuálna. Na druhú stranu mi nedá sa nevyjadriť aspoň teraz.

Prvá pripomienka je k nízkej účasti vo vyšších ročníkoch. Tu existujú predmety, ktoré má vyučujúci s veľmi malým počtom študentom. A verím, že tu funguje iný spôsob spetnej väzby, ako keď je v sále 60 poslucháčov.

Druhá vec, čo sa mne osobne na ankete veľmi páči je, že si spomeniem aké vlastne predmety v tom semestri boli. Ankety vypĺňam tak v marci a príde mi super si zrekapitulovať, čo sa udialo v zimnom semestri. A teda okrem komentáru učiteľov si aj ja ujasním, čo ma zaujalo, čo sa mi páčilo.

Takže mne príde anketa ako prospešná, aj keď mi vždy trvá pokým si na ňu nájdem čas.