[R] RJDBC的例子，透過顧客行為的相似度建立推薦系統

自從之前安裝好R上的 rJava 和 RJDBC 套件（這篇：R 上安裝 RJDBC 和 rJava 的除錯），就應該可以借回那本書繼續學習R上連結用MySQL的例子。加上最近又想繼續股票短線的技術分析模型，希望將計算後的指標輸出到 Excel可以接手做試驗的形式，於是這幾天都在對著RStudio。股票方面思考過匯出怎樣的資料和格式才方便Excel處理，整理過之前的幾段Scirpt, 但想要的結果仍在做回溯測試中。而SQL的例子就可以告一段落了。
這個例子中的"Sakila"數據是MySQL 提供的樣本，假設一間DVD租售店的營運，數據庫的結構參考: https://dev.mysql.com/doc/sakila/en/sakila-structure.html。這個教學例子是利用顧客的租借記錄，以及電影的類別、分級等資料，製做一個推薦系統，為顧客推薦他可能有興趣的電影。一個方法是計算利用顧客的借閱記錄計算顧客間的相似性，這個就是下面的例子。書中也提及另一個方法是利用被電影被借閱的記錄計算電影間的相似性。實際上，更好的算法應該還要考慮在新的顧客或電影時如何更新推薦。

[Java/Excel] 用 Eratosthenes Sieve (和 Euler Sieve) 求質數表，以及因式分解

上星期想破頭的數論之後，這星期都在看質數相關的Coding。

雖然最終要求的是：$ x^2+y^2 ＝N $ 的整數解，過程中也回顧了 Eratosthenes's Sieve 求質數表，和用質數表做因式分解 的方法。所用的語言方面，一個目標是自己想要熟習，而且資源又常見的Java；另一個是如果自己在中學時期想這樣做的話，應該會用到的VBA。

Java的例子不少，但試過才知道即使實現的是同一套算法，效率也可以有很大差別。從前只知道應用數學中會看一套算法的Big O去比較時間複雜度，但原來實踐起來用什麼語言、什麼變數物件，結果用什麼什麼形式去表現⋯⋯都會大大影響速度。就是為了找出實際運行得更快的寫法，就一頭栽到這個質數的做法上。雖然一開始時用LinkedList、Map等寫法真的很方便理解，但之後還是儘量換成基本的陣列。

下面這樣的Java寫的  Eratosthenes Sieve 求 一億（$10^8$）之內的質數，大約是10秒。如果不計最後一個for loop用來製作傳回值的LinkedList<Integer>的話，主流程大約4秒。不過要求更大的質數，應該還要考慮該程式對使用整數的上限（int: [-2,147,483,648, 2,147,483,647]），大數字在記憶體的儲存方法，整數表的儲存方法等。很多事情都是這樣吧，開始時只要求做到是容易的，但要追求深究下去就會困難⋯⋯

最後還有兩個方法是Modified Eratosthenes Sieve 和 Euler Sieve，都是理論上應該更有效率的算法，不過實踐起來還是達不到應有的分別，要怪我對如何更好地寫代碼還是不熟識吧。 Eratosthenes Sieve的Modification的想法是一開始就不考慮2和3的倍數，只看6k+1和6k+5的情況。至於 Euler Sieve 是改善Eratosthenes Sieve中一個合成數會重覆被質數篩去而浪費的時間，例如，合成數6 會在篩選質數 2和3 的倍數時重覆考慮。理想中Eratosthenes Sieve的時間複雜度是 O( n*log(log(n)) )，而Euler Sieve的時間複雜度是O(n)。實測中，同樣求一億（$10^8$）之內的質數，大約是2-3秒的時間。

[Math] 由3個連續數組成的平方和組合 - Consecutive Triple, which are simultaneously sum of 2 squares

前言

先看一下以下數式，有某些數字可以寫成2個平方的和。

 $
00 = 0^2 + 0^2\\
01 = 1^2 + 0^2\\
02 = 1^2 + 1^2\\
03 = ---..... =3;\\
04 = 2^2 + 0^2\\
05 = 2^2 + 1^2\\
06 = ---...... =2*3\\
07 = ---...... =7\\
08 = 2^2 + 2^2\\
09 = 3^2 + 0^2\\
10 = 3^2 + 1^2   \\
11 = ---..... =11 \\
12 = ---.....  =2*2*2*3\\
13 = 3^2 + 2^2\\
14 = ---..... =2*7\\
15 = ---..... =3*5\\
16 = 4^2 + 0^2\\
17 = 4^2 + 1^2\\
18 = 3^2 + 3^2\\
19 = ---..... =19\\
20 = 4^2 + 2^2\\
......\\
$
$
25 = 4^2 + 3^2 = 5^2 + 0^2\\
......\\
65 = 7^2 + 4^2 = 8^2 + 1^2\\
......\\
$

－　某些數字可以寫成2個平方的和，某些則不能，而要寫成更多個平方的和。公元3世紀時的Diophantus提出「是否每一個正整數都是四個平方數之和」的問題。更一般性的問題是 18世紀時的Waring’s problem，他猜想：「對於每個非1的正整數 k，皆存在正整數 g(k)，使得每個正整數都可以表示為至多g(k)個k次方數之和。」Diophantus的提問即是當 k=2 的情況 。Lagrange證明了這個情況是 g(2) = 4：任何一個正整數可用4個平方數之和得出。
(e.g. $60=7^2+3^2+1^2+1^2$)

其他情況的證明有 Arthur Wieferich：g(3)=9。Joseph Liouville：g(4)=19。陳景潤：g(5)=37。任何一個正整數可用9個立方數之和、或19個4次方數之和、或37個5次方數之和得出。


