內(nèi)容

• 概述
• 1. 如何在交易中運(yùn)用該方法
• 2. FP-Growth 算法實(shí)現(xiàn)
• 2.1. 樹的節(jié)點(diǎn)類實(shí)現(xiàn)
• 2.2. 關(guān)聯(lián)規(guī)則挖掘類的實(shí)現(xiàn)
• 3. 測試
• 結(jié)束語
• 參考文獻(xiàn)列表
• 本文中用到的程序

概述

在前一篇文章中，我們開始學(xué)習(xí)隸屬無監(jiān)督學(xué)習(xí)方法的關(guān)聯(lián)規(guī)則挖掘算法。 我們研究了兩種算法來解決這類問題：Apriori 和 FP-Growth。 Apriori 算法的瓶頸在于其大量數(shù)據(jù)庫的調(diào)用，旨在判定對于頻繁形態(tài)候選者的支持度。 FP-Growth 方法則通過構(gòu)建包含整個(gè)數(shù)據(jù)庫的樹來解決這個(gè)問題。 所有更進(jìn)一步的操作都是依 FP 樹執(zhí)行的，無需訪問數(shù)據(jù)庫。 由于 FP 樹位于內(nèi)存當(dāng)中，這提高了問題解決速度。訪問它比完整迭代數(shù)據(jù)庫要快捷得多。

1. 如何在交易中運(yùn)用該方法

在繼續(xù)利用 MQL5 構(gòu)建關(guān)聯(lián)規(guī)則挖掘算法之前，我們來研究一下如何在交易中運(yùn)用它們。

創(chuàng)建關(guān)聯(lián)規(guī)則挖掘算法來搜索數(shù)據(jù)庫中二元特征之間的穩(wěn)定依賴關(guān)系。 因此，這些算法可用來尋找各種特征之間的穩(wěn)定關(guān)系。 這可以是由多個(gè)指標(biāo)和/或工具組成的各種形態(tài)。 算法不關(guān)心每個(gè)單獨(dú)的特征是否代表不同的度量，或者它是不同時(shí)間段中相同度量的值。 算法評估時(shí)把每個(gè)特征均視為獨(dú)立的。 因此，我們可以嘗試將此算法與監(jiān)督學(xué)習(xí)方法的開發(fā)結(jié)合起來。 我們在歷史數(shù)據(jù)的訓(xùn)練樣本中添加一些目標(biāo)特性。 算法應(yīng)該搜索關(guān)聯(lián)規(guī)則，這將導(dǎo)致我們的目標(biāo)值形成。

我們已有了一個(gè)算法，和如何運(yùn)用它來解決實(shí)際問題的思路。 我們來看看如何利用 MQL5 實(shí)現(xiàn)它。 然后我們將在實(shí)踐中檢測這個(gè)思路。

2. FP-Growth 算法實(shí)現(xiàn)

為了實(shí)現(xiàn)上一篇文章中研究的 FP-Growth 算法，我們要記住其構(gòu)造是基于決策樹的。 MQL5 標(biāo)準(zhǔn)庫擁有構(gòu)建二叉樹的 CTree 類。 不幸的是，二叉樹選項(xiàng)對我們來說并不完全方便，因?yàn)橐豢?FP 樹的一個(gè)節(jié)點(diǎn)的分支數(shù)可以超過 2 個(gè)（二元實(shí)現(xiàn)中的最大可用分支數(shù)）。 因此，在構(gòu)建算法本身之前，我們先創(chuàng)建 CMyTreeNode 類來實(shí)現(xiàn)擁有多個(gè)分支的樹節(jié)點(diǎn)。

2.1. 樹的節(jié)點(diǎn)類實(shí)現(xiàn)

該類將從動(dòng)態(tài)對象數(shù)組 CArrayObj 的標(biāo)準(zhǔn) MQL5 類派生而來。 這個(gè)類之所以被選為父類，是因?yàn)樗鼡碛信c創(chuàng)建和維護(hù)動(dòng)態(tài)對象數(shù)組相關(guān)的所需功能，在我們的例子中，分支節(jié)點(diǎn)其實(shí)就是動(dòng)態(tài)對象數(shù)組。

此外，為了實(shí)現(xiàn)算法所需的功能，類中已加入了三個(gè)新變量：

• m_cParent — 指向上一個(gè)父節(jié)點(diǎn)對象的指針。 對應(yīng)樹根，它將為空
• m_iIndex — 源數(shù)據(jù)庫中特征的索引；用于識(shí)別特征
• m_dSupport — 接收特征支持度值的變量

class CMyTreeNode : public CArrayObj
  {
protected:
   CMyTreeNode      *m_cParent;
   ulong             m_iIndex;
   double            m_dSupport;

public:
                     CMyTreeNode();
                    ~CMyTreeNode();
  }

在類構(gòu)造函數(shù)中，設(shè)置變量的初始值，并清除動(dòng)態(tài)數(shù)組。 將類析構(gòu)函數(shù)保留為空。

CMyTreeNode::CMyTreeNode() :  m_iIndex(ULONG_MAX),
                              m_dSupport(0)
  {
   Clear();
  }

為了操控隱藏的類變量，我們將創(chuàng)建一些方法，這些方法將在 FP-Growth 算法的創(chuàng)建過程中用到。 我還會(huì)提供方法目的解釋及其用途。

