Home >  List

Line plot
2017-02-27

Smooth line in pyplot stackoverflow

from scipy.interpolate import spline

T = np.array([6, 7, 8, 9, 10, 11, 12])
power = np.array([1.53E+03, 5.92E+02, 2.04E+02, 7.24E+01, 2.72E+01, 1.10E+01, 4.70E+00])

#300 represents number of points to make between T.min and T.max
xnew = np.linspace(T.min(),T.max(),300) 

power_smooth = spline(T,power,xnew)

plt.plot(xnew,power_smooth)
plt.show()
Not smooth Smooth

Read full-text »

Algorithm: 数据结构和算法的可视化
2017-02-18

Data Structure Visualizations

  • link: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
  • 优点：
    • 这是比较全面的包含了，基本的数据结构和算法的演示
    • 演示的界面包含python写的代码
  • 缺点：界面比较古老
  • 内容列表：algorithm_visualize1-1.png
  • 二分查找演示界面：algorithm_visualize1_binary_search.png

algorithm-visualizer

  • link: https://algorithm-visualizer.org/
  • 优点：
    • 内容全面
    • 界面现代化程度高，比较精美
  • 缺点：
    • 代码支持三种：Java，C++，JavaScript
  • 内容列表：algorithm_visualizer.png
  • 二分查找演示界面：algorithm_visualizer_binary_search.png

VisuAlgo

  • link: https://visualgo.net/en
  • 优点：
    • 支持多种语言的界面，英文+中文等
    • 涉及的内存全面
  • 缺点：
    • 主要包含算法，缺少数据结构的演示
    • 基本的算法没有，比如二分查找
  • 内容列表：algorithm_visulogo.png
  • 快速排序演示界面：algorithm_visulogo_quicksort.png

Read full-text »

Set up config for jupyter notebook
2017-02-10

jupyter notebook的配置

新建配置文件

参考这篇文章，对自己的notebook进行配置，方便快捷。比如可以在打开notebook时直接先加载一些模块等。

# creat新建配置文件
gongjing@MBP ~/.ipython/profile_default % ipython profile create
[ProfileCreate] Generating default config file: u'/Users/gongjing/.ipython/profile_default/ipython_config.py'
[ProfileCreate] Generating default config file: u'/Users/gongjing/.ipython/profile_default/ipython_kernel_config.py'
gongjing@MBP ~/.ipython/profile_default % ll
total 16304
drwxr-xr-x  2 gongjing  staff    68B Jun 18  2016 db
-rw-r--r--  1 gongjing  staff   7.9M Feb 10 09:42 history.sqlite
-rw-r--r--  1 gongjing  staff    22K Feb 10 09:43 ipython_config.py
-rw-r--r--  1 gongjing  staff    18K Feb 10 09:43 ipython_kernel_config.py
drwxr-xr-x  2 gongjing  staff    68B Jun 18  2016 log
drwx------  2 gongjing  staff    68B Jun 18  2016 pid
drwx------  2 gongjing  staff    68B Jun 18  2016 security
drwxr-xr-x  3 gongjing  staff   102B Jun 18  2016 startup

ipython_config.py 这个文件是配置ipython的；

ipython_kernel_config.py 这个文件是配置notebook的；

编辑配置文件

加载常用模块，matplot设置成inline

# Configuration file for ipython-kernel.

c = get_config()

c.InteractiveShellApp.exec_lines = [
        "import pandas as pd",
        "import numpy as np",
        "import scipy.stats as spstats",
        "import scipy as sp",
        "import matplotlib.pyplot as plt",
        "import seaborn as sns",
        "sns.set(style='white')",
        "sns.set_context('poster')",
        ]

c.IPKernelApp.matplotlib = 'inline'

Connect notebook server

# login the server
$ ssh -X -p 12000 zhangqf7@166.111.152.116

$ export PYTHONPATH=~/anaconda2/lib/python2.7/site-packages

# specify a port
$ jupyter-notebook --port 9988

# local
$ ssh -N -f -L localhost:9987:localhost:9988 zhangqf7@166.111.152.116 -p 12000

# type url: localhost:9987
# may need token

自动生成目录

主要是参考这里 为Jupyter Notebook添加目录：

# 安装后重启
~/anaconda3/bin/conda install -c conda-forge jupyter_contrib_nbextensions

添加R kernel

参考这里：在jupyter notebook中使用R语言

install.packages(c('repr', 'IRdisplay', 'evaluate', 'crayon', 'pbdZMQ', 'devtools', 'uuid', 'digest'))
devtools::install_github('IRkernel/IRkernel')

