再看数据库系统概念

Posted on 2017-03-16 | In SQL

E-R

实体集：同类同性质实体
联系集：同类联系集合
属性／实体：强关联属性，弱关联单独出实体
超码：一个或多个属性集，唯一标识一个实体
候选码：任何真子集不为超码，即最小超码

###　实体联系图

矩形：实体
椭圆：属性
菱形：联系
双椭圆：多值属性
虚椭圆：派生属性
弱实体集：属性不足以形成主码，依赖于强实体集
特殊化：实体集内部分组
概括：高层实体集包含底层实体集
概括／特殊化
- 高层属性和联系适用于底层
- 底层特有属性只限自身
  E-R转表
实体集直接转表
弱实体集表加入依赖强实体集主码
联系集：联系实体主键　＋　联系属性
多值属相创建新表

关系模型

选择：元组
投影：属性
并／差
- 关系同元：属性数目相同
- 对应属性域相同
交
自然链接：笛卡尔积，童淑星相等性选择，去重
广义投影：投影之后算数扩展
外链接：链接之后扩展缺失信息

视图定义时之存储定义本身，每次查询都会重新计算

SQL
SELECT　投影

FROM 笛卡尔积
WHERE 谓词运算
1
2
3
4
5
6
SELECT [distinct] A1,A2,A3....
FROM r1,r2 ,r3.....
WHERE P
ORDER by  [asc/desc]
GROUP by 
HAVING

LIKE
- %:任意字串
- _ :任意字符
集合操作: UNION [ALL]/ INTERSECT/ EXCEPT
聚集函数：　avg/sum/max/min/count
测试子元组集是否为空：exist/not exist
测试子查询是否含重：unique/not unique
视图：create v as

删除

1
2
3

DELETE FROM account
WHERE balance < (SELECT AVG(balance)
                    FROM account)

插入

1 2	INSERT INTO account(name1, name2, name3) VALUES("v1", "v2", "v3")

更新

UPDATE acount
SET balance  = balance * 1.5
WHERE balance > SELECT ARG(balance)
                        FROM account

完整性约束

参照完整性
- 联系集参照完整性：依赖于各实体集主码
- 弱实体集参照完整性：依赖于强实体集主码
外键参照级联

正则覆盖：关系模式上函数依赖集Ｆ，在该关系上做任何更新时，必须保证Ｆ中所有函数依赖在新数据库下满足，否则回滚该更新操作
Ｆ的正则依赖集Fc:
包含Ｆ中全部依赖关系
函数依赖的左半部唯一

模式分解

子关系连接合并后投影可得原关系则为无损分解（分解不引起记录增加）
保持依赖：分解后依赖集蕴含全部原依赖集依赖关系
BDNF：具有函数依赖集Ｆ＋的关系模式
Ｆ+中任意a->b 的函数依赖，其中a属于Ｒ且b属于Ｒ，以下至少一个成立
- a->b 为平凡函数依赖（b 为a 的子集）
- a是模式超码
BCNF不一定保持依赖
3NF：具有函数依赖集Ｆ＋的关系模式
Ｆ+中任意a->b 的函数依赖，其中a属于Ｒ且b属于Ｒ，以下至少一个成立
- a->b 为平凡函数依赖（b 为a 的子集）
- a是模式超码
- b-a 中每个属性Ａ都包含在Ｒ的候选码中
  3NF无损且保持依赖
  不存在非主属性对主码的传递依赖
多值依赖？
连接依赖？

储存结构文件结构（数据库系统实现）

索引

按搜索码顺序存储，搜索码对应索引为主索引
稠密索引：每个搜索码值有一个索引记录
稀疏索引：搜索码值　＋　搜索码值指向具有该搜索码值的第一个数据项

稀疏索引空间小，易维护，开销小，稀疏索引放入主存，查找迅速

B+树索引

每个节点最多包含　n-1个搜索码值和ｎ个子节点指针
B+树非叶节点形成叶节点的多级稀疏索引，叶节点顺序链接
B+树为平衡树，根到任一叶子节点路径长度相同，非叶节点只起索引作用
B树搜索码只出现一次，增加一个指向文件的指针，即非叶节点不仅是索引作用，也指向具体记录或者文件
B树中查询一次访问节点数取决于节点位置，找到即停止，B+树必须找到叶节点才能确定记录位置
散列索引
- 闭散列：增加溢出桶
- 开散列：线性搜索（删除比较麻烦）
动态索引？

网格索引和分段散列适用于多属性查询

1 2	CREATE [UNIQUE]INDEX <index-name> ON <realtion-name> (<attribute-list>) DROP INDEX <index-name>

查询处理

选择运算

