利用K-均值聚类算法对未标注数据分组和使用Apriori算法进行关联与分析
利用K-均值聚类算法对未标注数据分组
一、1.K-均值聚类算法
K-均值算法的伪代码如下：
创建k个点作为起始质心（经常是随机选择）
当任意一个点的簇分配结果发生改变时
对数据集中的每个数据点
对每个质心
计算质心与数据点之间的距离
将数据点分配到距其最近的簇
对每个簇，计算簇中所有点的均值并将均值作为质心
注意：质心意味着需要进行某种距离计算，可以选择任意距离度量方法
例子：`# coding=utf-8
from numpy import *
def loadDataSet(fileName) :
dataMat = []
fr = open(fileName)
for line in fr.readlines() :
curLine = line.strip().split(’\t’)
fltLine = map(float, curLine)
dataMat.append(fltLine)
return dataMat
计算两个向量的欧式距离
def distEclud(vecA, vecB) :
return sqrt(sum(power(vecA - vecB, 2)))
为给定的数据集构建一个包含k个随机质心的集合
def randCent(dataSet, k) :
n = shape(dataSet)[1]
centroids = mat(zeros((k,n)))
构建簇质心
for j in range(n) :
每一维的最小值
minJ = min(dataSet[:, j])
每一维的最大值最小值之差
rangeJ = float(max(dataSet[:,j]) - minJ)
random.rand(i,j)，生成一个i行j列的数组，其中每个元素都0-1之间的随机数
centroids[:,j] = minJ + rangeJ *
random.rand(k,1)
return centroids
2.后处理来提高聚类性能
在包含簇分配结果的矩阵中保存着每个点的误差，即该点到簇质心的距离平方值，可以利用该误差来评价聚类质量的方法。K均值算法有时虽收敛但聚类效果却较差。原因是，K均值算法收敛到了局部最小值，而非全局最小值。
一种度量聚类效果的指标是SSE（Sum
of Square Error，误差平方和），对应上面程序中clusterAssment矩阵的第一列之和。SSE值越小表示数据点越接近它们的质心，聚类效果越好。因为对误差取了平方，因此，更加重视那些远离中心的点。增加簇的个数肯定可以降低SSE值，但这违背了聚类的目标。聚类的目标是在保持簇的数目不变的情况下提高簇的质量。
对生成的簇进行后处理，将具有最大SSE值得簇过滤出来，在这些点上运行k-均值算法（其中k=2）划分成两个簇。为保持簇总数不变，可将某两个簇进行合并。两种可量化的合并方法：
合并最近的质心，通过计算所有质心的之间的距离，然后合并距离最近的两个点实现；
合并两个使SSE增幅最小的质心，需要合并两个簇后计算总SSE值。必须在所有可能的两个簇上重复上述过程，直到找到合并最佳的两个簇为止。
二、二分K-均值算法
为了克服k-均值算法收敛于局部最小值的问题。该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择一个簇继续划分，选择哪个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，直到得到指定的簇数目为止。
二分K-均值算法的伪代码形式如下：
使用Apriori算法进行关联与分析
一、概述
忠诚度计划是指顾客使用会员卡可以获得一定的折扣，利用这种计划，商店可以了解顾客所购买的商品。即使顾客不使用会员卡，商店也会查看顾客购买商品所使用的信用卡记录。如果顾客不使用信用卡而使用现金付账，商店则可以查看顾客一起购买的商品。通过查看哪些商品经常在一起购买，可以帮助商店了解用户的购买行为。
这种从数据海洋中抽取的知识可以用于商品定价、市场促销、存货管理等环节。从大规模数据集中寻找物品间的隐含关系被称作关联分析（association analysis）或者关联规则学习（association
rule learning）。
这里的主要问题在于，寻找物品的不同组合是一项十分耗时的任务，所需的计算代价很高，蛮力搜索方法并不能解决这个问题，所以需要用更智能的方法在合理的时间范围内找到频繁项集。
所以我们将学习如何使用Apriori算法来解决上述问题。
Apriori算法优缺点
优点：易编码实现。
缺点：在大数据集上可能较慢。
适用数据类型：
数值型
标称型
Apriori算法的一般过程
(1) 收集数据：使用任意方法。
(2) 准备数据：任何数据类型都可以，因为我们只保存集合。
(3) 分析数据：使用任意方法。
(4) 训练算法：使用Apriori算法来找到频繁项集。
(5) 测试算法：不需要测试过程。
(6) 使用算法：用于发现频繁项集以及物品之间的关联规则
2.Apriori 原理
假设我们在经营一家商品种类并不多的杂货店，我们对那些经常在一起被购买的商品非常感兴趣。我们只有4种商品：商品0，商品1，商品2和商品3。
这些商品组合可能只有一种商品，比如商品0，也可能包括两种、三种或者所有四种商品。我们并不关心某人买了两件商品0以及四件商品2的情况，我们只关心他购买了一种或多种商品。下图显示了物品之间所有可能的组合。图中从上往下的第一个集合是ϕ \phiϕ ，表示空集或不包含任何物品的集合。物品集合之间的连线表明两个或者更多集合可以组合形成一个更大的集合
。
我们可以数一下图的集合数目，会发现即使对于仅有4种物品的集合，也需要遍历数据15次。而随着物品数目的增加遍历次数会急剧增长。对于包含N种物品的数据集共有2N−1 2^{N}-12
N
−1种项集组合。
为了降低所需的计算时间，研究人员发现一种所谓的Apriori原理，可以帮我们减少可能感兴趣的项集。
Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。
上图给出的例子，这意味着如果{0,1}是频繁的，那么{0}、{1}也一定是频繁的。这个原理直观上并没有什么帮助，但是如果反过来看就有用了，也就是说如果一个项集是非频繁集，那么它的所有超集也是非频繁的。
如下图：
整个Apriori算法的伪代码如下：当集合中项的个数大于0时
构建一个k个项组成的候选项集的列表
检查数据以确认每个项集都是频繁的
保留频繁项集并构建k+1项组成的候选项集的列表
1234剩下部分代码如下：
小结
关联分析是用于发现大数据集中元素间有趣关系的一个工具，可以用在许多不同物品上。商店中的商品以及网站的访问页面是其中比较常见的例子。关联分析也曾用于查看选举人及法官的投票历史。
可以采用两种方式来量化关系：
第一种方式是使用频繁项集，它会给出经常在一起出现的元素项；
第二种方式是关联规则，每条关联规则意味着元素项之间的“如果……那么”关系。
发现元素项间不同的组合是个耗时耗资源的任务，而Apriori算法可以在合理的时间范围内找到频繁项集。能够实现这一目标的一个方法是，它使用Apriori原理来减少在数据库上进行检查的集合的数目。
Apriori原理是说如果一个元素项是不频繁的，那么那些包含该元素的超集也是不频繁的。 Apriori算法从单元素项集开始，通过组合满足最小支持度要求的项集来形成更大的集合。
支持度用来度量一个集合在原始数据中出现的频率。
Apriori算法缺点：每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集。当数据集很大时，这会显著降低频繁项集发现的速度。