mujjiga

查找连接组件的DFS

import queue
import itertools
n = 10

def DFS(data, v, x,y,z, component):
    q = queue.Queue()
    q.put((x,y,z))
    while not q.empty():
        x,y,z = q.get()
        v[x,y,z] = component

        l = [[x], [y], [z]]

        for i in range(3):
            if l[i][0] > 0:
                l[i].append(l[i][0]-1)
            if l[i][0] < v.shape[1]-1:
                l[i].append(l[i][0]+1)

        c = list(itertools.product(l[0], l[1], l[2]))
        for x,y,z in c:
            if v[x,y,z] == 0 and data[x,y,z] == 1:
                q.put((x,y,z))

data = np.random.binomial(1, 0.2, n*n*n)
data = data.reshape((n,n,n))

coordinates = np.argwhere(data > 0)
v = np.zeros_like(data)

component = 1
for x,y,z in coordinates:
    if v[x,y,z] != 0:
        continue
    DFS(data, v, x,y,z, component)
    component += 1

主要算法:

1. 组成部分)
2. 3. 如果没有访问该点,则从该点开始启动一个DFS

DFP公司: (x,y,z) 我们使用 itertools.product . 在3D情况下,每个点将有27个邻居,包括它自己(3个位置和3个可能值-相同、递增、递减,所以27个方向)。

v 存储从1开始编号的连接组件。

当数据=

 [[[1 1 1]
  [1 1 1]
  [1 1 1]]

 [[0 0 0]
  [0 0 0]
  [0 0 0]]

 [[1 1 1]
  [1 1 1]
  [1 1 1]]]

可视化:

两个相对的边是两个不同的连接组件

[[[1 1 1]
  [1 1 1]
  [1 1 1]]

 [[0 0 0]
  [0 0 0]
  [0 0 0]]

 [[2 2 2]
  [2 2 2]
  [2 2 2]]]

这是正确的。

可视化:

从视觉上可以看出 绿色表示一个连接的组件,蓝色表示另一个连接的组件。

import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

def plot(data):
    fig = plt.figure(figsize=(10,10))
    ax = fig.gca(projection='3d')

    for i in range(data.shape[0]):
        for j in range(data.shape[1]):
            ax.scatter([i]*data.shape[0], [j]*data.shape[1], 
            [i for i in range(data.shape[2])], 
                   c=['r' if i == 0 else 'b' for i in data[i,j]], s=50)

plot(data)
plt.show()
plt.close('all')
plot(v)
plt.show()

df = [pd.DataFrame({'Location': np.random.randint(0,5,size=(100))}) for i in range(10)]
df = list(map(lambda x: x.groupby('Location').get_group(1), df))

梯度下降法是一种求函数最小值的优化算法。

非常简单的视图

让我们从一维函数y=f(x)开始

让我们从x的任意值开始,找到f(x)的梯度(斜率)。

• 如果斜率在x处减小,则意味着我们必须进一步向(数字线右侧)x(为了达到最小值)

• 如果斜率在x处增加,那就意味着我们必须离开(数字线的左边)x

  我们可以通过求函数的导数得到斜率。如果斜率减小,导数为-ve;如果斜率增大,导数为+ve

所以我们可以从x的任意值开始,用x的导数慢慢地向最小值移动,移动的速度由学习速率或步长决定。所以我们有更新规则

x = x - df_dx*lr

我们可以看到,如果斜率减小,导数(df_dx)为-ve,x增大,所以x进一步向右移动。另一方面,如果斜率增加,df_dx是+ve,这会减小x,所以我们向左转。

我们继续这个过程,或者多次,或者直到导数很小

多元函数z=f(x,y)

同样的逻辑也适用,除了现在我们用偏导数代替导数。 更新规则是

x = x - dpf_dx*lr
y = y - dpf_dy*lr

其中dpf_dx是f相对于x的偏导数

上述算法称为梯度下降算法。在机器学习中,f(x,y)是我们感兴趣的最小代价/损失函数。

例子

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d.axes3d import Axes3D
from pylab import meshgrid
from scipy.optimize import fmin
import math

def z_func(a):
 x, y = a
 return ((x-1)**2+(y-2)**2)

x = np.arange(-3.0,3.0,0.1)
y = np.arange(-3.0,3.0,0.1)
X,Y = meshgrid(x, y) # grid of point
Z = z_func((X, Y)) # evaluation of the function on the grid

fig = plt.figure()
ax = fig.gca(projection='3d')
surf = ax.plot_surface(X, Y, Z, rstride=1, cstride=1,linewidth=0, antialiased=False)
plt.show()

z_func的最小值为(1,2)。这可以使用scipy的fmin函数来验证

fmin(z_func,np.array([10,10]))

现在让我们编写我们自己的梯度下降算法来找到z_func的最小值

def gradient_decent(x,y,lr):
    while True:
        d_x = 2*(x-1)
        d_y = 2*(y-2)

        x -= d_x*lr
        y -= d_y*lr

        if d_x < 0.0001 and d_y < 0.0001:
            break
    return x,y

print (gradient_decent(10,10,0.1)

我们从任意值x=10和y=10开始,学习率为0.1。上面的代码打印 1.000033672997724 2.0000299315535326 这是正确的。

因此,如果你有一个连续可微凸函数,要找到它的最优值(对于凸函数来说是最小值),你所要做的就是找到函数对每个变量的偏导数,并使用上面提到的更新规则。重复这些步骤,直到梯度很小,这意味着我们已经达到了凸函数的最小值。

如果函数不是凸的,我们可能会陷入局部最优。