A1：线性搜索，平均代价Br/2，最坏情况Br
A2: 二分搜索，属性有序，代价[logBr]
索引选择
A3: (主索引，码属性等值比较)可以检索到唯一一条满足条件的记录，代价：B+树树高加上读取一条记录I/O代价
A4: (主索引，非码属性等值比较)主索引可以检索到多条满足条件的记录，且多条记录顺序存储，代价：B+树树高加上具有搜索码值的盘块数
A5: (辅助索引，等值比较)索引字段为码属性直接得到一条记录．索引字段为非码属性，得到多条记录
比较选择
A6: (主索引，比较)B+树有序主索引
A7: (辅助索引，比较)有序辅助索引，小值从小段开始，大值从　大端开始
比较选择
A8: 索引合取（取交）先现则满足一个条件的记录，加入缓冲区，在缓冲区中验证其他条件
A9: (组合所用合取)直接利用合适的符合索引查询
A10: (记录标识符的交)每个条件遍历标记一边，取所有被标记的交际
A11: (记录标识符的并）逐一扫描索引获取满足单个条件的元祖指针，将所有指针集做并集

连接运算

嵌套循环（重名属性会出现）
块嵌套循环，每次在块内循环嵌套检查元组匹配，有效减少比较次数
索引嵌套循环连接：嵌套循环连接的内层如果有索引，使用索引代替循环
归并链接：用于自然链接和等值连接
- 双有序直接有序归并
- 单有序，归并后，对索引项进行按地址排序，可实现有序
消除重复: 代价高，明确声明是否去重
- 归并/散列可直接在过程中消除重复
集合
- 并集：　Hr建立散列索引，将Hs中元组加入到上诉散列索引中，条件是该元组不在散列索引中，散列索引最终即结果
- 交集：　Hr建立散列索引，对Hs中元组探查散列索引，出现在散列索引的记录放入结果
- 差集：　Hr建立散列索引，对Hs中元组探查散列索引，出现在散列索引的记录从索引中删除

外连接

计算连接法：
左外连接：计算链接，将左集未参与链接集合扩展放入结果
右外连接：计算链接，将右集未参与链接集合扩展放入结果
全外连接：计算链接，将左右集未参与链接集合扩展放入结果
- 嵌套修改法
  - 左外连接：左边外循环，右表内循环，内外匹配加入结果，内部均不匹配的外记录也加入结果
  - 右外连接：右边外循环，左表内循环，内外匹配加入结果，内部均不匹配的外记录也加入结果
- 扩展归并连接获得自然链接和等值全外联
  - 归并完成，将不与另一关系任一记录匹配的记录加入结果
    启发优化
合取选择分解为单个选择
选择运算下推到最早执行位置
选择与链接合并求取最小元组数关系
选择加笛卡尔积替换成链接
投影分解下移

事务

事务性质：原子性，一致性，隔离性，持久性
原子性：事务未完成则回复原值
- db-pointer 指向影子副本，更新完成时指向影子副本
持久性：
- 事务更细在事务完成前已写入磁盘
- 事务执行的更新和已写更新信息充分，故障时可重新构造数据库
交换非冲突指令得出冲突等价，等价与串行执行时，即为冲突可串行化
两个视图中读取的值来源形同，写进的值来源相同，即试图等价
每个冲突可串行化都是视图可串行化的，但存在非冲突可串行化视图可以串行化调度
冲突可串行化判定：构造无环优先图（拓扑排序）
并发
锁授予

不存在冲突锁
两阶段锁
- 增长阶段：只加锁，不释放
- 缩减阶段：可释放，不申请新锁
  
  两阶段封锁不能保证避免死锁
严格两阶段事务锁：事务持有的排它锁必须在事务提交后才能释放
强两阶段事务锁：事务提交前不释放任何锁
树协议
- 首次加锁直接执行
- 之后加锁前提是必须先获得父项的锁
- 解锁随时可以进行
- 一个数据项加锁解锁后不能再加锁（只可加锁解锁一次）
  
  树协议保证冲突可串行化，保证避免死锁
时间戳
每个数据项Ｑ维持两个时间戳关联数据
- 成功执行写操作最大时间Wtimestap
- 成功执行读操作最大时间Rtimestap

事务Ti发出read(Q)操作
- TS(Ti) < Wtimestap，　Ti 需要读入的Q值已经被覆盖，read 操作被拒绝，Ti回滚
- TS(Ti) >= Wtimestap，执行read操作，Rtimestap更新为　max(Rtimestap,TS(Ti))
事务Ti发出write(Q)操作
- TS(Ti) < Rtimestap，　Ti 产生的Q值先前被覆盖，write操作被拒绝
- TS(Ti) < Wtimestap， Ti 想写入Q值过时，Ti 拒绝，回滚
- 其他执行write,　Wtimestap设为TS(Ti)
  死锁预防
事务开始前封锁它的全部数据项
抢占与事务回滚
- wait-die机制非抢占：老事务等待新事务释放数据项
- wound-die机制抢占：老事务不等待新事物
锁超时：事务等待锁超时自动回滚
幻象冲突：两事务就数据项是否存在产生不一致
- 解决：在关系上加锁，插入数据项的事务需要排它锁，将和其他事务在以存在数据项上冲突
- 问题：两个插入事务将冲突，并发程度降低
有效性检查

事务读入局部变量并修改，然后进行有效性检查，有效时写入数据库

恢复

undo日志：事务更新的数据行回复为旧值
redo日志：事务更新的数据项更新为新值
事务Ti需要undo, 如果日志记录包含,但不包含
事务Ti需要redo, 如果日志记录包含, 又包含
从后向前扫描遇到第一个
主存日志记录输出到稳定存储器上
所有修改了的缓冲块输出到磁盘

将日志记录输出到稳定存储器

重启动回复

崩溃回复时：构造undo-list和redo-list事务

- 从后向前扫描日志，直到发现第一个<checkpoint>
- 对每一个形如<Ti commit>, 将Ti加入redo-list
- 对每一个形如<Ti start>, 如果Ti不属于redo-list ,Ti 加入undo-list
- 构造完成后，从后向前重新扫描日志，执行undo-list记录undo操作
- 找出最后一个cjeckpoint,从前向后扫描执行redo-list中的redo事务

FLAG

立下FLAG,已经看到15章，后几章一定要看的涉及数据库体系结构、分布式数据库、高级查询、授权

decision tree

Posted on 2017-03-12 | In ML

Project Address:

https://github.com/TheOneAC/ML.git

dataset in ML/ML_ation/tree

###　决策树

计算复杂度低，中间值缺失不敏感，可理解不相关数据

可能过度匹配（过度分类）

适用：数值型和标称型

决策树伪代码createbranch

检测数据集中子项是否全部属于一类
    if so return class_tag
    else 寻找数据集最佳划分特征
            划分数据集
            创建分支节点
            对每一个子集，递归调用createbranch
        返回分支节点

递归结束条件：所有属性遍历完，或者数据集属于同一分类

香农熵

def calcShannonEnt(dataSet):
	numEntries = len(dataSet)
	labelCounts = {}
	for featVec in dataSet:
		currentLabel = featVec[-1]
		if currentLabel not in labelCounts.keys():
			labelCounts[currentLabel] = 0
		labelCounts[currentLabel] += 1
	shannonEnt = 0.0
	for key in labelCounts:
		prob = float(labelCounts[key])/numEntries
		shannonEnt -= prob * log(prob,2)
	return shannonEnt

数据及划分与最优选择（熵最小）

def splitDataSet(dataSet, axis, value):
	retDataSet = []
	for featVec in dataSet:
		if featVec[axis] == value:
			reduceFeatVec = featVec[:axis]
			reduceFeatVec.extend(featVec[axis + 1:])
			retDataSet.append(reduceFeatVec)
	return retDataSet
def chooseBestFeatureToSplit(dataSet):
	numFeatures = len(dataSet[0])- 1
	baseEntropy = calcShannonEnt(dataSet)
	bestInfoGain = 0.0
	bestFeature = -1
	for i in range(numFeatures):
		featList = [example[i] for example in dataSet]
		uniqueVals = set(featList)
		newEntropy = 0.0
		for value in uniqueVals:
			subDataSet = splitDataSet(dataSet, i, value)
			prob = len(subDataSet)/float(len(dataSet))
			newEntropy += prob * calcShannonEnt(subDataSet)
		infoGain = baseEntropy - newEntropy
		if infoGain > bestInfoGain:
			baseInfoGain = infoGain
			bestFeature = i
	return bestFeature

所有标签用尽无法确定类标签时：　多数表决决定子叶分类


def majorityCnt(classList):
	classCount = {}
	for vote in classList:
		if vote not in classCount.keys(): classCount[vote] = 0
		classCount[vote] += 1
	sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse = True)
	return sortedClassCount[0][0]

创建树


