炙心演算法

A. 論文閱讀_時序聚類K-Shape

這是一篇發表於2015年SIGMODE數據管理國際頂會的論文，它主要針對時序數據的聚類問題，提出了K-Shape方法。與以往的方法相比，它優化了距離計算方法，質心計算方法，還引入了提取頻域特徵方法，以提升效率。

作者認為它是一種獨立於領域、高精度、高效率的時間序列聚類方法。

我覺得相對於傳統方法，它聚類效果更好；相對於DTW類方法，效果稍差，但速度快很多。畢竟從原理來看，K-Shape只考慮了縱向拉伸和橫向平移，而DTW還考慮了橫向拉伸。

K-Shape原理和K-means相似，不同在於它改進了距離計算方法，並優化了質心計算方法。一方面支持振幅縮放和平移不變性，另一方面計算效率也比較高，並且不用手動設置參數，便於擴展到更多領域。

距離演算法用於計算兩組時序數據的差異，其中的核心問題是如何處理時序數據的形變，論文中的圖-1 展示的心電圖數據被分為A/B兩類：

其中A類的特點是：上升->下降->上升，而B類的特點是：下降->上升。圖-1 的右下圖展示了理想的建模效果，它識別到了相同的模式，而忽略了幅度和相位的差異。人們也更傾向使用這種方法計算距離，很多時候甚至認為距離計算方法比聚類方法更加重要。一般來說，支持振幅縮放和平移不變性的方法，計算成本較高，難以對大數據量建模。

K-Shape之前的主流距離演算法如下：

K-Shape用互相關方法計算兩個時間序列的距離。假設有X和Y兩個時間序列，序列長度均為m。為實現平移不變性，Y不變，一步一步劃動X，並計算每一步X與Y的差異。

如上圖所示：假設綠色區域為Y，白色區域為劃動的X，每一行s（step)向前劃動一步，序列長度為m=4，s∈(-3,3)共7種取值，w是所有移動的可能性2m-1=7次，w-m=s=k，也就是下面公式中的對齊位置（對齊邏輯貫穿整個演算法）。

定義互相關系數CC：

利用R來計算x和y在每一步的相似度，在對的上(在X,Y中都存在)的位置計算點積，最終R是有效區域的點積之和（對每個對上的小塊加和）。可以說，R越大兩個序列越相似。

由於對比的每個子序列振幅不同，塊數也不同，所以在對比時需要進行歸一化，歸一化方法有三種， 第三種使用了互相關方法，效果最好。

歸一化效果如下圖所示：

其中圖(a)使用z-normalization只做了對振幅的歸一化，沒有平移，可見在上述情況下，不平移（正對上）時對齊效果最好。從(b)(c)(d)可以看到：(d)圖使用第三種方法，在最中間的點上相似度值最大（s=0時），即正對上的時候，其相似度最大，這與(a)呈現出的效果一致。而(b)(c)都認為最相似的情況出現在右側，這明顯不太對。

文中定義了基於形態的距離SBD（Shape-based distance），塊重疊越多形狀越像CC越大，對比所有可能位置的相似度值，取最相似的max(CC)，然後用1-max(CC)得到SBD，也就是說形狀越相似，距離SBD越小，歸一化後的NCC值在[-1,1]之間，因此，SBD值在[0,2]之間。

可以看到，用以上方法時間在序列較長時復雜度比較高，當序列較長時，計算量也會很大，為解決這一問題，作者提出使用傅里葉變換將序列由時域轉到頻域再比較，以節約計算量。

定義了距離之後，還需要根據距離邏輯來調整質心演算法。

從圖-4 可以看到：時序數據的質心也是一條時序變化線，圖中的藍色線使用均值方法（計算每個點的均值）來計算質心；由於錯位，波峰和波谷被拉成了直線，因此不能正確地表達形狀趨勢。

K-Shape使用基於SBD的方式計算質心。