－　而對於一個正整數是否可以寫成兩個平方數之和。
首先可留意到上面3、7、11、15、19.... 這些 $(4k+3)$ 的單數項都不能表達成兩個平方數之和。要將一個單數寫成兩個平方之和，兩數必定是一正一負，寫成： $(2k+1)^2 + (2k)^2 =  4(2k^2 + k) + 1$。Fermat首先證明對於單數的質數，可以寫成 (4k+1) 是該數能否寫成兩個平方數之和的充分及必要的條件。 然後，再留意上面寫不到平方和的例子，質因數分解中都出現單數次(4k+3) 形式的質因數項。Euler 證明出以下的條件:

"A number N is expressible as a sum of 2 squares if and only if in the prime factorization of N, every prime of the form (4k+3) occurs an even number of times! "

$$N = {2}^{a_0} {p_1}^{2a_1}...{p_r}^{2a_r} {q_1}^{b_1}...{q_s}^{b_s}$$
於是，我們可以分辨出一個數是否可以寫成兩個平方之和。

2016年秋 - 一個月的外地工作：印度班加羅爾(Bangalore)－食

今年終於成行到印度的Bangalore的部門，訓練這邊的同事接手部份工作。居住和工作的地方都位於Bellandur區，附近都是辦公室的地區，有幾個科學園區、商業園區、工業園區，這些有點像香港的科學園般，我們公司就用到園區內某大樓的數層作辦公室。

如果在Google上尋找，你會看到Bengaluru這個名字，話說在2014年正式改名為Bengaluru之前這裡一直是稱為Bangalore，平時生活基本上都是見習慣用Bangalore的。而印度政府早在20年代至今一直有將一些城市改名，例如Bangalore附近的Mysore(舊)改名為Mysuru(新)、旅遊地點Ooty(習慣)與Udhagamandalam(正式)，我一直認知的交易所Bombay(舊)原來即是Mumbai(新)。在找資料時記得有時用舊名更方便。

雖然今次出差有一個月的日子，不過星期一至五專心工作，自己也帶了電腦、書和電路板繼續項目，都是周未才會外出。除了Bellandur附近的街道，也就去了Bangalore的市中心，跟當地團去參觀Bangalore附近的城市Mysore。今次正正經歷到 8/11 印度總理 宣佈大額紙幣 500和1000盧比 即晚起停止流通，逼使國民存回銀行和申報。他目的是打擊國民瞞稅和權貴舞弊而藏在家中的"黑錢"，事前未有透露計劃，由宣佈到實行只有4小時。Mysore之行正好在廢鈔令之後的周未，在擔心缺錢下，由包車也改為跟團，總算遊了一趟。

在印度一個月的「食、住、行」方面的體驗，「食」留下的照片最易整理，就先記錄食的部份。還有很多沒有拍下的就留在印象中，有拍照的如下：

小食

公司園區外有一堆流動小食檔，由下午4-5時開檔至凌晨。賣茶或咖啡（和煙）的檔主第二朝一早就已經見佢開檔，仲會帶住脆口的零食。

Dosa：Dosa有兩種，比較喜歡煎成脆身的Dosa，內裡可以加入餡料，再沾些醬汁。圖中是綠色帶薄荷／香草的Mint Chutney，一向比較喜歡。其他地方試過最喜歡那種白色不帶辣的Coconut Chutney，另一款辣的甘醬就不太合口味了。

Android + Arduino 小車的手機藍牙遙控計劃

對於手機的Android Apps今次是作為初學者的第一個項目。但不枉我在這次印度公幹期間，電腦之外，我都執了幾件零件和書。在印度試好了如何在Android上用藍牙連接Arduino，簡單的按鍵去傳送方向指令（數字），和預備日後作其他用途的顯示和輸入介面。詳細的檔案己經放到下面的dropbox link。
Arduino Sketch: https://dl.dropboxusercontent.com/u/71621110/Blogger/Sketch_CarBT.ino
Android Project: https://dl.dropboxusercontent.com/u/71621110/Blogger/myFirstBluetoothApp.zip

 Arduino

首先，Arduino 的Sketch中，令小車移動的指令是連接L298D的4個腳位控制個馬達的正轉反轉和速度。先把向前向後轉左轉右等指令包裝成forward()、backward()、left()、right()、brake()等指令：

int Left_motor_go=8;     //左馬達前進(IN1)
int Left_motor_back=9;     //左馬達後退(IN2)
int Right_motor_go=10;    // 右馬達前進(IN3)
int Right_motor_back=11;    // 右馬達後退(IN4)

void forward()     // 前進
{
  digitalWrite(Right_motor_go,HIGH);  // 右馬達前進
  digitalWrite(Right_motor_back,LOW);     
  digitalWrite(Left_motor_go,LOW);  // 左馬達前進
  digitalWrite(Left_motor_back,HIGH);
  
  analogWrite(Right_motor_go,200);
  analogWrite(Right_motor_back,0);  
  analogWrite(Left_motor_go,0);
  analogWrite(Left_motor_back,200);
}

連接藍牙到Arduino時要像以下般連接，藍牙模組會直播接連到板子上的TX，RX 腳位。當Arduino開始"setup()"時除了設定相關腳位的pinMode外，也需設定Serial的通訊。之後的程式上就可以像Serial 通訊般互傳指令。而Serial Rate 要跟自己藍牙模組的Baud Rate 相同，才可以在同一頻率下理解訊息。之前在電腦上搜尋這藍牙時，確定自己用的是HC-05的藍牙組件。HC-05出廠設定是rate=9600，配對密碼1234。

Bluetooth's TX  <-->  Arduino's RX

Bluetooth's RX  <-->  Arduino's TX

Bluetooth's GND  <-->  Arduino's GND

Bluetooth's VCC  <-->  Arduino's 5V