程式扎記

來源自這裡
Preface:
apriori 是在資料探勘的領域中，用來找尋關聯式規則（association rules）的經典演算法之一。關聯式規則的應用，較常見的例子是在顧客的購物分析上，在其他領域也有相當多的應用。一個比較常被提出的故事為「尿布與啤酒」，這故事就是發現許多顧客買了尿布就會買啤酒。經過研究分析後，發現到：「在美國，許多年輕母親都留在家中照顧嬰兒，而父親匯到超市買尿布，但往往就會順便買啤酒」。在資料探勘的領域中，藉由「尿布與啤酒」的故事，我們發現在生活上，可存在許多表面上看似毫無關連的事物，但其實有著密不可分的關係。apriori 就是被提出用來找出這些關連的演算法之一.

Algorithm:
首先來看看這個演算法會用到的符號：

* D:Transaction Database，儲存我們所要分析資料的資料庫
* T：Transaction，資料庫中的一筆資料（交易），T ∈ D
* Support：在 D 中，支持該 itemset 的 T 佔有的比例，Support( X ) = Occur( X ) / Count( D ) = P( X )
* Confidence：Conf( X → Y) = Support( X ∩ Y ) / Support( X ) = P( Y | X )
* Candidate Itemset：通過 apriori 合併操作所得到的 itemset
* Frequent Itemset：support 值大於 min support 之 itemset
* C(k)：含有 k 個元素之 candicate itemset 之集合
* L(k)：含有 k 個元素之 frequent itemset 之集合

底下是演算法的文字說明:

1. 從 D 中找出 C(1)
2. 再掃描 D 找出所有包含 C(1) 的 T，計算其 support，將 C(1) 中不符合 min support 的 itemset 剔除，結果即為 L(1)
3. 自 L(k) 來產生其他的 L(k+1)，直到找 L(k+1) 為空集合（k 由 1 開始）
4. 產生 L(k+1) 的首要步驟為合併 L(k) 來產生 C(k+1)
5. 在 C(k+1) 中，若有某 itemset 其所有含 k 項的 subset 不屬於 L(k)，即可將其自 C(k+1) 剔除
6. 掃描 D 找出所有包含 C(k+1) 的 T，計算其 support，將 C(k+1) 中不符合 min support 的 itemset 剔除，結果即為 L(k+1)
7. 枚舉此 L(k+1) 中的 itemset，將 itemset 分成兩個部份 {A}{B} 的所有可能（其中 A 含有 p 個項目，而 B 含有 (k+1)-p 個項目，1<=p<=(k+1)-1）
8. 判斷 P(itemset) / P(A) 是否大於等於 min confidence，若符合我們可以判斷存在 A => B 的 association rule

而 Pseudo code 如下:

view plaincopy to clipboardprint?
L(1) = Scan database to find {frequent itemset}  
      
do  
    Gnerate C(k+1) from L(k)  
    Remove the itemset which has any subset that is not a frequent itemset (detect from L(k))  
    L(k+1) = candicates in C(k+1) with min_support  
      
    for all possible of partition L(k+1) into two parts A,B  
        if P(L(k+1)) / P(A) >= min_confidence  
            A => B is one association rule  
      
until L(k+1) is ∅  

上面演算法的優點是 1) 簡單易懂, 2)實現複雜度低. 而缺點是 1)產生過多的 candicate itemset, 2)需重複掃描資料庫.

Implementation:
如果是 C 語言, 則你可以參考原文中的鏈結 Gist, 而下面是我使用 Java 實作的代碼. 完整的代碼可以在這裡下載.

- 定義訓練資料
要使用我撰寫的 Apriori 實作, 首先要定義訓練資料的類別, 而資料類別都需要實作介面 IDataBean. 這邊我定義資料類別 RichData:

view plaincopy to clipboardprint?
package ml.alg.apriori;  
  
public class RichData implements IDataBean{  
    public String outlook=null;  
    public String age=null;  
    public String height=null;  
    public Boolean hasCar=null;  
    @Target  
    public Boolean rich=null;  
      
    public RichData()  
    {  
          
    }  
      
    public RichData(String outlook, String age, String height, boolean hasCar, boolean rich)  
    {  
        this.outlook = outlook;  
        this.age = age;  
        this.height = height;  
        this.hasCar = hasCar;  
        this.rich = rich;  
    }  
}  

上面定義了我們的資料包含了欄位 "outlook", "age", "height", "hasCar" 與 "rich", 這邊我們藉由 annotation @Target 告訴工具說欄位 "rich" 為目標欄位, 也就是說產生的規則 condition->result 格式中欄位 "rich" 會是 result!

