Nemlineáris Blog

Nemlineáris dinamika. Alkalmazott matematika. Bifurkáció és káosz. Differenciálegyenletek és alkalmazásai. Szegedi matematika. Matematikai hírek, emberek, érdekességek.

facebook

Friss topikok

Üzenet/Javaslat

A nemlinearis(kukac)freemail(pont)hu címen üzenhetsz, vagy javasolhatsz témát a blog szerzőjének.

Címkék

alhambra (1) alice (1) áltudomány (1) arnold (1) autista (1) autogram (1) bioritmus (1) bolgár (1) bolyai díj (1) bor (1) csoportos teszt (1) csuka (1) czeizel (1) dawkins (1) dekoltázs (1) diákolimpia (1) diszkrét dinamikai rendszerek (1) doktori (1) down szindróma (1) du sautoy (2) erdős (1) erdős szám (1) európai matematika kongresszus (1) facebook (1) fail (1) favágó (1) fermat (1) fields medál (3) foci (1) fraktál (3) fraktálok (1) függvény (1) fundamentális lemma (1) galois (1) gardner (1) géntérkép (1) gömböc (2) gráf (1) gyilkosság (1) hausel tamás (1) hellókarácsony (1) holland (1) hollywood (1) homeopátia (1) hülyék (1) idiotizmus (1) időgép (1) immunitás (1) india (1) influenza (1) inga (1) intel (1) interjú (5) iterált (1) japán (1) járvány (3) kalkulus (1) kaotikus (1) karrier (1) képlet (1) kézfogás (1) kneubühl (1) kollaboráció (1) könyv (1) koordinátageometria (1) krakkó (1) kriptográfia (2) kürschák (1) kutatók éjszakája (1) kutatok ejszakaja (1) kvantummechanika (1) kvíz (1) kyoto díj (1) lander (1) lax péter (1) lemma (1) lewis carroll (1) lovász (6) lovász lászló (1) mandelbrot (2) manga (1) maradona (1) matematikus (1) maverick (1) meteor (1) modellezés (1) moziműsor (1) mta (1) musical (1) művészet (2) natalie portman (2) neumann (2) ngo bao chau (1) ngo bau chao (1) nyugdíjas (1) obama (1) olimpia (1) oltás (1) öngyilkosság (1) optimalizálás (2) oscar (1) oxford (1) pályázat (1) parkolás (1) párosítás (1) pécs (1) pi (2) piatetski shapiro (1) proktometria (1) reklám (1) rekord (3) riesz (1) ritoók zsigmond (1) rocksztár (1) royal society (1) rubik (1) ruzsa (2) sigmund freund (1) spanyol (1) statisztika (1) stipsicz (1) svájci (1) szakma (1) számelmélet (1) számítógép (1) szeged (5) szemerédi (1) szemerédi endre (1) szifilisz (1) Szilágyi Áron (1) szimmetria (1) sztori (2) születésnap (1) tanácsadó (1) tanár (1) tanmese (1) tao (2) tardos gábor (1) ted (1) természet világa (2) tévhit (1) texas (1) time magazin (1) transzplantáció (1) tréfa (1) turing (1) valentin nap (1) vasút (1) vb (1) victoria (1) villani (1) vizi e (1) wolfram (1) záróra (2) zeneszerző (1) Címkefelhő

Hogyan teszteljünk szifiliszt?

2011.08.23. 19:35 - Nemlineáris

Címkék: optimalizálás szifilisz csoportos teszt

Bizonyára sokan emlékeznek még középiskolából arra a feladattípusra, amikor minél kevesebb mérésből kell kitalálni, melyik ládában van az igazi kincs. Ennek nagyon sok változata van (egykarú és kétkarú mérleggel is), és ezek nagyon jó kis logikai fejtörők, de valószínűleg kevesen gondolták, hogy ennek köze lehet valami gyakorlati problémához. Pedig igen, és ezt a szifilisz-tesztelés példájával fogom illusztrálni.

A szifilisz egy elég csúnya fertőző nemi betegség, ha máshol nem is, az iskolában Ady Endre kapcsán mindenki hallott már róla. Az antibiotikumoknak köszönhetően nagyrészt sikerült visszaszorítani, de az elmúlt évtizedben ismét emelkedett az esetek száma több fejlett országban, így az Egyesült Államokban is. Az amerikai hadseregben is újra gondokat okoz a szifilisz. Tegyük fel, hogy mindenkit le akarnak tesztelni, hogy kiszűrjék a fertőzötteket, de egy szifiliszteszt nagyon drága. Hogyan lehet minél olcsóbban megoldani az egész hadsereg letesztelését? Ezt a problémát már konkrétan megoldották a második világháború idején is.