# 只在当前用户下安装(在集群上安装)
IRkernel::installspec()
# 或者是在系统下安装
IRkernel::installspec(user = FALSE)

比如是在集群上安装的，之后打开jupyter-lab后，可以看到启动界面多了一个R的选择：20190822095638

df禁用科学计数法

有时在显示df（比如head，describe），数字会以科学计数法的方式展现，而不知道具体的比如百分比数字大小，可以设置禁用科学计数法表示：

pd.set_option('display.float_format',lambda x : '%.2f' % x)

显示df而不是print

通过下面的display命令可以将df显示为带有表格的table，而不是直接打印print(df)的效果：

from IPython.display import display
display(df)

快捷键

  • code block左缩进：shift+tab，参考这里
  • 切换不同的notebook tab: ctl+shift+[左切，ctl+shift+]右切
  • 设置：C+arrowUp将cell上移动，C+arrowDown将cell上移动，O将cell的输出collapse，OO将cell的输出拓展开。首先要使用esc退出编辑模式，进入命令模式。 
    {
  // Move cell up
  "shortcuts": [
      {
    "selector": ".jp-Notebook:focus",
    "command": "notebook:move-cell-up",
    "keys": [
      "C",
      "ArrowUp"
    ]
      },
  // Move cell down
      {
    "selector": ".jp-Notebook:focus",
    "command": "notebook:move-cell-down",
    "keys": [
      "C",
      "ArrowDown"
    ]
  },
      {
    "command": "notebook:hide-cell-outputs",
    "keys": [
      "O"
    ],
    "selector": ".jp-Notebook:focus"
  },    
  {
    "command": "notebook:show-cell-outputs",
    "keys": [
      "O", 
      "O"
    ],
    "selector": ".jp-Notebook:focus"
  },    
  ]
}

df显示时指定千分位符号

参考这里：

# for all columns
df.head().style.format("{:,.0f}")

# per column
df.head().style.format({"col1": "{:,.0f}", "col2": "{:,.0f}"})

Read full-text »

Bubble plot
2017-02-07

bubble plot可以结合展示三个变量之间的关系，本文主要是演练了这里这里的代码：

# create data
x = np.random.rand(5)
y = np.random.rand(5)
z = np.random.rand(5)

控制bubble的颜色、透明度：

# Change color with c and alpha
plt.scatter(x, y, s=z*4000, c="red", alpha=0.4)

控制bubble的形状：

plt.scatter(x, y, s=z*4000, marker="D")

控制bubble的大小:

plt.scatter(x, y, s=z*200)

控制bubble的边缘（线条粗细等）：

plt.scatter(x, y, s=z*4000, c="green", alpha=0.4, linewidth=6)

先导入seaborn，则采用seaborn的主题：

import seaborn as sns
plt.scatter(x, y, s=z*4000, c="green", alpha=0.4, linewidth=6)

同时给气泡上颜色和大小，相当于展示了4个变量：

# create data
x = np.random.rand(15)
y = x+np.random.rand(15)
z = x+np.random.rand(15)
z=z*z
 
# Change color with c and alpha. I map the color to the X axis value.
plt.scatter(x, y, s=z*2000, c=x, cmap="Blues", alpha=0.4, edgecolors="grey", linewidth=2)

### plot color bar
### https://stackoverflow.com/questions/6063876/matplotlib-colorbar-for-scatter
sc = plt.scatter(x, y, s=z*2000, c=x, cmap="Blues", alpha=0.4, edgecolors="grey", linewidth=2)
plt.colorbar(sc)

Read full-text »

Algorithm: 动态规划算法与最长公共子串
2017-02-07

动态规划算法的启示

  • 能在给定约束条件下找到最优解。背包问题：在背包容量下。
  • 问题可分解为彼此独立且离散的子问题时
  • 提出DP方案：
    • 每种DP解决方案都涉及网格
    • 单元格中的值通常就是要优化的值
    • 每一个单元格都是一个子问题，因此应该考虑如何将问题分成子问题

最长公共子串

  • 给定串中任意个连续的字符组成的子序列称为该串的子串，longest common substring
  • 问题：一个字典查询网站，用户输入hish，但是有两个类似的词fish、vista，判断用户应该是输入的哪一个？
  • 绘制网格：
    • 单元格中的值是什么？
    • 如何将这个问题划分为子问题？
    • 网格的坐标轴是什么？
  • 填充表格：
    • 填充值的公式是什么？
    • 没有固定的公式，需要自行摸索。比如上面的背包问题公式，并不是通用的。
  • 答案：
    • 背包：最后的单元格值是的
    • 最长公共子串：网格中的最大数字，可能不是位于最后的单元格中 DP_longest_common_string.png

