讲稿月机器学习

66

f

,

令

,

,

1

x2ix2

0xi

1 k

fx1,x2xk

x

k

E2 用估计量ˆ去估计θ，其误差是ˆ，该差显然随样本X1,X2,Xn而定，因此，ˆ随量，它的平方的均值，称作均方

显然，若ˆ是无偏估计，则MSE即方差

了解层次聚类理度聚类并能够应用于实掌握谱聚类闵可夫斯基距离Minkowski/欧式距

distX,Y

x

1p杰卡德相似系数

JA,BAAAaTba

i 余弦相似度(cosine

cosncovX,Y

EXY

XiXYiYXY

Pearson相似系

X

X

Y相对熵(K-L距离

Dp|q

px

iE

px qx

px

qx

Dp|q

2 1

px1qx1dx 12

inger Dp||q 1

1

px

qx

dx

21

2

pxdxqxdx2 pxqxdxpx2 pxqxqxpx qx 2dx余弦相似度与Pearson相似系ncos

xT

xixnxxnxi nyincovX,Y

EXY

xiXyiYXY

22 22 X

xi

–X

yi

–Y假定输入样本为S=x1,x2,...,xm，则算法步骤选择初始的k个类别中心对于每个样本xi，将其标记为距离类别中心最近的类别，即

arg1jk

xi将每个类别中心更新为隶属该类别的所有样本的均j1j|cj

重复最后两步，直到类别中心的变化小于某阈值最小平方误差MSE(MinimumSquared6666数组、、、、的均值为是解决聚类问题的一种经典算法，简单、对处理大数据集，该算法保持可伸缩性和当簇近似为高斯分布时，它的效果较不适合于发现非凸形状的簇或者大小差别很大的对躁声和孤立点数AGNESAGglomerativeNESting)算法最初将每个对DIANA(DIvisive 程，属于的层次聚类，首先将所有的对象初始密度最大值算 DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)pi∈D，(1≤i≤n)，pi+1是从pi关于ε和m直接密度可达的，簇：一个基于密度的簇是最大的密度相连对象的集合噪声：不包含在任何簇中的对象称为噪声作为对象的新簇；寻找并合并对象直接密度可达的对象没有新点可以更新簇时，算法每个簇至少包含一 对象 包含过少对象的簇被认为是噪密度最大值聚类是一种简洁优美的聚类算法可以识别各种形状的类簇,并且参数很容易确定。i

j

–

，其中，x

xdc是一个截断距离ρi即到对象i的距离小于dc的对象的个数。由于该算法只对ρi的相对值敏感所以对dc的选择是简称“高密距离”(注：该称呼不具代表性)高局部密度点距高局部密度点距离

min ijj:j左图是所有点在二的分布,右图是以ρ为横坐标以δ为纵坐标绘制的决策图。可以看到，1和(borderregion)，亦即划分给该簇但是距离其他簇的该簇中所有局部密度大于ρh的点被认为是簇的6666

Ax

Ax

Ax

xTAxxTAx

xTAxxT

xT

xxTxT

xTx

–xTx而xT

nn

xi

nx0inx0i所 0应的特征向量分别是μ1μ2；其中，λ1λ2μ1μ2都则有：Aμ1=λ1μ1，(Aμ1)T=(λ1μ1)T，从而所以同时，μ1TAμ2=μ1T(Aμ2)=μ1Tλ2μ2所以故：(λ1-λ2而λ1≠λ2，所以μ1Tμ2=0，即：μ1，μ2正交将多个特征综合为少数几性特征

Taa aaT2A

am1,n

maTm

1am Tam假定样本是去均值化a取投影直线L的延伸方向u，计算A×u的a

Ta aT2

Tuaa12Tuaa12Au

u

am1,n

maTm

am1 aTam1

u

amn

1am Tam

TuVarAu

Au

E

Au

–E

Au

目标函数：Ju

1uTAT2

Ju

12

AT2u 2u

1

uTu2建立Lagrange2Lu

12

AT

–uT

Lu

AT

令–u0

AT

ATA常常称为散列矩阵(scatter以上即为主成分分析PCA的推导过程方法，通过对样本数据的拉斯矩阵的特成相似度图(similaritygraph)：G=(V,E)。如无向图顶点的度di度矩阵D(对角阵子图A εk近邻图(k-nearestneighborε近邻图：ε=0.3，“月牙部分”非常紧的连接了，但“部全连接图：使用相似度函数可以很好的建立权值矩阵。但矩阵：L=D–WLL的最小特征值是0L有n定理：令G是权值非负的无向图，若两个点的相似度值越大，表示这两个点越相似同时，定义wij=0表示vi,vj两个点没有任何相似性(无穷远dii表示第i个点的除主对角线元素，D其他位置为未正则的矩阵：L=D-矩矩正则矩矩矩对称随Random正则矩阵的性(0，1)是Lrw的特征值和特征向量，(0，D1/2正则矩阵的性谱聚类算法：未正则矩计算矩阵L=D-计算正则矩阵Lrw=D-1(D-将k个列向量u1,u2,...,uk组成矩阵U，URn×kC1,C2,...Ck谱聚类算法：对称矩计算n×n的相似度矩阵W和度矩阵计算正则矩阵Lsym=D-1/2(D-W)D-计算Lsym的前k个特征向量将k个列向量u1,u2,...,uk组成矩阵对于i=1,2,...,n,令yi∈Rk是U的第i行的向量对于i=1,2,...,n,将yi∈Rk依次单位化，使得使用k-means算法将点(yi)i=1,2,...,n聚类成簇输出簇A1,A2,...Ak，其中kk得函数1的最小值A|相的时候达；函数 1 kki1

i1volAi带等式约束的极值问题，约束kAiki

volAikk定义向量RatioCut与矩阵的关

f若f为，可以使得f’Lf最小，显然这对应着全连接向量一定与正交。因为要求最小，因此，求次小聚类标准：次小特征向量各个分量的正负 计算得到的各个特征值λ：选择k，使得λ1,λ2,…,λk很未正则矩阵、对称矩阵、随机随 矩 矩阵除了通过切割图的方法，可以通过随机、扰附：指示向量组成的矩随机和矩阵的关图论中的随机是一个随机过程，它从一图的一个划分，使得随机在相同的簇中Clusteringbyfastsearchandfindofdensitypeak.AlexRodriguez,AlessandroLaioAtutorialonspectralclustering，UlrikevonLuxburg,LütkepohlH,HandbookofMatrices.Wiley,LangK,Fixingtwoweaknessesofthespectralmethod.In:WeissY,SchölkopfB,ttJ(eds.)AdvancesinNeuralInformationProcessingSystems18,pp.715–722.MITPress,Cambridge,2006BachF,JordanM，Learnin