Az alapötlet nagyon egyszerű: a szifiliszt vérmintából tesztelik, így egybeönthetjük egy csomó ember vérét, és teszteljük ezt. Ha a minta negatív, akkor az adott csoportban senki sem szifiliszes, így további tesztre nincs szükség. Ha pozitív, akkor a csoportban van legalább egy szifiliszes, ez esetben a csoport minden tagját leteszteljük. Mivel a szifilisz viszonylag ritka, arra számíthatunk, hogy ha az embereket csoportosítva teszteljük, akkor sok csoport tesztje ad negatív eredményt, így megspórolunk jó sok tesztet, hiszen ezen csoportok tagjait nem kell külön letesztelni. A matematikai feladvány meghatározni azt, hogy mekkora csoportokat alakítsunk ki, hogy a lehető legkevesebb tesztből megtaláljuk az összes szifiliszest.

 Legyen $N$ a tesztelendő populáció létszáma és $x$ az egyes csoportok létszáma, tehát lesz $\frac{N}{x}$ csoportunk. Ha $x$ túl kicsi (szélsőséges esetben $x=1$, amikor mindenkit egyenként tesztelünk), akkor a csoportok nagy száma miatt sok tesztet kell végeznünk. Ha $x$ túl nagy, akkor pedig várhatóan minden csoportban akad majd szifiliszes így minden csoport tesztje pozitív lesz. Az várható tehát, hogy van egy köztes, optimális csoportméret. Ki tudjuk-e ezt számolni?

Van $\frac{N}{x}$ csoportunk, tehát ennyi tesztet mindenképpen el kell végeznünk. Legyen $p$ annak a valószínűsége, hogy egy véletlenszerűen kiválasztott személy szifiliszes (vagyis $p$ a szifilisz gyakorisága a populációban). Ekkor $(1-p)^x$ a valószínűsége, hogy egy $x$ fős csoportban senki sem az, ekkora eséllyel lesz a minta negatív, tehát $1-(1-p)^x$ eséllyel pozitív. Ha a minta pozitív, akkor a csoport minden tagján, összesen tehát $x$ számú további tesztet végzünk. A pozitív mintájú csoportok várható száma $\frac{N}{x}(1-(1-p)^x)$. Az összes tesztek számát tehát az $\frac{N}{x}(1+(1-(1-p)^x)x)$ formula adja meg, ennyi tesztet elvégezve megtalálhatjuk az összes szifiliszest. Ebből $N$-et kiemelhetjük, így kapjuk, hogy az

$f(x)=\frac{1}{x}+1-(1-p)^x $

függvényt kéne minimalizálnunk. Vegyük észre, hogy az optimális $x$ nem függ $N$-től, úgyhogy azzal nem is foglalkozunk a továbbiakban, csak feltesszük, hogy egy elég nagy szám (hogy ki tudjunk alakítani $x$ fős csoportokat). Függ viszont a $p$-től, ami érthető, hiszen ha a szifilisz nagyon gyakori, akkor más csoportméret lehet az optimális, mint ha nagyon ritka lenne.

Az $f(x)$ függvény minimumát explicit módon is kifejezhetjük $p$ függvényében, bár kissé komplikált (lásd itt, a $W$ a ProductLog vagy más néven a Lambert-féle W-függvényt jelenti). Konkrét $p$ értékre viszont egyszerűen kiszámolhatjuk numerikusan is. A CDC adatai szerint az USA-ban 100 000 emberből 15.4 szifiliszes, ami $p$=0.000154-et jelent. A Minimize[{1/x + 1 - (1 - 0.000154)^x, x > 0}, x] Mathematica parancs rögtön kiadja nekünk, hogy ehhez a $p$ értékhez 81 fős csoportok az optimálisak,  és ekkor $f$ értéke 0.0247431, ami azt jelenti, hogy elegendő a populáció 2.47%-ának megfelelő számú tesztet végezni, ahelyett, hogy mindenkit egyenként letesztelnénk.

Tehát egy kis matematikával 97,5%-ot spórolhatunk.

