[發明專利]出租車載客熱點識別推薦算法

在審

• 申請號: 201911104350.1
• 申請日: 2019-11-09
• 公開（公告）號: CN110851741A
• 公開（公告）日: 2020-02-28
• 發明（設計）人: 郭建國;閻磊;孫浩;李燁星;邢立軍;韓夢飛
• 申請（專利權）人: 鄭州天邁科技股份有限公司
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06F16/29;G06K9/62;G06Q50/30;G08G1/01
• 代理公司: 鄭州明華專利代理事務所(普通合伙) 41162
• 代理人: 高麗華

1.一種出租車載客熱點識別推薦算法，其特征在于，基于海量歷史乘客打車出行數據，通過在電子地圖上按照設定的參數構建網格、蜂窩和小區類型的電子圍欄輪廓，對歷史居民出行數據進行大數據挖掘，提煉出在時間和空間緯度上的客流出行特征模型，包括以下步驟：

第一步，把收到的數據經緯度，按投影法映射到平面直角坐標系，通過以下公式轉換，確定各數據在平面直角坐標系中的位置(x，y)，

x＝(R-R₀)×λ；

式中,λ代表經度，代表緯度，R代表投影半徑；

第二步，將轉換數據畫出在地圖上，研究人員進行初步的標定初步選取熱度區域；

第三步，采用Graham掃描法或Jarris步進法，通過凸包檢測對每一個區域進行檢測；

第四步，求出了凸包檢測覆蓋的面積，根據所選區域的面積，形狀和點數選擇合適的eps和min_points參數，用eps表示檢測半徑，用min_points表示最小閾值點，對每一個點進行檢測：以該點為中心eps為半徑的圓內，包含的點數超過了min_points，那么這個點就標記為核心對象；設該區域面積為S，區域內包含點數為N，則“最小測量尺度”k＝S/N；

凸包檢測覆蓋面積的采用DBSCAN聚類算法，

輸入：樣本集D＝(x₁，，...，x_m)，鄰域參數(∈，MinPts),樣本距離度量方式；輸出：簇劃分C；包括以下內容：

步驟1：初始化核心對象集合初始化聚類簇數k＝0，初始化未訪問樣本集合Γ＝D,簇劃分

步驟2：對于j＝1，2，...m,按下面的步驟找出所有的核心對象：

a)通過距離度量方式，找到樣本x_j的∈-鄰域子樣本集N∈(x_j)；

b)如果子樣本集樣本個數滿足|N∈(x_j)|≥MinPts，將樣本x_j加入核心對象樣本集合：Ω＝Ω∪{x_j}；

步驟3：如果核心對象集合則算法結束，否則轉入步驟4；

步驟4：在核心對象集合Ω中，隨機選擇一個核心對象o，初始化當前簇核心對象隊列Ω_cur＝{o},初始化類別序號k＝k+1，初始化當前簇樣本集合C_k＝{o},更新未訪問樣本集合Γ＝Γ-{o}；

步驟5：如果當前簇核心對象隊列則當前聚類簇C_k生成完畢,更新簇劃分C＝{C₁，...，C_k},更新核心對象集合Ω＝Ω-C_k，轉入步驟3；

步驟6：在當前簇核心對象隊列Ω_cur中取出一個核心對象o′,通過鄰域距離閾值∈找出所有的∈-鄰域子樣本集N∈(o′)，令Δ＝N∈(o′)∩Γ,更新當前簇樣本集合C_k＝C_k∪Δ,更新未訪問樣本集合Γ＝Γ-Δ,更新Ω_cur＝Ω_cur∪(Δ∪Ω)-o′，轉入步驟5；

輸出結果為：簇劃分C＝{C₁，...，C_k}；

其中x表示樣本集，i，j，m為大于0的整數，∈是上文中eps的希臘字母，是空集，在初始的時候每個簇里面都沒有元素故為空集；

第五步，經過聚類后，對分類的點進行可行性“區域范圍規劃”包括修改不可執行的路線；

第六步，實時計算，根據車載GPS發出定位，結合當天的熱點推薦地圖，以及該地區的重載率，路況信息，進行推薦。