最长公共子序列

  • 问题：用户输入的是fosh，那么其是想输入fish还是fort呢？
  • 最长公共子串：
    • 结果相同，都为2
    • 但是明显FISH是更接近的，因为有3个字符是相同的 DP_longest_common_subsequence.png
  • 最长公共子序列：
    • 两个单词中都有的序列包含的字母数，longest common sequence
    • appears in the same relative order, but not necessarily contiguous，将给定序列中零个或多个元素去掉之后得到的结果
    • “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, 等等都是“abcdefg”的子序列
    • 复杂度：长度为n的字符串，其子序列共有2^n种
    • 所以比如F是FOSH、FISH都包括的，即使和后面的SH不相连，也应该计算在内
    • 计算公式推导：DP_longest_common_subsequence3.png
    • 网格流程：DP_longest_common_subsequence2.png
  • 下面是一个数字字符串的比对流程：DP_longest_common_subsequence4.png
  • 回溯：
    • 从最后一个格子开始
    • 如果格子对应的x值和y值相等，则可知这个值是左上角值+1的得来的
    • 如果格子对应的x值和y值不相等，则可知这个值是从上边或者左边的最大值来的
      • 如果上边和左边值是相等的，则选择其中一个。当选择了一个方向之后，后面如果碰到相等的情况，也使用相同的方向回溯。 DP_longest_common_subsequence_reconstruct.png

代码实现

递归实现：

# A Naive recursive Python implementation of LCS problem 

# X: string1, Y: string2
# m: len(X), n: len(Y)

def lcs(X, Y, m, n): 

	if m == 0 or n == 0: 
		return 0; 
	elif X[m-1] == Y[n-1]: 
		return 1 + lcs(X, Y, m-1, n-1); 
	else: 
		return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 


# Driver program to test the above function 
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X, Y, len(X), len(Y)) 

# Length of LCS is  4

Dynamic programming 实现：

# Dynamic Programming implementation of LCS problem 

def lcs(X, Y): 
	# find the length of the strings 
	m = len(X) 
	n = len(Y) 

	# declaring the array for storing the dp values 
	L = [[None]*(n + 1) for i in xrange(m + 1)] 

	"""Following steps build L[m + 1][n + 1] in bottom up fashion 
	Note: L[i][j] contains length of LCS of X[0..i-1] 
	and Y[0..j-1]"""
	for i in range(m + 1): 
		for j in range(n + 1): 
			if i == 0 or j == 0 : 
				L[i][j] = 0
			elif X[i-1] == Y[j-1]: 
				L[i][j] = L[i-1][j-1]+1
			else: 
				L[i][j] = max(L[i-1][j], L[i][j-1]) 

	# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1] 
	return L[m][n] 
# end of function lcs 


# Driver program to test the above function 
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X, Y) 

# This code is contributed by Nikhil Kumar Singh(nickzuck_007) 

# Length of LCS is  4

DP其他应用

  • DNA序列之间的相似性，从而确定物种相似性
  • git diff命令找两个文件的差异
  • 编辑距离：两个字符串的相似程度，拼写检查，用户上传的资料是否为盗版
  • word的断字功能，判断在什么地方断字以保证行长一致

参考

Read full-text »

进化树
2017-02-05

进化树

定义

  • 系统发生树又称演化树或进化树，是表明被认为具有共同祖先的各物种间演化关系的树状图。是一种亲缘分支分类方法（cladogram）。在图中，每个节点代表其各分支的最近共同祖先，而节点间的线段长度对应演化距离（如估计的演化时间）。

建树步骤

  • 1、多序列比对
  • 2、选择建树算法构建进化树
  • 3、进化树构建结果的评估

多序列比对软件

  • clustwal。也可用命令行形式：clustalo -i input.fa -o input.align.fa
  • MEGA

构建算法

  • 近邻结合法 neighbor-joining (NJ)
  • 最大简约法 maximum parsimony (MP)
  • 最大似然估计 maximum likelihood (ML)
  • 贝叶斯法 Bayesian

软件

  • Phylip、MrBayes、Simple Phylogeny

进化树含义

这里有两张图解释了进化树的各含义，可以参考一下。

主要的几点如下：

  • 根节点：所有物种（序列）的共同祖先（下图中酒红色的点）
  • 节点：分类单元（下图中蓝色的点和绿色的点）
  • 进化支：>=2个物种（序列）及其祖先组成的分支
  • 距离标尺：进化树的比例尺，序列的差异度的大小，比如下图是0.07
  • 分支长度：节点之间或者节点与祖先之间的累计支长，越小则差异越小
  • 自展值：表征可信度的，因为建树的过程需要通过bootstrap方法重复多次，一般小于50%（0.5）的会被认为不可靠