Az ábrán az $f$ függvény grafikonja látható $p$=0.000154 esetben.  Észre lehet venni, hogy az optimális $x$=81 nagyon közel van az ${1}/{\sqrt{p}}$=80.6-hoz. Ezt egy heurisztikával is levezethetjük:  $f$ minimalizálásához válasszuk $x$-et úgy, hogy a két tag, ${1}/{x}$ és $1-(1-p)^x$ egyenlő legyen. Ha $x={1}/{\sqrt{p}}$, akkor $p={1}/{x^2}$, vagyis $1-(1-p)^x=1-(1-x^{-2})^x$. Most az $(1-x^{-2})^{x^2/x} \approx e^{-1/x} \approx 1-1/x$ közelítésből kapjuk, hogy $1-(1-p)^x$ is kb. $1/x$. Vagyis az optimális csoportméretet így közelíthetjük $x={1}/{\sqrt{p}}$-vel, $f$ minimuma pedig $2/x=2\sqrt{p}$ ami a $p$=0.000154 esetben a 0.02482, elég pontos közelítést adja.

Ezt a módszert lehet még javítani is, ha rekurzívan alkalmazzuk. Tehát először csoportokra osztjuk a populációnkat, majd a pozitív eredményűeket újra kisebb csoportokra osztjuk, és így tovább. Legyen házi feladat, hogy meddig lehet így elmenni.

forrás: Jeffrey Shallit Recursivity blog

A bejegyzés trackback címe:

https://nemlinearis.blog.hu/api/trackback/id/tr863167251

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

Yeto 2011.08.23. 22:52:46

"Miért kell matematikát tanulni? Ott a számológép meg a számítógép."
Hát ezér bazmeg.

atti1981 2011.08.24. 02:06:24

Hasonló érdekességek vannak pl. John Allen Paulos: Számvakság c. könyvében is, bár a matematikai megoldás a könyvből a legtöbb esetben hiányzik.

Überspannung 2011.08.24. 06:45:53

"Észre lehet venni, hogy az optimális x=81 nagyon közel van az 1/p√=80.6-hoz."
Ez a kedvenc mondatom, én is rögtön észrevettem. :P

meszi 2011.08.24. 06:54:49

kurva firefox nem jeleníti meg a függvényeket

vészmadár (pica pica) · http://feleslegesszavaink.blog.hu 2011.08.24. 07:33:12

lenne még egy kérdésem. Nem túl nagyvonalú azzal elintézni a második kört, hogy a csoport minden tagját leteszteljük? további - második-harmadik-stb. körös) csoportbontásokkal nem lehetne csökkenteni a vizsgálatok számát?

Ozsy 2011.08.24. 07:37:20

@vészmadár (pica pica):
Az utolsó bekezdésben pont erről van szó :)

vészmadár (pica pica) · http://feleslegesszavaink.blog.hu 2011.08.24. 07:41:36

@Ozsy: igen, valamiért átsiklottam első körben azon az utolsó mondaton. Köszönöm.

Hmmm... 2011.08.24. 10:01:54

Az elv remek, de az új módszerek bevezetése ellőtt célszerű végiggondolni a vizsgálllat egész folyamatát, mer nem biztos, hogy azmi jó Lilly putri méretben, az működ az Órások földjén is, satöbb (pl legrosszabb esetben hány ember mennyi vérét kell a hol tárolni + vizsgálni a milyen alkalmas módszerrel).

eszemmm 2011.08.24. 10:15:39

Az elv nagyon szép, de szerintem van két gyakorlati probléma. Az egyik az, hogy p értéket valahogyan meg kell határozni, aminek meg a módszere nem más, mint a tesztelés, éppen az, aminek a számát próbáljuk minimalizálni. A másik pedig az, h jelen példánál p értéke dinamikusan változik, mivel egy nemi betegségről van szó, és hát az emberek ritkán ülnek otthon és néznek tévét, viszont sokat szexelnek:)

petimegmondja 2011.08.24. 11:02:40

@eszemmm:

Ezt az értéket (p) statisztikai módszerekkel szokták meghatározni. Egy statisztikai mintavétel a lehető legkisebb számú alany tesztelését jelenti, tehát a teljes populáó nem lesz tesztelve. Arról nem is beszélve, hogy a gyakorlati példa egy nemi betegségről szól, amiről az orvosok jelentést tesznek a járványügyi hatóságnak és mivel a szifiliszes betegek nagy többsége orvoshoz fordul, a látens betegszám statisztikai szempontból elhanyagolható.

