相關文章演算法

① 決策樹演算法-原理篇

關於決策樹演算法，我打算分兩篇來講，一篇講思想原理，另一篇直接擼碼來分析演算法。本篇為原理篇。
通過閱讀這篇文章，你可以學到：
1、決策樹的本質
2、決策樹的構造過程
3、決策樹的優化方向

決策樹根據使用目的分為：分類樹和回歸樹，其本質上是一樣的。本文只講分類樹。

決策樹，根據名字來解釋就是，使用樹型結構來模擬決策。
用圖形表示就是下面這樣。

其中橢圓形代表：特徵或屬性。長方形代表：類別結果。
面對一堆數據（含有特徵和類別），決策樹就是根據這些特徵（橢圓形）來給數據歸類（長方形）
例如，信用貸款問題，我根據《神奇動物在哪裡》的劇情給銀行造了個決策樹模型，如下圖：

然而，決定是否貸款可以根據很多特徵，然麻雞銀行選擇了：（1）是否房產價值>100w；（2）是否有其他值錢的抵押物；（3）月收入>10k；（4）是否結婚；這四個特徵，來決定是否給予貸款。
先不管是否合理，但可以肯定的是，決策樹做了特徵選擇工作，即選擇出類別區分度高的特徵。

由此可見， 決策樹其實是一種特徵選擇方法。 （特徵選擇有多種，決策樹屬於嵌入型特徵選擇，以後或許會講到，先給個圖）即選擇區分度高的特徵子集。

那麼， 從特徵選擇角度來看決策樹，決策樹就是嵌入型特徵選擇技術

同時，決策樹也是機器學習中經典分類器演算法，通過決策路徑，最終能確定實例屬於哪一類別。
那麼， 從分類器角度來看決策樹，決策樹就是樹型結構的分類模型

從人工智慧知識表示法角度來看，決策樹類似於if-then的產生式表示法。
那麼， 從知識表示角度來看決策樹，決策樹就是if-then規則的集合

由上面的例子可知，麻雞銀行通過決策樹模型來決定給哪些人貸款，這樣決定貸款的流程就是固定的，而不由人的主觀情感來決定。
那麼， 從使用者角度來看決策樹，決策樹就是規范流程的方法

最後我們再來看看決策樹的本質是什麼已經不重要了。
決策樹好像是一種思想，而通過應用在分類任務中從而成就了「決策樹演算法」。

下面內容還是繼續講解用於分類的「決策樹演算法」。

前面講了決策樹是一種 特徵選擇技術 。

既然決策樹就是一種特徵選擇的方法，那麼經典決策樹演算法其實就是使用了不同的特徵選擇方案。
如：
（1）ID3：使用信息增益作為特徵選擇
（2）C4.5：使用信息增益率作為特徵選擇
（3）CART：使用GINI系數作為特徵選擇
具體選擇的方法網上一大把，在這里我提供幾個鏈接，不細講。

但，不僅僅如此。
決策樹作為嵌入型特徵選擇技術結合了特徵選擇和分類演算法，根據特徵選擇如何生成分類模型也是決策樹的一部分。
其生成過程基本如下：

根據這三個步驟，可以確定決策樹由：（1）特徵選擇；（2）生成方法；（3）剪枝，組成。
決策樹中學習演算法與特徵選擇的關系如下圖所示：

原始特徵集合T：就是包含收集到的原始數據所有的特徵，例如：麻瓜銀行收集到與是否具有償還能力的所有特徵，如：是否結婚、是否擁有100w的房產、是否擁有汽車、是否有小孩、月收入是否>10k等等。
中間的虛線框就是特徵選擇過程，例如：ID3使用信息增益、C4.5使用信息增益率、CART使用GINI系數。
其中評價指標（如：信息增益）就是對特徵的要求，特徵需要滿足這種條件（一般是某個閾值），才能被選擇，而這一選擇過程嵌入在學習演算法中，最終被選擇的特徵子集也歸到學習演算法中去。
這就是抽象的決策樹生成過程，不論哪種演算法都是將這一抽象過程的具體化。
其具體演算法我將留在下一篇文章來講解。

而決策樹的剪枝，其實用得不是很多，因為很多情況下隨機森林能解決決策樹帶來的過擬合問題，因此在這里也不講了。