def createTree(dataSet, labels):
	classList = [example[-1] for example in dataSet]
	if classList.count(classList[0]) == len(classList):
		return classList[0]
	if len(dataSet[0]) == 1:
		return majorityCnt(classList)
	
	bestFeat = chooseBestFeatureToSplit(dataSet)
	bestFeatureLabel = labels[bestFeat]
	myTree = {bestFeatureLabel:{}}
	del(labels[bestFeat])
	featValues = [example[bestFeat] for example in dataSet]
	uniqueVals = set(featValues)
	for value in uniqueVals:
		subLabels = labels[:]
		myTree[bestFeatureLabel][value] = createTree(splitDataSet(dataSet, bestFeat,value), subLabels)
	return myTree

测试

def classify(inputTree,featLabels,testVec):
	firstStr = inputTree.keys()[0]
	secondDict = inputTree[firstStr]
	featIndex = featLabels.index(firstStr)
	for key in secondDict.keys():
		if testVec[featIndex] == key:
			if type(secondDict[key]).__name__=='dict':
				classLabel = classify(secondDict[key],featLabels,testVec)
			else:
				classLabel = secondDict[key]
	return classLabel

>>> import trees
>>> myDat,labels=trees.createDataSet()
>>> labels
['no surfacing', 'flippers']
>>> myTree=treePlotter.retrieveTree (0)
>>> myTree
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
>>> trees.classify(myTree,labels,[1,0])
'no'
>>> trees.classify(myTree,labels,[1,1])
'yes'

###　存储与重载

def storeTree(inputTree, filename):
	import pickle
	fw = open(filename, 'w')
	pickle.dump(inputTree,fw)
	fw.close()
def grabTree(filename):
	import pickle
	fr = open(filename)
	return pickle.load(fr)

###　test

#!/usr/bin/python
import trees
myDat,labels = trees.createDataSet()
myTree = trees.createTree(myDat, labels)
trees.storeTree(myTree,'classifierStorage.txt')
print(trees.grabTree('classifierStorage.txt'))

图形化显示树结构

#!/usr/bin/python
import matplotlib.pyplot as plt 
decisionNode = dict(boxstyle = "sawtooth", fc = "0.8")
leafNode = dict(boxstyle = "round4", fc = "0.8")
arrow_args = dict(arrowstyle = "<-")
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
	createPlot.ax1.annotate(nodeTxt, xy = parentPt, xycoords = "axes fraction",
	xytext = centerPt, textcoords = "axes fraction",
	va = "center", ha = "center", bbox = nodeType, arrowprops = arrow_args)

创建节点

def createPlot():
	fig = plt.figure(1, facecolor = "white")
	fig.clf()
	createPlot.ax1 = plt.subplot(111, frameon = False)
	plotNode("a decision node",(0.5, 0.1), (0.1, 0.5), decisionNode)
	plotNode("a leaf node",(0.8, 0.1), (0.3, 0.8), leafNode)
	plt.show()

python command line run command as this
1
2
import treeplotter
treePlotter.createPlot()

result like this
图片标题

def getNumLeafs(myTree):
	numLeafs = 0
	firstStr = myTree.keys()[0]
	secondDict = myTree[firstStr]
	for key in secondDict.keys():
		if type(secondDict[key]).__name__ == 'dict':
			numLeafs += getNumleafs(secondDict[key])
		else: numLeafs +=1
	return numLeafs
def getTreeDepth(myTree):
	maxDepth = 0
	firstStr = myTree.keys()[0]
	secondDict = myTree[firstStr]
	for key in secondDict.keys():
		if type(secondDict[key]).__name__ == 'dict':
			thisDepth = 1+ getTreeDepth(secondDict[key])
		else:
			thisDepth = 1
		if thisDepth > maxDepth: maxDepth = thisDepth
	return maxDepth
def retrieveTree(i):
	listOfTrees =[{'no surfacing': {0: 'no', 1: {'flippers': \
		{0: 'no', 1: 'yes'}}}},
		{'no surfacing': {0: 'no', 1: {'flippers': \
		{0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}}
		]
	return listOfTrees[i]
def plotMidText(cntrPt, parentPt, txtString):
	xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]
	yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
	createPlot.ax1.text(xMid, yMid, txtString)
	
def plotTree(myTree, parentPt, nodeTxt):
	numLeafs = getNumLeafs(myTree)
	
	depth = getTreeDepth(myTree)
	
	firstStr = myTree.keys()[0]
	cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW,\
			plotTree.yOff)
	plotMidText(cntrPt, parentPt, nodeTxt)
	
	plotNode(firstStr, cntrPt, parentPt, decisionNode)
	
	secondDict = myTree[firstStr]
	plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
	
	for key in secondDict.keys():
		if type(secondDict[key]).__name__=='dict':
			plotTree(secondDict[key],cntrPt,str(key))
		else:
			plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
			plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff),
			cntrPt, leafNode)
			plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
	plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
	
def createPlot(inTree):
	fig = plt.figure(1, facecolor='white')
	fig.clf()
	axprops = dict(xticks=[], yticks=[])
	createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
	plotTree.totalW = float(getNumLeafs(inTree))
	plotTree.totalD = float(getTreeDepth(inTree))
	plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;
	plotTree(inTree, (0.5,1.0), '')
	plt.show()

扩展测试 lens.py

1 2	Project Address: ` https://github.com/TheOneAC/ML.git` dataset: `lens.txt in ML/ML_ation/tree`

#!/usr/bin/python
import trees
import treePlotter
fr = open("lenses.txt")
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
lensesLabels=['age', 'prescript', 'astigmatic', 'tearRate']
lensesTree = trees.createTree(lenses,lensesLabels)
print(lensesTree)
treePlotter.createPlot(lensesTree)

k-means

Posted on 2017-03-12 | In ML

Project Address:

https://github.com/TheOneAC/ML.git

dataset in ML/ML_ation/knn

K近邻算法

优点：精度高、异常不敏感、无数据输入假定

缺点：计算复杂度高、空间复杂度高

适用数据：数值型、标称型

选择ｋ个最相似数据中次数出现最多的分类，作为新数据的分类

k-means 伪码

计算当前点与已知分类点距离

按距离递增排序，选取最近的前Ｋ个

确定前ｋ个点所在类别的出现频率

返回出现最高的频率最为当前点的分类返回

python code

def classify0(inX, dataSet,labels, k):
	dataSetSize = dataSet.shape[0]
	#print(dataSetSize)
	diffMat = tile(inX, (dataSetSize,1)) - dataSet
	#print(diffMat)
	sqDiffMat = diffMat ** 2
	sqDistance = sqDiffMat.sum(axis = 1)
	#print(sqDistance)
	distance = sqDistance ** 0.5
	sortedDistanceIndices = distance.argsort()
	#print (sortedDistanceIndices)
	classCount = {}
	for i  in range(k):
		voteIlabel = labels[sortedDistanceIndices[i]]
		classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
	sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1),
	reverse = True)
	#print(sortedClassCount)
	return sortedClassCount[0][0]