有了訓練資料後, 我們便可以如下進行 Apriori algorithm 的運行並列印出產生的 association rules:

view plaincopy to clipboardprint?
Apriori apriori = new Apriori(Level.ALL);  
// Add training data set  
apriori.addT(AddRichData("ugly", "m", "m", true, true));  
apriori.addT(AddRichData("normal", "y", "m", false, false));  
apriori.addT(AddRichData("handsome", "m", "h", false, false));  
apriori.addT(AddRichData("ugly", "o", "l", false, false));  
apriori.addT(AddRichData("normal", "m", "m", true, true));  
apriori.addT(AddRichData("normal", "y", "m", false, false));  
apriori.addT(AddRichData("normal", "m", "m", true, true));  
apriori.addT(AddRichData("ugly", "o", "h", false, true));  
apriori.addT(AddRichData("handsome", "y", "h", true, true));  
apriori.addT(AddRichData("handsome", "y", "l", false, true));  
apriori.addT(AddRichData("ugly", "y", "l", true, true));  
apriori.addT(AddRichData("ugly", "m", "l", false, false));  
apriori.addT(AddRichData("ugly", "y", "l", false, true));  
apriori.addT(AddRichData("normal", "m", "m", true, true));  
apriori.addT(AddRichData("ugly", "o", "m", true, true));  
apriori.addT(AddRichData("handsome", "m", "m", false, false));  
apriori.addT(AddRichData("handsome", "y", "m", false, false));  
apriori.addT(AddRichData("handsome", "y", "m", false, true));  
apriori.addT(AddRichData("handsome", "y", "l", false, false));  
apriori.addT(AddRichData("handsome", "m", "m", true, true));  
apriori.addT(AddRichData("ugly", "o", "l", true, true));  
apriori.addT(AddRichData("normal", "m", "h", true, false));  
apriori.addT(AddRichData("normal", "m", "h", false, false));  
apriori.addT(AddRichData("normal", "m", "h", true, true));  
apriori.addT(AddRichData("normal", "m", "m", true, true));  
  
// Run association learning  
List ruleList = apriori.run();  
  
// Output result  
for(Rule r:ruleList) System.out.printf("%s\n", r);  

執行結果如下:

hasCar=true->rich=true (0.44, 0.92) # 說明只要有車 (hasCar=true) 就是有錢, 其 support=0.44; confidence=0.92
age=m,height=m->rich=true (0.24, 0.86)
hasCar=false,height=m->rich=false (0.16, 0.80)
hasCar=true,height=m->rich=true (0.28, 1.00)
hasCar=false,outlook=normal->rich=false (0.12, 1.00)
hasCar=true,outlook=normal->rich=true (0.20, 0.83)
hasCar=true,outlook=ugly->rich=true (0.16, 1.00)
age=m,hasCar=false->rich=false (0.16, 1.00)
age=m,hasCar=true->rich=true (0.28, 0.88)
age=m,height=m,outlook=normal->rich=true (0.16, 1.00)
hasCar=true,height=m,outlook=normal->rich=true (0.16, 1.00)
age=m,hasCar=true,height=m->rich=true (0.24, 1.00)
age=m,hasCar=true,outlook=normal->rich=true (0.20, 0.83)

Supplement:
* Apriori - Association Rule Induction / Frequent Item Set Mining

Christian Borgelt's Web Pages - A program to find association rules and frequent item sets (also closed and maximal as well as generators) with the Apriori algorithm (Agrawal et al. 1993), which carries out a breadth first search on the subset lattice and determines the support of item sets by subset tests...

* CODE PROJECT - Apriori Algorithm

In data mining, Apriori is a classic algorithm for learning association rules. Apriori is designed to operate on databases containing transactions (for example, collections of items bought by customers, or details of a website frequentation)...

This message was edited 16 times. Last update was at 30/05/2013 13:37:02

來源自這裡
Preface:
Nachos的全稱是“Not Another Completely Heuristic Operating System”，它是一個可修改和 trace 的操作系統教學軟件. 它給出了一個支持多線程和虛擬存儲的操作系統骨架，可讓學生在較短的時間內對操作系統中的基本原理和核心算法有一個全面和完整的了解. 該操作系統核心部分使用C++實現，代碼可讀性較強. 這邊我們實作的第一個實驗就是基於NachOS去撰寫 System Call.

