魔のkyo的BLOG
0%

发表于 更新于 分类于 Valine： 本文字数： 862 阅读时长 ≈ 1 分钟

Python的线程没有提供从外部主动终止线程的方法，当然从程序设计上应该避免这种方式，但有些时候我们希望把线程超时当做一种异常来处理，我们需要提前终止它，下面的代码提供了一种可参考方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import threading
import inspect
import ctypes

def _async_raise(tid, exctype):
    """raises the exception, performs cleanup if needed"""
    tid = ctypes.c_long(tid)
    if not inspect.isclass(exctype):
        exctype = type(exctype)
    res = ctypes.pythonapi.PyThreadState_SetAsyncExc(tid, ctypes.py_object(exctype))
    if res == 0:
        raise ValueError("invalid thread id")
    elif res != 1:
        # """if it returns a number greater than one, you're in trouble,
        # and you should call it again with exc=NULL to revert the effect"""
        ctypes.pythonapi.PyThreadState_SetAsyncExc(tid, None)
        raise SystemError("PyThreadState_SetAsyncExc failed")

def kill_thread(tid):
    _async_raise(tid, SystemExit)

实际测试下来大多数情况是可以工作的，除了线程长时间陷在time.sleep的情况，也就是说上面的代码无法把一个线程从sleep状态唤醒并终止。

发表于 更新于 分类于 Valine： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

无监督学习算法指的是算法只有输入数据（Features），不需要用到(或根本不知道)输入的对应输出(Target)，从中提取一些有用的知识。

sklearn中无监督学习算法主要分为以下类型：预处理、分解和聚类。

scikit-learn中的算法实现

算法中文名 所属模块 类名 主要参数
范围缩放 preprocessing MinMaxScaler feature_range=(0,1)
标准化缩放 preprocessing StandardScaler
One-Hot编码 preprocessing OneHotEncoder categorical_features = ‘all’
多项式特征 preprocessing PolynomialFeatures degree=2
主成分分析 decomposition PCA n_components, whiten=False
非负矩阵分解 decomposition NMF n_components
K聚类 cluster KMeans n_clusters
凝聚聚类 cluster AgglomerativeClustering n_clusters, linkage=ward
DBSCAN cluster DBSCAN min_samples, eps

可以看到上述算法所属模块即对应了预处理、分解和聚类。

预处理就是用于对监督学习算法的输入数据做前期处理，输入和输出都是一组Features。

事实上分解和聚类也可以作为监督学习算法的前期处理，不过他们也可以提供一些额外的功能。

下面对这些算法做逐一简要说明：

MinMaxScaler

根据最大最小值缩放和平移特征，默认参数使得每个特征都在0~1之间。

StandardScaler

根据均值和方差缩放和平移特征，默认参数使得每个特征的均值是0，方差是1。

OneHotEncoder

对分类变量（特征是离散的枚举值）进行编码，把一个具有N个枚举值的特征用N个0,1值的特征表示。

PolynomialFeatures

制造原特征的交互特征和多项式特征，例如(x1,x2)可以生成出(1, x1, x2, x1^2, x2^2, x1*x2)，通过degree可以控制生成特征的最高次。可以让线性模型学习出对原特征来说非线性的结果。

PCA

主成分分析是找到原特征的一种新的表示，从线性代数的角度讲是找到一组正交基，然后把原特征当成向量，算出它们在新基下的表示，也就得到一组新表示下特征。这组正交基的取法是先找到原特征离散度最大的轴向，作为正交基的第一个轴，然后第二个轴是在与第一个轴“垂直”的超平面上，继续选取离散度最大的轴向，第三个轴要在与前两个轴都“垂直”的超平面上找离散度最大的轴向，以此类推。因为变换得到的新特征再前几个轴上离散程度较高后面依次降低，我们有理由期望新特征的前几个分量对Target的影响更大（虽然不一定），因此我们可以用PCA来对Feature降维（即丢弃掉后面离散程度最小的一些轴向上的坐标）。

NMF

非负矩阵分解原理类似PCA，不过它的基并不正交，NMF要求原特征均为非负，其基的每个分量和得到的新特征也均为非负，对于有多个独立源叠加而成的数据，比如多人说话的音轨或包含多种乐器的音乐，NMF能识别出组成合成数据的原始分量。NMF也可以用于降维。

KMeans

K均值聚类，所谓聚类就是把数据集按照一定的规则进行分组，使得同组的数据相似，不同组的数据相异，这些组在聚类算法中称为簇，K均值聚类要事先告知簇个数，算法的核心就是不停修正每个簇的簇中心，先随机选K个点作为簇中心，交替进行以下两个步骤：将每个数据点分配给最近的簇中心，然后将每个簇中心设置为所分配的所有数据点的平均值，重复以上步骤直至簇的分配不再变化。前面说聚类也可以作为监督学习算法的前期处理，这里如果我们用簇中心来代表簇里的数据点，那么每个点都可以用一个单一分量来表示（簇的编号），这称为矢量量化。（不过这种分量一般不具有连续意义，似乎还要再进行OneHot编码）

