Yandex.Taxi가 자동차가 없을 때 자동차를 검색하는 방법

좋은 택시 서비스는 안전하고 신뢰할 수 있으며 빨라야 합니다. 사용자는 세부 사항을 설명하지 않습니다. "주문" 버튼을 클릭하고 가능한 한 빨리 자동차를 받아 A 지점에서 B 지점으로 이동하는 것이 중요합니다. 근처에 자동차가 없는 경우 서비스를 받아야 합니다. 고객이 잘못된 기대를 갖지 않도록 이에 대해 즉시 알리십시오. 그러나 "자동차 금지" 표시가 너무 자주 나타나면 해당 서비스 사용을 중단하고 경쟁사로 이동하는 것이 논리적입니다.

이 기사에서는 기계 학습을 사용하여 밀도가 낮은 지역(즉, 얼핏 보면 자동차가 없는 지역)에서 자동차를 검색하는 문제를 어떻게 해결했는지에 대해 이야기하고 싶습니다. 그리고 그 결과.

선사 시대

택시를 부르기 위해 사용자는 몇 가지 간단한 단계를 수행하지만 서비스 내부에서는 어떤 일이 발생합니까?

사용자	무대	백엔드 Yandex.Taxi
시작점을 선택합니다	핀	후보자에 대한 단순화된 검색인 핀 검색을 시작합니다. 발견된 운전자를 기반으로 도착 시간이 예측됩니다. 즉, 핀에 ETA가 표시됩니다. 특정 지점에서 증가하는 계수가 계산됩니다.
목적지, 운임, 요건을 선택합니다.	권하다	우리는 증가하는 계수를 고려하여 경로를 구축하고 모든 관세에 대한 가격을 계산합니다.
"택시 호출" 버튼을 누릅니다.	주문	우리는 자동차에 대한 전체 검색을 시작합니다. 우리는 가장 적합한 운전자를 선택하고 그에게 주문을 제안합니다.

약 핀의 ETA, 가격 계산 и 가장 적합한 드라이버 선택 우리는 이미 썼습니다. 그리고 이것은 운전자를 찾는 이야기입니다. 주문이 생성되면 핀과 주문에 대해 검색이 두 번 발생합니다. 주문 검색은 후보자 모집과 순위의 두 단계로 이루어집니다. 먼저, 도로 그래프를 따라 가장 가까운 후보 운전자를 찾습니다. 그런 다음 보너스와 필터링이 적용됩니다. 나머지 후보자의 순위가 매겨지고 승자는 주문 제안을 받습니다. 동의하면 주문이 배정되고 배송 지점으로 이동합니다. 그가 거절하면 제안은 다음 제안으로 넘어갑니다. 더 이상 후보자가 없으면 검색이 다시 시작됩니다. 이는 XNUMX분 이상 지속되지 않으며, 그 이후에는 주문이 취소되고 소각됩니다.

핀 검색은 주문 검색과 유사하지만 주문만 생성되지 않고 검색 자체가 한 번만 수행됩니다. 후보자 수와 검색 반경에 대한 단순화된 설정도 사용됩니다. 이러한 단순화는 순서보다 핀 수가 훨씬 더 많고 검색이 다소 어려운 작업이기 때문에 필요합니다. 이야기의 핵심: 예비 검색 중에 핀에서 적합한 후보자를 찾을 수 없는 경우 주문을 할 수 없습니다. 적어도 예전에는 그랬습니다.

사용자가 애플리케이션에서 본 내용은 다음과 같습니다.

자동차 없는 자동차 검색

어느 날 우리는 가설을 세웠습니다. 아마도 어떤 경우에는 핀에 자동차가 없더라도 주문이 여전히 이행될 수 있을 것입니다. 결국 핀과 주문 사이에 약간의 시간이 흐르고 주문 검색이 더 완전해지고 때로는 여러 번 반복됩니다. 이 시간 동안 사용 가능한 드라이버가 나타날 수 있습니다. 우리는 그 반대도 알고 있었습니다. 드라이버가 핀에서 발견되면 주문할 때 발견된다는 것은 사실이 아닙니다. 때때로 그들은 사라지거나 모두가 주문을 거부합니다.

이 가설을 테스트하기 위해 우리는 실험을 시작했습니다. 테스트 그룹의 사용자를 대상으로 핀을 검색하는 동안 자동차 존재 여부 확인을 중단했습니다. 즉, 사용자는 "자동차 없이 주문"할 기회를 얻었습니다. 결과는 전혀 예상치 못한 것이었습니다. 자동차가 핀에 없으면 29%의 경우 나중에 주문을 검색할 때 발견되었습니다! 또한, 차량이 없는 주문은 취소율, 평점, 기타 품질 지표 측면에서 일반 주문과 큰 차이가 없었습니다. 자동차 없이 예약한 경우는 전체 예약의 5%를 차지했지만, 성공한 전체 여행의 경우에는 1%를 조금 넘었습니다.