該公式的目標是尋找μk*，使質心μk與該簇Pk中各條序列xi的相似度NCC最大。

演算法一：先使用SBD() 函數計算dist和y'，dist是時序x,y之間的距離，y'是y中與x最匹配的子段。使用這種方法解決了波峰波谷對不齊，以致相互抵消的問題。

然後用基於線性代數方法，將公式13展開成公式15：

最終可利用瑞利商公式加以簡化：

瑞利商R(M,x)的一個重要的性質是：R的最大值等於矩陣M最大的特徵值，最小值等於矩陣M最小的特徵值。此時，就不用太考慮R(M,x)中的x(即本問題中的uk)。公式13被簡化成以下演算法：

演算法二：ShapeExtraction()根據簇的當前質心C和簇內的所有點X，計算更合理的質心C'。
line2: 遍歷簇內所有的點X(i)
line3: 計算各點與質心的距離dist以及其中與質心最為相似的片斷x'
line4: 將最為相似的片斷加入X'
line5: X'轉置與X相乘生成一個方陣（X的平方）
line6: 創建用於正則化的矩陣Q
line7: 正則化後生成矩陣M
line8: 取矩陣M對應最大特徵值時的特徵向量，以實現對X'的特徵抽取
（以上說明為個人理解，不一定對，僅供參考）

最終的聚類方法通過迭代實現，每次迭代分為兩步：第一步重新計算質心，第二步根據每個序列與新質心的距離將它們重新分配到不同的簇中；一直循環迭代到標簽不再變化為止。

演算法三：聚類的完整過程由 k-Shape() 實現：

其中X是所有序列，k是簇的個數，IDX是標簽。
line3: 在標簽穩定前&迭代次數不超過100次的條件下，不斷迭代
line4-10：根據簇中的元素重新計算每個簇的質心C
line11-line17：計算每個序列與各個質心的距離，並將它分配到新的簇中（重新打標簽）。

K-Shape演算法每次迭代所需時間為：
O(max{n·k·m·log(m), n·m^2, k·m^3})
其中n是實例個數，k是簇個數，m是序列長度。可見，該演算法大部分的計算代價依賴於時間序列的長度m。然而，這個長度通常比時間序列的數目小得多，因此，對m的依賴不是瓶頸。在m非常大的極少數情況下，可以使用分段或降維方法來有效地減小序列的長度。

圖-5對比了K-Shape、ED和DTW模型效果，可以看到絕大多數情況下，SBD好於ED，部分情況下SBD好於DTW。但SBD比DTW好在它速度更快。

B. 質心演算法matlab求講解

自從網路文庫和網路知道通道阻塞後，好久沒回答問題了，今天抽空回答一下：
clear
clc
for i=1:1:10
for j=1:1:10
x(j+(i-1)*10)=(i-1)*10;
y(j+(i-1)*10)=(j-1)*10;
end
end
figure
plot(x,y,'.')

hold on
axis([0 100 0 100])
xy=[x;y]
hold on
xm=90;
ym=90;
n=50;%在原有100個點中隨機產生50個點
for i=1:1:n
Sx(i)=rand(1,1)*xm;
Sy(i)=rand(1,1)*ym;
plot(Sx(i),Sy(i),'r*')
xlabel('x軸')
ylabel('y軸')
hold on
end
dm=30
m=100;%%%以上都知道，就是下面看不懂，求講解
for j=1:1:n
SS=[Sx(j);Sy(j)];%選擇一個點
k=0;
for i=1:1:m
d=norm((xy(:,i)-SS),2);%計算這個點和其它100點的距離(用歐式距離)
if d<=dm %距離小於閾值則記錄
xx(j,i)=xy(1,i);
yy(j,i)=xy(2,i);
k=k+1;
else%距離太大就不記錄(可以這么理解：將隨機點的周圍點作為一組，太遠的點就不作為這一組了)
xx(j,i)=0;
yy(j,i)=0;
end
end
if k~=0%如果這個隨機點所在的組不是空集，則計算該組的均值
cent(:,j)=[sum(xx(j,:));sum(yy(j,:))]/k;
else
cent(:,j)=0;
end
plot(cent(1,j),cent(2,j),'o')%畫出這個組的質心（將一張圖分為幾組）
hold on
plot([cent(1,j) Sx(j)],[cent(2,j) Sy(j)],'R') %畫出這個隨機點所屬於的質心
Title('Centroid')
hold on
MM=[cent(1,j);cent(2,j)]
e(j)=norm((MM-SS),2)/dm%計算誤差（質心和隨機點）
end
figure
axis([0 n 0 1])
j=1:1:n
plot(j,e(j) ,'-r.')%畫出這50個點的誤差，即距離質心的距離
hold on
Title('Centroid')
E=sum(e)/n

