sanatate / pairAdjacentViolators

Prezentare generala

O implementare a algoritmului Pair Adjacent Violators pentru regresia izotonica. Scris in Kotlin, dar utilizabil din Java sau orice alt limbaj JVM.

Retineti ca acest algoritm este, de asemenea, cunoscut sub numele de „Pool Adjacent Violators”.

Ce este „Regresia izotonica” si de ce ar trebui sa-mi pese?

Imaginati-va ca aveti doua variabile, x si y , si nu cunoasteti relatia dintre ele, dar stiti ca daca x creste, atunci y va creste, iar daca x scade, atunci y va scadea. Alternativ, poate fi opus, daca x creste, atunci y scade, iar daca x scade, atunci creste y .

Exemple de astfel de relatii izotonice sau monotonice includ:

• x este presiunea aplicata acceleratorului intr-o masina, y este acceleratia masinii (acceleratia creste pe masura ce se aplica mai multa presiune)
• x este rata la care un server web primeste solicitari HTTP, y este utilizarea CPU a serverului web (utilizarea procesorului serverului va creste odata cu cresterea ratei de solicitare)
• x este pretul unui articol, si y este probabilitatea ca cineva sa il cumpere (aceasta ar fi o relatie descrescatoare, deoarece x creste y scade)

Acestea sunt toate exemple ale unei relatii izotonice intre doua variabile, in care relatia este probabil mai complexa decat liniara.

Deci, stim ca relatia dintre x si y este izotonica si sa spunem, de asemenea, ca am reusit sa colectam date despre valorile reale x si y care apar in practica.

Ceea ce ne-ar placea cu adevarat sa putem face este sa estimam, pentru orice x dat , ce va fi y , sau alternativ pentru orice y dat , ce x ar fi necesar.

Dar, desigur, datele din lumea reala sunt zgomotoase si este putin probabil sa fie strict izotonice, asa ca dorim ceva care sa ne permita sa alimentam aceste date zgomotoase brute, sa ne dam seama de relatia reala dintre x si y si apoi sa folosim acest lucru pentru a ne permite pentru a prezice y dat x sau pentru a prezice ce valoare a lui x ne va da o valoare particulara a lui y . Acesta este scopul algoritmului pair-adjacent-violators.

… si de ce sa-mi pese?

Folosind exemplele oferite mai sus:

• O masina cu conducere automata ar putea sa o foloseasca pentru a afla cata presiune trebuie aplicata acceleratorului pentru a da o cantitate dorita de acceleratie
• Un sistem de scalare automata ar putea sa-l foloseasca pentru a ajuta la prezicerea numarului de servere web de care au nevoie pentru a gestiona o anumita cantitate de trafic web
• Un comerciant cu amanuntul ar putea sa-l foloseasca pentru a alege un pret pentru un articol care sa le maximizeze profitul (alias „optimizarea randamentului”)

Regresie izotonica in publicitatea online

Daca aveti la dispozitie o ora si doriti sa aflati mai multe despre modul in care functioneaza publicitatea online – ar trebui sa verificati aceasta prelegere pe care am sustinut-o in 2015, unde va explic cum am putut folosi perechea de violatori adiacenti pentru a rezolva unele probleme distractive.

O imagine valoreaza o mie de cuvinte

Iata relatia pe care PAV o extrage din unele date de intrare foarte zgomotoase in care exista o relatie in crestere intre x si y :

Caracteristici

• Incearca sa faci un lucru si sa o faci bine cu balonare minima, fara dependente externe (altele decat stdlib-ul lui Kotlin)
• Teste unitare foarte amanuntite, realizand aproximativ 75% acoperire a testului de mutatie
• Foloseste un algoritm splonic izotonic pentru interpolare lina
• Implementare destul de eficienta fara a compromite lizibilitatea codului
• In timp ce este implementat in Kotlin, functioneaza frumos din Java si alte limbaje JVM
• Suporta interpolare inversa
• Va inteligent extrapoleaza pentru a calcula y pentru valorile lui x mai mare sau mai mica decat cele folosite pentru a construi modelul PAV

Utilizare

Adaugarea dependentei de biblioteca

Puteti utiliza aceasta biblioteca adaugand o dependenta pentru Gradle, Maven, SBT, Leiningen sau un alt sistem de gestionare a dependentei compatibil cu Maven datorita Jitpack:

Utilizare de baza de la Kotlin

Utilizare de baza din Java

Intrebari / Feedback

Va rugam sa puneti intrebari, sa raportati erori, sa solicitati functii etc. prin intermediul problemelor Github, de asemenea, sunteti binevenit sa trimiteti cereri de extragere.

Licenta

Lansat sub versiunea LGPL versiunea 3 de Ian Clarke.

Vezi si

• O implementare a PAV pentru limbajul de programare Rust de catre acelasi autor: https://github.com/sanity/pair_adjacent_violators