另一门课的lab，lab太多让我写的lab变成缝合怪。
好吧，谈谈今日缝合怪之粗糙集属性约简+ID3决策树，用的是之前的UCI DNA数据集，基本上就是之前ID3决策树改了改。
（代码晚点贴，目前仅讲讲思路）
先贴UCI DNA数据集：https://download.csdn.net/download/pvfeldt/16142737?spm=1001.2014.3001.5501
关于数据集的信息详见：https://blog.csdn.net/pvfeldt/article/details/115216262?spm=1001.2014.3001.5501
一、粗糙集约简目的
对于ID3来说，如果是属性列很多的话，这个算法比较有意义，如果就那么几列的话，光约简的过程几个loop复杂度就要比直接遍历还高。就我的理解而言，就是把属性中不是很重要的列排除在熵和信息增益的计算之外，其余还是原来的ID3算法。
二、等价类
等价类就是同一分类下的所有行。
以UCI DNA数据集为例，可以分为3个等价类，分别是分类为1（第61列为1）的集合，分类为2（第61列为2）的集合，分类为3（第61列为3）的集合。
三、差别矩阵
差别矩阵是一个记录两个属于不同等价类的行的属性差别的矩阵。
1.判断是不是同一等价类
如果是同一等价类，该位置空集。
如果是不同等价类，进入2。
2.判断每两行之间不同的属性是哪几列
找到不同的列以后，把列号存进差别矩阵中。
其中需要注意的是，差别矩阵的行和列代表的是两个相互比较的行的行号，所以其实只要算一个上三角或者下三角就够了。
四.求核
把差别矩阵的非零元素都拿出来求交集，交到若干个集合再交就为空集的时候停，然后可以得到相对小的那个集合为核。
上面是我对于粗糙集约简的理解，具体例子可以看，因为我也是照着论文里的算法在类比实现：
[1] 余建军, 张琼之. 基于粗糙集的决策树ID3算法. 计算机系统应用, 2020, 29(4): 156-162.
五、粗糙集约简+ID3决策树
关于ID3算法，详见：https://blog.csdn.net/pvfeldt/article/details/115216262?spm=1001.2014.3001.5501
和之前ID3相比，修改的地方，仅为加了粗糙集约简过程，在计算熵和信息增益的时候只计算了指定几列。
然后遇到了点问题，集合计算怎么写成code，按普通的方式可能会交到最后成空集。对于属性列较少的数据集可以手动集合运算，我跟朋友自嘲过我这是个半自动算法，但对于DNA数据集来说手动算可是相当窒息的，而且属性列少它也没有约简的必要。
我具体实现方式，最后等lab due了结合代码一起讲。
六、完整代码
1.准确率比较
具体实现是取了数据集的前300行。
普通ID3：

粗糙集约简+ID3：

实现了准确率基本不波动。
然后实验下来的结果是，如果排除粗糙集约简过程的话，约简了的ID3肯定比普通ID3快。但约简过程本身它就很慢，造成实际运行起来不如不约简，也许是我哪里写的复杂度又高了，一个不太聪明的尝试，裂开。。
2.代码
等lab due了更新。
Over.