炙心算法

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.基于最近邻密度

        该方法通过检测样本点的样本密度和与之前质心的分散度来决定下一个质心。