決策樹的優化主要也是圍繞決策樹生成過程的三個步驟來進行優化的。
樹型結構，可想而知，演算法效率決定於樹的深度，優化這方面主要從特徵選擇方向上優化。
提高分類性能是最重要的優化目標，其主要也是特徵選擇。
面對過擬合問題，一般使用剪枝來優化，如：李國和基於決策樹生成及剪枝的數據集優化及其應用。
同時，決策樹有很多不足，如：多值偏向、計算效率低下、對數據空缺較為敏感等，這方面的優化也有很多，大部分也是特徵選擇方向，如：陳沛玲使用粗糙集進行特徵降維。
由此，決策樹的優化方向大多都是特徵選擇方向，像ID3、C4.5、CART都是基於特徵選擇進行優化。

參考文獻
統計學習方法-李航
特徵選擇方法綜述-李郅琴
決策樹分類演算法優化研究_陳沛玲
基於決策樹生成及剪枝的數據集優化及其應用-李國和

② 文章自動打分演算法

文章自動打分簡稱 AES (Automated Essay Scoring)，AES 系統利用 NLP 技術自動對文章進行打分，可以減輕閱卷人員的負擔。目前有不少大型的考試都採用了 AES 演算法進行作文打分，例如 GRE 考試，GRE 考試會有一位閱卷老師和 AES 系統一起打分，如果 AES 的分數和閱卷老師的分數相差過大，才有再增加一位閱卷老師進行打分。本文主要介紹兩種比較經典的自動打分演算法。

自動打分演算法從優化目標或者損失函數來說大致可以分為三種：

傳統的自動打分演算法通常會人工設置很多特徵，例如語法錯誤，N 元組，單詞數量，句子長度等，然後訓練機器學習模型進行打分。目前也有很多使用了神經網路的方法，通過神經網路學習出文章的特徵。

下面介紹兩種打分演算法：

出自論文《Regression based Automated Essay Scoring》。給定很多需要打分的文章後，首先需要構造出文章的特徵，用到了人工設置特徵和向量空間特徵。

拼寫錯誤 Spelling Errors ：使用 pyenchant 包統計出拼寫錯誤單詞數量占總單詞數量的比例。

統計特徵 Statistical Features ：統計字元數量，單詞數量，句子數量，段落數量，停止詞數量，命名實體數量，標點符號數量 (反映文章的組織情況)，文本長度 (反映寫作流暢程度)，不同詞彙的數量與總單詞數的佔比 (反映詞彙量水平)。

詞性統計 POS count ：統計各種詞性出現的頻率，例如名詞，動詞，形容詞，副詞等，詞性通過 nltk 包獲取。

語法流暢特徵 Grammatical Fluency ：使用 link grammar (鏈語法) 解析句子，然後統計 links 的個數；統計 n 元組出現的概率；統計詞性 n 元組出現的概率。

可讀性 Readability ：可讀性分數是衡量文本組織以及文本句法和語義復雜程度的一個指標。採用了 Kincaid 可讀性分數作為一個特徵，計算公式如下

本體特徵 Ontological Features ：為每個句子打上標簽，例如研究、假設、主張、引用、支持和反對等。

可以將一篇文章投影到一個向量空間模型中 (VSM)，此時文章可以用向量空間中的一個特徵向量表示，例如可以用 one-hot 編碼表示一篇文章，長度等於詞彙表長度，如果一個單詞出現在文章中，則對應的位置置為 1，如下：

另外也可以使用 TF-IDF 向量表示文本，但是採用這種表示方式單詞之間不存在任何關聯，為了解決這個問題，文章中使用了一個單詞相關性矩陣 W 加上線性變換從而引入單詞之間的相關性。

單詞的相關性矩陣 W 通過 word2vec 生成的詞向量計算，即 W (i,j) = 單詞 i 和單詞 j 詞向量的餘弦相似度。

最後，為了考慮文章中單詞的順序問題，將文章拆分成 k 個段落，然後分別計算向量空間特徵，融合在一起。

得到上述特徵之後，採用 SVR 演算法進行回歸學習。數據集是 kaggle ASAP 比賽數據集，數據集包含 8 個集合的文章，評價指標採用 KAPPA 和相關系數，以下是一些實驗效果。

這是在 8 個集合上分別使用 linear kernel 和 rbf kernel 的效果。

這是和人類打分者的對比。

以下內容出自論文《Neural Networks for Automated Essay Grading》，可以採用回歸或者分類的方法進行訓練，模型如下圖所示。

論文中主要使用了三種方法構造出文章的特徵向量：

論文中主要用了三種神經網路結構，NN (前向神經網路)，LSTM 和 BiLSTM。所有的網路都會輸出一個向量 h(out)，根據 h(out) 構造出損失函數，下面分別是回歸和分類的損失函數。