class CMyTreeNode : public CArrayObj
  {
   ........
public:
   ........
   //--- methods of access to protected data
   CMyTreeNode*      Parent(void)           const { return(m_cParent); }
   void              Parent(CMyTreeNode *node)  {  m_cParent = node; }
   void              IncreaseSupport(double support)  { m_dSupport += support; }
   double            GetSupport(void)       {  return m_dSupport;  }
   void              SetSupport(double support)       { m_dSupport = support;  }
   ulong             ID(void)             {  return m_iIndex;  }
   void              ID(ulong ID)         {  m_iIndex = ID; }
  };

為了計(jì)算置信水平，我們創(chuàng)建 GetConfidence 方法。 在其中，我們首先檢查指向前置節(jié)點(diǎn)的指針，如果它有效，則將當(dāng)前節(jié)點(diǎn)支持度除以父節(jié)點(diǎn)支持度。

注意，F(xiàn)P 樹構(gòu)建算法的組織方式是，任何節(jié)點(diǎn)的支持度都不能大于父節(jié)點(diǎn)的支持度。 因此，方法操作的結(jié)果將始終為正值，并且不會(huì)大于 1。

由于樹節(jié)點(diǎn)是基于現(xiàn)有業(yè)務(wù)添加的，所以我們沒有除零檢查。 因此，如果一個(gè)節(jié)點(diǎn)在樹中，那么它的特征在數(shù)據(jù)庫中至少出現(xiàn)過一次，且它的支持度最低。

double CMyTreeNode::GetConfidence(void)
  {
   CMyTreeNode *parent = Parent();
   if(!parent)
      return 1;
//---
   double result = m_dSupport / parent.GetSupport();
   return result;
  }

此外，我們添加了一個(gè)創(chuàng)建新分支節(jié)點(diǎn)的 AddNode 方法。 在方法參數(shù)中，我們傳遞訓(xùn)練樣本源數(shù)據(jù)庫中的特征 ID，和節(jié)點(diǎn)的支持度。 該方法返回指向所創(chuàng)建對象的指針。

在方法實(shí)體中，我們創(chuàng)建樹節(jié)點(diǎn)的新實(shí)例，并立即檢查操作結(jié)果。 如果發(fā)生錯(cuò)誤，則返回?zé)o效的對象指針。

接下來，我們指定所創(chuàng)建節(jié)點(diǎn)的 ID，并將指向當(dāng)前對象的指針傳遞給它，作為父對象。

將新對象添加到當(dāng)前節(jié)點(diǎn)的動(dòng)態(tài)數(shù)組中，并檢查操作結(jié)果。 如果往數(shù)組中添加對象時(shí)出錯(cuò)，則刪除所創(chuàng)建對象，并退出方法，同時(shí)返回?zé)o效指針。

在方法結(jié)束時(shí)，將參數(shù)中指定的支持度保存到新對象當(dāng)中，然后退出該方法。

CMyTreeNode *CMyTreeNode::AddNode(const ulong ID, double support = 0)
  {
   CMyTreeNode *node = new CMyTreeNode();
   if(!node)
      return node;
   node.ID(ID);
   if(!Add(node))
     {
      delete node;
      return node;
     }
   node.Parent(GetPointer(this));
//---
   if(support > 0)
      node.SetSupport(support);
   return node;
  }

一旦我們創(chuàng)建了一個(gè)新對象，我們應(yīng)該能夠刪除它。 父類中已存在依據(jù)動(dòng)態(tài)數(shù)組中的索引刪除對象的方法。 為了擴(kuò)展功能，我們創(chuàng)建 DeleteNode 方法，并按功能 ID 刪除節(jié)點(diǎn)。

該方法接收要?jiǎng)h除的功能 ID，并返回操作的布爾結(jié)果。

在方法實(shí)體中，實(shí)現(xiàn)循環(huán)以在當(dāng)前節(jié)點(diǎn)的動(dòng)態(tài)數(shù)組中查找匹配指定 ID 的節(jié)點(diǎn)。 循環(huán)將迭代遍歷從 0 到 m_data_total 變量值范圍內(nèi)的元素。 該變量包含動(dòng)態(tài)數(shù)組的活動(dòng)元素?cái)?shù)量，并由父類管控。

在方法實(shí)體中，從動(dòng)態(tài)數(shù)組中提取下一個(gè)元素，并驗(yàn)證指針。 通過調(diào)用父類的 Delete 方法（含有指向欲刪除元素的索引），可以立即刪除含有無效指針的元素。

注意，Delete 方法返回操作的布爾結(jié)果。 如果成功地從動(dòng)態(tài)數(shù)組中刪除了一個(gè)元素，則減少循環(huán)迭代的計(jì)數(shù)器，并移動(dòng)到下一個(gè)數(shù)組。 我們只減少循環(huán)迭代計(jì)數(shù)器，而不更改 m_data_total 變量值。 這是因?yàn)樗闹翟?Delete 父類的方法中已經(jīng)更改。

如果在從動(dòng)態(tài)數(shù)組中刪除無效元素時(shí)發(fā)生錯(cuò)誤，只需移動(dòng)到數(shù)組的下一個(gè)元素即可。 我們不會(huì)終止方法時(shí)返回 false 結(jié)果，因?yàn)榉椒ㄈ蝿?wù)不是從無效對象中清除動(dòng)態(tài)數(shù)組。 這只是一個(gè)輔助功能。 該方法的主要任務(wù)是刪除特定元素。 因此，我們繼續(xù)執(zhí)行方法，直至發(fā)現(xiàn)所需的元素。

當(dāng)找到動(dòng)態(tài)數(shù)組的所需元素后，調(diào)用前面提到的父類的 Delete 方法。 這一次，我們在退出方法的同時(shí)返回對象刪除結(jié)果。