def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector

使用第二列和第三列数据形成散点图

import knn
group, labels = knn.creatdataset()
#print( knn.classify0([0,0],group,labels, 3) )
datingDatMat, datinglabels = knn.file2matrix('datingTestSet2.txt')
import matplotlib
import matplotlib.pyplot as plt 
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDatMat[:,1], datingDatMat[:,2])
plt.show()

./test.py

修改，加入颜色

1
2
3

#ax.scatter(datingDatMat[:,1], datingDatMat[:,2])
->>>>> 
ax.scatter(datingDatMat[:,1], datingDatMat[:,2],15.0 *array(datinglabels), 15.0 *array(datinglabels))

修改坐标参考，改为使用第一列和第二列数据

1
2
3

#ax.scatter(datingDatMat[:,1], datingDatMat[:,2],15.0 *array(datinglabels), 15.0 *array(datinglabels))
->>>>>>>
ax.scatter(datingDatMat[:,0], datingDatMat[:,1],15.0 *array(datinglabels), 15.0 *array(datinglabels))

数值归一化

newValue = (oldValue - min)/(max - min)


def autoNorm(dataSet):
	minVals = dataSet.min(0)
	maxVals = dataSet.max(0)
	ranges = maxVals - minVals
	normDataSet = zeros(shape(dataSet))
	m = dataSet.shape[0]
	normDataSet = dataSet - tile(minVals,(m,1))
	normDataSet = normDataSet/tile(ranges,(m,1))
	return normDataSet,ranges, minVals
def datingClassTest():
	hoRatio = 0.05
	datingDatMat, datinglabels = file2matrix('datingTestSet2.txt')
	normSet,ranges, minVals = autoNorm(datingDatMat)
	m = normSet.shape[0]
	numTestVecs = int(m* hoRatio)
	errorCount = 0
	for i in range(numTestVecs):
		classifierResult = classify0(normSet[i,:],normSet[numTestVecs:m,:],datinglabels[numTestVecs:m],3)
		print "the classifier came back with: %d , the real answer is: %d" % (classifierResult, datinglabels[i])
		if(classifierResult != datinglabels[i]): errorCount += 1.0
	print "the total error rate is %f " % (errorCount/float(numTestVecs))

knn.datingClassTest()

手写字符识别

def img2vector(filename):
    returnVect = zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect
from os import listdir 
def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')           #load the training set
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('testDigits')        #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr)
        if (classifierResult != classNumStr): errorCount += 1.0
    print "\nthe total number of errors is: %d" % errorCount
    print "\nthe total error rate is: %f" % (errorCount/float(mTest))

./test.py

#!/usr/bin/python
from numpy import *
import operator
knn.handwritingClassTest()

unp socket/select/poll

Posted on 2017-01-23

在多进程的并发服务器中，接受连接后fork子进程，让子进程处理连接请求，主进程继续等待连接，子进程关闭链接等待接口，主进程关闭已经连接的接口（socket）
阻塞的发生
- 等待处理：等待接受，等待处理结果，等待（某种信号或者信息）
阻塞的函数或者操作被中断后必须考虑，系统是自动重启还是手动重启，手动重启的话可以将函数放入循环实现自动重启
fork之后必须捕获SIGCHLD信号，保证fork出的子进程完成后，被父进程回收资源
父进程捕获SIGCHLD信号时，可能中断当前阻塞的系统调用，应该或者最好考虑系统调用被中断的情况。
SIGCHLD处理函数最好使用waitpid 针对固定pid回收等待，防止僵尸子进程存在
wait函数收到一个子进程结束信号即执行并结束，其他子进程就会变成僵尸进程
connect 函数对应TCP三次握手：即在connect函数之后完成TCP的三次握手
阻塞的问题：一旦一端下线，另一端会一直阻塞在响应操作处，即使一端不掉线也可能使得另一端一直处于等待状态，浪费资源，更不要高并发场景了

select/poll

IO复用：一个服务器程序处理超过一个接口（连接，服务，协议等），需要IO复用
非阻塞IO，不等待内核处理结果，在不能满足请求时当前操作不睡眠等待结果，而是直接返回错误
IO复用
- select 监视不止一个描述符，当某个描述符可用时，即唤醒当前描述符的响应操作，即让一个select函数监视多个端口的等待情况
- 多线程IO模型，每个线程调用一个阻塞IO函数监视一个描述符
信号驱动IO
- 不再依赖等待，而是靠信号通知原本需要等待的函数启动
异步IO：相比于信号驱动，异步IO直接通知的操作结果，而信号驱动通知的是可操作
一图胜千言
close 与shutdown 的qubie
- close 减少描述符计数，当减为0时，直接关闭描述符
- shutdown 不减少描述符，但正常激发结束系列即发出FIN信号，单向终止

STL source code twice

Posted on 2017-01-18 | In c++

组件关系
- container 通过容器allocator 获得数据空间
- Algorithm 通过迭代器存取container 内容
- functor 协助 Algorithm 完成不同的策略变化
- Adaapter 可以修饰或者套接functor
  内存分配
STL的allocate类基本是 new 和 delete 的简单包装
new 操作包含 operator new 配置内存和对象初始化
delete 操作包含对象析构和 operator delete 释放内存
STL的二级内存分配机制
次级空间配置实现方式：
- 多级链表实现内存池，从8 ~ 128 字节不等，且以8字节对齐的链表节点，形成16个链表
内存处理基本函数：判断是否会POD，POD直接复制或者填充，non- POD则构造填充

迭代器与traits技法

迭代器主要内容是：dereference 和 member access，核心是对 operator * 和operator -> 重载
原生指针没有能力定义自己的型别，class-type iterators 都有能力且应该定义自己的相应型别
iterator_traits 必须对传入的pointer 和 pointer to const 设计特化版本
traits 技法：利用标签和c++重载机制，实现自动调用相应高效算法版本

序列容器

vector

存储空间连续，空间不足时扩充，复制，清理原空间
内存不足时，空间加倍
连续空间，原生指针可以作为迭代器
插入操作引起空间再分配，将使得迭代器失效
三个标签实现空间管理： start finish end_of_storage
vector 动态本质：空间不足时，申请大空间，将原空间元素复制到新空间，释放原空间（新空间配置导致迭代器失效）

list

插入删除复杂度简单，空间不连续，指针连接，本质是双向循环链表
移动增删基于指针操作
不能直接使用STL的sort算法，因为其迭代器不是random access iterater

deque