回歸損失

分類損失

第一種模型：NN (前向神經網路)

使用了兩層前向神經網路，網路輸入的文章特徵向量是 Glove 詞向量的平均值或者訓練的詞向量平均值。h(out) 的計算公式如下。

第二種模型：LSTM

LSTM 模型接受的輸入是文章所有單詞的詞向量序列，然後將 LSTM 最後輸出的向量作為文章的特徵向量 h(out)。

第三種模型：BiLSTM

因為文章通常比較長，單向的 LSTM 容易丟失前面的信息，因此作者也使用了 BiLSTM 模型，將前向 LSTM 和後向 LSTM 模型的輸出加在一起作為 h(out)。

添加 TF-IDF 向量

以上模型的輸出 h(out) 都可以再加上 TF-IDF 向量提升性能，首先需要對 TF-IDF 向量降維，然後和模型的輸出拼接在一起，如下圖所示 (BiLSTM 為例子)。

《Regression based Automated Essay Scoring》
《Neural Networks for Automated Essay Grading》

③ 機器學習演算法之神經網路

在學習了機器學習的相關知識以後，我們知道其中的演算法有很多種，比如回歸演算法、K近鄰演算法等等，這些都是需要大家掌握的演算法，而神經網路演算法是一個十分實用的演算法，在這篇文章中我們就給大家介紹一下機器學習演算法中的神經網路演算法知識。
那麼什麼是神經網路演算法呢？其實神經網路也稱之為人工神經網路，簡單就是ANN，而演算法是80年代機器學習界非常流行的演算法，不過在90年代中途衰落。現在，隨著深度學習的發展，神經網路再次出現在大家的視野中，重新成為最強大的機器學習演算法之一。而神經網路的誕生起源於對大腦工作機理的研究。早期生物界學者們使用神經網路來模擬大腦。機器學習的學者們使用神經網路進行機器學習的實驗，發現在視覺與語音的識別上效果都相當好。
那麼神經網路的學習機理是什麼呢？簡單來說，就是分解與整合。我們可以通過一個例子進行解答這個問題，比如說，我們可以把一個正方形分解為四個折線進入視覺處理的下一層中。四個神經元分別處理一個折線。每個折線再繼續被分解為兩條直線，每條直線再被分解為黑白兩個面。於是，一個復雜的圖像變成了大量的細節進入神經元，神經元處理以後再進行整合，最後得出了看到的是正方形的結論。這就是大腦視覺識別的機理，也是神經網路工作的機理。
那麼神經網路的邏輯架構是什麼呢？其實一個簡單的神經網路的邏輯架構分成輸入層，隱藏層，和輸出層。輸入層負責接收信號，隱藏層負責對數據的分解與處理，最後的結果被整合到輸出層。每層中的一個圓代表一個處理單元，可以認為是模擬了一個神經元，若干個處理單元組成了一個層，若干個層再組成了一個網路，這就是所謂的神經網路知識。
當然，在神經網路中，其實每一個處理單元事實上就是一個邏輯回歸模型，邏輯回歸模型接收上層的輸入，這樣，把模型的預測結果作為輸出傳輸到下一個層次。這些過程，神經網路可以完成非常復雜的非線性分類。在神經網路在圖像識別領域的一個著名應用，而這個程序叫做LeNet，是一個基於多個隱層構建的神經網路。通過LeNet可以識別多種手寫數字，並且達到很高的識別精度與擁有較好的魯棒性。這也是神經網路中最著名的應用。
在這篇文章中我們給大家介紹了很多關於神經網路的相關知識，通過這些知識我們可以更好地了解神經網路演算法。當然，我們要想了解機器學習還需要掌握更多的演算法。

④ 嵌入式工程師面試中常出現的演算法

嵌入式工程師面試中常出現的演算法

嵌入式系統是以應用為中心，以計算機技術為基礎，並且軟硬體可裁剪，適用於應用系統對功能、可靠性、成本、體積、功耗有嚴格要求的專用計算機系統。下面我為大家整理了關於嵌入式工程師面試中經常出現的演算法文章，希望對你有所幫助。

二分查找的代碼.

int bfind(int* a,int len,int val)

{

int m = len/2;

int l = 0;

int r = len;

while(l!=m && r!= m)

{

if(a[m] > val)

{

r = m;

m = (m+l)/2;

}

else if(a[m] < val)

{

l = m;

m = (m+r)/2;

}

else

return m;

}

return -1; //沒有找到

}