AgglomerativeClustering

凝聚聚类，先把每个数据点视作一个簇，然后按照一定的规则逐步合并，凝聚聚类算法可以生成可视的树状图来观察合并过程。凝聚聚类也需要提前告知簇个数。

DBSCAN

DBSCAN聚类，先随机选取一个没标记过的数据点标记一个新簇，以eps为距离做DFS让遍历到的数据点加入簇，如果最终遍历到的点少于min_samples则视为噪声，然后在再随机选取数据点再遍历再标记，进行直到所有点被标记到一个簇里或标记为噪声，DBSCAN可以生成具有复杂形状的簇，噪声也可以用来做异常值检测。

发表于 更新于 分类于 Valine： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

K近邻

适用于小型数据集，基准模型，容易解释。不适用于高维稀疏数据，不能外推（超出训练数据集的范围进行预测）。

线性模型（最小二乘法、岭回归、Lasso回归、弹性网络、逻辑回归、线性支持向量机）

非常可靠的首选算法，适用于非常大的数据集，也适用于高维数据，可以外推。在低维空间中泛化性能可能很差（这还要看具体问题本身的特点，还可以通过扩展特征来增加线性模型的可用性）。

其中最小二乘法、岭回归、Lasso回归、弹性网络为回归器，不需要数据缩放。逻辑回归、线性支持向量机为分类器，逻辑回归如果不进行数据缩放会导致收敛较慢需要增加迭代次数，线性支持向量机需要进行数据缩放。

朴素贝叶斯（高斯朴素贝叶斯、伯努利朴素贝叶斯、多项式朴素贝叶斯）

只适用于分类问题。适用于非常大的数据集和高维数据，比线性模型速度快，精度低于线性模型。

决策树

速度很快，不需要数据缩放，可以可视化，很容易理解。不适用于高维稀疏数据，不能外推。

随机森林

几乎总是比单棵决策树的表现要好，鲁棒性很好(可以容忍训练集中有一些错误的数据)，通常不需要反复调节参数就可以给出很好的结果，不需要数据缩放，不适用于高维稀疏数据，不能外推。

梯度提升机

是监督学习中最强大也最常用的模型之一。精度通常比随机森林略高，与随机森林相比，训练速度更慢，但预测速度更快，需要的内存更少，比随机森林需要更多的参数调节，不适用于高维稀疏数据，不能外推。

核支持向量机

是非常强大的模型，允许决策边界很复杂，在低维和高维数据集上的表现都很好。对于特征含义相似的中等大小（几千~几万这样的量级）的数据集很强大。需要数据缩放，对参数敏感，可以外推。

神经网络（多层感知机）

可以构建非常复杂的模型，特别是对于大型数据集而言。对于数据缩放敏感，对参数选取敏感。大型网络需要很长的训练时间。

scikit-learn中的算法实现

算法名 所属模块 分类器 回归器 主要参数(-号表示越小越模型复杂)
K近邻（KNN） neighbors KNeighborsClassifier KNeighborsRegressor -n_neighbors=5
最小二乘法 linear_model LinearRegression
岭回归 linear_model Ridge -alpha=1
Lasso回归 linear_model Lasso -alpha=1
弹性网络 linear_model ElasticNet -alpha=1, l1_ratio=0.5
逻辑回归 linear_model LogisticRegression +C=1.0
线性支持向量机 svm LinearSVC LinearSVR +C=1.0
高斯朴素贝叶斯 naive_bayes GaussianNB
伯努利朴素贝叶斯 naive_bayes BernoulliNB -alpha=1.0
多项式朴素贝叶斯 naive_bayes MultinomialNB -alpha=1.0
决策树 tree DecisionTreeClassifier DecisionTreeRegressor +max_depth
随机森林 ensemble RandomForestClassifier RandomForestRegressor +n_estimators
梯度提升机 ensemble GradientBoostingClassifier GradientBoostingRegressor +n_estimators, +learning_rate
核支持向量机 svm SVC SVR kernel=‘rbf’, +C, +gamma
多层感知机 neural_network MLPClassifier MLPRegressor solver=‘lbfgs’, -alpha, hidden_layer_sizes

发表于 更新于 分类于 Valine： 本文字数： 1.8k 阅读时长 ≈ 2 分钟

shader里面有个函数叫smoothstep，是用来做平滑插值的，dx的文档对其介绍如下

smoothstep (DirectX HLSL)

Returns a smooth Hermite interpolation between 0 and 1, if x is in the range [min, max].

ret smoothstep(min, max, x)

Parameters

  • min

    [in] The minimum range of the x parameter.

  • max

    [in] The maximum range of the x parameter.

  • x

    [in] The specified value to be interpolated.

Return Value

Returns 0 if x is less than min; 1 if x is greater than max; otherwise, a value between 0 and 1 if x is in the range [min, max].