如果迭代遍歷動(dòng)態(tài)數(shù)組的所有元素后找不到該元素，請采用 false 結(jié)果退出該方法。

bool CMyTreeNode::DeleteNode(const ulong ID)
  {
   for(int i = 0; i < m_data_total; i++)
     {
      CMyTreeNode *temp = m_data[i];
      if(!temp)
        {
         if(!Delete(i))
            continue;
         return DeleteNode(ID);
        }
      if(temp.ID() != ID)
         continue;
      return Delete(i);
     }
//---
   return false;
  }

進(jìn)一步討論樹節(jié)點(diǎn) CMyTreeNode 新類的有關(guān)方法，我想提請您注意 Mining 方法。 此方法負(fù)責(zé)在 FP 樹中查找我們正在分析的特征的路徑。 在我們繼續(xù)講述方法的算法之前，我必須說，它在創(chuàng)建時(shí)已考慮到交易中的預(yù)期用途。 因此，它稍微偏離了基本算法。

首先，我們不會(huì)判定所有特性的關(guān)聯(lián)規(guī)則，而只為目標(biāo)值判定關(guān)聯(lián)規(guī)則。 因此，在構(gòu)建規(guī)則樹時(shí)，我們很可能會(huì)遇到這樣的情況，即所需的特征不是葉子，而是包含路徑中后續(xù)元素的節(jié)點(diǎn)。 但我們不能忽略后續(xù)節(jié)點(diǎn)，因?yàn)樗鼈儠?huì)增加目標(biāo)結(jié)果的可能性。 因此，在選擇所分析特征的路徑時(shí)，應(yīng)考慮它們。

構(gòu)造此方法時(shí)，我曾注意的另一點(diǎn)如下。 根據(jù)該算法，我們首先需要在 FP 樹中找到所分析特征的所有路徑。 然后，我們可以計(jì)算選定路徑中每個(gè)特征的支持度值。 我決定在一個(gè)方法中執(zhí)行這兩個(gè)子任務(wù)。

請注意，為了構(gòu)建 FP 樹，僅計(jì)劃采用 CMyTreeNode 類實(shí)例。 因此，為了執(zhí)行深度優(yōu)先搜索，我們將采用遞歸方法調(diào)用。

現(xiàn)在，我們看看在類的 Mining 方法中如何實(shí)現(xiàn)這些任務(wù)。 在方法參數(shù)中，我們傳遞指向一個(gè)向量的指針，該向量是為了寫入元素支持度值，一個(gè)為了寫入路徑的矩陣，所分析特征的標(biāo)識(shí)符，以及最小置信級別。 該方法將返回操作的布爾結(jié)果。

在方法實(shí)體中，首先檢查欲分析節(jié)點(diǎn)是否是期望的特征。 為此，取節(jié)點(diǎn) ID，并與參數(shù)中接收到的期望節(jié)點(diǎn) ID 進(jìn)行比較。 如果它們相等，則檢查當(dāng)前分支中節(jié)點(diǎn)的置信級別。 該級別是調(diào)用前面研究的 GetConfidence 方法來判定的。 置信水平不得小于允許的最小值。 否則，以 true 結(jié)果退出方法。

bool CMyTreeNode::Mining(vector &supports, matrix &paths, const ulong ID, double min_conf)
  {
   if(ID == m_iIndex)
      if(GetConfidence() < min_conf)
         return true;

下一個(gè)模塊實(shí)現(xiàn)全樹的進(jìn)一步深度搜索。 在此，首先將當(dāng)前節(jié)點(diǎn)的支持度值保存到一個(gè)局部變量當(dāng)中。 然后，運(yùn)行一個(gè)循環(huán)，從當(dāng)前節(jié)點(diǎn)到全樹深度遍歷所有分支。 該方法遞歸調(diào)用搜索所有分支。

注意，采用遞歸方法，我們只傳遞期望的標(biāo)識(shí)符，直到找到相應(yīng)的節(jié)點(diǎn)。 此后，我們將 ULONG_MAX 常量傳遞到全樹深度，替代期望的標(biāo)識(shí)符。 這是因?yàn)橛捎?FP 樹構(gòu)造的特殊性，在我們找到期望項(xiàng)的路徑之前，形態(tài)置信度可能小于 100%。 隨著我們沿著這條路徑繼續(xù)前進(jìn)，期望特征的概率將是 100%。 否則，我們將構(gòu)建一條不同的路徑，繞過期望的節(jié)點(diǎn)。

當(dāng)然，當(dāng)我們采用自定義算法時(shí)，這種情況就被排除在外。 當(dāng)判定所有特征的規(guī)則時(shí)，我們開始處理 FP 樹中任何節(jié)點(diǎn)的時(shí)候，它將是一個(gè)沒有后續(xù)節(jié)點(diǎn)的葉片。 這是因?yàn)樗兄С侄容^低的特征都將被處理，并從樹中刪除。

因此，當(dāng)我們偏離算法時(shí)，我們必須評估該變化對整個(gè)過程的影響，并對算法進(jìn)行相應(yīng)調(diào)整。 在這種情況下，我們必須將包含期望特征的所有路徑添加到列表中。 這是從期望特征到樹根的路徑，以及從任何后續(xù)節(jié)點(diǎn)路過期望特征至樹根的所有路徑。 為此目的，我們需要通知其它節(jié)點(diǎn)，在節(jié)點(diǎn)和樹根之間找到了期望的特征。 當(dāng)期望特征的 ID 更改為 ULONG_MAX 常量時(shí)，會(huì)出現(xiàn)此類標(biāo)志。