参考

Read full-text »

Algorithm: 动态规划算法与背包问题
2017-02-03

背包问题：穷举算法

  • 问题：偷取物品价值最高，如何选择？
  • 简单算法：穷举
    • 3件商品：8种组合，选取最小的
    • 4件商品：16种组合，选取最小的
    • 5件商品：32种组合，选取最小的
    • 32件商品：40种组合，选取最小的
    • 每增加一件商品，需计算的集合数将翻倍
    • 算法时间：O(2^n)

背包问题：动态规划

  • 原理：先解决子问题，再逐步解决大问题
  • 背包问题：先解决小背包问题，再逐步解决原来的问题
  • 下面是具体的流程：

构建网格

  • DP都是从网格开始
  • 最初是空的，就是通过填充网格，拿到最终解
  • 填充是按照行开始的，一行一行的填充

填充行

  • 行：表示当前的最大价值，当前所有物品+可选容积所决定
  • 吉他行：
    • 物品：目前只有吉他可供选择
    • 实施：在对应容积（列）限制下，使得对应单元格价值最大，应该如何偷取？
    • 结果：现在只有吉他，且重量为1，在1-4之间，都偷取吉他达到单元格最大
  • 音响行：
    • 物品：吉他+音响
    • 实施：在对应容积（列）限制下，使得对应单元格价值最大，应该如何偷取？
    • 结果1：更新单元格1，此前最大是吉他(1500)，现在可选的有音响(3000,4磅)，但是容积超过限制，因此不能偷取。
    • 结果2-3：同样的，可以偷取音响，但是容积不够，因此保持偷取原来最大的
    • 结果4：现在容积到达4，满足音响的，因此可以偷取音响，且价值高于原来的只偷取吉他，因此更新此处的偷取策略和价值
  • 笔记本行：
    • 物品：吉他+音响+笔记本
    • 实施：在对应容积（列）限制下，使得对应单元格价值最大，应该如何偷取？
    • 结果1-2：小于2的时候，只能偷取1磅的吉他，保持偷吉他1500不变
    • 结果3：3磅的时候，满足可以偷取2000的笔记本，因此更新
    • 结果4：4的情形
    • 从这里可以看到，为什么前面需要计算小背包时，能够获取的最大价值
  • 填充公式：

背包问题FAQ

再增加一个商品，需要重新构建网格吗？

  • 不用，本身DP就是逐步计算最大价值
  • 可直接在原始网格后面，再添加一行新的物品，填充行

沿着列往下走，最大价值可能降低吗？

  • 不会
  • 每次迭代时，存储的都是当前的最大值，当新的值更小时，会保持这个最大值；当新的值更大时，会更新这个最大值，所以不可能比以前低。

行的顺序发生变化，结果会变吗？

  • 不会有变化
  • 各行的排列顺序无关紧要

可以逐列而不是逐行填充吗？

  • 可以
  • 就背包问题，逐列填充没有影响
  • 但对于其他问题，可能有影响

增加一个重量更小的商品有影响吗？

  • 需要重新构建粒度更细的网格
  • 比如总共4，有一个0.5的项链，如果偷取项链，那么剩余3.5的最大价值是多少，之前的表格是不知道的，因此需要调整网格

可以偷取商品的一部分吗？

  • 比如：有大米和扁豆，可打开包装，各偷取部分
  • 不行。DP考虑的是要么拿走整件，要么不拿的情况，不能判断该不该拿商品的一部分。
  • 其他方案：贪婪算法，先尽可能多的拿价值最高的，再次高的，等等

旅游行程最优化

  • 前面的旅游问题可用DP方案
  • 约束条件：有限的时间
  • 单元格：整体的评分最大化
  • 行：每个不同的城市景点

处理相互依赖的情况

  • 比如在上面的形成增加了三个在巴黎的景点？是否可以DP？
  • 不行。因为这三个地点在一起，是相互依赖的，当你到了其中一个之后，其他两个的时间是改变的。
  • 仅当每个子问题都是离散的，即不依赖于其他子问题时，DP才管用。

计算最终的解时会设计两个以上的子背包吗？

  • 不会。
  • 大问题切成两个小问题
  • 只是小问题，又可以切成两个小问题，但是每一次只涉及两个。

最优解可能导致背包没装满吗？

  • 完全可能
  • 比如还有一个3.5磅的无价之宝，当然会偷取这个，还剩0.5装不下任何其他东西。

参考

Read full-text »

Algorithm: 近似算法中的贪婪算法
2017-01-28

贪婪算法