双向开口连续空间，双端可增删操作
deque 不存在容量概念，动态非配空间，排序则是先转存成vector，用STL排序后，存回deque
deque 首位定量申请新空间维持整体连续
deque 使用map维护分段，分段空间实现整体连续，迭代器检查缓冲区边界确定下一位置从而实现连续
插入和删除主要工作在缓冲区边界检查和元素跨区移动
stack：配接器，底层以连续空间或者链表实现，无迭代器
queue：封装deque，不可遍历，无迭代器
heap
底层连续空间(array,vector)实现
尾部插入，上调至根节点；删除时将根节点置于尾部，上移原尾节点后缩小空间

关联容器

底层封装rb_tree 实现set和map，根据是否允许键值重复衍生multiset和multimap
hashtable： buckets 以质数个节点指针的vector实现，每个vector元素为一个list头，维持一个链表
基于hashtable实现hashset和hashmap元素无序，转调hashtable操作即可实现
hashtable 实现：桶质数个，保证填充率保证小于0.5，SGI STL桶内开链存储

仿函数

仿函数型别主要用来表现函数参数型别和回传值型别
仿函数对象或者无名临时对象用来履行函数功能

Neural-Networks-Programming-comments

Posted on 2017-01-05 | In ML

学习总结

感知机学习算法

误分类驱动：通过错误点修正权值和偏置
梯度：损失函数对参数的导数
梯度下降：误差函数求最小值的修正过程，在梯度方向上函数变化最大，通过梯度方向探索求取损失函数最小值
学习率: 误分类点每次修正权值和偏差的程度，即误分类点的权值更新的改变程度
随机梯度下降之随机：误分类点中随机选择一个错误点修正权值和偏差参数，求出该点的梯度向量，然后以负梯度方向为搜索方向，以一定的步长学习率进行搜索，从而确定下一个迭代点。持续迭代到收敛
收敛 ：误分类次数小于允许错误门限值（上界）

感知机模型（激活函数）

其中x1, x2为输入，ｗ为权值（即输入对输出的影响程度），ｂ为偏差，整个神经元（感知机）输出为ｙ，　
函数ｆ可以认为是神经元输出表达式，在神经网络中被命名为激活函数

常见的激活函数及其特征
- Sigmoid（S 型激活函数）
  - 特征：输入一个实值，输出一个 0 至 1 间的值
  - 表达式：σ(x) = 1 / (1 + exp(−x))
- tanh（双曲正切函数）
  - 特征：输入一个实值，输出一个 [-1,1] 间的值
  - 表达式：　tanh(x) = 2σ(2x) − 1
- ReLU
  - 特征：输出一个实值，并设定 0 的阈值（函数会将负值变为零）
  - 表达式：f(x) = max(0, x)
基本激活函数函数图像
激活函数的直观作用：对神经元多输入的结果进行函数化处理，按照一定映射规则获得输出（本质：函数映射）
- 激活函数的作用参考

神经网络与反向传播

前向传播过程
- 根据激活函数迭代计算下一层神经元状态
反向传播过程
- 根据偏差反向修正上一层节点的权值，修正方法为链式求导
- 反向传播和权重更新：计算输出节点的总误差，并将误差用反向传播算法传播回网络计算梯度。
- 使用类似梯度下降之类的算法来「调整」网络节点的权重，以减少输出层的误差。
  反向传播参考
   反向传播参考
  神经网络学习算法基本概念
  损失函数
损失函数在数据集上的得到的损失值越小，模型的学习效果就越好，误差越小
经验损失
在训练数据足够大时经验损失接近期望损失，学习算法的目标是选择期望损失最小的参数模型
结构损失
结构风险（结构损失）在经验损失最小化基础上加入调整参数，实现正则化
训练误差：训练数据集的平均损失
测试误差：测试数据集的平均损失
过拟合：模型过度过度学习，太贴近训练数据集的特征，但不能准确反映整体数据的一般特征
- 即：训练误差小，但是测试误差明显大于训练误差
结构风险最小化：加入正则影响因子，避免过度靠近训练数据
交叉验证
- 简单交叉验证：数据集一部分用于训练，一部分用于测试，选择测试误差最小模型
- S折交叉验证：数据集分为s个独立子集，利用S-1个数据集训练，剩余一个做测试，对选择S中选择数据集训练，选择平均测试误差最小模型
- 留一交叉验证：选择一个数据作为测试，适用于数据不足情况
  算法分析
ws: weight 矩阵随机初始化　tf.Variable(tf.random_normal([in_size,out_size]))
bs: bias 偏差矩阵随机化,全部置为０.5 tf.Variable(tf.zeros([1,out_size])+0.5)
wxpb : 节点状态计算　tf.matmul(inputs,Ws) + bs
每层激活函数sigmoid传入
均方误差学习速率
交叉熵学习速率
交叉熵与均方差的比较

交叉熵参考说明

根据误差方向学习修正参数，交叉熵最小化保证学习速率稳定，避免一般激活函数导致的学习趋近于０的情况

朴素贝叶斯

支持向量机

线性可分
支持向量
函数间隔
几何间隔：w为L2 范数（多维空间距离）
线性可分：使用几何间隔最大化：分离点到分离平面距离之和最大
线性不可分：软间隔最大化，误分距离最小化
核方法：多维空间转化

决策树

决策方法：在任一节点选择条件概率作为特征空间的一个划分，任一节点做二分类将条件概率大的归为一类
每个层级节点选择最有特征，基于该特征分割数据集，直到数据集全部被分到一个确定叶节点（即一个类）
当叶节点划分过细时（过拟合）需要剪枝，将叶子分类归结到父节点，合并唯一类
特征选择
- 熵
- 条件熵
- 信息增益
- 信息增益比
ID3算法：从根节点开始选择信息增益醉的特征作为节点分割的特征
C45算法：用信息增益比选择节点分裂特征
CART算法：每个节点二分类，利用平方误差最小化尽可能生产复杂的决策树，然后通过最小化损失值向上回缩，两颗子树的损失之和大于归并到父节点之后的损失值
基尼指数
基尼系数表明集合在特征A上分类不确定性，系数越大表明数据集的分类弹性变化越大，稳定性越差

项目地址

戳here

A1手写字符识别

学习验证原理

运行环境

# 安装numpy,
sudo apt-get install python-numpy # http://www.numpy.org/
# 安装opencv
sudo apt-get install python-opencv # http://opencv.org/
##安装OCR和预处理相关依赖
sudo apt-get install tesseract-ocr
sudo pip install pytesseract
sudo apt-get install python-tk
sudo pip install pillow
# 安装Flask框架、mongo
sudo pip install Flask
sudo apt-get install mongodb # 如果找不到可以先sudo apt-get update
sudo service mongodb started
sudo pip install pymongo

运行

1 2	cd BloodTestReportOCR python view.py # upload图像,在浏览器打开http://yourip:8080

核心训练代码