在遞歸方法得到肯定結(jié)果之后，對于下一個(gè)節(jié)點(diǎn)，我們從循環(huán)之前創(chuàng)建的局部變量中減去當(dāng)前節(jié)點(diǎn)的支持度值。 如果下一個(gè)節(jié)點(diǎn)I D 等于期望 ID，則刪除已處理的節(jié)點(diǎn)。

   double support = m_dSupport;
   for(int i = 0; i < m_data_total; i++)
     {
      CMyTreeNode *temp = m_data[i];
      if(!temp)
        {
         if(Delete(i))
            i--;
         continue;
        }
      if(!temp.Mining(supports, paths, (ID == m_iIndex ? ULONG_MAX : ID), min_conf))
         return false;
      support -= temp.GetSupport();
      if(temp.ID() == ID)
         if(Delete(i))
            i--;
     }

您可看到，在前面的模塊中，我們只針對后續(xù)節(jié)點(diǎn)遞歸調(diào)用了相同的方法，但我們沒有保存找到的路徑。 保存動(dòng)作將在下一個(gè)方法模塊中執(zhí)行。 對于擁有期望屬性的節(jié)點(diǎn)和后續(xù)節(jié)點(diǎn)，將執(zhí)行該模塊。 為此，我們需要檢查當(dāng)前節(jié)點(diǎn)的 ID，和參數(shù)中接收到的 ID。 此外，遞歸方法執(zhí)行后對當(dāng)前節(jié)點(diǎn)的支持度必須大于 “0”。 此外，當(dāng)前節(jié)點(diǎn)不能是根節(jié)點(diǎn)。 這意味著它必須至少有一個(gè)前置節(jié)點(diǎn)。 這是因?yàn)槲覀冃枰玫揭恍〇|西作為規(guī)則的先行詞。

如果控件成功傳遞，則將路徑矩陣的大小增加 1 行，并在添加的行中填入零值。

接下來，實(shí)現(xiàn)從當(dāng)前節(jié)點(diǎn)到樹根的擴(kuò)散循環(huán)。 取我們的路徑線中當(dāng)前節(jié)點(diǎn)的剩余支持度，分配給當(dāng)前和所有前置節(jié)點(diǎn)。 此外，在相應(yīng)項(xiàng)的累積支持度向量中添加相同的值。

父迭代完成后，退出方法，并返回肯定結(jié)果。

   if(ID == m_iIndex || ID == ULONG_MAX)
      if(support > 0 && !!m_cParent)
        {
         CMyTreeNode *parent = m_cParent;
         ulong row = paths.Rows();
         if(!paths.Resize(row + 1, paths.Cols()))
            return false;
         if(!paths.Row(vector::Zeros(paths.Cols()), row))
            return false;
         supports[m_iIndex] += support;
         while(!!parent)
           {
            if(parent.ID() != ULONG_MAX)
              {
               supports[parent.ID()] += support;
               paths[row, parent.ID()] = support;
              }
            parent = parent.Parent();
           }
        }
//---
   return true;
  }

我用一個(gè)小例子解釋一下這個(gè)方法是如何工作的，因?yàn)樗臉?gòu)造稍微超出了上面講述的 PF-Growth 算法的范圍。 假設(shè)源數(shù)據(jù)庫內(nèi)含有以下業(yè)務(wù): "AB" 重復(fù)兩次，一次 "ABC"，"ABCD" 重復(fù)三次，以及一次 "ABCDE". 結(jié)果就是，F(xiàn)P 樹中形成了以下路徑： "A7-B7-C5-D4-E1"。 當(dāng)分析項(xiàng)目 “C” 時(shí)，我們需要從樹中恢復(fù)包含此項(xiàng)目的所有路徑。

我們開始先從根元素 “a” 調(diào)用一個(gè)方法，并指導(dǎo)它去查找 "C"。 在此我們遞歸調(diào)用節(jié)點(diǎn)的方法 "B"。 繼續(xù)直到葉片 "E"。 鑒于 "E" 葉片沒有后續(xù)節(jié)點(diǎn)，那么從方法的模塊 2 開始處理，并寫入路徑。 此處，我們首先保存 "ABCDE" 路徑，并為所有結(jié)點(diǎn)寫入支持度 1。 這意味著源數(shù)據(jù)庫中有 1 條這樣的路徑。 然后退出方法，將控制權(quán)轉(zhuǎn)交給更高級別。

在 "D" 節(jié)點(diǎn)級別保存路徑 "ABCD"。 從 "D" 節(jié)點(diǎn)的支持度，減去 "E" 葉片的支持度 (4-1=3)。 為這條路徑上的所有項(xiàng)，登記該結(jié)果值作為支持度。 如您所見，這對應(yīng)于初始數(shù)據(jù)，其中我們在訓(xùn)練樣本中有 3 筆相同的業(yè)務(wù)。 我們用項(xiàng)目支持度值，來替代重復(fù)業(yè)務(wù)三次。

同樣，保存路徑 “ABC”，支持度等于 1。 路徑 "AB" 未保存，因?yàn)樗话治龅奶卣鳌?/span>

在后附的文件 MyTreeNode.mqh 中查找所有類方法的完整代碼。

2.2. 關(guān)聯(lián)規(guī)則挖掘類的實(shí)現(xiàn)

我們繼續(xù)構(gòu)建 FP-Growth 關(guān)聯(lián)規(guī)則挖掘算法。 主要功能將在另一個(gè)類 CAssocRules 中實(shí)現(xiàn)。 這個(gè)類的結(jié)構(gòu)如下所示。 正如您所看到的，大多數(shù)方法都隱藏在“引擎蓋下”。 但首要之事依然是首要。