Remarks

Use the smoothstep HLSL intrinsic function to create a smooth transition between two values. For example, you can use this function to blend two colors smoothly.

可以看介绍里说了，Smoothstep就是使用的Hermite插值，
三次Hermite插值公式是

P(t)=(2∗t3−3∗t2+1)P0+(t3−2∗t2+t)M0+(t3−t2)M1+(−2∗t3+3∗t2)P1P(t) = (2*t^3 - 3*t^2 + 1)P0 + (t^3 - 2*t^2 + t)M0 + (t^3 - t^2)M1 + (-2*t^3 + 3*t^2)P1

其中P0是起始点，P1是终结点，M0是起始点处的方向，M1是终结点处的方向。参数t从0变化到1的过程中P(t)形成的轨迹构成了从P0到P1的平滑曲线，而且这个曲线两端顶点处的切向量就是M0，M1，还要说明的就是M0，M1的大小会影响到曲线的形状，可以把这个过程想象成一个机车从P0开到P1，M0，M1更像是速度的表示，当M0比较大时，在P0附近的曲线会沿M0方向冲出去更多一些才会弯曲。
Smoothstep插值的公式是

Smoothstep(t)=−2∗t3+3∗t2Smoothstep(t) = -2*t^3 + 3*t^2

对于dx文档中的参数，我们可以使用

t=(x−min)/(max−min)t = (x-min) / (max-min)

先计算得到t再使用前面的公式。

为什么Smoothstep的公式比Hermite简化的这么多，我尝试推导了一下，
把(0,0)代入P0，(1,1)代入P1，(1,0)代入M0，(1,0)代入M1，
用Px(t)表示Hermite插值的x分量,Py(t)表示Hermite插值的y分量，则有

Px(t)=(2∗t3−3∗t2+1)∗0+(t3−2∗t2+t)∗1+(t3−t2)∗1+(−2∗t3+3∗t2)∗1=tP_x(t) = (2*t^3 - 3*t^2 + 1)*0 + (t^3 - 2*t^2 + t)*1 + (t^3 - t^2)*1 + (-2*t^3 + 3*t^2)*1 = t

Py(t)=(2∗t3−3∗t2+1)∗0+(t3−2∗t2+t)∗0+(t3−t2)∗0+(−2∗t3+3∗t2)∗1=−2∗t3+3∗t2P_y(t) = (2*t^3 - 3*t^2 + 1)*0 + (t^3 - 2*t^2 + t)*0 + (t^3 - t^2)*0 + (-2*t^3 + 3*t^2)*1 = -2*t^3 + 3*t^2

再把参数t消掉就可以得到

Py=−2∗Px3+3∗Px2P_y = -2*Px^3 + 3*P_x^2

和Smoothstep插值公式是一致的。

我把这篇旧博文转过来主要为了测试在网页上渲染Markdown公式的表现 😛

发表于 更新于 分类于 Valine： 本文字数： 841 阅读时长 ≈ 1 分钟

* boost 标准库扩展，广为人知的“准”标准库
* pthread windows下的posix线程实现
* libcurl 文件传输库，支持多种协议。
* libeay32 OpenSSL Library
* libtidy,htmlcxx 解析html的库
* zlib 数据压缩库，本数以千计的软件广泛使用，已成为一种事实上的业界标准。
* freetype C接口的type2字体处理库
* libmad 一个编解码mp3的库
* libogg 一个编解码ogg音频格式的库
* libsnd 一个开源的编解码十多种音频格式的库
* ffmpeg 一个音视频格式编解码、转换的库
* FreeImage,CxImage 图像操作类库。它可以快捷地存取、显示、转换各种图像。
* libpng,libjpeg 图片的编码解码
* angelscript 一个类似lua的脚本引擎 其脚本风格类似于标准c语言
* flac/flac++ 一个编解码flac音频格式的库
* tinyxml,rapidxml,libxml 都是关于xml解析方面的
* luaplus,luabind 都是涉及绑定lua和c的库
* ode,bullet 开源的物理引擎库
* timidity 一个可以把mid音频格式转化为wav格式的库
* vlc 一个视频播放的库
* zthread 一个类型boost-thread,pthread的c风格的多线程库
* SDL 一个自由的跨平台的多媒体开发包，主要做音视频播放
* HGE Windows下基于d3d硬件加速的2d游戏引擎，基于DX8，已经停止维护很久了
* OpenCV 一个开源的图像处理库，实现了图像处理和计算机视觉方面的很多通用算法。
* mygui,cegui 都是游戏上使用的GUI系统
* Orge,irrlicht 都是开源的游戏中间件
* Qt,wxWidgets 开源的跨平台的C构架库，主要是做跨平台GUI
* loki 一个实验性质的c库
* ace 一个网络通信库
* FMOD 游戏音频引擎
* SQLite 一款轻型的数据库
* AmHttpSocket 基于WinAPI的简便http协议应用包