www.gusucode.com > 一个相对很完善的数据挖掘系统源码程序 > 一个相对很完善的数据挖掘系统源码程序/Discover/Discover开发文档.txt
Discover软件开发
一、编程思路：
1、界面：
左侧和下方都放置Controlbar，
左侧有两个tab页，
1）、用于处理连接数据库并将结果送到右侧的SplitterWnd上面的ListCtrl中显示
2）、进行各种算法的计算与处理，并将结果送到右侧的SplitterWnd下面的ListCtrl或FormView中显示
下方的Controlbar，处理输出结果等，放置几个tab页未定
二、数据结构及算法
(一)、关联规则(Association Rule)
程序基于数据库 TransactionDB.txt
A,B-单项（物品）;D-所有事务
频繁项集-Frequent itemset
假设关联规则为 A=>B (如果A则B)
支持度(support) s=P(AUB)=count(AUB)/count(D) --单项（物品）A和B同时出现的概率.count(AUB)A和B同时出现的次数，count(D)-事务总记录条数
可信度(confidence) c=P(B/A)=count(AUB)/count(A) --单项（物品）A出现的前提下B出现的概率
期望可信度 Ce=P(B)--单项（物品）B出现的概率
作用度 lift=c/Ce=P(B/A)/P(B) --衡量关联程度
0)自建函数
<1>BOOL CCollectDoc::IsStrItemInclude(CString strSmall,CString strBig)
//一个频繁项目集中的多个项目组成的strSmall，是否都包含于strBig，
//strSmall={I2,I3,I1} strBig={I4,I2,I5,I7,I3,I1} 则IsStrItemInclude返回TRUE
<2>将CStringArray m_AprioristructList1 中的所有元素（项目）进行升序排序
高级排序算法：它的工作看起来象一个二叉树。首先我们选择一个中间值middle，程序中使用数组中间值，然后
把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使
用这个过程（最容易的方法——递归）。
void CCollectDoc::QuickSortStrArray(CStringArray *pArray, int left,int right)
用法：
取得CStringArray中元素个数 nSingleItemArraySize，假设已经存在的CStringArray为 *SingleItemArray
以下格式调用函数 QuickSortStrArray(SingleItemArray, 0,nSingleItemArraySize-1)
即初始left=0，right=元素个数-1
<3>自建函数CStringArray* CCollectDoc::DevideStr(CString ItemFieldStr,char divider)实现：
"将一个有多个项目组成的字符串分解为单独的项目
比如来自一条记录的内容 ItemFieldStr="I1,I2,I4";每个项目间的分割字符 divider 为','
则函数最终得到的是由单独的项目"I1" "I2" "I4"组成的字符串数组CStringArray"
CStringArray* CCollectDoc::DevideDoubleStr(CString ItemFieldStr, char divider)
/*将一个有多个项目组成的字符串分解为单独的项目后，再组成两项集
比如来自一条记录的内容 ItemFieldStr="I1,I2,I4";每个项目间的分割字符 divider 为','
则函数最终得到的是包含单独的项目"I1" "I2" "I4"形成的"I1,I2","I1,I4","I2,I4" 组成的字符串数组CStringArray
*/
CStringArray* CCollectDoc::DevideTriStr(CString ItemFieldStr, char divider)
/*将一个有多个项目组成的字符串分解为单独的项目后，再组成三项集
比如来自一条记录的内容 ItemFieldStr="I1,I2,I4,I5";每个项目间的分割字符 divider 为','
则函数最终得到的是包含单独的项目"I1" "I2" "I4" "I5" 形成的"I1,I2,I4","I1,I4,I5","I2,I4,I5" 组成的字符串数组CStringArray
*/
<4>CStringArray* CCollectDoc::GenAssoRuleStr(CString Frequent3Str, char divider)
/*将一个有三个单项组成的字符串生成关联规则
比如来自一条字符串的内容 Frequent3Str="I1,I2,I3";每个项目间的分割字符 divider 为','
则函数最终得到的是包含 "I1,I2=>I3","I3=>I1,I2","I1,I3=>I2"等6种关联规则组成的字符串数组CStringArray
*/
1）Apriori关联算法-频繁项集的生成
先找出所有支持度大于最小支持度的项集-频繁项集；
对于频繁项集Y=I1,I2,I3...Ik(k>=2,Ii属于I(i=1,2,3...k)),产生只包含集合{I1,I2,I3...Ik}中的项的所有规则，形如
[Y-Ii]->Ii,如果此规则>最小可信度，则保留
要处理的数据集
TID Item
1 A,B,E
2 B,D
3 B,C
4 A,B,D
5 A,C
6 B,C
7 A,C
8 A,B,C,E
9 A,B,C
①按支持度要求（支持度为2）生成1项集L1，如下
A 6
B 7
C 6
D 2
E 2
②循环取L1中的所有项，每次分别挂接另一个 L1中的项，例如先选出A,然后挂接B变成2项组合“AB”,然后是AC,AD,AE
再接下来是BC,BD,BE,CD,CE,DE
③在所有事务D中计算上面步骤中生成的2项集的各个项的支持度，AB=4,AC=4,AD=1,AE=2,BC=4,BD=2,BE=2,CD=0,DE=0,
其中达不到最小支持度2的被剔除，于是得到频繁2项集L2为{AB,Ac,AE,BC,BD,BE}
AB 4
AC 4
AE 2
BC 4
BD 2
BE 2
④循环L2中的所有项，然后依次挂接其他各项，具体方法是逐个单项比较，比如AB挂接AC时，前面都有一个A保留，后面的B,C
不一样则挂接在一起形成ABC,依此形成ABE,ABD,ACE,BCD,BCE,BDE
⑤在所有事务D中计算上面步骤中生成的3项集的各个项的支持度,ABC=2,ABE=2,ABD=1,ACE=1,BCD=0,BCE=1,BDE=0，剔除小于最小支持度的，
所以最终的3项集L3是{ABC,ABE}
如果要求频繁4项集，5项集，重复前面步骤既可
⑥在得到最大的频繁项集（本例为L3）后，以 [L-i]->i,i->[L-i]形式生成所有规则。
本例：
AB->C AC->B BC->A
C->AB B->AC A->BC
AB->E AE->B BE->A
E->AB B->AE A->BE
⑦对上面各个规则,分别计算其可信度c,只有可信度>60%的菜做为有效规则保留下来
AB->C其可信度 c=P(C/AB)=count(CAB)/count(AB)=2/4=50%
C->AB其可信度 c=P(AB/C)=count(ABC)/count(C)=2/6=33%
AC->B其可信度 c=P(B/AC)=count(BAC)/count(AC)=2/4=50%
B->AC其可信度 c=P(AC/B)=count(BAC)/count(B)=2/7=28.6%
BC->A其可信度 c=P(A/BC)=count(BCA)/count(BC)=2/4=50%
A->BC其可信度 c=P(BC/A)=count(BCA)/count(A)=2/6=33%
...
最终只有AE->B,BE->A,E->AB三个规则留下来了
算法编程实现：
代码对Apriori算法进行了改良，只读取数据库一次便可得到所有的频繁项集。
使用集合类 typedef CTypedPtrList<CPtrList, CAprioriStruct*> CAprioriStructList;
其中：CAprioriStruct定义如下
class CAprioriStruct //Apriori算法数据结构
{
public:
CString m_strFrequentItem;//频繁项集（或一般项集的）项目组合字符串
long m_nFrequentItemCount;//频繁项集（或一般项集的）个数
public:
};
在CCollectDoc类中定义，分别存储频繁1，2，3项集
CAprioriStructList m_AprioristructList1;
CAprioriStructList m_AprioristructList2;
CAprioriStructList m_AprioristructList3;
----------------
逐条记录读取同时生成项目集m_AprioristructList1，m_AprioristructList2，m_AprioristructList3
每次取得RecordSet中的一条记录，就将Item分解为单项、双项和三项的多个 CAprioriStruct 类型的结构
（m_strFrequentItem分别为单项、双项和三项的内容，m_nFrequentItemCount为每项在此条记录情况下的个数加上同项集中已经出现的同样项集内容的个数之和）
分别存入 m_AprioristructList1 等三个频繁项集（当然此时只是项集，不能称为频繁项集）
比如，依次的两条记录为：
Tid Item
01 I1,I3,I4
02 I1,I2,I4,I5
当读到第一条记录时，
CAprioriStruct 生成3个单项的结构 {"I1",1},{"I3",1},{"I4",1}，存入 m_AprioristructList1
CAprioriStruct 生成3个双项的结构 {"I1,I3",1}，{"I1,I4",1}，{"I3,I4",1} 存入 m_AprioristructList2
CAprioriStruct 生成1个三项的结构 {"I1,I3,I4",1} 存入 m_AprioristructList3
当读到第2条记录时，
CAprioriStruct 生成4个单项的结构 {"I1",1},{"I2",1},{"I4",1},{"I5",1}，存入 m_AprioristructList1 ，
此时m_AprioristructList1 中已经存在 {"I1",1},{"I4",1}，则此时的 m_AprioristructList1变为：{"I1",2},{"I3",1},{"I4",2},{"I2",1},{"I5",1}
CAprioriStruct 生成6个双项的结构 {"I1,I2",1}，{"I1,I4",1}，{"I1,I5",1}，{"I2,I4",1},{"I2,I5",1},{"I4,I5",1} 存入 m_AprioristructList2
此时m_AprioristructList2 中已经存在 {"I1,I4",1}，则此时的 m_AprioristructList2变为：{"I1,I3",1}，{"I1,I4",2}，{"I3,I4",1},{"I1,I2",1}，{"I1,I5",1}，{"I2,I4",1},{"I2,I5",1},{"I4,I5",1}
CAprioriStruct 生成3个三项的结构 {"I1,I2,I4",1},{"I1,I2,I5",1},{"I1,I2,I4",1}{"I2,I4,I5",1} 存入 m_AprioristructList3
此时m_AprioristructList3变为：{"I1,I3,I4",1}，{"I1,I2,I4",1},{"I1,I2,I5",1},{"I1,I2,I4",1}{"I2,I4,I5",1}
将频繁1，2，3项集m_AprioristructList1，m_AprioristructList2，m_AprioristructList3分别排序后（用QuickSortStrArray实现排序）插入三个ListBox中
算法在TreeViewDMfunction.cpp中的void CTreeViewDMfunction::OnLButtonDown(UINT nFlags, CPoint point)实现
2）Apriori关联算法-关联规则的生成
当频繁项集已经存放在三个ListBox 中后，从ListBox3中逐条取得频繁三项集的各个条目（形如：I1,I2,I3->6 表示：同时具备 I1,I2,I3三个单项的记录条数有 6个），
然后将其分解分各种关联规则（I1,I2=>I3;I3=>I1,I2; I1,I3=>I2; 等6种），对每种规则分别到单项集或两项集ListBox
中查找左侧条件的个数及右侧结果的个数（比如针对 I1,I2=>I3，到两项集中查找左侧条件 I1,I2出现的记录数 ，到单项集对应的ListBox中查找I3出现的记录个数）
找到个数后，按公式计算支持度、可信度、期望可信度、作用度四个度量值，满足Dialog对话框中同样度量要求的关联规则插入到ListCtrl控件IDC_LIST_ASSO中
算法在AprioriDM.cpp中的 void CAprioriDM::OnBtnCaculate()中实现
(二)、分类(Classification)
1）ID3算法：
基于训练集（已经有明确归类的记录集合），首先找出最具判别力的因素，把记录分成多个子集，每个子集上又选择最有判别力的因素进行划分，
直到所有子集只包含同一类数据为止，这样便得到一棵决策书，用它来对新样例进行分类。
⑴主算法步骤：
①从训练集中随机选择一个包含正例与反例的子集（称作窗口）
②用下面的建树算法将当前窗口形成决策树
③用非窗口中的训练集的例子来验证决策树，找出错误的例子
④若有错例，将其插入窗口，转②
⑤否则结束循环，得到的决策树即为最终决策树
⑵建树算法
①对例子集合，计算各特征（特征又称为属性，指表中的各有效字段，有效字段-除去 序号、类别 等字段后的所有字段）的互信息
②选择互信息最大的特征Ak
③把在Ak处取值相同的例子归于同一子集，Ak取几个值就得到几个子集
④如子集中仅包含正例或反例，对应分支标上P或N，返回调用处
⑤如子集中包含正例和反例，递归调用建树算法
⑶算法实现
实例：
气候训练集 气候训练集
------------------------------------------ ------------------------------------------
序号 天气 气温 湿度 风 类别 序号 天气 气温 湿度 风 类别
1 晴 热 高 无 N 1 0 2 1 0 0
2 晴 热 高 有 N 2 0 2 1 1 0
3 多云 热 高 无 P 3 1 2 1 0 1
4 雨 适中 高 无 P 4 2 1 1 0 1
5 雨 冷 正常 无 P 5 2 0 0 0 1
6 雨 冷 正常 有 N 6 2 0 0 1 0
7 多云 冷 正常 有 P 7 1 0 0 1 1
8 晴 适中 高 无 N 8 0 1 1 0 0
9 晴 冷 正常 无 P 9 0 0 0 0 1
10 雨 适中 正常 无 P 10 2 1 0 0 1
11 晴 适中 正常 有 P 11 0 1 0 1 1
12 多云 适中 高 有 P 12 1 1 1 1 1
13 多云 热 正常 无 P 13 1 2 0 0 1
14 雨 适中 高 有 N 14 2 1 1 1 0
------------------------------------------ ------------------------------------------
(共14个样例,其中N类5个,P类正例9个) 天气：晴=0、多云=1、雨=2；气温：冷=0、适中=1、热=2
湿度：正常=0、高 =1； 风：无=0、有=1；N=0、P=1
①信息熵： H(U)=-∑P(Ui)Log(P(Ui))
i
其中 P(Ui)=∣Ui∣/∣S∣ ，∣Ui∣-类别Ui的个数，∣S∣-例子集的S总数, Log表示以2 为底的对数
本实例用U1表示正例P,用U2表示反例N.所以P(U1)=9/14,P(U2)=5/14
H(U)=-(9/14)Log(P(9/14))-(5/14)Log(P(5/14))=0.94bit
②条件熵：H(U/V)=-∑P(Vi)∑(P(Ui/Vj))Log(P(Ui/Vj))
j i
其中P(Ui/Vj)表示属性A1取值Vj时，类别为Ui的条件概率, P(Ui/Vj)=∣Ui∣/∣Vj∣,∣Ui∣-类别Ui的个数，∣Vj∣- 取值为Vj的属性A1的个数
本实例中
A1=天气, V1=晴,V2=多云,V3=雨
A2=气温， V1=冷,V2=适中,V3=热
A3=湿度, V1=正常, V2=高
A4=风, V1=无, V2=有
对于A1天气属性, V1=晴,V2=多云,V3=雨,对应的例子数分别为 5,4,5,所以 P(V1)=5/14,P(V2)=4/14,P(V3)=5/14,
取值"晴"的5个例子中,有2个正例,3个反例,所以 P(U1/V1)=2/5,P(U2/V1)=3/5, 同理:P(U1/V2)=4/4,P(U2/V2)=0, P(U1/V3)=2/5,P(U2/V3)=3/5
H(U/V)=(5/14)( (2/5)Log(5/2) + (3/5)Log(5/3) )+
(4/14)( (4/4)Log(4/4) + 0 )+
(5/14)( (2/5)Log(5/2) + (3/5)Log(5/3) )=0.694(bit)
同理,可以分别算出 A2=气温,A3=湿度,A4=风 的条件熵：H(U/V)
③互信息: I(U,V)=H(U)-H(U/V)
对于 A1天气属性,I(A1)=0.94-0.694=0.246(bit),同理算出 I(A2)=0.029, I(A3)=0.151, I(A4)=0.148
④建决策树
将互信息最大的特征A1 "天气"作为树根,将14个样例按"天气"的三个取值进行分支,得到3个子集:
F1={1,2,8,9,11}-对应"天气"取值V1"晴"的序号
F2={3,7,12,13}-对应"天气"取值V2"多云"的序号
F3={4,5,6,10,14}-对应"天气"取值V3"雨"的序号
其中F2的例子全属于 P类,所以该标记为P,其余两个子集既含有正例又含有反例,递归调用建树算法
⑤递归建树
分别对于F1和F3子集利用ID3算法,在F1,F3中仍然对各特征(仍然是4个特征)求互信息.
F1中"天气"全取"晴"值,则H(U)=H(U/V),所以I(U/V)=0,其他3个特征中求出"湿度"互信息最大,以其为该分支的根结点,再向下分支,
"湿度"取值"高"的例子全为N类,该分支标记为N,"湿度"取值"正常"的例子全为P类,该分支标记为P;
F3中,对4个特征中求互信息,得到"风"特征的互信息最大,以其为该分支的根结点,再向下分支,
"风"取值"有"的例子全为N类,该分支标记为N,"风"取值"无"的例子全为P类,该分支标记为P,
至此得到决策树如下:
天 气
————
/ | \
晴 多云 雨
/ | \
湿度 P 风
——— —
/ \ / \
高 正常 有 无
| | | |
N P N P
⑷算法编程设计
①算法说明:
由DataManage标签页传来的CWinapp类中的RecordSet得到总记录条数、字段数（特征数=字段数-2 除去 序号、类别 2个字段），由特征数
nAttribute, 声明 nAttribute 个CFiledInfo类对象存放各特征信息.
CArray<CFiledInfo,CFiledInfo&> FieldInfoArray; FieldInfoArray.SetSize( nAttribute);
然后逐条记录读取,每条记录中得到的特征的信息后，如果特征取值在 FieldValueList 中没有则将该特征值append到 FieldValueList ，
否则将FieldValueCount值累加，将该条记录类别值累加到PositiveClassCount或NegativeClassCount。
记录读取结束后，得到所有特征的信息，据此计算 信息熵、条件熵、互信息，然后建立顶层决策树（直接建立到已经存在的CTreeCtrl上）
然后取得顶层决策树的各个属性值对应的数据库子集（如何取-加入Where条件重新建立RecordSet？）递归建树
②声明类 CFiledInfo,用来存放各个特征取不同值的情况(CFiledInfo在文件colledoc.h中定义)
//typedef CArray<HTREEITEM,HTREEITEM> CAttributeValueTree;//每个特征值对应的treectrl的item
class CFiledInfo:public CObject
{
public:
CFiledInfo();
CFiledInfo(int nAttribute);
CFiledInfo(const CFiledInfo& OtherFiledInfo);
CString sFieldName;//特征名称
int nFieldValueTypeCount;//特征取不同值的个数
CStringArray FieldValueList;//特征取到的所有不同值的列表
CAttributeValueTree m_AttributeValueTree; //和上面字符串数组一一对应，存放每个特征值对应的treectrl的item
CDWordArray FieldValueCount;//和上面字符串数组一一对应，存放 特征取到的不同值的个数
CDWordArray PositiveClassCount;//和上面字符串数组一一对应，存放 特征取到不同值时 该条记录为P类的个数
CDWordArray NegativeClassCount;//和上面字符串数组一一对应，存放 特征取到不同值时 该条记录为N类的个数
...
}
例如，对于特征 “天气”其CFiledInfo对象是这样的
sFieldName=天气
nFieldValueTypeCount=3 //晴，多云，雨 共3种值
FieldValueList[0]=晴，FieldValueList[1]=多云，FieldValueList[2]=雨
m_AttributeValueTree[0]=树控件Item晴的item值，m_AttributeValueTree[1]=树控件Item多云的item值，m_AttributeValueTree[2]=树控件Item雨的item值
FieldValueCount[0]=天气取值为晴的个数5，FieldValueCount[1]=天气取值为多云的个数4，FieldValueCount[2]=天气取值为雨的个数5
PositiveClassCount[0]=天气取值为晴的情况中属于P类的个数2，PositiveClassCount[1]=天气取值为多云的情况中属于P类的个数4，NegativeClassCount[2]=天气取值为雨的情况中属于P类的个数3
NegativeClassCount[0]=天气取值为晴的情况中属于N类的个数3，NegativeClassCount[1]=天气取值为多云的情况中属于N类的个数0，NegativeClassCount[2]=天气取值为雨的情况中属于P类的个数2
③编制递归建树函数
void CTreeViewDMfunction::RecursionTree(HTREEITEM &htiParent,_RecordsetPtr m_pRecordset, int nAttribute, CString sSQL)
//htiParent-插入特征值对应的CTreeCtrl的 item
//m_pRecordset指向增加了where条件的SQL对应的记录集;
//nAttribute 特征数=字段数-2 除去 序号、类别 2个字段,主要是为了调用RecordTree时传递参数用
//sSQL-存放对应当前记录集的SQL语句
④编制返回记录特征信息函数，其中CFieldInfoArray&为引用，所以函数调用结束后FieldInfoArray已经被修改，函数返回值为void也可以
这个函数由RecursionTree调用
void CTreeViewDMfunction::RecordTree(_RecordsetPtr m_pRecordset,CFieldInfoArray& FieldInfoArray,int nAttribute)
//ID3算法中，循环处理所有记录的各个特征，返回记录特征信息，用于计算互信息及建树
//m_pRecordset-传递进来的最新的包含特征值条件的记录子集，但RecursionTree最早调用时，是对全部的记录集
//FieldInfoArray-对应新记录子集m_pRecordset的各个特征的CFiledInfo对象的数组
//nAttribute-特征个数
⑤计算互信息函数，返回互信息最大的属性对应的Filed序号，这个函数由RecursionTree调用
int CTreeViewDMfunction::IuvCaculate(CFieldInfoArray& FieldInfoArray,int nAttribute)
//FieldInfoArray- 对应新记录子集m_pRecordset的各个特征的CFiledInfo对象的数组
//nAttribute-特征个数
⑥自建函数
int CCollectDoc::IsInStringArray(CString str, CStringArray* strArray)
//检查一个字符串str 是否在字符串数组中出现，如果出现则返回字符串数组的下标+1
//如果没有出现则返回 0