class CAssocRules : public CObject
  {
protected:
   CMyTreeNode       m_cRoot;
   CMyTreeNode       m_cBuyRules;
   CMyTreeNode       m_cSellRules;
   vector            m_vMin;
   vector            m_vStep;
   int               m_iSections;
   matrix            m_mPositions;
   matrix            m_BuyPositions;
   matrix            m_SellPositions;
   //---
   bool              NewPath(CMyTreeNode *root, matrix &path);
   CMyTreeNode      *CheckPath(CMyTreeNode *root, vector &path);
   //---
   bool              PrepareData(matrix &data, matrix &bin_data, 
                                 vector &buy, vector &sell,
                                 const int sections = 10, const double min_sup = 0.03);
   matrix            CreatePath(vector &bin_data, matrix &positions);
   matrix            CreatePositions(vector &support, const double min_sup = 0.03);
   bool              GrowsTree(CMyTreeNode *root, matrix &bin_data, matrix &positions);
   double            Probability(CMyTreeNode *root, vector &data, matrix &positions);

public:
                     CAssocRules();
                    ~CAssocRules();
   //---
   bool              CreateRules(matrix &data, vector &buy, 
                                 vector &sell, int sections = 10, 
                                 double min_freq = 0.03,
                                 double min_prob = 0.3);
   bool              Probability(vector &data, double &buy, double &sell);
   //--- methods for working with files
   virtual bool      Save(const int file_handle);
   virtual bool      Load(const int file_handle);
   virtual bool      Save(const string file_name);
   virtual bool      Load(const string file_name);
  };

在類變量中，有上述樹節(jié)點(diǎn)的三個(gè)實(shí)例：

• m_cRoot — 我們將用它來記錄我們的 FP 樹
• m_cBuyRules — 這個(gè)將被用來記錄購買規(guī)則
• m_cSellRules — 這個(gè)用于賣出規(guī)則

矩陣 m_mPositions、m_BuyPositions 和 m_SellPositions 將包含按降序排序的特征，及其支持度值。

在測試所有之前的模型時(shí)，我們檢查了在形態(tài)第三根蠟燭形成之前判定分形的可能性。 因此，我將依據(jù)兩個(gè)規(guī)則挖掘樹來定義買入和賣出分形。 如果根據(jù)您的問題，您需要為大量的目標(biāo)特征定義規(guī)則，那么您將需要?jiǎng)?chuàng)建更多的專有規(guī)則樹。

例如，您可能有多個(gè)目標(biāo)買入和賣出級別。 不幸的是，關(guān)聯(lián)規(guī)則挖掘算法只依據(jù)二元表進(jìn)行操作。 因此，您必須為每個(gè)目標(biāo)級別創(chuàng)建單獨(dú)的項(xiàng)，并為其查找關(guān)聯(lián)規(guī)則。 您可用動(dòng)態(tài)數(shù)組排除大量專有變量。

構(gòu)造函數(shù)和析構(gòu)函數(shù)留空，因?yàn)樵谶@個(gè)類中，我沒有使用指向樹構(gòu)建對象的動(dòng)態(tài)指針。

如上所述，關(guān)聯(lián)規(guī)則挖掘算法僅適用于二元矩陣。 但有關(guān)行情狀況的數(shù)據(jù)很難歸類。 因此，它們在使用前需要進(jìn)行預(yù)處理。

為了簡化類的進(jìn)一步使用，該算法不需要預(yù)先處理來自用戶的數(shù)據(jù)。 取而代之，它是在 PrepareData 方法中實(shí)現(xiàn)的。 在參數(shù)中，該方法接收指向 2 個(gè)矩陣、2 個(gè)向量和 2 個(gè)常量的指針。 一個(gè)矩陣包含原始數(shù)據(jù)，第二個(gè)矩陣用于寫入處理后的二元數(shù)據(jù)。 矢量則包含目標(biāo)值。 在我們的案例中，它們本就以二元數(shù)據(jù)表示，因此不需要預(yù)處理。 需要對源數(shù)據(jù)進(jìn)行預(yù)處理。

為了將源數(shù)據(jù)的標(biāo)量單位轉(zhuǎn)換為二元值，我們將取每個(gè)特征的數(shù)值范圍，并將其劃分為幾個(gè)區(qū)間。 區(qū)間數(shù)量由 “sections” 參數(shù)設(shè)置。 每個(gè)特征的最小值和步長將保存在相應(yīng)的矢量 m_vMin 和 m_vStep 當(dāng)中。 在實(shí)際運(yùn)用過程中，矢量將用于將源數(shù)據(jù)轉(zhuǎn)換為二元值。

在此我們來準(zhǔn)備二元矩陣，設(shè)置所需的大小，并以零值填充。 我們還可以指定目標(biāo)特征的標(biāo)識(shí)符，稍后將其添加到矩陣中的最后一列。