C. 自動跟蹤的跟蹤演算法

質心跟蹤演算法：這種跟蹤方式用於跟蹤有界目標，且目標與環境相比有明顯不同灰度等級，如空中飛機等。目標完全包含在鏡頭視場范圍內。

相關跟蹤演算法：相關可用來跟蹤多種類型的目標，當跟蹤目標無邊界且動態不是很強時這種方式非常有效。典型應用於：目標在近距離的范圍，且目標擴展到鏡頭視場范圍外，如航行在大海中的一艘船。

相位相關演算法：相位相關演算法是非常通用的演算法，既可以用來跟蹤無界目標也可以用來跟蹤有界目標。在復雜環境下（如地面的汽車）能給出一個好的效果。

多目標跟蹤演算法：多目標跟蹤用於有界目標如飛機、地面汽車等。它們完全在跟蹤窗口內。對復雜環境里的小目標跟蹤，本演算法能給出一個較好的性能。
邊緣跟蹤演算法：當跟蹤目標有一個或多個確定的邊緣而同時卻又具有不確定的邊緣，這時邊緣跟蹤是最有效的演算法。典型如火箭發射，它有確定好的前邊緣，但尾邊緣由於噴氣而不定。

場景鎖定演算法：該演算法專門用於復雜場景的跟蹤。適合於空對地和地對地場景。這個演算法跟蹤場景中的多個目標，然後依據每個點的運動，從而估計整個場景全局運動，場景中的目標和定位是自動選擇的。當存在跟蹤點移動到攝像機視場外時，新的跟蹤點能自動被標識。瞄準點初始化到場景中的某個點，跟蹤啟動，同時定位瞄準線。在這種模式下，能連續跟蹤和報告場景里的目標的位置。

組合跟蹤演算法：顧名思義這種跟蹤方式是兩種具有互補特性的跟蹤演算法的組合：相關類演算法 + 質心類演算法。它適合於目標尺寸、表面、特徵改變很大的場景。

D. java代碼怎麼實現計算圖像二值連通區域的質心

一：幾何距(Geometric Moments)知識與質心尋找原理

1. Image Moments是圖像處理中非常有用的演算法，可以用來計算區域圖像的質心，方向等幾何特性，同時Mpq的高階具有旋轉不變性，可以用來實現圖像比較分類，正是因為Moments有這些特性，很多手繪油畫效果也會基於該演算法來模擬實現。它的數學表達為：

它的低階M00，M01, M10可以用來計算質心，中心化以後M11,M02,M20可以用來計算區域的方向/角度

2. 什麼是質心

就是通過該點，區域達到一種質量上的平衡狀態，可能物理學上講的比較多，簡單點的說就是規則幾何物體的中心，不規則的可以通過掛繩子的方法來尋找。

二：演算法流程

1. 輸入圖像轉換為二值圖像

2. 通過連通組件標記演算法找到所有的連通區域，並分別標記

3. 對每個連通區域運用計算幾何距演算法得到質心

4. 用不同顏色繪制連通區域與質心，輸出處理後圖像

