&>&&>&&>&&>&matlab sift，k-means等算法工具箱
matlab sift，k-means等算法工具箱
上传大小：12.26MB
matlab sift，k-means等算法工具箱
综合评分：3（7位用户评分）
所需积分：2
下载次数：39
审核通过送C币
创建者：oscer2016
创建者：goto1997
创建者：nigelyq
课程推荐相关知识库
上传者其他资源上传者专辑
开发技术热门标签
VIP会员动态
android服务器底层网络模块的设计方法
所需积分：0
剩余积分：720
您当前C币：0
可兑换下载积分：0
兑换下载分：
兑换失败，您当前C币不够，请先充值C币
消耗C币：0
你当前的下载分为234。
matlab sift，k-means等算法工具箱
会员到期时间：
剩余下载次数：
你还不是VIP会员
开通VIP会员权限，免积分下载
你下载资源过于频繁，请输入验证码
你下载资源过于频繁，请输入验证码
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
若举报审核通过，可奖励20下载分
被举报人：
xiaocui_penfish
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：下次自动登录
现在的位置:
& 综合 & 正文
opencv 利用sift特征进行bow的分类训练
Mat img=imread("E:\\res\\lena.jpg");
Ptr&FeatureDetector& features = FeatureDetector::create("SIFT");
Ptr&DescriptorExtractor& descriptors = DescriptorExtractor::create("SIFT");
Ptr&DescriptorMatcher& matcher = DescriptorMatcher::create("FlannBased");
//defining terms for bowkmeans trainer
TermCriteria tc(CV_TERMCRIT_ITER+CV_TERMCRIT_EPS, 10, 0.001);
BOWImgDescriptorExtractor bowDE(descriptors, matcher);
//training data now
Mat features1;
vector&KeyPoint& keypoints1;
features-&detect(img, keypoints1);
descriptors-&compute(img, keypoints1, features1);
cout&&features1.rows&&
int dictionarySize = 1000;
int retries = 1;
int flags = KMEANS_PP_CENTERS;
BOWKMeansTrainer bowTrainer(dictionarySize, tc, retries, flags);
bowTrainer.add(features1);
bowTrainer.add(features1);
Mat dictionary = bowTrainer.cluster();
cout&&dictionary.rows&&
cout&&dictionary.cols&&
bowDE.setVocabulary(dictionary);
pute(img, keypoints1, bow_descriptor);
cout&&bow_descriptor&&
&&&&推荐文章:
【上篇】【下篇】1.SIFT概述
SIFT的全称是Scale Invariant Feature Transform，尺度不变特征变换，由加拿大教授David G.Lowe提出的。SIFT特征对旋转、尺度缩放、亮度变化等保持不变性，是一种非常稳定的局部特征。
1.1 SIFT算法具的特点
图像的局部特征，对旋转、尺度缩放、亮度变化保持不变，对视角变化、仿射变换、噪声也保持一定程度的稳定性。
独特性好，信息量丰富，适用于海量特征库进行快速、准确的匹配。
多量性，即使是很少几个物体也可以产生大量的SIFT特征
高速性，经优化的SIFT匹配算法甚至可以达到实时性
扩招性，可以很方便的与其他的特征向量进行联合。
1.2 SIFT特征检测的步骤
有4个主要步骤
尺度空间的极值检测 搜索所有尺度空间上的图像，通过高斯微分函数来识别潜在的对尺度和选择不变的兴趣点。
特征点定位 在每个候选的位置上，通过一个拟合精细模型来确定位置尺度，关键点的选取依据他们的稳定程度。
特征方向赋值 基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向，后续的所有操作都是对于关键点的方向、尺度和位置进行变换，从而提供这些特征的不变性。
特征点描述 在每个特征点周围的邻域内，在选定的尺度上测量图像的局部梯度，这些梯度被变换成一种表示，这种表示允许比较大的局部形状的变形和光照变换。
2. 尺度空间
在一定的范围内，无论物体是大还是小，人眼都可以分辨出来。然而计算机要有相同的能力却不是那么的容易，在未知的场景中，计算机视觉并不能提供物体的尺度大小，其中的一种方法是把物体不同尺度下的图像都提供给机器，让机器能够对物体在不同的尺度下有一个统一的认知。在建立统一认知的过程中，要考虑的就是在图像在不同的尺度下都存在的特征点。
2.1 多分辨率图像金字塔
在早期图像的多尺度通常使用图像金字塔表示形式。图像金字塔是同一图像在不同的分辨率下得到的一组结果，其生成过程一般包括两个步骤：
对原始图像进行平滑
对处理后的图像进行降采样（通常是水平、垂直方向的1/2）
降采样后得到一系列不断尺寸缩小的图像。显然，一个传统的金字塔中，每一层的图像是其上一层图像长、高的各一半。多分辨率的图像金字塔虽然生成简单，但其本质是降采样，图像的局部特征则难以保持，也就是无法保持特征的尺度不变性。
2.2 高斯尺度空间
我们还可以通过图像的模糊程度来模拟人在距离物体由远到近时物体在视网膜上成像过程，距离物体越近其尺寸越大图像也越模糊，这就是高斯尺度空间，使用不同的参数模糊图像（分辨率不变），是尺度空间的另一种表现形式。
我们知道图像和高斯函数进行卷积运算能够对图像进行模糊，使用不同的“高斯核”可得到不同模糊程度的图像。一副图像其高斯尺度空间可由其和不同的高斯卷积得到：
\[ L(x,y,\sigma) = G(x,y,\sigma) * I(x,y)\]
其中，\(G(x,y,\sigma)是高斯核函数。\)
G(x,y,\sigma) = \frac{1}{2 \pi \sigma ^2} e ^ {\frac{x^2 +y^2}{2 \sigma^2}}\]
\(\sigma\)称为尺度空间因子，它是高斯正态分布的标准差，反映了图像被模糊的程度，其值越大图像越模糊，对应的尺度也就越大。\(L(x,y,\sigma)\)代表着图像的高斯尺度空间。
构建尺度空间的目的是为了检测出在不同的尺度下都存在的特征点，而检测特征点较好的算子是\(\Delta^2G\)(高斯拉普拉斯,LoG）,
\[\Delta ^2 = \frac{\partial ^2}{\partial x^2} + \frac{\partial ^2}{\partial y^2}\]
使用LoG虽然能较好的检测到图像中的特征点，但是其运算量过大，通常可使用DoG（差分高斯，Difference of Gaussina）来近似计算LoG[Marr and Hidreth]。
设\(k\)为相邻两个高斯尺度空间的比例因子，则DoG的定义：
\[D(x,y,\sigma) = [G(x,y,k\sigma) - G(x,y,\sigma)] \ast I(x,y) \\
= L(x,y,k\sigma) - L(x,y,\sigma)\]
其中，\(L(x,y,\sigma)\)是图像的高斯尺度空间。
从上式可以知道，将相邻的两个高斯空间的图像相减就得到了DoG的响应图像。为了得到DoG图像，先要构建高斯尺度空间，而高斯的尺度空间可以在图像金字塔降采样的基础上加上高斯滤波得到，也就是对图像金字塔的每层图像使用不同的参数\(\sigma\)进行高斯模糊，使每层金字塔有多张高斯模糊过的图像。降采样时，金字塔上边一组图像的第一张是由其下面一组图像倒数第三张降采样得到。
易知，高斯金字塔有多组，每组又有多层。一组中的多个层之间的尺度是不一样的（也就是使用的高斯参数\(\sigma\)是不同的），相邻两层之间的尺度相差一个比例因子\(k\)。如果每组有\(S\)层，则\(k = 2 ^{\frac{1}{S}}\)。上一组图像的最底层图像是由下一组中尺度为\(2\sigma\)的图像进行因子为2的降采样得到的（高斯金字塔先从底层建立）。高斯金字塔构建完成后，将相邻的高斯金字塔相减就得到了DoG金字塔。
高斯金字塔的组数一般是
\[o = [\log _2min(m,n)] - a\]
\(o\)表示高斯金字塔的层数，m，n分别是图像的行和列。减去的系数\(a\)可以在\(0-\log_2min(m,n)\)之间的任意值，和具体需要的金字塔的顶层图像的大小有关。
高斯模糊参数\(\sigma\)（尺度空间），可由下面关系式得到
\[\sigma(o,s) = \sigma_0 \cdot 2^{\frac{o + s}{S}}\]
其中\(o\)为所在的组，\(s\)为所在的层，\(\sigma_0\)为初始的尺度，\(S\)为每组的层数。
在Lowe的算法实现中\(\sigma_0=1.6,o_{min} = -1,S=3\)，\(o_{min}=-1\)就是首先将原图像的长和宽各扩展一倍。
从上面可以得知同一组内相邻层的图像尺度关系
\[\sigma_{s+1}=k\cdot\sigma_s=2^{\frac{1}{S}}\cdot\sigma_s\]
相邻组之间的尺度关系
\[\sigma_{o+1} = 2\sigma_o\]
2.3 高斯金字塔构建示例
以一个\(512 \times 512\)的图像I为例，构建高斯金字塔步骤：(从0开始计数，倒立的金字塔）
金字塔的组数，\(\log_2512 = 9\)，减去因子3，构建的金字塔的组数为6。取每组的层数为3。
构建第0组，将图像的宽和高都增加一倍，变成\(1024 \times 1024\)（\(I_0\)）。第0层\(I_0 \ast G(x,y,\sigma_0)\)，第1层\(I_0 \ast G(x,y,k\sigma_0)\)，第2层\(I_0 \ast G(x,y,k^2\sigma_0)\)
构建第1组，对\(I_0\)降采样变成\(512 \times 512\)（\(I_1\)）。第0层\(I_1 \ast G(x,y,2\sigma_0)\)，第1层\(I_1 \ast G(x,y,2k\sigma_0)\)\(I_1 \ast G(x,y,2k^2\sigma_0)\)
\(\vdots\)
构建第o组，第s层 \(I_o \ast G(x,y,2^ok^s\sigma_0)\)
高斯金字塔构建成功后，将每一组相邻的两层相减就可以得到DoG金字塔.
3. DoG空间极值检测
为了寻找尺度空间的极值点，每个像素点要和其图像域（同一尺度空间）和尺度域（相邻的尺度空间）的所有相邻点进行比较，当其大于（或者小于）所有相邻点时，改点就是极值点。如图所示，中间的检测点要和其所在图像的\(3 \times 3\)邻域8个像素点，以及其相邻的上下两层的\(3 \times 3\)领域18个像素点，共26个像素点进行比较。
从上面的描述中可以知道，每组图像的第一层和最后一层是无法进行比较取得极值的。为了满足尺度变换的连续性，在每一组图像的顶层继续使用高斯模糊生成3幅图像，高斯金字塔每组有\(S+3\)层图像，DoG金字塔的每组有\(S+2\)组图像。
3.1 尺度变化的连续性
设\(S=3\)，也就是每组有3层，则\(k = 2 ^ {\frac{1}{S}} = 2 ^ {\frac{1}{3}}\)，也就是有高斯金字塔每组有\((S-1)3层图像，DoG金字塔每组有\)(S-2)2层图像。在DoG金字塔的第一组有两层尺度分别是\(\sigma,k\sigma\)，第二组有两层的尺度分别是\(2\sigma,2k\sigma\)，由于只有两项是无法比较取得极值的（只有左右两边都有值才能有极值）。由于无法比较取得极值，那么我们就需要继续对每组的图像进行高斯模糊，使得尺度形成\(\sigma,k\sigma,k^2\sigma,k^3\sigma,k^4\sigma\)，这样就可以选择中间的三项\(k\sigma,k^2\sigma,k^3\sigma\)。对应的下一组由上一组降采样得到的三项是\(2k\sigma,2k^2\sigma,2k^3\sigma\)，其首项\(2k\sigma = 2\cdot2^{\frac{1}{3}}\sigma=2^{\frac{4}{3}}\sigma\)，刚好与上一组的最后一项\(k^3\sigma = 2^{\frac{3}{3}}\sigma\)的尺度连续起来。
4. 删除不好的极值点（特征点）
通过比较检测得到的DoG的局部极值点实在离散的空间搜索得到的，由于离散空间是对连续空间采样得到的结果，因此在离散空间找到的极值点不一定是真正意义上的极值点，因此要设法将不满足条件的点剔除掉。可以通过尺度空间DoG函数进行曲线拟合寻找极值点，这一步的本质是去掉DoG局部曲率非常不对称的点。
要剔除掉的不符合要求的点主要有两种：
低对比度的特征点
不稳定的边缘响应点
4.1 剔除低对比度的特征点
候选特征点x，其偏移量定义为\(\Delta x\)，其对比度为\(D(x)\)的绝对值\(\mid D(x) \mid\)，对\(D(x)\)应用泰勒展开式
\[D(x) = D + \frac{\partial D^T}{\partial x}\Delta x+ \frac{1}{2}\Delta x^T\frac{\partial ^2D}{\partial x^2}\Delta x\]
由于x是D(x)的极值点，所以对上式求导并令其为0，得到
\[\Delta x = -\frac{\partial^2D^{-1}}{\partial x^2}\frac{\partial D(x)}{\partial x}\]
然后再把求得的\(\Delta x\)代入到D(x)的泰勒展开式中
\[D(\hat{x}) = D +\frac{1}{2}\frac{\partial D^T}{\partial x}\hat{x}\]
设对比度的阈值为T，若\(\mid D(\hat{x})\mid \ge T\)，则该特征点保留，否则剔除掉。
4.2 剔除不稳定的边缘响应点
在边缘梯度的方向上主曲率值比较大，而沿着边缘方向则主曲率值较小。候选特征点的DoG函数D(x)的主曲率与\(2 \times 2\)Hessian矩阵\(H\)的特征值成正比。
H = \left[
\begin{array}{cc}
D_{xx} \quad D_{yx} \\
D_{xy} \quad D_{yy}
\end{array}
其中，\(D_{xx},D_{xy},D_{yy}\)是候选点邻域对应位置的差分求得的。
为了避免求具体的值，可以使用\(H\)特征值得比例。设\(\alpha = \lambda_{max}\)为H的最大特征值，\(\beta = \lambda_{min}\)为H的最小特征值，则
Tr(H) = D_{xx} + D_{yy} = \alpha +\beta \\
Det(H) = D_{xx} + D_{yy} - D_{xy}^2 = \alpha \cdot \beta
其中，\(Tr(H)\)为矩阵H的迹，\(Det(H)\)为矩阵H的行列式。
设\(\gamma = \frac{\alpha}{\beta}\) 表示最大特征值和最小特征值的比值，则
\frac{Tr(H)^2}{Det(H)} = \frac{(\alpha +\beta)^2}{\alpha \beta} = \frac{(\gamma \beta + \beta)^2}{\gamma \beta ^2} = \frac{(\gamma +1)^2}{\gamma}
上式的结果与两个特征值的比例有关，和具体的大小无关，当两个特征值想等时其值最小，并且随着\(\gamma\)的增大而增大。因此为了检测主曲率是否在某个阈值\(T_{\gamma}\)下，只需检测
\[\frac{Tr(H)^2}{Det(H)} & \frac{(T_{\gamma} + 1)^2}{T_{\gamma}}\]
如果上式成立，则剔除该特征点，否则保留。（Lowe论文中取\(T_{\gamma} = 10\))
5. 求取特征点的主方向
经过上面的步骤已经找到了在不同尺度下都存在的特征点，为了实现图像旋转不变性，需要给特征点的方向进行赋值。利用特征点邻域像素的梯度分布特性来确定其方向参数，再利用图像的梯度直方图求取关键点局部结构的稳定方向。
找到了特征点，也就可以得到该特征点的尺度\(\sigma\)，也就可以得到特征点所在的尺度图像
L(x,y) = G(x,y,\sigma) \ast I(x,y)
计算以特征点为中心、以\(3 \times 1.5 \sigma\)为半径的区域图像的幅角和幅值，每个点L(x,y)的梯度的模\(m(x,y)\)以及方向\(\theta(x,y)\)可通过下面公司求得
m(x,y) = \sqrt{[L(x+1,y) - L(x-1,y)]^2 + [L(x,y + 1) - L(x,y - 1)]^2} \\
\theta(x,y) = \arctan{\frac{L(x,y+1) - L(x,y - 1)}{L(x + 1,y) - L(x-1,y)}}
计算得到梯度方向后，就要使用直方图统计特征点邻域内像素对应的梯度方向和幅值。梯度方向的直方图的横轴是梯度方向的角度（梯度方向的范围是0到360度，直方图每36度一个柱共10个柱，或者没45度一个柱共8个柱），纵轴是梯度方向对应梯度幅值的累加，在直方图的峰值就是特征点的主方向。在Lowe的论文还提到了使用高斯函数对直方图进行平滑以增强特征点近的邻域点对关键点方向的作用，并减少突变的影响。为了得到更精确的方向，通常还可以对离散的梯度直方图进行插值拟合。具体而言，关键点的方向可以由和主峰值最近的三个柱值通过抛物线插值得到。在梯度直方图中，当存在一个相当于主峰值80%能量的柱值时，则可以将这个方向认为是该特征点辅助方向。所以，一个特征点可能检测到多个方向（也可以理解为，一个特征点可能产生多个坐标、尺度相同，但是方向不同的特征点）。Lowe在论文中指出
15%的关键点具有多方向，而且这些点对匹配的稳定性很关键。
得到特征点的主方向后，对于每个特征点可以得到三个信息\((x,y,\sigma,\theta)\)，即位置、尺度和方向。由此可以确定一个SIFT特征区域，一个SIFT特征区域由三个值表示，中心表示特征点位置，半径表示关键点的尺度，箭头表示主方向。具有多个方向的关键点可以被复制成多份，然后将方向值分别赋给复制后的特征点，一个特征点就产生了多个坐标、尺度相等，但是方向不同的特征点。
6. 生成特征描述
通过以上的步骤已经找到了SIFT特征点位置、尺度和方向信息，下面就需要使用一组向量来描述关键点也就是生成特征点描述子，这个描述符不只包含特征点，也含有特征点周围对其有贡献的像素点。描述子应具有较高的独立性，以保证匹配率。
特征描述符的生成大致有三个步骤：
校正旋转主方向，确保旋转不变性。
生成描述子，最终形成一个128维的特征向量
归一化处理，将特征向量长度进行归一化处理，进一步去除光照的影响。
为了保证特征矢量的旋转不变性，要以特征点为中心，在附近邻域内将坐标轴旋转\(\theta\)（特征点的主方向）角度，即将坐标轴旋转为特征点的主方向。旋转后邻域内像素的新坐标为：
\begin{array}{c}
x ^ \prime \\
y ^ \prime
\end{array}
\right] = \left[ \begin{array}{cc} \cos \theta \quad - \sin \theta \\
\sin \theta \quad \cos \theta \end{array} \right] \left[ \begin{array}{c} x \\ y \end{array}\right] \]
旋转后以主方向为中心取 \(8 \times 8\)的窗口。下图所示，左图的中央为当前关键点的位置，每个小格代表为关键点邻域所在尺度空间的一个像素，求取每个像素的梯度幅值与梯度方向，箭头方向代表该像素的梯度方向，长度代表梯度幅值，然后利用高斯窗口对其进行加权运算。最后在每个\(4 \times 4\)的小块上绘制8个方向的梯度直方图，计算每个梯度方向的累加值，即可形成一个种子点，如右图所示。每个特征点由4个种子点组成，每个种子点有8个方向的向量信息。这种邻域方向性信息联合增强了算法的抗噪声能力，同时对于含有定位误差的特征匹配也提供了比较理性的容错性。
与求主方向不同，此时每个种子区域的梯度直方图在0-360之间划分为8个方向区间，每个区间为45度，即每个种子点有8个方向的梯度强度信息。
在实际的计算过程中，为了增强匹配的稳健性，Lowe建议
对每个关键点使用$ 4 \times 4$共16个种子点来描述，这样一个关键点就可以产生128维的SIFT特征向量。
通过对特征点周围的像素进行分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。
SIFT特征以其对旋转、尺度缩放、亮度等保持不变性，是一种非常稳定的局部特征，在图像处理和计算机视觉领域有着很重要的作用，其本身也是非常复杂的，下面对其计算过程做一个粗略总结。
DoG尺度空间的极值检测。 首先是构造DoG尺度空间，在SIFT中使用不同参数的高斯模糊来表示不同的尺度空间。而构造尺度空间是为了检测在不同尺度下都存在的特征点，特征点的检测比较常用的方法是\(\Delta ^2G\)（高斯拉普拉斯LoG），但是LoG的运算量是比较大的，Marr和Hidreth曾指出，可以使用DoG（差分高斯）来近似计算LoG，所以在DoG的尺度空间下检测极值点。
删除不稳定的极值点。主要删除两类：低对比度的极值点以及不稳定的边缘响应点。
** 确定特征点的主方向**。以特征点的为中心、以\(3 \times 1.5\sigma\)为半径的领域内计算各个像素点的梯度的幅角和幅值，然后使用直方图对梯度的幅角进行统计。直方图的横轴是梯度的方向，纵轴为梯度方向对应梯度幅值的累加值，直方图中最高峰所对应的方向即为特征点的方向。
生成特征点的描述子。 首先将坐标轴旋转为特征点的方向，以特征点为中心的\(16 \times 16\)的窗口的像素的梯度幅值和方向，将窗口内的像素分成16块，每块是其像素内8个方向的直方图统计，共可形成128维的特征向量。
阅读(...) 评论()查看: 9074|回复: 15|关注: 0
关于SIFT之后的K-means聚类的问题
<h1 style="color:# 麦片财富积分
新手, 积分 5, 距离下一级还需 45 积分
本人在做bag of words这个模型，选择的是SIFT+SVM，中间涉及到聚类分析，想用K-means算法做聚类
现在的问题是，假设我用100张学习图片做SIFT特征提取，每张图片都是N*128的向量，并且每张图片的特征点N不同
那么在做K-means聚类的时候，是每一张图片分别作聚类，还是将100张图片的特征空间整合成（N1+N2+...+N100)*128的矩阵，再做聚类？
因为我用的是matlab自带的kmeans函数，如果是第二种情况，聚类后假设质点k取300，那么想分别得到每一张图片中属于各个质点的特征点有多少个要怎么实现？
另：MATLAB中自带kmeans函数说明如下：
[IDX,C] = kmeans(X,k) returns the k cluster centroid locations in the k-by-p matrix C.
[IDX,C,sumd] = kmeans(X,k) returns the within-cluster sums of point-to-centroid distances in the 1-by-k vector sumd.
[IDX,C,sumd,D] = kmeans(X,k) returns distances from each point to every centroid in the n-by-k matrix D.
本人也是昨天才看到聚类算法，许多不清楚，希望大虾指点，万分谢谢~~
<h1 style="color:# 麦片财富积分
怎么没有人回答啊？我也想知道
<h1 style="color:# 麦片财富积分
我也在做bag-of-feature啊，那个模型就是说先用SIFT提取模型，再用聚类，我遇到了跟楼主一样的问题啊，楼主的SIFT特征提取是怎么做的？
<h1 style="color:# 麦片财富积分
回复 1# realdust 的帖子
这位童鞋，你显然没有实质上的理解BoW Model，更不用说BoF Model了。建议你先搞清楚BoW ，结合BoW，再去理解BoF 。这样就很容易理解了。首先，对你指出你的两个问题。第一，使用100幅图片来做机器学习是远远不够的，至少要200以上，这样才能有质的效果；第二，即使是只使用100幅图片，使用matlab自带的kmeans函数，如果你的电脑内存是2G，win7系统，肯定会产生Out of Memeroy的问题。对于你提出的问题，显然是应该把你那100图片的所有SIFT特征点向量散布于一个128D的空间中来进行聚类，这样才能真正的找到每幅图片中的相似点，你放在一幅图片里面聚类，那机器能学到啥子哦~~这就是模式识别里面的机器学习啦，我是西电的，欢迎交流~~
<h1 style="color:# 麦片财富积分
回复 1# realdust 的帖子
你可以大概的算一下那些矩阵的大小，估计都七八百M了，内存也不可能全部分给matlab，系统就占了好多，肯定会有内存溢出的问题
<h1 style="color:# 麦片财富积分
每幅图片有几百个sift特征点 都是128维的 图像库有上千张图片 那做kmeans 不是要崩溃吗，大家是怎么做的呀？
<h1 style="color:# 麦片财富积分
不知道楼主解决了这个问题没有 我现在也是夹在了这里 用kmeas聚类后要用svm做分类，不知道大侠们有没有解决呢
<h1 style="color:# 麦片财富积分
你好！我也做这个！能不能加我QQ啊？物品的QQ：
<h1 style="color:# 麦片财富积分
mzhu66 发表于
怎么没有人回答啊？我也想知道
你好！我也做这个！能不能加我QQ啊？物品的QQ：
<h1 style="color:# 麦片财富积分
tian_ya_shang 发表于
**** 作者被禁止或删除 内容自动屏蔽 ****
你好！我也做这个！能不能加我QQ啊？物品的QQ：
Powered by一天就是225元，一个月大概花费四五千元。
手脚全上，只为可以得到娃娃，不顾围观目光。
声明：本文由入驻搜狐公众平台的作者撰写，除搜狐官方账号外，观点仅代表作者本人，不代表搜狐立场。
　　K-Means聚类
　　前面几章我们介绍了监督学习，包括从带标签的数据中学习的回归和分类算法。本章，我们讨论无监督学习算法，聚类（clustering）。聚类是用于找出不带标签数据的相似性的算法。我们将介绍K-Means聚类思想，解决一个图像压缩问题，然后对算法的效果进行评估。最后，我们把聚类和分类算法组合起来，解决一个半监督学习问题。
　　在第一章，机器学习基础中，我们介绍过非监督学习的目的是从不带标签的训练数据中挖掘隐含的关系。聚类，或称为聚类分析（cluster analysis）是一种分组观察的方法，将更具相似性的样本归为一组，或一类（cluster），同组中的样本比其他组的样本更相似。与监督学习方法一样，我们用n维向量表示一个观测值。例如，假设你的训练数据如下图所示：
　　聚类算法可能会分成两组，用圆点和方块表示，如下图所示：
　　也可能分成四组，如下图所示：
　　聚类通常用于探索数据集。社交网络可以用聚类算法识别社区，然后向没有加入社区的用户进行推荐。在生物学领域，聚类用于找出有相似模式的基因组。推荐系统有时也利用聚类算法向用户推荐产品和媒体资源。在市场调查中，聚类算法用来做用户分组。下面，我们就用K-Means聚类算法来为一个数据集聚类。
　　K-Means聚类算法简介
　　由于具有出色的速度和良好的可扩展性，K-Means聚类算法算得上是最著名的聚类方法。K-Means算法是一个重复移动类中心点的过程，把类的中心点，也称重心（centroids），移动到其包含成员的平均位置，然后重新划分其内部成员。K是算法计算出的超参数，表示类的数量；K-Means可以自动分配样本到不同的类，但是不能决定究竟要分几个类。K必须是一个比训练集样本数小的正整数。有时，类的数量是由问题内容指定的。例如，一个鞋厂有三种新款式，它想知道每种新款式都有哪些潜在客户，于是它调研客户，然后从数据里找出三类。也有一些问题没有指定聚类的数量，最优的聚类数量是不确定的。后面我们会介绍一种启发式方法来估计最优聚类数量，称为肘部法则（Elbow Method）。
　　K-Means的参数是类的重心位置和其内部观测值的位置。与广义线性模型和决策树类似，K-Means参数的最优解也是以成本函数最小化为目标。K-Means成本函数公式如下：
　　μk是第k个类的重心位置。成本函数是各个类畸变程度（distortions）之和。每个类的畸变程度等于该类重心与其内部成员位置距离的平方和。若类内部的成员彼此间越紧凑则类的畸变程度越小，反之，若类内部的成员彼此间越分散则类的畸变程度越大。求解成本函数最小化的参数就是一个重复配置每个类包含的观测值，并不断移动类重心的过程。首先，类的重心是随机确定的位置。实际上，重心位置等于随机选择的观测值的位置。每次迭代的时候，K-Means会把观测值分配到离它们最近的类，然后把重心移动到该类全部成员位置的平均值那里。让我们用如下表所示的训练数据来试验一下：
　　10 6 8
　　11 5 5
　　12 3 7
　　上表有两个解释变量，每个样本有两个特征。画图如下所示：
　　%matplotlibinlineimportmatplotlib.pyplotaspltfrommatplotlib.font_managerimportFontPropertiesfont=FontProperties(fname=r&c:\windows\fonts\msyh.ttc&,size=10)
　　importnumpyasnpX0=np.array([7,5,7,3,4,1,0,2,8,6,5,3])X1=np.array([5,7,7,3,6,4,0,2,7,8,5,7])plt.figure()plt.axis([-1,9,-1,9])plt.grid(True)plt.plot(X0,X1,'k.');
　　假设K-Means初始化时，将第一个类的重心设置在第5个样本，第二个类的重心设置在第11个样本.那么我们可以把每个实例与两个重心的距离都计算出来，将其分配到最近的类里面。计算结果如下表所示：
　　与C1距离
　　与C2距离
　　上次聚类结果
　　新聚类结果
　　是否改变
　　1 7 5 3.16 2.00 None C2 YES
　　2 5 7 1.41 2.00 None C1 YES
　　3 7 7 3.16 2.83 None C2 YES
　　4 3 3 3.16 2.83 None C2 YES
　　5 4 6 0.00 1.41 None C1 YES
　　6 1 4 3.61 4.12 None C1 YES
　　7 0 0 7.21 7.07 None C2 YES
　　8 2 2 4.47 4.24 None C2 YES
　　9 8 7 4.12 3.61 None C2 YES
　　10 6 8 2.83 3.16 None C1 YES
　　11 5 5 1.41 0.00 None C2 YES
　　12 3 7 1.41 2.83 None C1 YES
　　C1重心 4 6
　　C2重心 5 5
　　新的重心位置和初始聚类结果如下图所示。第一类用X表示，第二类用点表示。重心位置用稍大的点突出显示。
　　C1=[1,4,5,9,11]C2=list(set(range(12))-set(C1))X0C1,X1C1=X0[C1],X1[C1]X0C2,X1C2=X0[C2],X1[C2]plt.figure()plt.title('第一次迭代后聚类结果',fontproperties=font)plt.axis([-1,9,-1,9])plt.grid(True)plt.plot(X0C1,X1C1,'rx')plt.plot(X0C2,X1C2,'g.')plt.plot(4,6,'rx',ms=12.0)plt.plot(5,5,'g.',ms=12.0);
　　现在我们重新计算两个类的重心，把重心移动到新位置，并重新计算各个样本与新重心的距离，并根据距离远近为样本重新归类。结果如下表所示：
　　与C1距离
　　与C2距离
　　上次聚类结果
　　新聚类结果
　　是否改变
　　1 7 5 3.49 2.58 C2 C2 NO
　　2 5 7 1.34 2.89 C1 C1 NO
　　3 7 7 3.26 3.75 C2 C1 YES
　　4 3 3 3.49 1.94 C2 C2 NO
　　5 4 6 0.45 1.94 C1 C1 NO
　　6 1 4 3.69 3.57 C1 C2 YES
　　7 0 0 7.44 6.17 C2 C2 NO
　　8 2 2 4.75 3.35 C2 C2 NO
　　9 8 7 4.24 4.46 C2 C1 YES
　　10 6 8 2.72 4.11 C1 C1 NO
　　11 5 5 1.84 0.96 C2 C2 NO
　　12 3 7 1.00 3.26 C1 C1 NO
　　C1重心 3.80 6.40
　　C2重心 4.57 4.14
　　画图结果如下：
　　C1=[1,2,4,8,9,11]C2=list(set(range(12))-set(C1))X0C1,X1C1=X0[C1],X1[C1]X0C2,X1C2=X0[C2],X1[C2]plt.figure()plt.title('第二次迭代后聚类结果',fontproperties=font)plt.axis([-1,9,-1,9])plt.grid(True)plt.plot(X0C1,X1C1,'rx')plt.plot(X0C2,X1C2,'g.')plt.plot(3.8,6.4,'rx',ms=12.0)plt.plot(4.57,4.14,'g.',ms=12.0);
　　我们再重复一次上面的做法，把重心移动到新位置，并重新计算各个样本与新重心的距离，并根据距离远近为样本重新归类。结果如下表所示：
　　与C1距离
　　与C2距离
　　上次聚类结果
　　新聚类结果
　　是否改变
　　1 7 5 2.50 5.28 C1 C1 NO
　　2 5 7 0.50 5.05 C1 C1 NO
　　3 7 7 1.50 6.38 C1 C1 NO
　　4 3 3 4.72 0.82 C2 C2 NO
　　5 4 6 1.80 3.67 C1 C1 NO
　　6 1 4 5.41 1.70 C2 C2 NO
　　7 0 0 8.90 3.56 C2 C2 NO
　　8 2 2 6.10 0.82 C2 C2 NO
　　9 8 7 2.50 7.16 C1 C1 NO
　　10 6 8 1.12 6.44 C1 C1 NO
　　11 5 5 2.06 3.56 C2 C1 YES
　　12 3 7 2.50 4.28 C1 C1 NO
　　C1重心 5.50 7.00
　　C2重心 2.20 2.80
　　画图结果如下：
　　C1=[0,1,2,4,8,9,10,11]C2=list(set(range(12))-set(C1))X0C1,X1C1=X0[C1],X1[C1]X0C2,X1C2=X0[C2],X1[C2]plt.figure()plt.title('第三次迭代后聚类结果',fontproperties=font)plt.axis([-1,9,-1,9])plt.grid(True)plt.plot(X0C1,X1C1,'rx')plt.plot(X0C2,X1C2,'g.')plt.plot(5.5,7.0,'rx',ms=12.0)plt.plot(2.2,2.8,'g.',ms=12.0);
　　再重复上面的方法就会发现类的重心不变了，K-Means会在条件满足的时候停止重复聚类过程。通常，条件是前后两次迭代的成本函数值的差达到了限定值，或者是前后两次迭代的重心位置变化达到了限定值。如果这些停止条件足够小，K-Means就能找到最优解。不过这个最优解不一定是全局最优解。
　　局部最优解
　　前面介绍过K-Means的初始重心位置是随机选择的。有时，如果运气不好，随机选择的重心会导致K-Means陷入局部最优解。例如，K-Means初始重心位置如下图所示：
　　K-Means最终会得到一个局部最优解，如下图所示。这些类可能没有实际意义，而上面和下面两部分观测值可能是更有合理的聚类结果。为了避免局部最优解，K-Means通常初始时要重复运行十几次甚至上百次。每次重复时，它会随机的从不同的位置开始初始化。最后把最小的成本函数对应的重心位置作为初始化位置。
　　肘部法则
　　如果问题中没有指定KK的值，可以通过肘部法则这一技术来估计聚类数量。肘部法则会把不同KK值的成本函数值画出来。随着KK值的增大，平均畸变程度会减小；每个类包含的样本数会减少，于是样本离其重心会更近。但是，随着KK值继续增大，平均畸变程度的改善效果会不断减低。KK值增大过程中，畸变程度的改善效果下降幅度最大的位置对应的KK值就是肘部。下面让我们用肘部法则来确定最佳的KK值。下图数据明显可分成两类：
　　importnumpyasnpcluster1=np.random.uniform(0.5,1.5,(2,10))cluster2=np.random.uniform(3.5,4.5,(2,10))X=np.hstack((cluster1,cluster2)).Tplt.figure()plt.axis([0,5,0,5])plt.grid(True)plt.plot(X[:,0],X[:,1],'k.');
　　我们计算K值从1到10对应的平均畸变程度：
　　fromsklearn.clusterimportKMeansfromscipy.spatial.distanceimportcdistK=range(1,10)meandistortions=[]forkinK:kmeans=KMeans(n_clusters=k)kmeans.fit(X)meandistortions.append(sum(np.min(cdist(X,kmeans.cluster_centers_,'euclidean'),axis=1))/X.shape[0])plt.plot(K,meandistortions,'bx-')plt.xlabel('k')plt.ylabel('平均畸变程度',fontproperties=font)plt.title('用肘部法则来确定最佳的K值',fontproperties=font);
　　从图中可以看出，K值从1到2时，平均畸变程度变化最大。超过2以后，平均畸变程度变化显著降低。因此肘部就是K=2。下面我们再用肘部法则来确定3个类的最佳的K值：
　　importnumpyasnpx1=np.array([1,2,3,1,5,6,5,5,6,7,8,9,7,9])x2=np.array([1,3,2,2,8,6,7,6,7,1,2,1,1,3])X=np.array(list(zip(x1,x2))).reshape(len(x1),2)plt.figure()plt.axis([0,10,0,10])plt.grid(True)plt.plot(X[:,0],X[:,1],'k.');
　　fromsklearn.clusterimportKMeansfromscipy.spatial.distanceimportcdistK=range(1,10)meandistortions=[]forkinK:kmeans=KMeans(n_clusters=k)kmeans.fit(X)meandistortions.append(sum(np.min(cdist(X,kmeans.cluster_centers_,'euclidean'),axis=1))/X.shape[0])plt.plot(K,meandistortions,'bx-')plt.xlabel('k')plt.ylabel('平均畸变程度',fontproperties=font)plt.title('用肘部法则来确定最佳的K值',fontproperties=font);
　　从图中可以看出，K值从1到3时，平均畸变程度变化最大。超过3以后，平均畸变程度变化显著降低。因此肘部就是K=3。
　　聚类效果评估
　　我们把机器学习定义为对系统的设计和学习，通过对经验数据的学习，将任务效果的不断改善作为一个度量标准。K-Means是一种非监督学习，没有标签和其他信息来比较聚类结果。但是，我们还是有一些指标可以评估算法的性能。我们已经介绍过类的畸变程度的度量方法。本节为将介绍另一种聚类算法效果评估方法称为轮廓系数（Silhouette Coefficient）。轮廓系数是类的密集与分散程度的评价指标。它会随着类的规模增大而增大。彼此相距很远，本身很密集的类，其轮廓系数较大，彼此集中，本身很大的类，其轮廓系数较小。轮廓系数是通过所有样本计算出来的，计算每个样本分数的均值，计算公式如下：
　　s=b-amax(a,b)
　　a是每一个类中样本彼此距离的均值，b是一个类中样本与其最近的那个类的所有样本的距离的均值。下面的例子运行四次K-Means，从一个数据集中分别创建2，3，4，8个类，然后分别计算它们的轮廓系数。
　　importnumpyasnpfromsklearn.clusterimportKMeansfromsklearnimportmetricsplt.figure(figsize=(8,10))plt.subplot(3,2,1)x1=np.array([1,2,3,1,5,6,5,5,6,7,8,9,7,9])x2=np.array([1,3,2,2,8,6,7,6,7,1,2,1,1,3])X=np.array(list(zip(x1,x2))).reshape(len(x1),2)plt.xlim([0,10])plt.ylim([0,10])plt.title('样本',fontproperties=font)plt.scatter(x1,x2)colors=['b','g','r','c','m','y','k','b']markers=['o','s','D','v','^','p','*','+']tests=[2,3,4,5,8]subplot_counter=1fortintests:subplot_counter+=1plt.subplot(3,2,subplot_counter)kmeans_model=KMeans(n_clusters=t).fit(X)fori,linenumerate(kmeans_model.labels_):plt.plot(x1[i],x2[i],color=colors[l],marker=markers[l],ls='None')plt.xlim([0,10])plt.ylim([0,10])plt.title('K = %s, 轮廓系数 = %.03f'%(t,metrics.silhouette_score(X,kmeans_model.labels_,metric='euclidean')),fontproperties=font)
　　d:\programfiles\Miniconda3\lib\site-packages\numpy\core\_methods.py:59: RuntimeWarning: Mean of empty slice. warnings.warn(&Mean of empty slice.&, RuntimeWarning)
　　很显然，这个数据集包括三个类。在K=3K=3的时候轮廓系数是最大的。在K=8K=8的时候，每个类的样本不仅彼此很接近，而且与其他类的样本也非常接近，因此这时轮廓系数是最小的。
　　图像量化
　　前面我们用聚类算法探索了结构化数据集。现在我们用它来解决一个新问题。图像量化（image quantization）是一种将图像中相似颜色替换成同样颜色的有损压缩方法。图像量化会减少图像的存储空间，由于表示不同颜色的字节减少了。下面的例子中，我们将用聚类方法从一张图片中找出包含图片大多数颜色的压缩颜色调色板（palette），然后我们用这个压缩颜色调色板重新生成图片。这个例子需要用mahotas图像处理库，可以通过pip install mahotas安装：
　　importnumpyasnpfromsklearn.clusterimportKMeansfromsklearn.utilsimportshuffleimportmahotasasmh
　　首先，读入图片，然后将图片矩阵展开成一个行向量。
　　original_img=np.array(mh.imread('mlslpic\6.6 tree.png'),dtype=np.float64)/255original_dimensions=tuple(original_img.shape)width,height,depth=tuple(original_img.shape)image_flattened=np.reshape(original_img,(width*height,depth))
　　然后我们用K-Means算法在随机选择1000个颜色样本中建立64个类。每个类都可能是压缩调色板中的一种颜色。
　　image_array_sample=shuffle(image_flattened,random_state=0)[:1000]estimator=KMeans(n_clusters=64,random_state=0)estimator.fit(image_array_sample)
　　KMeans(copy_x=True, init='k-means++', max_iter=300, n_clusters=64, n_init=10, n_jobs=1, precompute_distances='auto', random_state=0, tol=0.0001, verbose=0)
　　之后，我们为原始图片的每个像素进行类的分配。
　　cluster_assignments=estimator.predict(image_flattened)
　　最后，我们建立通过压缩调色板和类分配结果创建压缩后的图片：
　　compressed_palette=estimator.cluster_centers_compressed_img=np.zeros((width,height,compressed_palette.shape[1]))label_idx=0foriinrange(width):forjinrange(height):compressed_img[i][j]=compressed_palette[cluster_assignments[label_idx]]label_idx+=1plt.subplot(122)plt.title('Original Image')plt.imshow(original_img)plt.axis('off')plt.subplot(121)plt.title('Compressed Image')plt.imshow(compressed_img)plt.axis('off')plt.show()
　　通过聚类学习特征
　　在下面的例子中，我们将聚类和分类组合起来研究一个半监督学习问题。你将对不带标签的数据进行聚类，获得一些特征，然后用这些特征来建立一个监督方法分类器。
　　假设你有一只猫和一条狗。再假设你买了一个智能手机，表面上看是用来给人打电话的，其实你只是用来给猫和狗拍照。你的照片拍得很棒，因此你觉得你的朋友和同事一定会喜欢它们。而你知道一部分人只想看猫的照片，一部分人只想看狗的照片，但是要把这些照片分类太麻烦了。下面我们就做一个半监督学习系统来分别猫和狗的照片。
　　回想一下第三章，特征抽取与处理的内容，有一个原始的方法来给图片分类，是用图片的像素密度值或亮度值作为解释变量。和我们前面进行文本处理时的高维向量不同，图片的特征向量不是稀疏的。另外，这个方法对图片的亮度，尺寸，旋转的变化都十分敏感。在第三章，特征抽取与处理里面，我们还介绍了SIFT和SURF描述器，用来描述图片的兴趣点，这类方法对图片的亮度，尺寸，旋转变化都不敏感。在下面的例子中，我们将用聚类算法处理这些描述器来学习图片的特征。每个元素将被编码成从图片中抽取的，被分配到同一个类的描述器的数量。这种方法有时也称为视觉词袋（bag-of-features）表示法，由于这个类的集合与词袋模型里的词汇表类似。我们将使用Kaggle's Dogs vs. Cats competition里面的1000张猫图片和1000张狗图片数据。注意，图片有不同的尺寸；由于我们的特征向量不用像素表示，所有我们也不需要将所有图片都缩放成同样的尺寸。我们将训练其中60的图片，然后用剩下的40图片来测试：
　　importnumpyasnpimportmahotasasmhfrommahotas.featuresimportsurffromsklearn.linear_modelimportLogisticRegressionfromsklearn.metricsimport*fromsklearn.clusterimportMiniBatchKMeansimportglob
　　首先，我们加载图片，转换成灰度图，再抽取SURF描述器。SURF描述器与其他类似的特征相比，可以更快的被提取，但是从2000张图片中抽取描述器依然是很费时间的。
　　all_instance_filenames=[]all_instance_targets=[]forfinglob.glob('cats-and-dogs-img/*.jpg'):target=1if'cat'infelse0all_instance_filenames.append(f)all_instance_targets.append(target)surf_features=[]counter=0forfinall_instance_filenames:print('Reading image:',f)image=mh.imread(f,as_grey=True)surf_features.append(surf.surf(image)[:,5:])train_len=int(len(all_instance_filenames)*.60)X_train_surf_features=np.concatenate(surf_features[:train_len])X_test_surf_feautres=np.concatenate(surf_features[train_len:])y_train=all_instance_targets[:train_len]y_test=all_instance_targets[train_len:]
　　然后我们把抽取的描述器分成300个类。用MiniBatchKMeans类实现，它是K-Means算法的变种，每次迭代都随机抽取样本。由于每次迭代它只计算这些被随机抽取的一小部分样本与重心的距离，因此MiniBatchKMeans可以更快的聚类，但是它的畸变程度会更大。实际上，计算结果差不多：
　　n_clusters=300print('Clustering',len(X_train_surf_features),'features')estimator=MiniBatchKMeans(n_clusters=n_clusters)estimator.fit_transform(X_train_surf_features)
　　之后我们为训练集和测试集构建特征向量。我们找出每一个SURF描述器的类，用Numpy的binCount()进行计数。下面的代码为每个样本生成一个300维的特征向量：
　　X_train=[]forinstanceinsurf_features[:train_len]:clusters=estimator.predict(instance)features=np.bincount(clusters)iflen(features)&n_clusters:features=np.append(features,np.zeros((1,n_clusterslen(features))))X_train.append(features)X_test=[]forinstanceinsurf_features[train_len:]:clusters=estimator.predict(instance)features=np.bincount(clusters)iflen(features)&n_clusters:features=np.append(features,np.zeros((1,n_clusterslen(features))))X_test.append(features)
　　最后，我们在特征向量和目标上训练一个逻辑回归分类器，然后估计它的精确率，召回率和准确率：
　　clf=LogisticRegression(C=0.001,penalty='l2')clf.fit_transform(X_train,y_train)predictions=clf.predict(X_test)print(classification_report(y_test,predictions))print('Precision: ',precision_score(y_test,predictions))print('Recall: ',recall_score(y_test,predictions))print('Accuracy: ',accuracy_score(y_test,predictions))
　　半监督学习系统仅仅使用像素密度作为特征向量，就获得了比逻辑回归分类器更好的精确率和召回率。而且，我们的特征向量只有300维，比100x100像素图片的10000维要小得多。
　　本章，我们介绍了我们的第一个无监督学习方法：聚类。聚类是用来探索无标签数据的结构的。我们介绍了K-Means聚类算法，重复将样本分配的类里面，不断的更新类的重心位置。虽然K-Means是无监督学习方法，其效果依然是可以度量的；用畸变程度和轮廓系数可以评估聚类效果。我们用K-Means研究了两个问题。第一个问是图像量化，一种用单一颜色表示一组相似颜色的图像压缩技术。我们还用K-Means研究了半监督图像分类问题的特征。
　　下一章，我们将介绍另一种无监督学习任务――降维（dimensionality reduction）。和我们前面介绍过的半监督猫和狗图像分类问题类似，降维算法可以在尽量保留信息完整性的同时，降低解释变量集合的维度。
　　博主简介：风雪夜归子（英文名: Allen），机器学习算法攻城狮，喜爱钻研Machine Learning的黑科技，对Deep Learning和Artificial Intelligence充满兴趣，经常关注kaggle数据挖掘竞赛平台，对数据、Machine Learning和Artificial Intelligence有兴趣的各位童鞋可以一起探讨。
欢迎举报抄袭、转载、暴力色情及含有欺诈和虚假信息的不良文章。
请先登录再操作
请先登录再操作
微信扫一扫分享至朋友圈
搜狐公众平台官方账号
生活时尚&搭配博主 /生活时尚自媒体 /时尚类书籍作者
搜狐网教育频道官方账号
全球最大华文占星网站-专业研究星座命理及测算服务机构
主演：黄晓明/陈乔恩/乔任梁/谢君豪/吕佳容/戚迹
主演：陈晓/陈妍希/张馨予/杨明娜/毛晓彤/孙耀琦
主演：陈键锋/李依晓/张迪/郑亦桐/张明明/何彦霓
主演：尚格?云顿/乔?弗拉尼甘/Bianca Bree
主演：艾斯?库珀/ 查宁?塔图姆/ 乔纳?希尔
baby14岁写真曝光
李冰冰向成龙撒娇争宠
李湘遭闺蜜曝光旧爱
美女模特教老板走秀
曝搬砖男神奇葩择偶观
柳岩被迫成赚钱工具
大屁小P虐心恋
匆匆那年大结局
乔杉遭粉丝骚扰
男闺蜜的尴尬初夜
客服热线：86-10-
客服邮箱：}