bool CAssocRules::PrepareData(matrix &data,
                              matrix &bin_data,
                              vector &buy, 
                              vector &sell,
                              const int sections = 10,
                              const double min_sup = 0.03)
  {
//---
   m_iSections = sections;
   m_vMin = data.Min(0);
   vector max = data.Max(0);
   vector delt = max - m_vMin;
   m_vStep = delt / sections + 1e-8;
   m_cBuyRules.ID(data.Cols() * m_iSections);
   m_cSellRules.ID(m_cBuyRules.ID() + 1);
   bin_data = matrix::Zeros(data.Rows(), m_cSellRules.ID() + 1);

接下來，執(zhí)行循環(huán)，遍歷輸入數(shù)據(jù)矩陣的所有行。 在循環(huán)實(shí)體中，從每行減去最小值的矢量，然后將結(jié)果除以步長。 為了排除超出范圍的數(shù)據(jù)，我們要限制矢量元素的下限和上限值。 作為這些操作的結(jié)果，向量的每項(xiàng)中數(shù)字的整數(shù)部分指示我們需要將源數(shù)據(jù)的相應(yīng)項(xiàng)包含到哪個(gè)數(shù)值范圍。 我們的二元矩陣的每個(gè)范圍都是一個(gè)單獨(dú)的特征。

我們運(yùn)行一個(gè)嵌套循環(huán)，并填充二元矩陣的相關(guān)行。 如果該特征處于活動(dòng)狀態(tài)，則將其值更改為 “1”。 未激活特征則保留零值。

   for(ulong r = 0; r < data.Rows(); r++)
     {
      vector pos = (data.Row(r) - m_vMin) / m_vStep;
      if(!pos.Clip(0, m_iSections - 1))
         return false;
      for(ulong c = 0; c < pos.Size(); c++)
         bin_data[r, c * sections + (int)pos[c]] = 1;
     }
   if(!bin_data.Col(buy, m_cBuyRules.ID()) ||
      !bin_data.Col(sell, m_cSellRules.ID()))
      return false;

填充二元矩陣后，我們可以立即計(jì)算每個(gè)特征的支持度，并在 CreatePositions 方法中按降序排序。 排序后，以肯定結(jié)果退出方法。

   vector supp = bin_data.Sum(0) / bin_data.Rows();
   m_mPositions = CreatePositions(supp, min_sup);
//---
   return true;
  }

既然我們提到了 CreatePositions 特征排序方法，我們就來研究一下它的算法。 該方法在參數(shù)中接收支持度向量，和最小支持度級別。

方法實(shí)體將包含一些準(zhǔn)備工作。 這是因?yàn)槭盏降闹С侄戎涤上蛄勘硎?，其中的?xiàng)目值包含支持度值。 項(xiàng)目的索引指示特征。 針對矢量項(xiàng)進(jìn)行簡單排序，我們將失去與源數(shù)據(jù)特征的聯(lián)系。 因此，我們需要?jiǎng)?chuàng)建“ 特特征 id - 支持度” 數(shù)據(jù)對。 配對數(shù)據(jù)將保存到矩陣當(dāng)中。

為此，首先創(chuàng)建一個(gè)標(biāo)識(shí)矩陣，該矩陣有 2 列，行數(shù)等于原始樣本中的特征數(shù)量。 然后按列計(jì)算項(xiàng)目的累計(jì)和，并將結(jié)果矩陣的值減少 “1”。 由此，我們得到一個(gè)矩陣，其中的列包含從 “0” 開始的升序值，與行索引對應(yīng)。 我們只需要用生成的支持度向量替換一列。 因此，我們得到了一個(gè)矩陣：每行將包含一個(gè)特征標(biāo)識(shí)符，和一個(gè)與之對應(yīng)的支持度值。

matrix CAssocRules::CreatePositions(vector &support, const double min_sup = 0.03)
  {
   matrix result = matrix::Ones(support.Size(), 2);
   result = result.CumSum(0) - 1;
   if(!result.Col(support, 1))
      return matrix::Zeros(0, 0);

我們只需要按支持度降序?qū)仃嚨男羞M(jìn)行排序。 為此，采用冒泡排序算法實(shí)現(xiàn)一個(gè)循環(huán)。

   bool change = false;
   do
     {
      change = false;
      ulong total = result.Rows() - 1;
      for(ulong i = 0; i < total; i++)
        {
         if(result[i, 1] >= result[i + 1, 1])
            continue;
         if(result.SwapRows(i, i + 1))
            change = true;
        }
     }
   while(change);

退出循環(huán)后，我們將得到一個(gè)擁有特征排序的矩陣。 我們只需要從該矩陣中刪除不滿足最低支持度要求的特征。 為此，找到低于最低支持度級別的第一個(gè)特征，并“切斷”低于此級別的所有特征。

   int i = 0;
   while(result[i, 1] >= min_sup)
      i++;
   if(!result.Resize(i, 2))
      return matrix::Zeros(0, 0);
//---
   return result;
  }

成功調(diào)整矩陣大小之后，退出方法，并返回結(jié)果矩陣。

在繼續(xù)探討公開方法之前，我們再查看一些方法，其中部分會(huì)執(zhí)行重復(fù)功能。 我們需要?jiǎng)?chuàng)建一個(gè)路徑，從二元數(shù)據(jù)轉(zhuǎn)換到 FP 樹。 此功能將在 CreatePath 方法中執(zhí)行。 該方法將接收指向二元數(shù)據(jù)矢量和排序已特征矩陣的指針。 然后，它將返回一個(gè)路徑矩陣，其中包含要添加到 FP 樹中的 “特征 id - 支持度” 對。

請注意已排序特征矩陣之間的差異 ，其一是我們在準(zhǔn)備數(shù)據(jù)時(shí)獲得的，另一個(gè)矩陣是為了添加路徑的 FP 樹。 這兩個(gè)矩陣都將包含“特征標(biāo)識(shí)符 - 支持度” 對。 但第一個(gè)矩陣包含源數(shù)據(jù)中提供的所有特征，及其在訓(xùn)練樣本中的支持度。 而路徑矩陣僅包含所分析業(yè)務(wù)中存在的特征，以及二元矩陣中表示的來自該業(yè)務(wù)的支持度。