三：演算法效果

左邊為原圖， 右邊藍色為連通組件標記演算法處理以後結果，白色點為質心

四：關鍵代碼解析

1. 計算幾何距演算法代碼

doublem00 = moments(pixels, width, height, 0, 0);

doublexCr = moments(pixels, width, height, 1, 0) / m00;// row

doubleyCr = moments(pixels, width, height, 0, 1) / m00;// column

return new double[]{xCr, yCr};

E. 無線感測器網路加權質心定位演算法Matlab模擬的一些疑問。

你沒有定義信標節點（BeaconAmount）的個數。不定義肯定報錯啊。一下是我最近隨便編的一段類似於質心演算法的東西的核心部分，你的同學應該能看懂，有點幫助。
if num_of_neb_anchor(i)>1&&num_of_neb_anchor(i)<6
%如果未知節點i的鄰居錨節點個數在2和5之間
fenmu(i)=0;
fenzi_x(i)=0;
fenzi_y(i)=0;
fenzi_z(i)=0;
for k=1:num_of_neb_anchor(i)
distant_rssi(i,k)=sqrt((node_x(i)-neighbor_anchor_x(i,k))^2+(node_y(i)-neighbor_anchor_y(i,k))^2+(node_z(i)-neighbor_anchor_z(i,k))^2);
fenmu(i)=fenmu(i)+1/distant_rssi(i,k);
fenzi_x(i)=fenzi_x(i)+neighbor_anchor_x(i,k)/distant_rssi(i,k);
fenzi_y(i)=fenzi_y(i)+neighbor_anchor_y(i,k)/distant_rssi(i,k);
fenzi_z(i)=fenzi_z(i)+neighbor_anchor_z(i,k)/distant_rssi(i,k);
end
esti_node_x(i)=fenzi_x(i)/fenmu(i);
esti_node_y(i)=fenzi_y(i)/fenmu(i);
esti_node_z(i)=fenzi_z(i)/fenmu(i);%未知節點的估計坐標
end

F. 請問有無線感測器網I加權質心演算法matlab代碼嗎

[capture-of-moving.rar] - 本文詳細介紹了在視頻圖像的基礎上用!"#$ & 』(( )*+ 實現運動目標形心捕獲的具體程序"從而可以實現運動 目標的位置檢測 程序運用改進的形心演算法計算目標圖形 的中心坐標"並使用了計時器函數實時顯示坐標變化值
[codebook.rar] - 實現了基於碼書的運動檢測，並有與其他的檢測演算法做對比，例如MOG，Bayes，三幀差分等。
[xin.rar] - 無線感測器網路加權質心自定位演算法中加權質心演算法模擬

[qq1_2.rar] - 3種定位演算法（多邊：3 邊及4邊 最小二乘 質心）的主程序
[802.11opnet.rar] - 802.11opnet，802.11在OPNET中的模擬代碼
[rssic.rar] - 無線感測器網路的加權質心演算法，用matlab編程的，需要的可以參考
[Simulation1.rar] - 本程序先使用RSSI中對數常態模型來測距離，然後用三邊測量法來計算未知節點的坐標。
[RSSIxin.rar] - 基於RSSI測距的無線感測器網路改進質心定位演算法
[xinsuanfa2.rar] - 無線感測器網路中質心演算法，並有錨節點比例和誤差分析
[myDVHOP.rar] - 一種基於RSSI的DV-HOP加權演算法，該演算法基於節點接收信標節點位置元組時的信號強度（RSSI）對鄰居節點間跳數進行加權處理，將節點間的跳數與距離相關聯，模擬試驗結果證明該加權演算法可大大提高定位精度。

G. 質心演算法主要用於哪些方面的研究

手機好像不行家還是不行不就是就摔跤吧爸爸你睡吧

H. 二維人體質心的計算原理