이러한 주문의 집행자가 어디에서 왔는지 이해하기 위해 핀 검색 중 해당 상태를 살펴보겠습니다.

• 사용 가능: 이용 가능했지만 어떤 이유로 후보자에 포함되지 않았습니다. 예를 들어, 그는 너무 멀리 떨어져 있었습니다.
• 주문 시: 바빴지만 그럭저럭 자유로워지거나 다른 일을 할 수 있게 되었습니다. 체인 주문;
• 바쁘다: 주문 수락 기능이 비활성화되었지만 운전자가 라인으로 돌아 왔습니다.
• 사용 불가: 운전자는 온라인 상태가 아니었는데 나타났습니다.

신뢰성을 더해보자

추가 주문도 좋지만, 검색 성공률이 29%라면 사용자의 71%가 오랜 시간 기다렸다가 결국 아무데도 가지 못했다는 의미입니다. 이는 시스템 효율성 측면에서 나쁜 것은 아니지만 실제로는 사용자에게 헛된 희망을 주고 시간을 낭비하게 하며, 그 후 사용자는 화가 나서 서비스 사용을 중단하게 됩니다. 이 문제를 해결하기 위해 우리는 주문한 차량이 발견될 가능성을 예측하는 방법을 배웠습니다.

계획은 다음과 같습니다.

• 사용자가 핀을 꽂습니다.
• 핀에 대한 검색이 수행됩니다.
• 자동차가 없다면 우리는 아마도 자동차가 나타날 것이라고 예측합니다.
• 그리고 확률에 따라 주문을 허용하거나 허용하지 않지만, 현재 이 지역에는 차량 밀도가 낮다는 점을 알려드립니다.

응용 프로그램에서는 다음과 같이 보였습니다.

모델을 사용하면 새로운 주문을 더 정확하게 생성할 수 있으며 사람들을 헛되이 안심시키지 않을 수 있습니다. 즉, 정밀도-리콜 모델을 이용하여 기계 없이 신뢰도 비율과 주문 수를 규제하는 것입니다. 서비스의 신뢰성은 제품을 계속 사용하려는 욕구에 영향을 미칩니다. 즉, 결국 모든 것은 여행 횟수에 달려 있습니다.

정밀도-재현율에 대해 조금기계 학습의 기본 작업 중 하나는 분류 작업입니다. 즉, 개체를 두 클래스 중 하나에 할당하는 것입니다. 이 경우 기계 학습 알고리즘의 결과는 확률 평가와 같이 클래스 중 하나의 멤버십에 대한 수치적 평가가 되는 경우가 많습니다. 그러나 수행되는 작업은 일반적으로 이분법적입니다. 자동차를 이용할 수 있으면 주문할 수 있고, 그렇지 않으면 주문하지 않습니다. 구체적으로 수치 추정을 생성하는 알고리즘을 모델이라고 부르고 분류기를 두 클래스(1 또는 -1) 중 하나에 할당하는 규칙이라고 하겠습니다. 모델 평가를 기반으로 분류자를 만들려면 평가 임계값을 선택해야 합니다. 얼마나 정확하게 작업에 따라 크게 달라집니다.

희귀하고 위험한 질병에 대한 테스트(분류자)를 하고 있다고 가정해 보겠습니다. 검사 결과에 따라 더 자세한 검사를 위해 환자를 보내거나 "좋아, 집에 가세요"라고 말합니다. 우리에게 아픈 사람을 집으로 보내는 것은 건강한 사람을 불필요하게 검사하는 것보다 훨씬 더 나쁩니다. 즉, 우리는 가능한 한 많은 아픈 사람들에게 이 검사가 효과가 있기를 바랍니다. 이 값을 재현율 =이라고 합니다.. 이상적인 분류기의 재현율은 100%입니다. 타락한 상황은 모든 사람을 검사에 보내는 것이며 리콜도 100%가 됩니다.

