k-means（k-均值）算法是一种基于距离的聚类算法，它用质心（Centroid）到属于该质心的点距离这个度量来实现聚类，通常可以用于N维空间中对象。下面，我们以二维空间为例，概要地总结一下k-means聚类算法的一些要点： 除了随机选择的初始质心，后续迭代质心是根据给定的待聚类的集合S中点计算均值得到的，所以质心一般不是S中的点，但是标识的是一簇点的中心。 基本k-means算法，开始需要随机选择指定的k个质心，因为初始k个质心是随机选择的，所以每次执行k-means聚类的结果可能都不相同。如果初始随机选择的质心位置不好，可能造成k-means聚类的结果非常不理想。 计算质心：假设k-means聚类过程中，得到某一个簇的集合Ci={p(x1,y1), p(x2,y2), …,p(xn,yn)}，则簇Ci的质心，质心x坐标为(x1+x2+ …+xn)/n，质心y坐标为(y1+y2+ …+yn)/n。 k-means算法的终止条件：质心在每一轮迭代中会发生变化，然后需要重新将非质心点指派给最近的质心而形成新的簇，如果只有很少的一部分点在迭代过程中，还在改变簇（如，更新一次质心，有些点从一个簇移动到另一
按分类浏览文章: 人工智能
DBSCAN聚类算法原理及其实现
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚类算法，它是一种基于高密度连通区域的、基于密度的聚类算法，能够将具有足够高密度的区域划分为簇，并在具有噪声的数据中发现任意形状的簇。我们总结一下DBSCAN聚类算法原理的基本要点： DBSCAN算法需要选择一种距离度量，对于待聚类的数据集中，任意两个点之间的距离，反映了点之间的密度，说明了点与点是否能够聚到同一类中。由于DBSCAN算法对高维数据定义密度很困难，所以对于二维空间中的点，可以使用欧几里德距离来进行度量。 DBSCAN算法需要用户输入2个参数：一个参数是半径（Eps），表示以给定点P为中心的圆形邻域的范围；另一个参数是以点P为中心的邻域内最少点的数量（MinPts）。如果满足：以点P为中心、半径为Eps的邻域内的点的个数不少于MinPts，则称点P为核心点。 DBSCAN聚类使用到一个k-距离的概念，k-距离是指：给定数据集P={p(i); i=0,1,…n}，对于任意点P(i)，计算点P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中所有点之间的距离，
使用libsvm实现文本分类
文本分类，首先它是分类问题，应该对应着分类过程的两个重要的步骤，一个是使用训练数据集训练分类器，另一个就是使用测试数据集来评价分类器的分类精度。然而，作为文本分类，它还具有文本这样的约束，所以对于文本来说，需要额外的处理过程，我们结合使用libsvm从宏观上总结一下，基于libsvm实现文本分类实现的基本过程，如下所示： 选择文本训练数据集和测试数据集：训练集和测试集都是类标签已知的； 训练集文本预处理：这里主要包括分词、去停用词、建立词袋模型（倒排表）； 选择文本分类使用的特征向量（词向量）：最终的目标是使得最终选出的特征向量在多个类别之间具有一定的类别区分度，可以使用相关有效的技术去实现特征向量的选择，由于分词后得到大量的词，通过选择降维技术能很好地减少计算量，还能维持分类的精度； 输出libsvm支持的量化的训练样本集文件：类别名称、特征向量中每个词元素分别到数字编号的映射转换，以及基于类别和特征向量来量化文本训练集，能够满足使用libsvm训练所需要的数据格式； 测试数据集预处理：同样包括分词（需要和训练
聚类算法：K-means
K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。 对于聚类问题，我们事先并不知道给定的一个训练数据集到底具有哪些类别（即没有指定类标签），而是根据需要设置指定个数类标签的数量（但不知道具体的类标签是什么），然后通过K-means算法将具有相同特征，或者基于一定规则认为某一些对象相似，与其它一些组明显的不同的数据聚集到一起，自然形成分组。之后，我们可以根据每一组的数据的特点，给定一个合适的类标签（当然，可能给出类标签对实际应用没有实际意义，例如可能我们就想看一下聚类得到的各个数据集的相似性）。 首先说明一个概念：质心（Centroid）。质心可以认为就是一个样本点，或者可以认为是数据集中的一个数据点P，它是具有相似性的一组数据的中心，即该组中每个数据点到P的距离都比到其他质心的距离近（与其他质心相似性比较低）。 k个初始类聚类质心（Centroid）的选取对聚类结果具有较大的影
分类算法：决策树（C4.5）
C4.5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行改进后的一种重要算法，相比于ID3算法，改进有如下几个要点： 用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵（entropy， 熵是一种不纯度度量准则），也就是熵的变化值，而C4.5用的是信息增益率。 在决策树构造过程中进行剪枝，因为某些具有很少元素的结点可能会使构造的决策树过适应（Overfitting），如果不考虑这些结点可能会更好。 对非离散数据也能处理。 能够对不完整数据进行处理。 首先，说明一下如何计算信息增益率。 熟悉了ID3算法后，已经知道如何计算信息增益，计算公式如下所示（来自Wikipedia）： 或者，用另一个更加直观容易理解的公式计算： 按照类标签对训练数据集D的属性集A进行划分，得到信息熵： 按照属性集A中每个属性进行划分，得到一组信息熵： 计算信息增益 然后计算信息增益，即前者对后者做差，得到属性集合A一组信息增益： 这样，信息增益就计算出来了。 计算信息增益率 下面看，计算信息增益率
分类算法：决策树（ID3）
决策树是以实例为基础的归纳学习算法。 它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，并根据不同的属性值从该结点向下分支，叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。 一棵决策树由以下3类结点构成： 根结点 内部结点（决策结点） 叶结点 其中，根结点和内部结点都对应着我们要进行分类的属性集中的一个属性，而叶结点是分类中的类标签的集合。如果一棵决策树构建起来，其分类精度满足我们的实际需要，我们就可以使用它来进行分类新的数据集。 这棵决策树就是我们根据已有的训练数据集训练出来的分类模型，可以通过使用测试数据集来对分类模型进行验证，经过调整模型直到达到我们所期望的分类精度，然后就可以使用该模型来预测实际应用中的新数据，对新的数据进行分类。 通过上面描述，我们已经能够感觉出，在构建决策树的过程中，如果选择其中的内部结点（决策结点），才能够使我们的决策树得到较高的分
使用libsvm进行分类预测
使用libsvm，首先需要将实际待分类的内容或数据（训练数据，或预测数据）进行量化，然后通过libsvm提供的功能实现分类和预测。下面介绍使用libsvm的基本步骤。 准备训练数据 数据格式： <label1> <index1>:<value11> <index2>:<value12>... <label2> <index1>:<value21> <index2>:<value22>... <label3> <index1>:<value31> <index2>:<value32>... ... 每一行，表示以已定义的类别标签，以及属于该标签的各个属性值，每个属性值以“属性索引编号:属性值”的格式。一行内容表示一个类别属性以及与该类别相关的各个属性的值。属性的值，一般可以表示为“该属性隶属于该类别的程度”，越大，表示该属性更能决定属性该类别。 上面的数据必须使用数字类型，例如类别，可以通过不同的整数来表示不同的类别。 准备的原始训练样本数据存放在文件raw_data.txt中，内容如下所示： 1 1:0.4599 2:0.8718 3:0.1987 2 1:0.9765 2:0.2398 3:0.3999 3 1:0.0988 2:0.2432 3:0