從這 Accelerometers 來看, 會取出三個數字, 這三個數字本質雖然是 -1000 到 1000, 但就自由度的觀點來看, 真正表現的應該可以從這個三維空間轉換成二維的球面座標, 也就是大家常見到的 0~360, 及 -90~90 的座標系統, 只是雖然可以很輕易的以地心引力去定義平面(切平面/軸心), 但最大的問題是 0 度的定義是很麻煩的.
但實務上雖然這個球面座標轉換是可以降冪, 但事實上就盡量想出一個不損耗電力的最低計算是不划算的, 保持這個三維座標體系並不是不可以, 而當時想的 9 個數值應該是:
1. 這段時間移動的總距離
2. 這段時間的向量變化
3. 這段時間的最常見的方向
當然單單定義這段時間, 跟取樣頻率就是傷腦筋了, 一開始實作可能會用 5 秒或 15 秒來作取樣, 這個可以解決前兩點, 但最直覺的第三組數字卻是最難的部份, 因為如前面所說的, 就實務上這演算法早就存在, 是一個很單純的 Clustering 分群就可以做到的事, 但這個演算法在 Data Mining 已經是不能存在的, 更何況在手機上跑.
假設我們以 15 分鐘做一個現在的最常見方向, 就會有 60 組數字, 而每組數字有 3 個, 若是算距離的話就代表是三倍的時間, 接下來若是一個標準的 Clustering, 大概每次要計算 60!*3 次, 這數字之大可想而之, 若還不包含比較及找出新重心的計算.
而若這是一維的數字, 要找出最接近的一組數字已經很困難了, 更何況這是三維的三個數字, 當然理論上也可以嘗試著降冪, 例如把 -1000~1000 變成 -20~20, 一口氣把可能性縮小 125 倍, 然後用數值方法來去 Approach 一個 Feasible Solution, 而不是最佳解.
0. 計算 N 點的初始的解空間 (三維的最高與最低)
1. 計算平均
2. 排除距離平均最遠的點
3. 計算目前的解空間
4. 看看在剩下的 n 中, 其解空間是否是只剩 (n/N)^3 或是直接少於 1/9 (一個定數) => 其平均就是解
5. 回到 1
當然這個計算有很多相乘, 平方與開立方根的比較, 而若只是比較的話 (計算最遠的點) 直接就不用開方了, a^3>b^3 => a>b, 這樣就可以把 60! 的計算變成 60 次的計算, 因為這樣就不用計算目前所有點的相互距離, 直接用平均求點.
這個有一個很糟糕的假設:
一群距離最接近的數值, 會影響平均很大, 若能慢慢扣掉偏離的點, 就會逐漸逼近這一群最接近的數值的集合.
而這個的假設應該極有可能證偽, 但應該是可以相信適用在 95% 的解空間 (尤其是常態分佈後), 但確可以節省 99% 以上的計算.
[編按] 在找到一個合適的圖中, 無意翻到這個資源 (Data Clustering and Pattern Recognition (資料分群與樣式辨認)), 對 Clustering 有不錯的介紹, 只是我上面提的這個解法是用來找到最大群(最常見的姿勢), 而不是單純的分群.
但這篇跟 N900 有甚麼關係阿? 呵呵, 我也不知道, 但至少就演算法面要先想出手機中最麻煩的耗電問題吧.
沒有留言:
張貼留言