def train(self, training_data_array):
        for data in training_data_array:
            # 前向传播得到结果向量
            y1 = np.dot(np.mat(self.theta1), np.mat(data.y0).T)
            sum1 =  y1 + np.mat(self.input_layer_bias)
            y1 = self.sigmoid(sum1)
            y2 = np.dot(np.array(self.theta2), y1)
            y2 = np.add(y2, self.hidden_layer_bias)
            y2 = self.sigmoid(y2)
            # 后向传播得到误差向量
            actual_vals = [0] * 10 
            actual_vals[data.label] = 1
            output_errors = np.mat(actual_vals).T - np.mat(y2)
            hidden_errors = np.multiply(np.dot(np.mat(self.theta2).T, output_errors), self.sigmoid_prime(sum1))
            # 更新权重矩阵与偏置向量
            self.theta1 += self.LEARNING_RATE * np.dot(np.mat(hidden_errors), np.mat(data.y0))
            self.theta2 += self.LEARNING_RATE * np.dot(np.mat(output_errors), np.mat(y1).T)
            self.hidden_layer_bias += self.LEARNING_RATE * output_errors
            self.input_layer_bias += self.LEARNING_RATE * hidden_errors

运行截图
加载服务器
预测和训练
可视化图示

A23 OCR识别预测

运行环境

# 安装numpy,
sudo apt-get install python-numpy # http://www.numpy.org/
# 安装opencv
sudo apt-get install python-opencv # http://opencv.org/
##安装OCR和预处理相关依赖
sudo apt-get install tesseract-ocr
sudo pip install pytesseract
sudo apt-get install python-tk
sudo pip install pillo
# 安装Flask框架、mongo
sudo pip install Flask
sudo apt-get install mongodb # 如果找不到可以先sudo apt-get update
sudo service mongodb started
sudo pip install pymongo

运行

1 2	cd BloodTestReportOCR python view.py # upload图像,在浏览器打开http://yourip:8080

训练预测核心代码（以tensorflow为例）

def add_layer(inputs,in_size,out_size,n_layer,activation_function=None):
    layer_name='layer%s'%n_layer
    with tf.name_scope('layer'):
        with tf.name_scope('weights'):
            Ws = tf.Variable(tf.random_normal([in_size,out_size]))
            tf.histogram_summary(layer_name+'/weights',Ws)
        with tf.name_scope('baises'):
            bs = tf.Variable(tf.zeros([1,out_size])+0.5)
            tf.histogram_summary(layer_name+'/baises',bs)
        with tf.name_scope('Wx_plus_b'):
            Wxpb = tf.matmul(inputs,Ws) + bs
        if activation_function is None:
            outputs = Wxpb
        else:
            outputs = activation_function(Wxpb)
        tf.histogram_summary(layer_name+'/outputs',outputs)
        return outputs
# 定义占位符
with tf.name_scope('inputs'):
    x = tf.placeholder(tf.float32, shape=[None, 26])
    y_ = tf.placeholder(tf.float32, shape=[None, 2])
#2个隐藏层
l1 = add_layer(tf.reshape(x, [-1, 26]),26,64,n_layer=1,activation_function=tf.nn.relu)
l2 = add_layer(l1,64,512,n_layer=2,activation_function=tf.nn.relu)
# add output layer
y_result = add_layer(l2,512,2,n_layer=3)
# 定义损失函数 交叉熵
with tf.name_scope('loss'):
    cross_entropy = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(y_result, y_))
    tf.scalar_summary('loss',cross_entropy)
# 定义训练op
with tf.name_scope('train'):
    train_step = tf.train.AdamOptimizer(0.0001).minimize(cross_entropy)
# 定义正确预测
# correct_prediction = tf.less_equal(tf.abs(tf.sub(tf.argmax(y_result, 1), tf.argmax(y_, 1))), 5)
correct_prediction = tf.equal(tf.argmax(y_result, 1), tf.argmax(y_, 1))
# 定义正确率
accuracy = tf.reduce_mean(tf.cast(correct_prediction, tf.float32))

中间两层隐藏层，使用relu作为激活函数
学习目标是交叉熵最小化
优化函数时tensorflow自带的AdamOptimizer,一种逻辑回归优化算法在多维空间的变种

运行效果
提交报告单
OCR识别
预测

Summary

学习内容：　

统计学习方法:这书凝练到想做笔记基本等于抄书
Python　基础教程：推荐
numpy and Scipy：Python 玩出花来。。。
tensorflow：　tensorlearn、tensorlaywer可能会更好（傻）
学习心得体会
项目Ａ1学习过程接触到tensorflow,当时认为是一个很成熟的机器学习框架，参考了官网教程和部分博客，意识到机器学习的基础和困境在于数学，所以把学习的重点放在了数学和算法上，算法部分直接看的＜统计学习方法＞，有种大呼过瘾的感觉，通俗易懂深入浅出，基本覆盖机器学习的基本领域，明白了算法的数学本质，为什么能够学习道数据内在规律，之后自己琢磨工具学习了Python 和tensorflow，　可能因为代码基础差吧，一直跟在大神后边跑，看着大神们的代码溜到飞起，明白自己的差距还是代码量的问题，同时页说明我最初的方向或者方法出了点问题，或许直接上代码比绕了大圈去看算法更容易出成果吧，站在前人基础上才能看的更远吧，毕竟源码面前了无秘密嚯嚯。
最大遗憾: talk is cheap, show me the code
感受总结为以下几点：
1. 机器学习所需数学基础主要时：求导、概率、分布，没有想象中对数学要求那么高，少数涉及拉格朗日，马尔科夫的内容边看边学时完全可以的理解的
2. 机器学习本质的时大数据量的统计分析，编程的需求或者要求没有想象中高，更多需要的是对数据本身意义的理解即其所代表的现实意义（可以理解为特征工程）
3. 机器学习适合的人群：　科研－＞码农－＞业务数据分析（发现抽象规律）　
4. 学习算法的本质：
```
- 大规模数据的特征的拟合：即找出从定义域到值域的映射关系，学习目标即：（偏差最小）
```
  　　 - 表象：　映射关系不同，多特征的导致的多维计算量的拟合，偏差标识方式和最小化的方式
  - 数学本质：某种程度上是传统统计规律的现代封装
5. Python、tensorflow 、Keras、tensorlearn、Caffe、tensorlaywer等工具封装底层数学算法，供工程目标研究者使用学习
6. 机器学习、数据挖掘工程师的核心竞争力：　数据代表的现实意义和将要探究的目标之间的联系
7. 正确的学习过程：　数据　和　目标　－＞　找出又用数据（特征）－＞　数据的现实意义（统计目标的意义基础）－＞　数据处理　－> 筛选学习泛化　－＞　隐藏的规律（已知数据域未知数据的联系）

Reference

统计学习方法pdf by 李航
台大机器学习入门ppt by 李宏毅
知乎问答：关于感知机与神经网络

Effective c++ twice

Posted on 2017-01-03 | In C++

static

