En god drosjetjeneste skal være trygg, pålitelig og rask. Brukeren vil ikke gå inn i detaljer: det er viktig for ham at han klikker på "Bestill"-knappen og mottar en bil så raskt som mulig som tar ham fra punkt A til punkt B. Hvis det ikke er noen biler i nærheten, bør tjenesten umiddelbart informere om dette slik at klienten ikke har det var falske forventninger. Men hvis tegnet "Ingen biler" vises for ofte, er det logisk at en person rett og slett slutter å bruke denne tjenesten og går til en konkurrent.
I denne artikkelen vil jeg snakke om hvordan vi ved hjelp av maskinlæring løste problemet med å søke etter biler i områder med lav tetthet (med andre ord hvor det ved første øyekast ikke er noen biler). Og hva kom ut av det.
forhistorie
For å ringe en taxi utfører brukeren noen få enkle trinn, men hva skjer inne i tjenesten?
| Bruker | Scene | Backend Yandex.Taxi |
|---|---|---|
| Velger startpunktet | pin | Vi lanserer et forenklet søk etter kandidater – pinsøk. Basert på sjåførene som er funnet, er ankomsttiden spådd - ETA i pinnen. Den økende koeffisienten ved et gitt punkt beregnes. |
| Velger destinasjon, pris, krav | By på | Vi bygger en rute og beregner priser for alle tariffer, tar hensyn til den økende koeffisienten. |
| Trykker på "Ring en taxi"-knappen | Rekkefølge | Vi starter et fullstendig søk etter bilen. Vi velger den mest passende sjåføren og tilbyr ham en bestilling. |
Про , и vi har allerede skrevet. Og dette er en historie om å finne sjåfører. Når en ordre er opprettet, skjer søket to ganger: på PIN-koden og på ordren. Søket etter en ordre foregår i to trinn: rekruttering av kandidater og rangering. Først finner man tilgjengelige sjåfører som er nærmest langs veigrafen. Deretter brukes bonuser og filtrering. De resterende kandidatene rangeres og vinneren mottar et bestillingstilbud. Hvis han samtykker, blir han tildelt bestillingen og går til leveringsstedet. Hvis han nekter, så kommer tilbudet til det neste. Hvis det ikke er flere kandidater, starter søket på nytt. Dette varer ikke mer enn tre minutter, hvoretter bestillingen kanselleres og brennes.
Å søke på en PIN-kode ligner på å søke på en bestilling, bare bestillingen er ikke opprettet og selve søket utføres kun én gang. Det brukes også forenklede innstillinger for antall kandidater og søkeradius. Slike forenklinger er nødvendige fordi det er en størrelsesorden flere pinner enn ordrer, og søk er en ganske vanskelig operasjon. Nøkkelpunktet for historien vår: Hvis det under det foreløpige søket ikke ble funnet noen egnede kandidater på PIN-koden, tillater vi deg ikke å legge inn en bestilling. Slik var det i hvert fall.
Dette er hva brukeren så i applikasjonen:
Søk etter biler uten biler
En dag kom vi med en hypotese: kanskje i noen tilfeller kan bestillingen fortsatt fullføres, selv om det ikke var noen biler på pinnen. Tross alt går det litt tid mellom pinnen og bestillingen, og søket etter bestillingen er mer fullstendig og noen ganger gjentatt flere ganger: i løpet av denne tiden kan tilgjengelige drivere vises. Vi visste også det motsatte: Hvis sjåfører ble funnet på pinnen, var det ikke et faktum at de ville bli funnet ved bestilling. Noen ganger forsvinner de eller alle nekter bestillingen.
For å teste denne hypotesen lanserte vi et eksperiment: vi sluttet å sjekke tilstedeværelsen av biler under et søk på en PIN-kode etter en testgruppe med brukere, det vil si at de hadde muligheten til å gjøre en "bestilling uten biler." Resultatet var ganske uventet: hvis bilen ikke var på pinnen, ble den i 29% av tilfellene funnet senere - ved søk på bestillingen! Dessuten var bestillinger uten biler ikke vesentlig forskjellig fra vanlige bestillinger når det gjelder kanselleringsrater, rangeringer og andre kvalitetsindikatorer. Bestillinger uten bil utgjorde 5 % av alle bestillinger, men litt over 1 % av alle vellykkede reiser.
For å forstå hvor utførerne av disse ordrene kommer fra, la oss se på statusene deres under et søk på en Pin:
- Tilgjengelig: var tilgjengelig, men ble av en eller annen grunn ikke inkludert i kandidatene, for eksempel var han for langt unna;
- På bestilling: var opptatt, men klarte å frigjøre seg eller bli tilgjengelig for ;
- Opptatt: muligheten til å akseptere bestillinger ble deaktivert, men så kom sjåføren tilbake til linjen;
- Ikke tilgjengelig: sjåføren var ikke på nett, men han dukket opp.
La oss legge til pålitelighet
Ytterligere bestillinger er bra, men 29 % av vellykkede søk betyr at 71 % av tiden ventet brukeren lenge og endte opp med å gå ingensteds. Selv om dette ikke er en dårlig ting fra et systemeffektivitetssynspunkt, gir det faktisk brukeren falskt håp og kaster bort tid, hvoretter de blir lei seg og (muligens) slutter å bruke tjenesten. For å løse dette problemet lærte vi å forutsi sannsynligheten for at en bil på bestilling vil bli funnet.
Opplegget er slik:
- Brukeren setter en nål.
- Det foretas søk på pinnen.
- Hvis det ikke er noen biler, spår vi: kanskje de dukker opp.
- Og avhengig av sannsynligheten, tillater eller tillater vi deg ikke å legge inn en bestilling, men vi advarer deg om at tettheten av biler i dette området på dette tidspunktet er lav.
I søknaden så det slik ut:
Ved å bruke modellen kan du opprette nye bestillinger mer nøyaktig og ikke berolige folk forgjeves. Det vil si å regulere forholdet mellom pålitelighet og antall bestillinger uten maskiner ved bruk av presisjonsgjenkallingsmodellen. Tjenestens pålitelighet påvirker ønsket om å fortsette å bruke produktet, det vil si at det til syvende og sist handler om antall turer.
Litt om presisjonsgjenkallingEn av de grunnleggende oppgavene i maskinlæring er klassifiseringsoppgaven: å tilordne et objekt til en av to klasser. I dette tilfellet blir resultatet av maskinlæringsalgoritmen ofte en numerisk vurdering av medlemskap i en av klassene, for eksempel en sannsynlighetsvurdering. Handlingene som utføres er imidlertid vanligvis binære: hvis bilen er tilgjengelig, lar vi deg bestille den, og hvis ikke, vil vi ikke gjøre det. For å være spesifikk, la oss kalle en algoritme som produserer et numerisk estimat for en modell, og en klassifikator en regel som tilordner den til en av to klasser (1 eller -1). For å lage en klassifisering basert på modellvurderingen, må du velge en vurderingsterskel. Hvordan avhenger i stor grad av oppgaven.
Anta at vi gjør en test (klassifiserer) for en sjelden og farlig sykdom. Basert på testresultatene sender vi enten pasienten til en mer detaljert undersøkelse, eller sier: «Bra, gå hjem». For oss er det mye verre å sende en syk person hjem enn å unødvendig undersøke en frisk person. Det vil si at vi ønsker at testen skal fungere for så mange virkelig syke som mulig. Denne verdien kalles recall =. En ideell klassifiserer har en tilbakekalling på 100 %. En degenerert situasjon er å sende alle til undersøkelse, da blir også tilbakekallingen 100%.
Det skjer også omvendt. Vi lager for eksempel et testsystem for studenter, og det har en juksedetektor. Hvis sjekken plutselig ikke fungerer for noen tilfeller av juks, så er dette ubehagelig, men ikke kritisk. På den annen side er det ekstremt ille å urettferdig anklage elever for noe de ikke har gjort. Det vil si at det er viktig for oss at blant de positive svarene til klassifisereren er det så mange riktige som mulig, kanskje til skade for antallet. Dette betyr at du må maksimere presisjonen = . Hvis utløsning skjer på alle objekter, vil presisjonen være lik frekvensen til den definerte klassen i prøven.
Hvis algoritmen produserer en numerisk sannsynlighetsverdi, kan du ved å velge forskjellige terskler oppnå forskjellige presisjonsgjenkallingsverdier.
I vårt problem er situasjonen som følger. Tilbakekalling er antall bestillinger vi kan tilby, presisjon er påliteligheten til disse bestillingene. Slik ser presisjonsgjenkallingskurven til modellen vår ut:
Det er to ekstreme tilfeller: ikke la noen bestille og la alle bestille. Hvis du ikke tillater noen, vil tilbakekallingen være 0: vi lager ikke bestillinger, men ingen av dem vil mislykkes. Hvis vi tillater alle, vil tilbakekallingen være 100 % (vi vil motta alle mulige bestillinger), og presisjonen vil være 29 %, dvs. 71 % av bestillingene vil være dårlige.
Vi brukte ulike parametere for utgangspunktet som tegn:
- Tid/sted.
- Systemtilstand (antall okkuperte maskiner av alle tariffer og pinner i nærheten).
- Søkeparametere (radius, antall kandidater, begrensninger).
Mer om skiltene
Konseptuelt ønsker vi å skille mellom to situasjoner:
- "Dyp skog" - det er ingen biler her på dette tidspunktet.
- "Uheldig" - det er biler, men ved søk var det ingen passende.
Et eksempel på «uheldig» er om det er stor etterspørsel i sentrum fredag kveld. Det er mange bestillinger, mange som er villige, og ikke nok sjåfører til alle. Det kan vise seg slik: det er ingen passende drivere i pinnen. Men bokstavelig talt i løpet av sekunder dukker de opp, for på dette tidspunktet er det mange sjåfører på dette stedet, og statusen deres endrer seg stadig.
Derfor viste ulike systemindikatorer i nærheten av punkt A seg å være gode funksjoner:
- Totalt antall biler.
- Antall biler på bestilling.
- Antall biler som ikke er tilgjengelig for bestilling i «Opptatt»-status.
- Antall brukere.
Tross alt, jo flere biler det er, jo mer sannsynlig er det at en av dem blir tilgjengelig.
Faktisk er det viktig for oss at ikke bare biler blir plassert, men at det også foretas vellykkede turer. Derfor var det mulig å forutsi sannsynligheten for en vellykket tur. Men vi bestemte oss for ikke å gjøre dette, fordi denne verdien i stor grad avhenger av brukeren og sjåføren.
Modelltreningsalgoritmen var . Data hentet fra eksperimentet ble brukt til trening. Etter implementeringen måtte opplæringsdata samles inn, noen ganger slik at et lite antall brukere kunne bestille mot modellens beslutning.
Resultater av
Resultatene av eksperimentet var som forventet: ved å bruke modellen kan du øke antallet vellykkede turer betydelig på grunn av bestillinger uten biler, men uten at det går på bekostning av påliteligheten.
For øyeblikket har mekanismen blitt lansert i alle byer og land, og med dens hjelp skjer omtrent 1% av vellykkede reiser. Dessuten, i noen byer med lav tetthet av biler, når andelen av slike turer 15%.
Andre innlegg om Taxiteknologi
Kilde: www.habr.com