好了，因?yàn)槲覀兲幚淼氖嵌仃?，所以每筆業(yè)務(wù)中的特征支持度值必須相同。 稍后，我們將采用相同的方法來構(gòu)建專有規(guī)則樹。 早前，我們在講述 CMyTreeNode::Mining 方法時(shí)研究過一個(gè)示例。 我們在該示例中多次采用支持度級別，取代重復(fù)一條路徑。 因此，為了統(tǒng)一操作，我們將在 2 個(gè)子流程中調(diào)用 1 個(gè)方法。 在這種情況下，引入支持度級別將非常有用。

在該方法伊始，我們將源數(shù)據(jù)向量的大小和所分析特征的數(shù)量保存在局部變量之中，它小于由支持度低于最小值的隨機(jī)特征構(gòu)成的源數(shù)據(jù)向量大小。

此外，我們還準(zhǔn)備了一個(gè)矩陣來寫出結(jié)果。 它不能大于分析特征矩陣。 此外，我們還引入了一個(gè)變量來指示路徑的尺寸。 在這個(gè)階段，它等于 “0”。

接下來，我們按照支持度的降序循環(huán)遍歷所有已分析特性。 在循環(huán)體中，我們提取下一個(gè)選中特征的標(biāo)識(shí)符。 檢查二元源數(shù)據(jù)矢量中的值。 如果該特征未激活，則轉(zhuǎn)到下一個(gè)特征。

如果特征處于活動(dòng)狀態(tài)，則將二元源數(shù)據(jù)矢量中的特征 id 及其支持度添加到路徑矩陣之中。 之后，我們增加路徑尺寸變量。

退出循環(huán)后，將路徑矩陣的尺寸減至已填充元素的數(shù)量，然后退出方法。

matrix CAssocRules::CreatePath(vector &bin_data, matrix &positions)
  {
   ulong size = bin_data.Size();
//---
   ulong total = positions.Rows();
   int vect_pos = 0;
   matrix path = matrix::Zeros(2, total);
   for(ulong c = 0; c < total; c++)
     {
      ulong pos = (ulong)positions[c, 0];
      if(pos >= size)
         continue;
      if(bin_data[pos] == 0)
         continue;
      path[0, vect_pos] = (double)pos;
      path[1, vect_pos] = bin_data[pos];
      vect_pos++;
     }
   if(!path.Resize(2, vect_pos))
      return matrix::Zeros(0, 0);
//---
   return path;
  }

另一種我們需要的方法是將路徑添加到 FP 樹：NewPath。 該方法接收指向樹根節(jié)點(diǎn)和先前所創(chuàng)建路徑矩陣的指針。 然后，它將返回操作的布爾結(jié)果。 在方法體中，我們首先檢查結(jié)果路徑的尺寸。 它應(yīng)該大于 0。 然后，我們增加對根節(jié)點(diǎn)的支持度，并運(yùn)行循環(huán)遍歷路徑的所有項(xiàng)。

在循環(huán)體中，檢查是否存在含有所需 ID 的下一個(gè)節(jié)點(diǎn)，如有必要，創(chuàng)建一個(gè)新節(jié)點(diǎn)。 然后增加節(jié)點(diǎn)支持度大小。 然后繼續(xù)搜索路徑中的下一個(gè)節(jié)點(diǎn)。

遍歷路徑的所有項(xiàng)后，退出該方法。

bool CAssocRules::NewPath(CMyTreeNode *root, matrix &path)
  {
   ulong total = path.Cols();
   if(total <= 0)
      return false;
   CMyTreeNode *parent = root;
   root.IncreaseSupport(path[1, 0]);
   for(ulong i = 0; i < total; i++)
     {
      CMyTreeNode *temp = parent.GetNext((ulong)path[0, i]);
      if(!temp)
        {
         temp = parent.AddNode((int)path[0, i], 0);
         if(!temp)
            return false;
        }
      temp.IncreaseSupport(path[1, i]);
      parent = temp;
     }
//---
   return true;
  }

最后，我們繼續(xù)討論生成FP 樹的方法：GrowsTree。 它在參數(shù)中接收指向樹根節(jié)點(diǎn)的指針、源數(shù)據(jù)的二元矩陣、和經(jīng)過排序的已分析特征矩陣。 在方法內(nèi)部，運(yùn)行循環(huán)遍歷源數(shù)據(jù)里的所有行。

在循環(huán)體中，從訓(xùn)練樣本中捕獲下一筆業(yè)務(wù)，并調(diào)用 CreatePath 方法創(chuàng)建一個(gè)路徑，添加到樹中。 檢查并確保接收的部分大于 0。 然后調(diào)用 NewPath 方法把所創(chuàng)建路徑加進(jìn)我們的 FP 樹。 不要忘記檢查操作結(jié)果。

成功迭源數(shù)據(jù)中的所有業(yè)務(wù)之后，以肯定結(jié)果退出該方法，。

bool CAssocRules::GrowsTree(CMyTreeNode * root, matrix & bin_data, matrix &positions)
  {
   ulong rows = bin_data.Rows();
   for(ulong r = 0; r < rows; r++)
     {
      matrix path = CreatePath(bin_data.Row(r), positions);
      ulong size = path.Cols();
      if(size <= 0)
         continue;
      if(!NewPath(root, path))
         return false;
     }
//---
   return true;
  }