声明在堆上申请静态存储
对于局部变量，将存储方式改为静态存储
对于全局变量，将连接方式局限在文件内
类中static变量：属于整个类，独立存储，没有this指针
inline
inline 放在函数定义前，定义为内联函数
成员函数在类内定义默认为内联函数
inline 编译器做类型检查
避免函数调用开销
内联函数的每次调用都将复制代码，使得代码膨胀
explicit
强制显示构造,只能用于类内构造函数前，抑制隐式转换构造

内置类型手工初始化，c++不保证内置类型初始化
构造函数最好使用member initialnal list 初始化，尽量不使用赋值
具有多态性质的基类应该声明一个虚析构函数，带有虚函数时，也应该设计一个虚析构函数
在构造和析构函数中不要调用virtual函数，这类调用无法实现下降至derived class
operator= 返回一个reference to *this 以实现连续赋值
保证operator = 自我赋值或者交换时的正确性
copy 函数确保全部元素复制，不仅是对象内部成员变量，也包括其base class 成员
不要尝试用某个copy实现另一个copy函数，将共同即能放入第三个函数中，供copy函数调用即可
将资源封装成类对象，不使用时自动调用析构函数，释放资源。RAII（获得即初始化）

对RAII对象执行复制操作的处理
- 禁止复制：复制操作private
- 底层资源引用计数：tr1：:shared_ptr
- 复制底层资源：深拷贝
- 转移底层资源控制权：pointer 和tr1：：auto_pointer

以独立语句将new返回的指针置入智能指针中，避免在复合语句中执行置入
接口设计应该与内置类型保持一致
- 阻止误用：建立新类型，限制类型操作，束缚对象值，消除客户资源管理责任
不要返回local stack 对象，或者refrence of heap 对象
用non-menber non-firend 函数替换member函数，即通过外函数调用member 函数实现，保证类对象的封装性
重载操作符可以在类内部，也可以在类外部，外部定义重载操作符可以对全部参数隐式转型
降低文件之间的依赖关系
- 在定义文件中，用到的类只做前置声明而不引入头文件定义
- 在实现文件中，include用到的类的头文件
- 引用和指针不需要定义式，声明对象时需要定义式
derived class 将会掩盖同名的base class 函数，使用 using声明或者转交函数（函数内部调用base class 被覆盖的函数）使用base class 被覆盖的函数
接口继承与实现继承
- 声明一个pure virtual函数是为了让derived class 只继承函数接口
- 声明一个impure virtual 函数是为了让derived class 继承函数接口和缺省实现
- 声明一个non-virtual 函数是为了让derived class 继承函数接口和一份强制实现
绝对不重新定义继承来的non-virtual函数
绝对不重新定义继承来的缺省参考值: 缺省值是静态绑定的
应用域复合表示has a，实现域复合表示is implemented in terms of

private 继承意味着只有实现部分被继承，接口部分被忽略
private继承意味着参考实现，当derived class 需要访问基类成员或者重定义继承而来的virtual 函数时，使用private继承
private 继承可以实现empty class 最小化

derived class templates 内部通过 “this->”使用base class templates 内成员，或者使用using 子句表明成员来源

算法导论系列五：高级数据结构

Posted on 2016-12-26 | In CLRS

B树

n节点的B树高度为O(lgn)
- 每个节点:n[x]当前节点内关键字数，
- n[x]个关键字本身，非降序排列；
- leaf[x],x为叶子则为true；
- n[x]+1个子女指针，叶节点指针域为空
- 关键字对子树进行划分分割
- 叶节点具有相同深度，即树高
- 每个节点包含关键字字数有上界，即B树的最小度数t
  - 非根节点至少t-1个节点，t个子女
  - 每个节点至多2t-1关键字，内街店至多2t个节点
n个关键字，高度为h，最小度数为t》=2的B树有：h <= lgt((n+1)/2)
B树操作
- 搜索操作：多路分支
- 插入关键字
  - 满节点（2t-1）个关键字，按照中间关键字分裂成两个各含t-1个关键字的节点
  - 中间关键字提升到y的双亲节点
  - 插入的下降过程中每遇到一个满节点就将节点分裂，这样保证最后插入的的节点分裂时其父节点不是满节点
    二项堆
二项树
- 二项树B0只包含一个节点，二项树Bk由2两颗二项树Bk-1连接而成，其中一棵树根是另一棵树根的最左孩子
- 二项树性质
  - 共有2^k个节点
  - 树高k
  - 深度i处有Cki个节点
  - 根的度数为k，根的子女从左到右编号k-1到0，子女i是子树Bi的根
- n个节点的二项树，任意节点的最大度数lgn
二项堆
- 堆中每个二项树都遵循最小堆性质
- 对任意非负整数k，堆中之多有一颗二项树度数为k
创建二项堆：根表头置空
寻找最小关键字：在根表中寻找最小值
根表度数严格递增
合并两个二项堆
插入：直接插入根表中
抽取最小关键字：将最小关键字子树构建成一个新的二项堆，与原二项堆合并
减小关键字：递归向上调整至根表
删除关键字：将关键字降值为最小，然后抽取最小值，复杂度O(lgn)

斐波那契堆

结构：最小堆有序树构成，不一定是二项树
根表由双链表构成，且无序；min[h]指向根表中最小值
可合并堆操作
- 插入节点：构建节点，插入根表，调整最小值指针
- 寻最小节点：直接返回最小值指针
- 合并两个斐波那契堆：合并根表，重置最小值指针
- 抽取最小点：删除最小值，将其子节点加入根表，然后合并根表（度相同的根合并，保证最后度数唯一）
- 减小一个关键字和删除一个节点
- 当节点成为另一个节点的子节点后，第一次删除孩子时置mark域为true，第二次删除时，必须级练删除将节点本身从树上删除，加入到根表中
- 删除一个节点：将节点降值为最小，然后抽取最小值点
  并查集

合并策略：

- 按秩合并（节点少的树根合并到节点多大的树根）
- 路径压缩（查找路径上的每个节点都指向根节点）

算法导论系列四：算法设计与分析：动态规划、贪心、平摊分析

Posted on 2016-12-26 | In CLRS

动态规划

步骤
- 秒速最优解的结构
- 地规定以最优解的值
- 自底向上的计算最优解
- 由计算结果构造最优解
装配线调度
- 最快路线的结构
- 一个问题额最优解包含了子问题的一个最优解：即最优子结构
- 递归解
矩阵链乘
动态规划
- 最优子结构：问题的最优解包含了子问题的最优解，即具有最优子结构
- 剪切发证明子问题的最优解课推导出问题最优解，如果不是子问题最优解，则剪贴子问题最优解
- 重叠子问题：求解原问题过程中多次求解一个子问题，则存在重叠子问题
- 备忘录：遇到的子问题未曾遇到则求解并存储，再次遇到时不必重复计算
最长公共子序列
- 最长公共子序列结构
最优二叉查找树：期望查找代价最小
- 最优二叉查找树必然具有最优子结构
- 求解最优二叉查找树，必然先求自述的最优二叉查找子结构