實作簡介:
實作的內容是為 NachOS 添加幾個 System Call , 分別為 OSAdd(op1,op2), OSSub(op1,op2), OSDiv(op1,op2), OSMul(op1,op2) 與 Print(char *msg) (作用是在系統控制台上打印字符串). 從 code/threads/kernel.cc, code/machine/machine.h 與 code/userprog/synchconsole.h 可知，操作系統預設可以使用的函數或類別有:

view plaincopy to clipboardprint?
kernel->synchConsoleOut->PutChar( char ch);  //向控制台輸出字符  
kernel->machine->ReadRegister( int num);    //讀暫存器  
kernel->machine->WriteRegister( int num, int value);   //寫暫存器  
kernel->machine->ReadMem( int addr, int size, int * value); //從用戶進程內存讀值  

系統虛擬機運行原理:
使用 Nachos 運行 user program 可以使用命令:

> nachos –x program_name

nachos 執行檔的 entry point 在 code/threads/main.cc啟動，創建了Kernel對象並進行初始化（啟動主線程、創建線程調度表、中斷處理模塊、CPU、控制台、文件系統、中斷等）:

之後，程序創建了用戶空間程序，初始化的時候加載了指令集並調用了kernel->machine->WriteRegister 填寫CPU寄存器，然後開始執行。執行由 kernel->machine->Run 實現:
- /code/userprog/addrspace.cc

view plaincopy to clipboardprint?
...  
void  
AddrSpace::Execute()  
{  
  
    kernel->currentThread->space = this;  
  
    this->InitRegisters();      // set the initial register values  
    this->RestoreState();       // load page table register  
  
    kernel->machine->Run();     // jump to the user progam  
  
    ASSERTNOTREACHED();         // machine->Run never returns;  
                    // the address space exits  
                    // by doing the syscall "exit"  
}  
...  

接著使用 OneInstruction 函數模擬 CPU 的逐條指令執行過程:
- /code/machine/mipssim.cc

view plaincopy to clipboardprint?
...  
//----------------------------------------------------------------------  
// Machine::Run  
//  Simulate the execution of a user-level program on Nachos.  
//  Called by the kernel when the program starts up; never returns.  
//  
//  This routine is re-entrant, in that it can be called multiple  
//  times concurrently -- one for each thread executing user code.  
//----------------------------------------------------------------------  
  
void  
Machine::Run()  
{  
    Instruction *instr = new Instruction;  // storage for decoded instruction  
  
    if (debug->IsEnabled('m')) {  
        cout << "Starting program in thread: " << kernel->currentThread->getName();  
    cout << ", at time: " << kernel->stats->totalTicks << "\n";  
    }  
    kernel->interrupt->setStatus(UserMode);  
    for (;;) {  
        OneInstruction(instr);  
    kernel->interrupt->OneTick();  
    if (singleStep && (runUntilTime <= kernel->stats->totalTicks))  
      Debugger();  
    }  
}  
...  

當 user program 載入後, Fetch > Decode > Execute 的流程如下, 而 ExceptionHandler() 函數則是用來作為 System Call 的 dispatcher:

系統調用的實現過程:
如同 Linux 操作系統一樣，運行在虛擬機上的 NachOS 也使用中斷來實現 System Call（User Mode 程序調用操作系統內核服務的接口）.實現方法為:
0. 為了方便 debug, 我新增了一個 debug 類型 "dbJohn" 如下
- /code/lib/debug.h

view plaincopy to clipboardprint?
...  
const char dbJohn = 'j';        // Debug by John  
...  

之後可以使用參數 -d j 來打印我的除錯訊息.

1. 當 System Call 發生的時候，首先把函數參數、系統調用號存入寄存器，然後引發系統中斷，通過中斷調用進入 Kernel mode. 以 System Call "OSAdd" 為範例:
- /code/test/start.S

view plaincopy to clipboardprint?
    .globl  OSAdd  /*聲明為外部函數*/  
    .ent    OSAdd  /* OSAdd 函數開始*/  
OSAdd:  
    addiu $2,$0,SC_OSAdd  /* 將 system call 呼叫 case num 存入r2寄存器*/  
    syscall  /* all parameter of this system call will be stored in register 4,5,6 and 7 by MIPS machine automatically.*/  
    j   $31  
.end OSAdd  

2. 函數調用則會在中斷發生時進行 ./userprog/exception.cc, 在此撰寫中斷發生時的 handler:
- /code/userprog/exception.cc

view plaincopy to clipboardprint?
  case SC_OSAdd:  
DEBUG(dbJohn, "Add " << kernel->machine->ReadRegister(4) << " + " << kernel->machine->ReadRegister(5) << "\n");  
      //int result;  
      op1 = (int)kernel->machine->ReadRegister(4);  
      op2 = (int)kernel->machine->ReadRegister(5);  
      result = SysOSAdd(op1, op2);  
DEBUG(dbJohn, "Add returning with " << result << "\n");  
      kernel->machine->WriteRegister(2, (int)result); /* Prepare Result */  
      /* Modify return point */  
      {  
              /* set previous programm counter (debugging only)*/  
              kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg));  
  
              /* set programm counter to next instruction (all Instructions are 4 byte wide)*/  
              kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4);  
  
              /* set next programm counter for brach execution */  
              kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg)+4);  
      }  
  
      return;  
  
      ASSERTNOTREACHED();  
      break;  

這邊當 System Call "OSAdd" 發生時, 會進入 handler switch 的 case "SC_OSAdd", 這邊則將 System Call 的函數呼叫定義為 "SysOSAdd(op1, op2)", 並於呼叫完畢後將結果回存 2 號暫存器並增加 Program Counter 到下一個要執行的 instruction.

3. 將 System Call "OSAdd" 的函數 "SysOSAdd" 定義在 "./userprog/ksyscall.h":
- /code/userprog/ksyscall.h

view plaincopy to clipboardprint?
//----------------------------------------------------------------------  
// SysOSAdd  
//  Operation Add.  
//  
//  Add "op1" with "op2".  
//  
//  "op1" and "op2" are operands of operation Add.  
//      ex: SysOSAdd(1,2) = 1+2 = 3  
//----------------------------------------------------------------------  
int SysOSAdd(int op1, int op2)  
{  
    int result = op1 + op2;  
    return result;  
}  

4. 重新 compile Nachos 與調用測試代碼. 假設你寫了 project1.c 來測試剛剛寫的 System call 並放在 test 目錄下, 接著你必須在 Makefile 添加下面代碼以編譯 project.c :

view plaincopy to clipboardprint?
...  
PROGRAMS= add halt shell matmult sort segments project1  
...  
project1.o:project1.c  
$(CC) $(CFLAGS) -c project1.c  
  
project1: project1.o start.o  
$(LD) $(LDFLAGS) start.o project1.o - o project1.coff  
$(COFF2NOFF) project1.coff project1  
...  

上面的符號需要替換成 "\t" 鍵. 接著可以在 test 目錄下執行 make 編譯 project1.c

5. 使用 nachos 虛擬機載入 project1, 執行命令如下:

> nachos -d j -x project1 # 開啟 debug 類別 'j'
Add 15 + 10

Add returning with 25

Machine halting!

Ticks: total 29, idle 0, system 10, user 19
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

System Call Print(char* input, int length) 的具體實現:
有了上面的介紹, System Call OSAdd(op1,op2), OSSub(op1,op2), OSDiv(op1,op2), OSMul(op1,op2) 的實現應該都不是問題, 這裡要針對 Print(char *msg) System Call 進行詳細實作說明. 第一步當然就是在 start.S 添加 System Call Print 的聲明:
- /code/test/start.S

view plaincopy to clipboardprint?
    .globl  Print  
    .ent    Print  
Print:  
    addiu $2,$0,SC_Print  
    syscall  
    j   $31  
.end Print  

接著增加 System Call handler case 宣告:
- /code/userprog/syscall.h

view plaincopy to clipboardprint?
#define SC_Print       60  

接著撰寫 System Call handler 的 SC_Print case :
- /code/userprog/exception.cc

view plaincopy to clipboardprint?
case SC_Print:  
     DEBUG(dbJohn, "Print call...\n");  
     result = SysPrint(/* int op1 */(char*)kernel->machine->ReadRegister(4),  
                       /* int op2 */(int)kernel->machine->ReadRegister(5));  
     kernel->machine->WriteRegister(2, (int)result); /* Prepare Result */  
     /* Modify return point */  
     {  
        /* set previous programm counter (debugging only)*/  
        kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg));  
  
        /* set programm counter to next instruction (all Instructions are 4 byte wide)*/  
        kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4);  
  
        /* set next programm counter for brach execution */  
        kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg)+4);  
     }  
     return;  
     ASSERTNOTREACHED();  
     break;  

接著實作上面調用的函數 SysPrint :
- /code/userprog/ksyscall.h

