数据挖掘与多标签分类策略研究

### 数据挖掘与多标签分类策略研究 #### 1. 数据挖掘中的瓦片信息处理 在数据挖掘领域，瓦片（tile）信息的处理是一个重要问题。其中，瓦片描述复杂度的测量是关键，这里采用如下方法： \[DL(\tau) = - \sum_{t\in T_{\tau}} \log(p_t) - \sum_{t\notin T_{\tau}} \log(1 - p_t) - \sum_{i\in I_{\tau}} \log(p_i) - \sum_{i\notin I_{\tau}} \log(1 - p_i)\] 其中，\(p_i = \frac{column\ marginal}{number\ of\ rows}\) 且 \(i \in I\)（列的情况对应 \(p_t\)，\(t \in T\)）。 信息内容（InformationContent）与描述长度（DescriptionLength）的比率代表了嵌入在瓦片中信息的压缩比，即数据挖掘者通过查看瓦片获得的关于数据库的信息量与传输该信息所需的比特数之比，这个比率被称为信息比率（InformationRatio），可用于衡量瓦片的有趣程度。 在计算最有趣的瓦片集时，由于信息比率只能对单个瓦片进行排名，而列表顶部的项集通常具有高度冗余性，不能简单地通过排名来计算最有趣的瓦片集。因此，可以采用集合覆盖算法，将在描述长度上限约束下寻找具有最大总体信息内容的瓦片集问题转化为预算最大集合覆盖问题，使用贪心算法可以得到较好的近似解。 #### 2. 实验数据集与设置 实验使用了两个真实世界的数据集：KDDcoauthors 和 KDDabstracts 数据集。 - **KDDcoauthors 数据集**：收集了 KDD 会议主要会议、研讨会论文和海报的作者信息，将每篇论文视为包含不同作者的事务，形成了一个包含 1669 个事务、3058 个项的事务性数据库。考虑到学术出版物中学生与导师合作的常见现象，使用学生 - 导师对作为先验知识。 - **KDDabstracts 数据集**：收集了 KDD 会议论文的摘要，每个摘要构成二进制数据库中的一个事务，每个词干化的单词作为一个项，形成了一个包含 843 个事务、6159 个单词的数据库。将由 228 个关键词组成的数据集作为先验知识。 实验设置为每个数据集展示前 5 个最有趣的结果表，每个表包含使用不同先验知识获得的子表，目的是展示结果在不同先验知识下的演变情况。 #### 3. 实验结果分析 以下是两个数据集使用不同方法的前 5 个最有趣项集的结果： |数据集|方法|项集|支持度|信息比率|是否在先验知识数据库中| | ---- | ---- | ---- | ---- | ---- | ---- | |KDDcoauthors 数据集|Frequency|W. Hsu, B. Liu|9|-|No| |KDDcoauthors 数据集|Frequency|Y. Ma, B. Liu|8|-|No| |KDDcoauthors 数据集|Frequency|M. Ester, H.P. Kriegel|7|-|No| |KDDcoauthors 数据集|Frequency|C.C. Aggarwal, P.S. Yu|7|-|No| |KDDcoauthors 数据集|Frequency|H. Tong, C. Faloutsos|7|-|No| |KDDcoauthors 数据集|Inf. Ratio - Constraints on Marginals|R. Bhaumik, C. Williams, R. D. Burke, B. Mobasher|3|1.2482|Yes| |KDDcoauthors 数据集|Inf. Ratio - Constraints on Marginals|Y. Ma, W. Hsu, B. Liu|6|1.2414|No| |KDDcoauthors 数据集|Inf. Ratio - Constraints on Marginals|J. Wu, J. Chen, H. Xiong|4|1.2116|No| |KDDcoauthors 数据集|Inf. Ratio - Constraints on Marginals|W. Perrizo, W. Jockheck, A. Perera, D. Ren, W. Wu, Yi Zhang|2|1.1744|Yes| |KDDcoauthors 数据集|Inf. Ratio - Constraints on Marginals|K. Zhang, B.A. Shaphiro, J. Tsong-Li Wang, D. Shasha|3|1.1353|Yes| |KDDcoauthors 数据集|Inf.Ratio - Constraints on Marginals and Tile sums|Y. Ma, W. Hsu, B. Liu|6|1.2223|No| |KDDcoauthors 数据集|Inf.Ratio - Constraints on Marginals and Tile sums|S. Tao, N. Anerousis, X. Yan|2|0.9804|No| |KDDcoauthors 数据集|Inf.Ratio - Constraints on Marginals and Tile sums|M.L. Antonie, A. Coman|3|0.9530|No| |KDDcoauthors 数据集|Inf.Ratio - Constraints on Marginals and Tile sums|A. Gershman, G. Wei, T. Gardinier|2|0.9273|N