贪婪算法：

  • 原理：
    • 每步都采取最优的做法。比如下面的教室调度例子中，每次选择结束最早的课。
    • 即：每步都选择局部最优解，最终得到的就是全局最优解
  • 优点：简单易行

教室调度问题

greedy_classroom.png

  • 问题：给定一系列的课程上课时间，如何安排使得尽可能多的课程在同一个教室上？
  • 解法：贪婪算法
    • 1）选出结束最早的课，设置为在教室上的第一堂课
    • 2）接下来，必须选择第一堂课上完之后才开始上的课，且是结束的最早的
    • 3）接下来，选择上堂课上完之后才开始上的课，且是结束的最早的
    • 4）重复。

背包问题

greedy_bag.png

  • 问题：一个贪婪的小偷，想在机场偷取物品放在自己的背包中，偷得物品总重量不超过背包可装重量35磅，每个物品均有对应价值，如何偷取使得价值最大？
  • 贪婪解法：
    • 1）偷取可装入背包的最贵商品
    • 2）再偷取还可装入的最贵商品

    • 3）依次类推，直到装不下

    • 注意：
    • 贪婪策略虽然不能获得最优解，但是非常接近
    • 有些情况下，完美是优秀的敌人
    • 有时只需找到一个能大致解决问题的算法，而贪婪算法正好可以派上用场

集合覆盖问题：暴力穷举

greedy_TV.png

  • 问题：一系列电台，每个电台只能在几个州收听到，如何选取最少的电台，使得能覆盖所有的州？
  • 暴力解法：
    • 1）列出每个可能的电台集合，这里有2^n种，n是电台的总数
    • 2）从上述集合中，选出覆盖全美所有州的最小集合
    • 问题：
    • 随着电台数目的增加，集合数呈现指数上升（时间复杂度：2^n）
  • 没有任何算法可以足够快的解决此问题

集合覆盖问题：贪婪算法

  • 什么是近似算法：
    • approximation algorithm
    • 在获得精确解需要太长时间时，可使用近似
    • 近似算法的优劣判断：
      • 速度有多快
      • 得到的近似解与最优解的接近程度
  • 贪婪算法：
    • 1）选出1个电台，其覆盖了最多的未覆盖的州
    • 2）重复第一步，直到所有的州都被覆盖
    • 时间复杂度：O(n^2)
  • 实现：
    • 1）准备
      • 要覆盖集合：存储要覆盖的州。比如这里是所有的州
      • 电台字典。每个电台覆盖哪些州，州也用集合的形式给出。
      • 最终电台集合。存储最终选择的电台，动态变化，一步步添加，知道全部州被覆盖。
    • 2）循环
      • 当要覆盖集合不为空时，不断挑选电台
        • 挑选最好的电台，即覆盖未被覆盖的州数目最多的电台。
        • 最好电台加入到最终电台集合
        • 要覆盖集合中删除被此最好电台覆盖的电台 greedy_TV_time.png
# You pass an array in, and it gets converted to a set.
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])

stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])

final_stations = set()

while states_needed:
  best_station = None
  states_covered = set()
  for station, states_for_station in stations.items():
    covered = states_needed & states_for_station
    if len(covered) > len(states_covered):
      best_station = station
      states_covered = covered

  states_needed -= states_covered
  final_stations.add(best_station)

print(final_stations)

NP完全问题

定义：以难解著称的问题。需要计算所有的解，从中选出最小、最短的那个，比如旅行商问题或者集合覆盖问题

如何识别？

  • 元素较少时算法的运行速度非常快，但是随着元素数量的增加，速度会变得非常慢
  • 通常是：
    • 涉及“所有组合”的问题
  • 可能是：
    • 不能将问题分成小问题，必须考虑各种可能的情况
    • 问题涉及序列（如旅行商问题的城市序列）且难以解决
    • 问题涉及集合（如电台集合）且难以解决
  • 肯定是：
    • 问题可转换为集合覆盖问题或者旅行商问题

例子：

  • 有个邮递员负责给20个家庭送信，需要找出经过这20个家庭的最短路径。请问这是一个NP完全问题吗？【是的，都需要送到，旅行商问题】
  • 在一堆人中找出最大的朋友圈（即其中任何两个人都相识）是NP完全问题吗？【是的，需要穷举不同的集合，挑选出两两认识最多的那个集合】
  • 你要制作美国地图，需要用不同的颜色标出相邻的州。为此，你需要确定最少需要使用多少种颜色，才能确保任何两个相邻州的颜色都不同。请问这是NP完全问题吗？【我不确定。答案：是的】

参考

Read full-text »

Category

Latest articles

Links