K-means聚类算法的原理十分简单，具体的实现原理见笔记本，需要指出的是使用算法实现样本点与聚类中心点计算的时候，要用两层循环，总之具体的实现方法见代码
首先初始化定义分类函数：
function idx = findClosestCentroids(X, centroids) %FINDCLOSESTCENTROIDS computes the centroid memberships for every example % idx = FINDCLOSESTCENTROIDS (X, centroids) returns the closest centroids % in idx for a dataset X where each row is a single example. idx = m x 1 % vector of centroid assignments (i.e. each entry in range [1..K]) % % Set K K = size(centroids, 1); % You need to return the following variables correctly. idx = zeros(size(X,1), 1); % Instructions: Go over every example, find its closest centroid, and store % the index inside idx at the appropriate location. % Concretely, idx(i) should contain the index of the centroid % closest to example i. Hence, it should be a value in the % range 1..K % % Note: You can use a for-loop over the examples to compute this. % m=size(X,1); for i=1:m for j=1:K dis(i,j)=sum((X(i,:)-centroids(j,:)).^2); %计算第i个X与第j个中心的距离 %所以得到的dis矩阵的一行就是一个样本与各中心的距离 %所以每个样本的分类就是每一行最小值所对应的列 end end [~, idx] = min(dis,[],2); %min函数第一个返回值是数值，第二个返回值是索引，既然第三个参数是2，那么返回的就是列索引 % ============================================================= end第二步就是聚类中心的重新计算，定义函数如下：
function centroids = computeCentroids(X, idx, K) %COMPUTECENTROIDS returns the new centroids by computing the means of the %data points assigned to each centroid. % centroids = COMPUTECENTROIDS(X, idx, K) returns the new centroids by % computing the means of the data points assigned to each centroid. It is % given a dataset X where each row is a single data point, a vector % idx of centroid assignments (i.e. each entry in range [1..K]) for each % example, and K, the number of centroids. You should return a matrix % centroids, where each row of centroids is the mean of the data points % assigned to it. % % Useful variables [m n] = size(X); % You need to return the following variables correctly. centroids = zeros(K, n); % ====================== YOUR CODE HERE ====================== % Instructions: Go over every centroid and compute mean of all points that % belong to it. Concretely, the row vector centroids(i, :) % should contain the mean of the data points assigned to % centroid i. % % Note: You can use a for-loop over the centroids to compute this. % for i = 1:K centroids(i,:)=mean( X(idx==i,:) );%重新计算聚类中心点 end % ============================================================= end此外，我们可以让计算机随机自动地选择起始点，定义函数如下：
function centroids = kMeansInitCentroids(X, K) %KMEANSINITCENTROIDS This function initializes K centroids that are to be %used in K-Means on the dataset X % centroids = KMEANSINITCENTROIDS(X, K) returns K initial centroids to be % used with the K-Means on the dataset X % % You should return this values correctly centroids = zeros(K, size(X, 2)); % ====================== YOUR CODE HERE ====================== % Instructions: You should set centroids to randomly chosen examples from % the dataset X % randidx=randperm(size(X,1));%将X样本全部随机打乱 centroids=X(randidx(1:K),:);%选择K个作为起始聚类中心 % ============================================================= end把上述函数整合，封装成一个系统的执行程序：
function [centroids, idx] = runkMeans(X, initial_centroids, ... max_iters, plot_progress) %RUNKMEANS runs the K-Means algorithm on data matrix X, where each row of X %is a single example % [centroids, idx] = RUNKMEANS(X, initial_centroids, max_iters, ... % plot_progress) runs the K-Means algorithm on data matrix X, where each % row of X is a single example. It uses initial_centroids used as the % initial centroids. max_iters specifies the total number of interactions % of K-Means to execute. plot_progress is a true/false flag that % indicates if the function should also plot its progress as the % learning happens. This is set to false by default. runkMeans returns % centroids, a Kxn matrix of the computed centroids and idx, a m x 1 % vector of centroid assignments (i.e. each entry in range [1..K]) % % Set default value for plot progress if ~exist('plot_progress', 'var') || isempty(plot_progress) plot_progress = false; end % Plot the data if we are plotting progress if plot_progress figure; hold on; end % Initialize values [m n] = size(X); K = size(initial_centroids, 1); centroids = initial_centroids; previous_centroids = centroids; idx = zeros(m, 1); % Run K-Means for i=1:max_iters % Output progress fprintf('K-Means iteration %d/%d...\n', i, max_iters); if exist('OCTAVE_VERSION') fflush(stdout); end % For each example in X, assign it to the closest centroid idx = findClosestCentroids(X, centroids); % Optionally, plot progress here if plot_progress plotProgresskMeans(X, centroids, previous_centroids, idx, K, i); previous_centroids = centroids; fprintf('Press enter to continue.\n'); pause; end % Given the memberships, compute new centroids centroids = computeCentroids(X, idx, K); end % Hold off if we are plotting progress if plot_progress hold off; end end这就实现了聚类算法 主函数代码及其运行效果如下：
%% ================= Part 1: Find Closest Centroids ==================== % To help you implement K-Means, we have divided the learning algorithm % into two functions -- findClosestCentroids and computeCentroids. In this % part, you should complete the code in the findClosestCentroids function. % fprintf('Finding closest centroids.\n\n'); % Load an example dataset that we will be using load('ex7data2.mat'); % Select an initial set of centroids K = 3; % 3 Centroids initial_centroids = [3 3; 6 2; 8 5]; % Find the closest centroids for the examples using the % initial_centroids idx = findClosestCentroids(X, initial_centroids); fprintf('Closest centroids for the first 3 examples: \n') fprintf(' %d', idx(1:3)); fprintf('\n(the closest centroids should be 1, 3, 2 respectively)\n'); fprintf('Program paused. Press enter to continue.\n'); pause; %% ===================== Part 2: Compute Means ========================= % After implementing the closest centroids function, you should now % complete the computeCentroids function. % fprintf('\nComputing centroids means.\n\n'); % Compute means based on the closest centroids found in the previous part. centroids = computeCentroids(X, idx, K); fprintf('Centroids computed after initial finding of closest centroids: \n') fprintf(' %f %f \n' , centroids'); fprintf('\n(the centroids should be\n'); fprintf(' [ 2.428301 3.157924 ]\n'); fprintf(' [ 5.813503 2.633656 ]\n'); fprintf(' [ 7.119387 3.616684 ]\n\n'); fprintf('Program paused. Press enter to continue.\n'); pause; %% =================== Part 3: K-Means Clustering ====================== % After you have completed the two functions computeCentroids and % findClosestCentroids, you have all the necessary pieces to run the % kMeans algorithm. In this part, you will run the K-Means algorithm on % the example dataset we have provided. % fprintf('\nRunning K-Means clustering on example dataset.\n\n'); % Load an example dataset load('ex7data2.mat'); % Settings for running K-Means K = 3; max_iters = 10; % For consistency, here we set centroids to specific values % but in practice you want to generate them automatically, such as by % settings them to be random examples (as can be seen in % kMeansInitCentroids). initial_centroids = [3 3; 6 2; 8 5]; % Run K-Means algorithm. The 'true' at the end tells our function to plot % the progress of K-Means [centroids, idx] = runkMeans(X, initial_centroids, max_iters, true); fprintf('\nK-Means Done.\n\n'); fprintf('Program paused. Press enter to continue.\n'); clear pause;此外这个算法还可以应用于图片压缩，这部分本文不予讨论
PCA降维算法的数学原理十分复杂，我们只需要知道它的功能和代码实现即可。 在使用PCA对数据降维之前要对数据进行归一化处理 首先编辑一个计算协方差以及降温矩阵的函数，如下：
function [U, S] = pca(X) %PCA Run principal component analysis on the dataset X % [U, S, X] = pca(X) computes eigenvectors of the covariance matrix of X % Returns the eigenvectors U, the eigenvalues (on diagonal) in S % % Useful values [m, n] = size(X); % You need to return the following variables correctly. U = zeros(n); S = zeros(n); % ====================== YOUR CODE HERE ====================== % Instructions: You should first compute the covariance matrix. Then, you % should use the "svd" function to compute the eigenvectors % and eigenvalues of the covariance matrix. % % Note: When computing the covariance matrix, remember to divide by m (the % number of examples). % Sigma=(X'*X)/m; %计算协方差 [U,S,V]=svd(Sigma); %计算降维矩阵U和误差矩阵S %将来计算误差的时候就是S的全部对角线元素比上前K的元素的值 % ========================================================================= end这样我们就得到了降维矩阵U,U是个nn的矩阵象征n维，取出其中k列作为U_reduce，那么U_reduce就是nk维，X是mn维，那么我们降维后的新变量Z就可以表示为： Z=X(U_reduce) Z就是m*k维变量 编程如下：
function Z = projectData(X, U, K) %PROJECTDATA Computes the reduced data representation when projecting only %on to the top k eigenvectors % Z = projectData(X, U, K) computes the projection of % the normalized inputs X into the reduced dimensional space spanned by % the first K columns of U. It returns the projected examples in Z. % % You need to return the following variables correctly. Z = zeros(size(X, 1), K); % ====================== YOUR CODE HERE ====================== % Instructions: Compute the projection of the data using only the top K % eigenvectors in U (first K columns). % For the i-th example X(i,:), the projection on to the k-th % eigenvector is given as follows: % x = X(i, :)'; % projection_k = x' * U(:, k); % %U=n*n,U_reduce=n*K,Z=m*K,X=m*n U_reduce=U(:,1:K); Z=X*U_reduce % ============================================================= end当然，这也是压缩数据的原理，数据的还原原理亦然： X_rec=Z*(U_reduce)’ 编程如下：
function X_rec = recoverData(Z, U, K) %RECOVERDATA Recovers an approximation of the original data when using the %projected data % X_rec = RECOVERDATA(Z, U, K) recovers an approximation the % original data that has been reduced to K dimensions. It returns the % approximate reconstruction in X_rec. % % You need to return the following variables correctly. X_rec = zeros(size(Z, 1), size(U, 1)); % ====================== YOUR CODE HERE ====================== % Instructions: Compute the approximation of the data by projecting back % onto the original space using the top K eigenvectors in U. % % For the i-th example Z(i,:), the (approximate) % recovered data for dimension j is given as follows: % v = Z(i, :)'; % recovered_j = v' * U(j, 1:K)'; % % Notice that U(j, 1:K) is a row vector. % U_reduce=U(:,1:K); X_rec=Z*(U_reduce)'; % ============================================================= end主成分分析可以用于找到影响问题的主要方面，数据降维以节省计算时间，以及对数据压缩以节省空间等，但是绝不能用在过拟合问题中，而且PCA不是一个被推荐使用的算法，在使用PCA之前先想想不使用PCA可不可以，实在不行再说 主程序代码及其效果如下：
%% ================== Part 1: Load Example Dataset =================== % We start this exercise by using a small dataset that is easily to % visualize % fprintf('Visualizing example dataset for PCA.\n\n'); % The following command loads the dataset. You should now have the % variable X in your environment load ('ex7data1.mat'); % Visualize the example dataset plot(X(:, 1), X(:, 2), 'bo'); axis([0.5 6.5 2 8]); axis square; fprintf('Program paused. Press enter to continue.\n'); pause; %% =============== Part 2: Principal Component Analysis =============== % You should now implement PCA, a dimension reduction technique. You % should complete the code in pca.m % fprintf('\nRunning PCA on example dataset.\n\n'); % Before running PCA, it is important to first normalize X [X_norm, mu, sigma] = featureNormalize(X); % Run PCA [U, S] = pca(X_norm); % Compute mu, the mean of the each feature % Draw the eigenvectors centered at mean of data. These lines show the % directions of maximum variations in the dataset. hold on; drawLine(mu, mu + 1.5 * S(1,1) * U(:,1)', '-k', 'LineWidth', 2); drawLine(mu, mu + 1.5 * S(2,2) * U(:,2)', '-k', 'LineWidth', 2); hold off; fprintf('Top eigenvector: \n'); fprintf(' U(:,1) = %f %f \n', U(1,1), U(2,1)); fprintf('\n(you should expect to see -0.707107 -0.707107)\n'); fprintf('Program paused. Press enter to continue.\n'); pause; %% =================== Part 3: Dimension Reduction =================== % You should now implement the projection step to map the data onto the % first k eigenvectors. The code will then plot the data in this reduced % dimensional space. This will show you what the data looks like when % using only the corresponding eigenvectors to reconstruct it. % % You should complete the code in projectData.m % fprintf('\nDimension reduction on example dataset.\n\n'); % Plot the normalized dataset (returned from pca) plot(X_norm(:, 1), X_norm(:, 2), 'bo'); axis([-4 3 -4 3]); axis square % Project the data onto K = 1 dimension K = 1; Z = projectData(X_norm, U, K); fprintf('Projection of the first example: %f\n', Z(1)); fprintf('\n(this value should be about 1.481274)\n\n'); X_rec = recoverData(Z, U, K); fprintf('Approximation of the first example: %f %f\n', X_rec(1, 1), X_rec(1, 2)); fprintf('\n(this value should be about -1.047419 -1.047419)\n\n'); % Draw lines connecting the projected points to the original points hold on; plot(X_rec(:, 1), X_rec(:, 2), 'ro'); for i = 1:size(X_norm, 1) drawLine(X_norm(i,:), X_rec(i,:), '--k', 'LineWidth', 1); end hold off fprintf('Program paused. Press enter to continue.\n'); pause;还有一些具体应用，本文不作详细讨论
