📄 vqkmeans.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd"><html><head> <title>Description of vqKmeans</title> <meta name="keywords" content="vqKmeans"> <meta name="description" content="vqKmeans: Vector quantization using K-means clustering (Forgy's batch-mode method)"> <meta http-equiv="Content-Type" content="text/html; charset=big5"> <meta name="generator" content="m2html © 2003 Guillaume Flandin"> <meta name="robots" content="index, follow"> <link type="text/css" rel="stylesheet" href="../m2html.css"></head><body><a name="_top"></a><div><a href="../index.html">Home</a> > <a href="index.html">dcpr</a> > vqKmeans.m</div><!--<table width="100%"><tr><td align="left"><a href="../index.html"><img alt="<" border="0" src="../left.png"> Master index</a></td><td align="right"><a href="index.html">Index for dcpr <img alt=">" border="0" src="../right.png"></a></td></tr></table>--><h1>vqKmeans</h1><h2><a name="_name"></a>PURPOSE <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="box"><strong>vqKmeans: Vector quantization using K-means clustering (Forgy's batch-mode method)</strong></div><h2><a name="_synopsis"></a>SYNOPSIS <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="box"><strong>function [center, U, distortion, allCenter] = vqKmeans(data, clusterNum, plotOpt) </strong></div><h2><a name="_description"></a>DESCRIPTION <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="fragment"><pre class="comment"> vqKmeans: Vector quantization using K-means clustering (Forgy's batch-mode method)
Usage: [center, U, distortion, allCenter] = vqKmeans(data, clusterNum, plotOpt)
data (dim x dataNum): data set to be clustered; where each column is a sample data
clusterNum: number of clusters (greater than one), or matrix of columns of centers
center (dim x clusterNum): final cluster centers, where each column is a center
U: final partition matrix
distortion: values of the objective function during iterations
Roger Jang, 20030330</pre></div><!-- crossreference --><h2><a name="_cross"></a>CROSS-REFERENCE INFORMATION <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2>This function calls:<ul style="list-style-image:url(../matlabicon.gif)"><li><a href="dcData.html" class="code" title="function DS = dcdata(dataID)">dcData</a> DCDATA Test data sets for data clustering (no class label).</li><li><a href="vqDataPlot.html" class="code" title="function vqDataPlot(data, center)">vqDataPlot</a> vqDataPlot: Plot the result of vector quantization (used in kmeans.m and vqLBG.m)</li><li><a href="vqInitCenter.html" class="code" title="function center = vqInitCenter(data, clusterNum, method)">vqInitCenter</a> vqInitCenter: Find initial centers for VQ or k-means</li></ul>This function is called by:<ul style="list-style-image:url(../matlabicon.gif)"><li><a href="genBBT.html" class="code" title="function NODE = genbbt(data, clusterNum, levelNum);">genBBT</a> GENBBT Generate BBT (Branch and Bound Tree) for nearest neighbor search</li><li><a href="gmmInitParamSet.html" class="code" title="function gmmParam=gmmInitParamSet(data, gaussianNum, covType, gmmTrainParam);">gmmInitParamSet</a> gmmParamSet: Set a set of initial parameters for GMM</li><li><a href="vqKmeansTest.html" class="code" title="">vqKmeansTest</a> Test k-means on 2-D data</li></ul><!-- crossreference --><h2><a name="_subfunctions"></a>SUBFUNCTIONS <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><ul style="list-style-image:url(../matlabicon.gif)"><li><a href="#_sub1" class="code">function [center, distortion, U] = vqUpdateCenter(center, data)</a></li><li><a href="#_sub2" class="code">function selfdemo</a></li></ul><h2><a name="_source"></a>SOURCE CODE <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="fragment"><pre>0001 <a name="_sub0" href="#_subfunctions" class="code">function [center, U, distortion, allCenter] = vqKmeans(data, clusterNum, plotOpt)</a>0002 <span class="comment">% vqKmeans: Vector quantization using K-means clustering (Forgy's batch-mode method)</span>0003 <span class="comment">% Usage: [center, U, distortion, allCenter] = vqKmeans(data, clusterNum, plotOpt)</span>0004 <span class="comment">% data (dim x dataNum): data set to be clustered; where each column is a sample data</span>0005 <span class="comment">% clusterNum: number of clusters (greater than one), or matrix of columns of centers</span>0006 <span class="comment">% center (dim x clusterNum): final cluster centers, where each column is a center</span>0007 <span class="comment">% U: final partition matrix</span>0008 <span class="comment">% distortion: values of the objective function during iterations</span>0009 <span class="comment">%</span>0010 <span class="comment">% Roger Jang, 20030330</span>0011 0012 <span class="keyword">if</span> nargin<1, <a href="#_sub2" class="code" title="subfunction selfdemo">selfdemo</a>; <span class="keyword">return</span>; <span class="keyword">end</span>0013 <span class="keyword">if</span> nargin<3, plotOpt=0; <span class="keyword">end</span>0014 0015 dim=size(data,1);0016 dataNum=size(data,2);0017 <span class="keyword">if</span> clusterNum==1 | (size(clusterNum,1)>1 & size(clusterNum,2)==1)0018 center=mean(data, 2);0019 U=ones(1, dataNum);0020 distortion=sum(sum((data-center*ones(1,dataNum)).^2));0021 allCenter=center;0022 <span class="keyword">return</span>;0023 <span class="keyword">end</span>0024 0025 maxLoopCount = 100; <span class="comment">% Max. iteration</span>0026 distortion = zeros(maxLoopCount, 1); <span class="comment">% Array for objective function</span>0027 <span class="keyword">if</span> length(clusterNum)==10028 center = <a href="vqInitCenter.html" class="code" title="function center = vqInitCenter(data, clusterNum, method)">vqInitCenter</a>(data, clusterNum, 3); <span class="comment">% Initial cluster centers</span>0029 <span class="keyword">else</span>0030 center = clusterNum; <span class="comment">% The passed argument is actually a matrix of cluster centers</span>0031 <span class="keyword">end</span>0032 <span class="keyword">if</span> nargout==4, allCenter(:,:,1)=center; <span class="keyword">end</span>0033 0034 <span class="keyword">if</span> plotOpt & dim==20035 plot(data(1,:), data(2,:), <span class="string">'b.'</span>);0036 centerH=line(center(1,:), center(2,:), <span class="string">'color'</span>, <span class="string">'r'</span>, <span class="string">'marker'</span>, <span class="string">'o'</span>, <span class="string">'linestyle'</span>, <span class="string">'none'</span>, <span class="string">'linewidth'</span>, 2);0037 axis image0038 <span class="keyword">end</span>;0039 0040 <span class="comment">% Main loop</span>0041 <span class="keyword">for</span> i = 1:maxLoopCount,0042 [center, distortion(i), U] = <a href="#_sub1" class="code" title="subfunction [center, distortion, U] = vqUpdateCenter(center, data)">vqUpdateCenter</a>(center, data);0043 <span class="keyword">if</span> nargout==4, allCenter(:,:,i+1)=center; <span class="keyword">end</span>0044 <span class="keyword">if</span> plotOpt, fprintf(<span class="string">'Iteration count = %d/%d, distortion = %f\n'</span>, i, maxLoopCount, distortion(i)); <span class="keyword">end</span>0045 <span class="keyword">if</span> plotOpt & dim==2 0046 set(centerH, <span class="string">'xdata'</span>, center(1,:), <span class="string">'ydata'</span>, center(2,:));0047 drawnow;0048 <span class="keyword">end</span>0049 <span class="comment">% check termination condition</span>0050 <span class="keyword">if</span> (i>1) & (abs(distortion(i-1)-distortion(i))<eps), <span class="keyword">break</span>; <span class="keyword">end</span>0051 <span class="keyword">end</span>0052 loopCount = i; <span class="comment">% Actual number of iterations</span>0053 distortion(loopCount+1:maxLoopCount) = [];0054 <span class="keyword">if</span> plotOpt & dim==2, figure; <a href="vqDataPlot.html" class="code" title="function vqDataPlot(data, center)">vqDataPlot</a>(data, center); <span class="keyword">end</span>0055 0056 <span class="comment">% ========== subfunctions ==========</span>0057 0058 <span class="comment">% ====== Update centers</span>0059 <a name="_sub1" href="#_subfunctions" class="code">function [center, distortion, U] = vqUpdateCenter(center, data)</a>0060 dim = size(data, 1);0061 dataNum = size(data, 2);0062 centerNum = size(center, 2);0063 <span class="comment">% ====== Compute distance matrix</span>0064 distMat=pairwiseSqrDistance(center, data);0065 <span class="comment">% ====== Find the U (partition matrix)</span>0066 [minDist, colIndex] = min(distMat);0067 U = zeros(size(distMat));0068 U(colIndex+centerNum*(0:dataNum-1)) = 1;0069 distortion = sum(minDist); <span class="comment">% objective function</span>0070 <span class="comment">% ====== Find new centers</span>0071 index=find(sum(U,2)==0);0072 emptyGroupNum=length(index);0073 <span class="keyword">if</span> emptyGroupNum==0 <span class="comment">% Find the new centers (with no empty cluster)</span>0074 center = (data*U')./(ones(dim,1)*sum(U,2)'); <span class="comment">% Find the new centers</span>0075 <span class="keyword">else</span> <span class="comment">% Add new centers for the empty clusters</span>0076 fprintf(<span class="string">'Found %d empty group(s)!\n'</span>, emptyGroupNum);0077 U(index,:)=[];0078 center = (data*U')./(ones(dim,1)*sum(U,2)'); <span class="comment">% Find the new centers</span>0079 <span class="keyword">if</span> emptyGroupNum<=centerNum/2 <span class="comment">% ”??X distortion ???j???X?? cluster ???i?? center splitting</span>0080 fprintf(<span class="string">'Try center splitting...\n'</span>);0081 distMat(index,:)=[];0082 distortionByGroup=sum(distMat.*U, 2);0083 [junk, index]=sort(-distortionByGroup); <span class="comment">% Find the indices of the centers to be split</span>0084 index=index(1:emptyGroupNum);0085 temp=center; temp(:, index)=[];0086 center=[temp, center(:,index)-eps, center(:,index)+eps]; <span class="comment">% Center splitting</span>0087 distMat=pairwiseSqrDistance(center, data);0088 [minDist, colIndex] = min(distMat);0089 U = zeros(size(distMat));0090 U(colIndex+centerNum*(0:dataNum-1)) = 1;0091 distortion = sum(minDist); <span class="comment">% objective function</span>0092 center = (data*U')./(ones(dim,1)*sum(U,2)');0093 <span class="keyword">else</span> <span class="comment">% Select new centers based on random selection on the data points</span>0094 fprintf(<span class="string">'Try random selection...\n'</span>);0095 newU = zeros(1,1);0096 <span class="keyword">while</span> ~isempty(find(sum(newU, 2)==0))0097 temp=randperm(dataNum);0098 selectedIndex=temp(1:emptyGroupNum);0099 newU = [zeros(emptyGroupNum, dataNum); U];0100 <span class="keyword">for</span> i=1:emptyGroupNum0101 dataIndex=selectedIndex(i);0102 index=find(U(:, dataIndex)==1);0103 newU(index, dataIndex)=0;0104 newU(i, dataIndex)=1;0105 <span class="keyword">end</span>0106 <span class="keyword">end</span>0107 U=newU;0108 distortion = sum(minDist); <span class="comment">% objective function</span>0109 center=[center, data(:, selectedIndex)];0110 <span class="keyword">end</span>0111 <span class="keyword">end</span>0112 0113 <span class="comment">% ====== Self demo</span>0114 <a name="_sub2" href="#_subfunctions" class="code">function selfdemo</a>0115 DS = <a href="dcData.html" class="code" title="function DS = dcdata(dataID)">dcData</a>(2);0116 centerNum=8;0117 plotOpt=1;0118 [center, U, distortion] = feval(mfilename, DS.input, centerNum, plotOpt);</pre></div><hr><address>Generated on Thu 30-Oct-2008 12:53:56 by <strong><a href="http://www.artefact.tk/software/matlab/m2html/">m2html</a></strong> © 2003</address></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -