其他 #
因为书中的代码比较老，这里是 python2.7 + pillow3.4.2 来运行。
监督学习和无监督学习 #
有监督学习算法根据指定算法输入和输出的样本数据进行训练。例如，数据可以是手写数字的图像，这些图像添加了注释以指示它们代表哪些数字。如果有足够的标记数据，有监督学习系统最终将识别与每个手写数字相关的像素和形状集群。
相比之下，无监督学习算法会使用未标记的数据进行训练。该算法会扫描新数据，并在未知输入和预先确定的输出之间建立有意义的连接。例如，无监督学习算法可以将来自不同新闻网站的新闻文章分为体育和犯罪等常见类别。
Word Vectors 单词向量 #
聚合算法一般需要使用一组公共的数值来进行计算，这些公共的数值称为 Word Vectors。
这里使用了几个字来作为衡量单位
Hierarchical Clustering 分类聚合 #
分类聚合 通过连续不断地将群组两两合并，构建出一个带层级的结构出来，比下图
通过树状结构也可以很好的展示
以博文为例子，聚合的树中的节点应该是一个 聚类(非叶子节点) 或者是一个 博文(叶子节点)。
定义了一个数据结构
class bicluster:
def __init__(
self,
vec,
left=None, # 左节点
right=None, # 右节点
distance=0.0, # 距离
id=None,
):
self.left = left
self.right = right
self.vec = vec
self.id = id
self.distance = distance
开始计算
def hcluster(rows, distance=pearson):
distances = {}
currentclustid = -1
# 将 Data 数组转换为 bicluster 对象
clust = [bicluster(rows[i], id=i) for i in range(len(rows))]
while len(clust) > 1:
# 声明一个 lowestpair 计算最近的两个 bicluster 的下标，这里默认是 0 和 1
lowestpair = (0, 1)
# 最近的肯定就是 0 和 1 之间了，算 皮尔逊 相关度
closest = distance(clust[0].vec, clust[1].vec)
# 因为要算所有的 2 点之间的距离，显然是一个 N*N 的算法
for i in range(len(clust)):
for j in range(i + 1, len(clust)):
# 缓存了一下，避免重复计算
if (clust[i].id, clust[j].id) not in distances:
distances[(clust[i].id, clust[j].id)] = \
distance(clust[i].vec, clust[j].vec)
d = distances[(clust[i].id, clust[j].id)]
# 如果找到更小的距离，就更新
if d < closest:
closest = d
lowestpair = (i, j)
# 将最近的 clusters 两两合并，这里使用平均值
mergevec = [(clust[lowestpair[0]].vec[i] + clust[lowestpair[1]].vec[i])
/ 2.0 for i in range(len(clust[0].vec))]
# 创建一个新的 cluster
newcluster = bicluster(mergevec, left=clust[lowestpair[0]],
right=clust[lowestpair[1]], distance=closest,
id=currentclustid)
# 创建出来的 cluster，使用负数来记录，-1，-2，-3 这样的
currentclustid -= 1
# 从原始集中删除 merge 这2个
del clust[lowestpair[1]]
del clust[lowestpair[0]]
# 将新的 cluster 添加到 clust 中
clust.append(newcluster)
return clust[0]
这个过程比较慢，第一轮是 NN，第二轮就是 (N-1)(N-1) 这样一直计算到 1 为止，因此是 O(NNN) 的时间复杂度，比较慢。
Column Clustering 列聚合 #
上面的操作是针对行来说的（博文），如果希望对列（关键字）就可以通过旋转矩阵，再计算的方式获得答案。
def rotatematrix(data):
newdata = []
for i in range(len(data[0])):
newrow = [data[j][i] for j in range(len(data))]
newdata.append(newrow)
return newdata
K-Means Clustering K-均值聚合 #
分类聚合的算法复杂度相当的高 O(nnn) ，还有一种算法，预先设定 K 个聚类数量，算法调整聚类大小。
K-Mean 的算法先确定 K 个中心位置，然后把数据分配给最近的中心位置，然后重新计算中心位置。这时候中心位置变化了，然后再重复这个过程，直到中心位置不再变化。
流程如下
def kcluster(rows, distance=pearson, k=4):
# 确定数据集中的最大值和最小值
ranges = [(min([row[i] for row in rows]), max([row[i] for row in rows]))
for i in range(len(rows[0]))]
# 创建 K 个随机点
clusters = [[random.random() * (ranges[i][1] - ranges[i][0]) + ranges[i][0]
for i in range(len(rows[0]))] for j in range(k)]
lastmatches = None
# 最多迭代 100 次
for t in range(100):
print 'Iteration %d' % t
bestmatches = [[] for i in range(k)]
# 找每一行最近的那个中心点
for j in range(len(rows)):
row = rows[j]
bestmatch = 0
# 每一行都和中心点进行计算
for i in range(k):
d = distance(clusters[i], row)
# 如果比 best 那行要小，就更新
if d < distance(clusters[bestmatch], row):
bestmatch = i
bestmatches[bestmatch].append(j)
# 如果没有产生变化，就结束
if bestmatches == lastmatches:
break
lastmatches = bestmatches
# 移动中心点
for i in range(k):
avgs = [0.0] * len(rows[0])
if len(bestmatches[i]) > 0:
for rowid in bestmatches[i]:
for m in range(len(rows[rowid])):
avgs[m] += rows[rowid][m]
for j in range(len(avgs)):
avgs[j] /= len(bestmatches[i])
clusters[i] = avgs
return bestmatches
二维展示 #
上面通过树来聚合，但是不是很直观，如果我们希望把所有的东西都放在一个二维图上，那么我们肯定希望越接近的地方就关联度越高。书中就提及了一个 多维缩放 的技术
一开始将节点随机的放在二维平面上
然后计算出当前各个节点之间的位置
然后调整位置，比如 C 当前距离A 太远了，就拉近，B 就远离
def scaledown(data, distance=pearson, rate=0.01):
n = len(data)
# 计算出各个节点之间的距离
realdist = [[distance(data[i], data[j]) for j in range(n)] for i in
range(0, n)]
# 随机出 N 个点
loc = [[random.random(), random.random()] for i in range(n)]
fakedist = [[0.0 for j in range(n)] for i in range(n)]
lasterror = None
for m in range(0, 1000):
# 算出现在的距离
for i in range(n):
for j in range(n):
fakedist[i][j] = sqrt(sum([pow(loc[i][x] - loc[j][x], 2)
for x in range(len(loc[i]))]))
# 移动的点
grad = [[0.0, 0.0] for i in range(n)]
totalerror = 0
for k in range(n):
for j in range(n):
if j == k:
continue
# 现在的距离 - 真实的距离，然后处于真是距离，就是一个偏差的比例
errorterm = (fakedist[j][k] - realdist[j][k]) / realdist[j][k]
# 按比例移动点，拉近，或者远离
grad[k][0] += (loc[k][0] - loc[j][0]) / fakedist[j][k] \
* errorterm
grad[k][1] += (loc[k][1] - loc[j][1]) / fakedist[j][k] \
* errorterm
# 记录一下总的偏差比例
totalerror += abs(errorterm)
print totalerror
# 如果这次的 totalerror 比上次还大，说明已经优化到头了，就结束了
if lasterror and lasterror < totalerror:
break
lasterror = totalerror
# 按照 rate 参数调整，上面的 grade 记录的是一个绝对的值，但是因为偏移太大会导致不稳定，应该小步的移动
for k in range(n):
loc[k][0] -= rate * grad[k][0]
loc[k][1] -= rate * grad[k][1]
return loc
其他 #
def pearson(v1, v2):
# Simple sums
sum1 = sum(v1)
sum2 = sum(v2)
# Sums of the squares
sum1Sq = sum([pow(v, 2) for v in v1])
sum2Sq = sum([pow(v, 2) for v in v2])
# Sum of the products
pSum = sum([v1[i] * v2[i] for i in range(len(v1))])
# Calculate r (Pearson score)
num = pSum - sum1 * sum2 / len(v1)
den = sqrt((sum1Sq - pow(sum1, 2) / len(v1)) * (sum2Sq - pow(sum2, 2) / len(v1)))
if den == 0:
return 0
return 1.0 - num / den