贪心（最小生成树，单源最短路径）

确定最优子结构，设计递归解，确定最优选择之一是贪心解，证明贪心选择后，只余一个子问题，设计贪心递归，递归算法转为迭代算法

贪心要素：贪心选择性质和最优子结构

贪心选择性质：全局最优解和通过局部最优（贪心）达到

最优子结构：问题的最优解包含了子问题的最优解，即具有最优子结构

贪心理论
- 拟阵
- 拟阵证明：非空子集，遗传性（传递性），交换性
- 拟阵中所有最大独立子集是相同的
- 贪心问题：在加权拟阵中寻找具有最大权值的独立子集
  任务调度
- 惩罚最小的调度安排，使得迟任务惩罚最小即早任务集惩罚最大，即求早任务集最大的安排方案

平摊分析

聚集分析：n个操作的全部时间平均到n个操作中去
- 计算多个操作的总代价，然后平均到一次操作
记账方法
- 总的平摊代价不能为负，保证平摊代价是总的代价的上界
势能方法
动态表
- 表扩张
  - 聚集分析
  - 记账方法

算法导论系列三：数据结构

Posted on 2016-12-26 | In CLRS

散列

链接法解决碰撞问题，散列进同一个桶中元素以链接方式存储
链接解决碰撞问题，依次查找不成功或成功的查找的期望时间θ（1+a）其中a为装载因子
散列函数
- 除法散列:取余数映射（m取值多去与2的整数次幂不太接近的质数）
- 乘法散列（其中m多取2的整数次幂）
开放寻址：连续检查散列表直到寻找到空槽插入元素
线性探查：单向线性查找空巢
二次探查：左右平法探查空巢
双重散列：冲突节点，再次散列探查
完全散列：保证二次散列不发生碰撞，且二次散列的期望总体空间为O(n)

二叉查找树

前驱和后继
插入

红黑树

红黑树性质
- 每个节点红或者黑
- 根节点是黑的
- 每个叶子节点是黑的
- 红节点的子节点均为黑色
- 任何一个节点从它本身到其子孙节点路径上抱哈相同数目的黑节点（黑高相同）
黑高：从节点本身出发到叶子节点路径上黑节点的数目
一颗n各节点的红黑树的高度最多为2lg（n+1）
left_rotate 左旋：右孩子成为父节点
左旋与右旋对称且只改变指针，在常量时间内完成
插入
- 以二叉排序树方法插入节点，并将节点颜色标为红色
- 插入调整：当父节点为红色时，进入调整过程
- 父节点为祖父节点左子
  - 叔节点为红色：父节点，叔节点同时置黑，祖父节点置红，递归调整祖父节点
  - 叔节点为黑色，且当前节点为父节点的右孩子：父节点左旋
  - 叔节点为黑色，且当前节点为父节点的左孩子：父节点置黑，祖父节点置红，右旋
- 父节点为祖父节点右子：
  - 叔节点为红色：父节点、叔节点同时置黑，祖父节点置红，提柜调整祖父节点
  - 叔节点为黑色，且当前节点为父节点的做孩子：父节点右旋
  - 叔节点为黑色，且当前节点为父节点的右孩子：父节点置黑，祖父节点置红，左旋
- 插入时间复杂度为O(lgn)
删除
- 以二叉排序树方法删除一个节点
  - 若待删节点为单子节点，则删除节点本身，否则寻找后继节点
  - 将找到的后继节点或者节点本身，链接为待删节点父节点的子节点
  - 如果是后继节点，则用后继节点覆盖待删节点
  - 如果删除的后继节点或者节点本身是黑色，则调整
- 删除调整：当删除节点不是根节点且为黑色时调整
  - 删除节点为左子节点
    - 兄弟节点为红色，改变兄弟节点和父节点颜色，并对父节点左旋（待删节点下移一层）转入情况234之一
    - 兄弟节点为黑色，且兄弟节点子节点均为黑色：兄弟节点置红（待删节点向上走一层）
    - 兄弟节点为黑色，兄弟节点左子红，右子黑：交换兄弟节点和其左子颜色，并右旋，转入情况4
    - 兄弟节点为黑色，兄弟节点左子黑，右子红：兄弟节点复制父节点颜色，父节点和兄弟节点右子均置黑，左旋父节点
    - 待删节点指向根
  - 删除节点为右子节点
    - 兄弟节点为红色：改变兄弟节点和父节点颜色，并对父节点右旋（待删节点下移一层）转入情况234之一
    - 兄弟节点为黑色：且兄弟节点子节点均为黑色：兄弟节点置红（待删节点向上走一层）
    - 兄弟节点为黑色：兄弟节点左子黑，右子红：交换兄弟节点和其右子节点颜色，并左旋，转入情况4
    - 兄弟节点为黑色：兄弟节点右子黑，左子红：兄弟节点复制父节点颜色，父节点和兄弟节点左子均置黑，右旋父节点
    - 待删节点指向根
  - 根节点置黑
- 删除时间复杂度为O(lgn)

扩展红黑树

顺序统计树：红黑树加入size域，标记以该节点为根的子树节点数
检索给定序列元素

数据结构扩张

选择基础数据结构
确定要在基础数据结构中添加哪些信息
验证可用基础数据结构上基本修改操作维护新添加的信息
设计心得操作

区间树

增加一个区间左界和一个区间右界，一个以该结点为根的子树的右界最大值

E-R

E-R转表

关系模型

SQL

完整性约束

模式分解

储存结构文件结构（数据库系统实现）

索引

B+树索引

查询处理

选择运算

索引选择

比较选择

比较选择

连接运算

外连接

启发优化

事务

并发

死锁预防

恢复

重启动回复

FLAG

Project Address:

决策树伪代码createbranch

香农熵

数据及划分与最优选择（熵最小）

创建树

测试

图形化显示树结构

创建节点

扩展测试 lens.py

Project Address:

K近邻算法

k-means 伪码

python code

使用第二列和第三列数据形成散点图

数值归一化

手写字符识别

select/poll

内存分配

迭代器与traits技法

序列容器

vector

list

deque

heap

关联容器

仿函数

学习总结

感知机学习算法

感知机模型（激活函数）

神经网络与反向传播

神经网络学习算法基本概念

损失函数

经验损失

结构损失

算法分析

朴素贝叶斯

支持向量机

决策树

项目地址

A1手写字符识别

运行环境

运行

A23 OCR识别预测

运行环境

运行

运行效果

Summary

学习内容：

学习心得体会

Reference

static

inline

explicit

B树

二项堆

斐波那契堆

并查集

学习内容：　