Dr. Bélus___ 2011.08.24. 11:11:17

Ha az egyik csoportban szifiliszest találsz, nagy valséggel csak egy szifiliszes van a csoportban. Ekkor bináris keresést célszerűbb lenne használni, mint mindenkit külön letesztelni. Azaz először kettészeded a csoportot, és remélhetőleg ezzel a csoport felét kizárod (ha mákod van, akkor az első teszt negatív, és a második felében van a hunyó, ekkor csak 1 teszt kellett). Aztán megint felezel, és így tovább.

Dr. Bélus___ 2011.08.24. 11:17:14

Hm... és akkor mi van, ha az összes x=N és onnan nyomjuk a bináris keresést? Ha nagyon sok ember van és nagyon kevés a beteg (közel 1), akkor szerintem ez lesz az optimális. Este végig fogom gondolni, hogy a másik megüti-e az O(log n)-es skálázódást... :)

KenSentMe 2011.08.24. 11:25:50

@j'en ai fair any stone: Igen, ez a mondat általában úgy születik, hogy
1.) A pontos képleten látszik, hogy talán létezik egy egyszerű közelítés. Ilyenkor ugye észre lehet venni, csak nem a számokat kell nézni, hanem a formulákat.
2.) Az ember az (1-p)^x-re rápillantva szagot fog, hogy ebből talán ki lehet hozni egy e^y-os tagot valahogy (ez az "e" egyik definíciója), abból pedig egy 1+y-os tagot (Taylor-sor), és mivel 1-(1+y) = -y, ezt már egyáltalán nem reménytelen 1/x-el egyenlővé teni. Ezt meglátni főleg tapasztalat és rutin kérdése. Emberünk tehát vadul elkezd számolgatni, és néhány óra alatt megkapja a levezetést. Utána, amikor ezt egy cikkben vagy dolgozatban összefoglalja, akkor nagyon szerényen odaírja, hogy "vegyük észre", lehetőleg valami olyasmit vegyünk észre, amit ember magától észre nem venne. Ha még ennél is szerényebb az illető, akkor a dolgozatát teletűzdeli a "triviális" szó különböző formáival. (Triviális, teljesen triviális, egyszerű és triviális, stb.)

nickita 2011.08.24. 11:32:33

egy vérmintából mennyi tesztet lehet vajon elvégezni? mert ha a 81 tagú csoportokat mindig ketté bontogatod tovább, akkor legrosszabb esetben akár 8 tesztre is szükség lehet (feltéve, hogy egy 81-es csoportban csak egy pozitív inta van). ezért inkább jobb a rekurzív módszert alkalmazni a kisebb csoportokon is.

KenSentMe 2011.08.24. 11:33:01

@VRbagoly: (Természetesen a lim(y tart nullához) (1+1/y)^y az "e" definíciója, ezt kéne belelátni az (1-p)^x-be)

McKinney 2011.08.24. 11:47:02

technikai problémának látom, ha x meghalad egy bizonyos értéket, akkor az adott teszt a túl nagy vérmennyiség miatt vagy megbízhatatlan, vagy biztos de drágább lenne. Egy ilyen országos projeknél még számos itt nem említett költségtétel is lenne. Ettől függetlenül a matek riszpekt

musi 2011.08.24. 11:58:00

Ezt nem vagyok hajlandó végigolvasni és felfogni :D

Rokkantnyugdíjaspornósztár 2011.08.24. 12:03:22

A közelítést lehet úgy végezni, hogy melyik az a legnagyobb csoportlétszám, ahol még nincs fertőzött, mert ekkor lehet a legkevesebb számú csoportot létrehozni, ahol biztosan negatív lesz az erdmény. Ez azt jelenti, hogy addig lehet elmenni, amíg egy fertőzött lesz a csoportban:
[1-(1-p)^x]x=1
ha p<<1 akkor (1-p)^x~1-xp
[1-(1-xp)]x=1
(xp)x=1
x=1/gyök p

Gyakorlatban ez azt is jelenti, hogy promiszkuáló egyén átlagosan 80-81 partner esetén találkozik egy fertőzöttel, vagyis ennyi partnerenként érdemes teszetet végeztetnie.
süti beállítások módosítása