寫出在母串中查找子串出現次數的代碼.

int count1(char* str,char* s)

{

char* s1;

char* s2;

int count = 0;

while(*str!='')

{

s1 = str;

s2 = s;

while(*s2 == *s1&&(*s2!='')&&(*s1!='0'))

{

s2++;

s1++;

}

if(*s2 == '')

count++;

str++;

}

return count;

}

查找第一個匹配子串位置,如果返回的是s1長度len1表示沒有找到

size_t find(char* s1,char* s2)

{

size_t i=0;

size_t len1 = strlen(s1)

size_t len2 = strlen(s2);

if(len1-len2<0) return len1;

for(;i {

size_t m = i;

for(size_t j=0;j {

if(s1[m]!=s2[j])

break;

m++;

}

if(j==len)

break;

}

return i }

寫出快速排序或者某種排序演算法代碼

快速排序:

int partition(int* a,int l,int r)

{

int i=l-1,j=r,v=a[r];

while(1)

{

while(a[++i] while(a[--j]>v) if(j<=i) break;

if(i>=j)

break;

swap(a[i],a[j]);

}

swap(a[i],a[r]);

return i;

}

void qsort(int* a,int l,int r)

{

if(l>=r) return;

int i = partition(a,l,r);

qsort(a,l,i-1);

qsort(a,i+1,r);

}

冒泡排序:

void buble(int *a,int n)

{

for(int i=0;i {

for(int j=1;j {

if(a[j] {

int temp=a[j];

a[j] = a[j-1];

a[j-1] = temp;

}

}

}

}

插入排序：

void insertsort(int* a,int n)

{

int key;

for(int j=1;j {

key = a[j];

for(int i=j-1;i>=0&&a[i]>key;i--)

{

a[i+1] = a[i];

}

a[i+1] = key;

}

}

出現次數相當頻繁

實現strcmp函數

int strcmp11(char* l,char* r)

{

assert(l!=0&&r!=0);

while(*l == *r &&*l != '') l++,r++;

if(*l > *r)

return 1;

else if(*l == *r)

return 0;

return -1;

}

實現字元串翻轉

void reserve(char* str)

{

assert(str != NULL);

char * p1 = str;

char * p2 = str-1;

while(*++p2); //一般要求不能使用strlen

p2 -= 1;

while(p1 {

char c = *p1;

*p1++ = *p2;

*p2-- = c;

}

}

將一個單鏈表逆序

struct list_node

{

list_node(int a,list_node* b):data(a),next(b) //這個為了測試方便

{}

int data;

list_node* next;

};

void reserve(list_node* phead)

{

list_node* p = phead->next;

if(p == NULL || p->next == NULL) return; //只有頭節點或一個節點

list_node* p1=p->next;

p->next=NULL;

while(p1!=NULL)

{

p = p1->next;

p1->next = phead->next;

phead->next = p1;

p1 = p;

}

}

測試程序：

list lt;

lt.phead = new list_node(0,0);

lt.phead->next = new list_node(1,0);

lt.phead->next->next = new list_node(2,0);

lt.phead->next->next->next = new list_node(3,0);

lt.reserve();

list_node * p = lt.phead;

while(p)

{

coutnext;

}

循環鏈表的節點對換和刪除。

//雙向循環

list_node* earse(list_node* node)

{

// if(node == rear) return node->next; //對於頭節點可判斷也可不判斷。最好加上

list_node* next = node->next;

next->prev = node->prev;

node->prev->next = next;

delete node;

retrun next;

}

//單項循環

list_node* earse(list_node* node)

{

// if(node == rear) return node->next; //對於頭節點可判斷也可不判斷。最好加上

list_node* p = rear;

while(p->next != node) p=p->next;

p->next = node->next;

delete node;

retrun p->next;

}

將一個數字字元串轉換為數字."1234" -->1234

int atoii(char* s)

{

assert(s!=NULL);

int num = 0;

int temp;

while(*s>'0' && *s<'9')

{

num *= 10;

num += *s-'0';

s++;

}

return num;

}

出現次數相當頻繁

.實現任意長度的整數相加或者相乘功能。

void bigadd(char* num,char* str,int len)

{

for(int i=len;i>0;i--)

{

num[i] += str[i];

int j = i;

while(num[j]>=10)

{

num[j--] -= 10;

num[j] += 1;

}

}

}

.寫函數完成內存的拷貝

void* memcpy( void *dst, const void *src, unsigned int len )

{

register char *d;

register char *s;

if (len == 0)

return dst;

if ( dst > src ) //考慮覆蓋情況

{

d = (char *)dst + len - 1;

s = (char *)src + len - 1;

while ( len >= 4 ) //循環展開，提高執行效率

{

*d-- = *s--;

*d-- = *s--;

*d-- = *s--;

*d-- = *s--;

len -= 4;

}

while ( len-- )

{

*d-- = *s--;

}

}

else if ( dst < src )

{

d = (char *)dst;

s = (char *)src;

while ( len >= 4 )

{

*d++ = *s++;

*d++ = *s++;

*d++ = *s++;

*d++ = *s++;

len -= 4;

}

while ( len-- )

{

*d++ = *s++;

}

}

return dst;

}

出現次數相當頻繁

編寫類String的構造函數、析構函數和賦值函數，已知類String的原型為：

class String

{

public:

String(const char *str = NULL); // 普通構造函數

String(const String &other); // 拷貝構造函數

~ String(void); // 析構函數

String & operate =(const String &other); // 賦值函數

private:

char *m_data; // 用於保存字元串

};

解答：

//普通構造函數

String::String(const char *str)

{

if(str==NULL)

{

m_data = new char[1]; // 得分點：對空字元串自動申請存放結束標志''的`空

//加分點：對m_data加NULL 判斷

*m_data = '';

}

else

{

int length = strlen(str);

m_data = new char[length+1]; // 若能加 NULL 判斷則更好

strcpy(m_data, str);

}

}

// String的析構函數

String::~String(void)

{

delete [] m_data; // 或delete m_data;

}

//拷貝構造函數

String::String(const String &other) // 得分點：輸入參數為const型

{

int length = strlen(other.m_data);

m_data = new char[length+1]; //加分點：對m_data加NULL 判斷

strcpy(m_data, other.m_data);

}

//賦值函數

String & String::operate =(const String &other) // 得分點：輸入參數為const型

{

if(this == &other) //得分點：檢查自賦值

return *this;

delete [] m_data; //得分點：釋放原有的內存資源

int length = strlen( other.m_data );

m_data = new char[length+1]; //加分點：對m_data加NULL 判斷

strcpy( m_data, other.m_data );

return *this; //得分點：返回本對象的引用

}

剖析：

能夠准確無誤地編寫出String類的構造函數、拷貝構造函數、賦值函數和析構函數的面試者至少已經具備了C++基本功的60%以上!

在這個類中包括了指針類成員變數m_data，當類中包括指針類成員變數時，一定要重載其拷貝構造函數、賦值函數和析構函數，這既是對C++程序員的基本要求，也是《EffectiveC++》中特別強調的條款。

實現strcpy

char * strcpy( char *strDest, const char *strSrc )

{

assert( (strDest != NULL) && (strSrc != NULL) );

char *address = strDest;

while( (*strDest++ = * strSrc++) != ‘’ );

return address;

}

編寫一個函數，作用是把一個char組成的字元串循環右移n個。比如原來是“abcdefghi”如果n=2，移位後應該是“hiabcdefgh”

函數頭是這樣的：

//pStr是指向以''結尾的字元串的指針

//steps是要求移動的n

void LoopMove ( char * pStr, int steps )

{

//請填充...

}

解答：

正確解答1：

void LoopMove ( char *pStr, int steps )

{

int n = strlen( pStr ) - steps;

char tmp[MAX_LEN];

strcpy ( tmp, pStr + n );

strcpy ( tmp + steps, pStr);

*( tmp + strlen ( pStr ) ) = '';

strcpy( pStr, tmp );

}

正確解答2：

void LoopMove ( char *pStr, int steps )

{

int n = strlen( pStr ) - steps;

char tmp[MAX_LEN];

memcpy( tmp, pStr + n, steps );

memcpy(pStr + steps, pStr, n );

memcpy(pStr, tmp, steps );

}

;

⑤ 如何用Python分析一篇文章的關鍵詞有什麼相關的庫或演算法

應該用Python的正則表達式模塊re
示例：
#...
import re
with open('test.txt','r') as txt:
f = txt.read()
print re.match('正則表達式/關鍵詞',f)
#...

具體可以多了解一下這個模塊，查詢有三種方法，一個是match匹配，也是比較常用的
然後還有search和findall

個人覺得這個人的正則表達式介紹文章還不錯，推薦你參考：
http://blog.csdn.net/theminority/article/details/7629227