그 반대의 경우도 발생합니다. 예를 들어, 우리는 학생들을 위한 테스트 시스템을 만들고 있는데 그 시스템에는 부정행위 감지 기능이 있습니다. 일부 부정 행위에 대해 갑자기 확인이 작동하지 않으면 이는 불쾌하지만 중요하지는 않습니다. 반면에, 학생들이 하지 않은 일을 부당하게 비난하는 것은 극히 나쁜 일입니다. 즉, 분류자의 긍정적인 답변 중에는 가능한 한 많은 정답이 있고 그 수는 줄어들 수 있다는 것이 우리에게 중요합니다. 이는 정밀도를 최대화해야 함을 의미합니다 = . 모든 객체에서 트리거링이 발생하면 정밀도는 샘플에 정의된 클래스의 빈도와 동일합니다.

알고리즘이 수치적 확률 값을 생성하는 경우 다른 임계값을 선택하여 다른 정밀도-재현율 값을 얻을 수 있습니다.

우리 문제의 상황은 다음과 같습니다. 리콜은 우리가 제공할 수 있는 주문 수이고, 정밀도는 이러한 주문의 신뢰성입니다. 우리 모델의 정밀도-재현율 곡선은 다음과 같습니다.

두 가지 극단적인 경우가 있습니다. 누구도 주문하지 못하게 하는 것과 모든 사람이 주문하도록 허용하는 것입니다. 누구도 허용하지 않으면 리콜은 0이 됩니다. 주문을 생성하지 않지만 그 중 어느 것도 실패하지 않습니다. 모든 사람을 허용하면 재현율은 100%(가능한 모든 주문을 받음)가 되고 정밀도는 29%가 됩니다. 즉, 주문의 71%가 불량이 됩니다.

우리는 시작점의 다양한 매개변수를 기호로 사용했습니다.

• 시간/장소.
• 시스템 상태(인근의 모든 관세 및 핀이 점유된 기계 수).
• 검색 매개변수(반경, 후보 수, 제한 사항)

징후에 대한 추가 정보

개념적으로 우리는 두 가지 상황을 구별하고 싶습니다.

• “깊은 숲” – 현재 이곳에는 차가 없습니다.
• "불운" - 자동차가 있지만 검색할 때 적합한 자동차가 없었습니다.

"불운"의 한 가지 예는 금요일 저녁에 센터에 수요가 많은 경우입니다. 주문은 많고 원하는 사람은 많지만 모든 사람을 위한 운전자는 충분하지 않습니다. 다음과 같이 나타날 수 있습니다. 핀에 적합한 드라이버가 없습니다. 그러나 문자 그대로 몇 초 안에 그들은 나타납니다. 왜냐하면 현재 이곳에는 많은 운전자가 있고 그들의 상태는 끊임없이 변화하고 있기 때문입니다.

따라서 A 지점 근처의 다양한 시스템 표시기가 좋은 특징으로 판명되었습니다.

• 총 자동차 수.
• 주문 차량 수.
• "Busy" 상태에서 주문할 수 없는 차량 수입니다.
• 사용자 수.

결국, 자동차가 많을수록 그 중 하나를 이용할 수 있을 가능성이 더 높아집니다.
사실, 자동차의 위치뿐만 아니라 성공적인 여행이 이루어지는 것도 우리에게 중요합니다. 그러므로 여행의 성공 확률을 예측할 수 있었다. 하지만 우리는 이렇게 하지 않기로 결정했습니다. 왜냐하면 이 값은 사용자와 운전자에 따라 크게 달라지기 때문입니다.

모델 훈련 알고리즘은 다음과 같습니다. 캣부스트. 실험에서 얻은 데이터는 훈련에 사용되었습니다. 구현 후에는 교육 데이터를 수집해야 했으며 때로는 소수의 사용자가 모델 결정에 반대하는 명령을 내릴 수도 있었습니다.

결과

실험 결과는 예상한 대로였습니다. 모델을 사용하면 자동차 없이도 주문으로 인해 성공적인 여행 횟수를 크게 늘릴 수 있지만 신뢰성은 저하되지 않습니다.

현재 이 메커니즘은 모든 도시와 국가에서 시작되었으며 그 도움으로 성공적인 여행의 약 1%가 발생합니다. 더욱이, 자동차 밀도가 낮은 일부 도시에서는 이러한 여행의 비율이 15%에 이릅니다.

택시 기술에 관한 다른 게시물

• Yandex.Taxi에서 운전자 간에 주문을 분배하는 방법
• 동적 가격 책정 또는 Yandex.Taxi가 높은 수요를 예측하는 방법
• 컴퓨터 비전을 사용하여 자동차 상태를 평가하는 방법. Yandex.Taxi 경험
• Yandex.Taxi가 기계 학습을 사용하여 자동차 픽업 시간을 예측하는 방법

출처 : habr.com