現(xiàn)在，我們將上述所有方法合并到公開方法 CreateRules 當(dāng)中。 在方法參數(shù)中，我們傳遞源數(shù)據(jù)標(biāo)量（非二元）的矩陣、目標(biāo)值的二元向量、把標(biāo)量值轉(zhuǎn)換為二元值的區(qū)間數(shù)量、最小支持度和最小置信度。

在方法實(shí)體中，我們首先檢查接收到的源數(shù)據(jù)。 我們主要檢查獲得的矩陣向量的維數(shù)與區(qū)間數(shù)量的對應(yīng)關(guān)系，區(qū)間數(shù)必須大于 0。

在模塊檢查之后，將源數(shù)據(jù)標(biāo)量轉(zhuǎn)換為二元形似。 這是調(diào)用上述 PrepareData 方法完成的。

bool CAssocRules::CreateRules(matrix &data,
                              vector &buy,
                              vector &sell,
                              int sections = 10,
                              double min_sup = 0.03,
                              double min_conf = 0.3)
  {
   if(data.Rows() <= 0 || data.Cols() <= 0 || sections <= 0 ||
      data.Rows() != buy.Size() || data.Rows() != sell.Size())
      return false;
//---
   matrix binary_data;
   if(!PrepareData(data, binary_data, buy, sell, sections))
      return false;

進(jìn)而，為了移動(dòng)到相對單位平面，將二元矩陣值除以訓(xùn)練樣本中的業(yè)務(wù)數(shù)量，并調(diào)用 GrowsTree 方法構(gòu)建 FP 樹。

   double k = 1.0 / (double)(binary_data.Rows());
   if(!GrowsTree(GetPointer(m_cRoot), binary_data * k, m_mPositions))
      return false;

在構(gòu)建 FP 樹之后，我們就能夠繼續(xù)創(chuàng)建規(guī)則。 首先，準(zhǔn)備一個(gè)記錄支持度的向量，和一個(gè)記錄路徑的矩陣。 然后調(diào)用 Mining 方法，在 FP 樹里查找所有含有買入特征的路徑。

   vector supports = vector::Zeros(binary_data.Cols());
   binary_data = matrix::Zeros(0, binary_data.Cols());
   if(!m_cRoot.Mining(supports, binary_data, m_cBuyRules.ID(),min_conf))
      return false;

成功提取所有路徑后，重置購買特征的支持度，從而將其從所有路徑的過程里刪除。 并按降序?qū)Ｓ兄С侄冗M(jìn)行排序。 調(diào)用 CreatePositions 方法，并把結(jié)果記錄到 m_BuyPositions 矩陣當(dāng)中。 如果，特征排序之后，我們?nèi)匀荒軌驑?gòu)建規(guī)則（排序矩陣仍然有特征用作規(guī)則的先行項(xiàng)），那么調(diào)用樹成長方法，并將先前選擇的路徑輸入到該方法之中。

作為這些操作的結(jié)果，我們將在 m_cBuyRules 節(jié)點(diǎn)獲得一個(gè)含有根的專有規(guī)則樹。

   supports[m_cBuyRules.ID()] = 0;
   m_BuyPositions = CreatePositions(supports, min_sup);
   if(m_BuyPositions.Rows() > 0)
      if(!GrowsTree(GetPointer(m_cBuyRules), binary_data, m_BuyPositions))
         return false;

與此類似，為賣出特征創(chuàng)建一棵規(guī)則樹。

   supports = vector::Zeros(binary_data.Cols());
   binary_data = matrix::Zeros(0, binary_data.Cols());
   if(!m_cRoot.Mining(supports, binary_data, m_cSellRules.ID(),min_conf))
      return false;
   supports[m_cSellRules.ID()] = 0;
   m_SellPositions = CreatePositions(supports, min_sup);
   if(m_SellPositions.Rows() > 0)
      if(!GrowsTree(GetPointer(m_cSellRules), binary_data, m_SellPositions))
         return false;
//---
   m_cRoot.Clear();
//---
   return true;
  }

選擇所有規(guī)則后，清除源 FP 樹對象，以便釋放計(jì)算機(jī)資源。 然后以肯定結(jié)果退出方法。

“Probability” 方法是為實(shí)際應(yīng)用而創(chuàng)建的。 作為參數(shù)，該方法接收源數(shù)據(jù)的標(biāo)量向量，和指向兩個(gè)雙精度型變量的指針，這兩個(gè)變量是為了存儲(chǔ)特定的形態(tài)置信度。 該方法的算法用到上述所有方法。 您可以在附件中看到它們。

附件中提供了所有類和方法的完整代碼。

3. 測試

我已創(chuàng)建了一個(gè)智能系統(tǒng)（assocrules.mq5），并基于實(shí)際數(shù)據(jù)來測試這個(gè)類。 EA 的測試完全兼容之前測試中所用的所有參數(shù)。 我不能說這個(gè)方法能判定所有的分形，且無錯(cuò)誤。 但創(chuàng)建的 EA 展現(xiàn)出有趣的結(jié)果，如下面的屏幕截圖所示。

結(jié)束語

在本文中，我們研究了采用非監(jiān)督學(xué)習(xí)方法解決另一類問題：關(guān)聯(lián)規(guī)則挖掘。 我們已創(chuàng)建了一個(gè)類，是為了利用 FP-Growth 算法構(gòu)建關(guān)聯(lián)規(guī)則。 以智能系統(tǒng)形式對其進(jìn)行了測試，結(jié)果很有趣。 由此，可以得出結(jié)論，這些算法可用來解決交易中的實(shí)際問題。