質心原理。二維人體質心的計算基於質心原理的插值演算法，會使計算與測量的結果符合且更好，質心原理也就是對插值點只考慮與該點最鄰近周圍點的影響，確定出插值點與最鄰近的周圍點，一次來得出二維的人體質心。

I. Scratch -- Makey Makey 演算法課程

1. 枚舉法 -- 百錢百雞 M:控制購買數量

2. 遞推法 -- 精明的兔子（斐波那契）

3. 遞歸法 -- 漢諾塔 M：簡易漢諾塔

（https://scratch.mit.e/projects/67961040/）

4. 冒泡排序 -- 吃豆人 M：控制吃豆人或者直接點大小（https://scratch.mit.e/projects/107749084/）

（https://scratch.mit.e/projects/120325225/）

5. 貪心法 -- 田鼠糧倉 M：控制購物數量

6. 深度搜索 -- 自動尋路 https://scratch.mit.e/projects/73610308/

7. 回溯演算法 -- 自動迷宮 https://scratch.mit.e/projects/17358777/

8. Shunting Yard Algorithm -- 計算器 https://scratch.mit.e/projects/25237375/ M：計算器

9. 模糊演算法 -- 濾鏡 https://scratch.mit.e/projects/74217022/ M：滑動條

10. 質心演算法 -- 自由自在的三角形 https://scratch.mit.e/projects/82717794/#editor

11. 尋跡演算法 -- 尋跡小車 https://scratch.mit.e/projects/96272025/

12. 保證演算法 -- 走迷宮 https://scratch.mit.e/projects/2814737/#editor

13. 點燈游戲 -- https://scratch.mit.e/projects/1765283/

14. 回溯法 -- 八皇後游戲 https://scratch.mit.e/projects/142926062/

15 數獨游戲 -- https://scratch.mit.e/projects/135695216/

【復雜游戲;

吃豆人：https://scratch.mit.e/projects/117474890/

3D賽車 https://scratch.mit.e/projects/86222656/#editor

手繪圓形：https://scratch.mit.e/projects/68999758/#editor

3D圖形：https://scratch.mit.e/projects/127249376/#editor

打井：https://scratch.mit.e/projects/138013519/

密碼鎖： https://scratch.mit.e/projects/114259151/

水杯游戲：https://scratch.mit.e/projects/90643951/】

J. K-Means（二）初始質心的選擇

回顧：

通過第一講，我們已經知道了關於最優k值的選擇，可以用SSE（組內差）和輪廓系數。

K值的選擇

        1.先驗知識

        2.SSE

        3.輪廓系數

現在介紹一下 初始質心的選擇：

        1.隨機選擇

        選擇初始質心，我們可以用最基本的隨機方法，但是這種方法會導致一個局部最優解問題。即，將一個比較大的簇分裂，同時將兩個較小的簇進行合並。

        由於K-Means演算法具有不穩定性，初始質心選擇不同，結果也不同。所以解決局部最優的方法，其一可以多次運行演算法，選擇具有最小SSE值的那組作為最終解。這種方法通過多次運行，通過嘗試，來解決隨機選擇初始質心問題。

        不過可以通過以下其他方法來尋找比較好的初始質心。

        2.層次聚類

        通過層次聚類，劃分k個層次，計算出每個簇對應的質心作為K-Means演算法的初始質心。這種方法可以很好地解決初始質心指派不合理的問題。但是也有局限性。

        3.K-Means++

        K-Means++演算法是基本演算法的改進版，其區別就在於初始質心的選擇。

        該演算法第一個質心是隨機選擇的，接下來的質心基於樣本點與最近質心的距離，距離越大越可能被選為下一個質心，直到選擇完k個質心。

        該方法有效地解決了關於初始質心的選取問題，目前已經成為了一種硬聚類演算法的標准。但是該方法無法解決離群點問題。

        4.基於最近鄰密度

        該方法通過檢測樣本點的樣本密度和與之前質心的分散度來決定下一個質心。