view plaincopy to clipboardprint?
#include "kernel.h"  
#include "synchconsole.h"  
#include "utility.h"  
#include "stdio.h"  
...  
//----------------------------------------------------------------------  
// SysPrint  
//  Print Message to Nachos Console Output.  
//  
//  Output message from  with  chars.  
//  
//  "input" is the char* which pointer to output message; "length" tells the length of output message.  
//      ex: SysPrint("John", 4) -> Output "John" to console.  
//----------------------------------------------------------------------  
int SysPrint(char* input, int length)  
{  
    int i;  
    int memVal = 0;  
    int memPt = (int)input;  
    for(i=0; i
    {  
        kernel->machine->ReadMem(int(memPt+i),1,&memVal); /* 從用戶程序內存空間讀取字符串的值*/  
        if(0 == memVal) return i;  
        kernel->synchConsoleOut->PutChar((char)memVal);  
    }  
    return length;  
}  

上面代碼記得要包含標頭檔 "synchconsole.h" 並透過函數 kernel->synchConsoleOut->PutChar(char) 將 output message 一次取一個 char 輸出. 接著重新編譯 Nachos:

../code/test/build.linux> make
g++ -g -Wall -I../network -I../filesys -I../userprog -I../threads -I../machine -I../lib -I- -DFILESYS_STUB -DRDATA -DSIM_FIX -Dx86 -DLINUX -DCHANGED -m32 -c ../userprog/exception.cc
...
/usr/lib/gcc/x86_64-linux-gnu/4.7/include/stddef.h:400:0: note: this is the location of the previous definition
g++ bitmap.o debug.o libtest.o sysdep.o interrupt.o stats.o timer.o console.o machine.o mipssim.o translate.o network.o disk.o alarm.o kernel.o main.o scheduler.o synch.o thread.o addrspace.o exception.o synchconsole.o directory.o filehdr.o filesys.o pbitmap.o openfile.o synchdisk.o post.o switch.o -m32 -o nachos

接著來寫測試代碼:
- /code/test/project1.c

view plaincopy to clipboardprint?
#include "syscall.h"  
  
int main()  
{  
    Print("Hello, I am John K Lee.\n" , 24);  
    Halt();  
}  

編譯完測試代碼後, 如下將 project1 program 載入 Nachos 虛擬機:

> nachos -d j -x project1
Print call... # Caused by DEBUG

Hello, I am John K Lee.
Machine halting!

Ticks: total 3230, idle 2390, system 820, user 20
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 24
Paging: faults 0
Network I/O: packets received 0, sent 0

參考事項:
- Duplicate definition on ConsoleInput & ConsoleOutput
在實作 SysPrint 函數時, 為了使用 kernel->synchConsoleOut 來輸出字元, 你可能會包含進 "synchconsole.h". 此時在編譯 Nachos 時可能會出現下面錯誤訊息:

../userprog/synchconsole.h:31:5: error: expected unqualified-id before numeric constant
../userprog/synchconsole.h:46:5: error: expected unqualified-id before numeric constant
make: *** [exception.o] Error 1

而可能的原因是在 "/code/userprog/syscall.h" 約 116 行:

view plaincopy to clipboardprint?
#define ConsoleInput 0  
#define ConsoleOutput    1  

與 "/code/machine/console.h" 約 47 行與 70 行

view plaincopy to clipboardprint?
...  
class ConsoleInput : public CallBackObj {  
...  
class ConsoleOutput : public CallBackObj {  
...  

重複定義了 ConsoleInput & ConsoleOutput. 我的解法方法是將 "/code/userprog/syscall.h" 上面定義改為:

view plaincopy to clipboardprint?
#define SysCallConsoleInput 0  
#define SysCallConsoleOutput    1  

再重新編譯, 便可以解決這裡的問題.

- Nachos Debugging
基本上有兩種方法來 debug Nachos: external & internal. external debugger 透過外部載入 Nachos 的程式, 並使用 interactive 方法與使用者互動, 你可以一行行 debug 程式並檢查相關變數的設定, 常見的有 GDB. internal debugger 就是在你的程式加入 debug message, 透過這些訊息來判斷問題出在哪裡, 最常用也最沒有效率, 因為你無法一步步除錯, 且無法知道執行當下的變數(除非你把他們都印出來 orz)與執行環境. 詳細的介紹可以參考 [ Nachos 4.0 ] Debugging Nachos

程式扎記

標籤

2013年5月29日星期三

[ ML 文章收集 ] Apriori Algorithm Introduction

2013年5月26日星期日

[ Nachos 4.0 ] Nachos System Call Implementation Sample

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

檢舉濫用情形

學習筆記

標籤

2013年5月29日 星期三