中文网页分层分类与网页广播聚类关联规则挖掘技术解析

### 中文网页分层分类与网页广播聚类关联规则挖掘技术解析 #### 中文网页分层分类技术 在中文网页分类领域，为了实现高效且准确的分类，一系列技术和算法被提出。 ##### N - grams提取算法 N - grams提取是整个分类流程的基础步骤，其目的是从文档集合中提取出符合特定约束条件的N - grams集合。该算法的具体步骤如下： 1. **提取1 - grams集合S1**：逐个扫描文档集合D中的所有文档，提取出所有满足约束条件1和2的1 - grams。 2. **提取2 - grams集合S2**：对S1进行笛卡尔积运算S1×S1，生成候选2 - grams集合C2，然后去除其中不符合约束条件1和2的项，剩余项构成S2。 3. **提取3到MAX - N的N - grams集合**： - 对于i从3到MAX - N，构建候选i - grams集合Ci。对于Si - 1中的任意两个(i - 1) - gram项tm和tn，若tm(k + 1) = tn(k)（k = 1̚(i - 2)），则Ci = Ci∪tmtn(i - 1)。 - 去除Ci中不符合约束条件1和2的项，剩余项构成Si。 4. **合并所有N - grams集合**：最终的N - grams集合S为S1∪…∪SMAX - N。 以下是该算法的伪代码表示： ```plaintext Algorithm 1: N - grams extraction Input: document collection D, min - tf, min - df and MAX - N. Output: A set of N - grams S (N ≤ MAX - N) that meet Constraint 1 and 2. Process (basic steps): 1. Finding the 1 - grams set S1: Scanning all documents in D one by one, and extracting all 1 - grams that meet Constraint 1 and 2. 2. Finding the 2 - grams set S2: Carrying out Cartesian product S1×S1 to produce the candidate 2 - grams set C2 from which the items not conforming to Constraint 1 and 2 are removed, and the left items make up S2. 3. For i = 3 to MAX - N do: 3.1 Constructing the candidate i - grams set Ci: for two arbitrary (i - 1) - gram items tm and tn in Si - 1, tm(k) and tn(k) (k = 1̚(i - 1)) refer to the k - th character in tm and tn respectively. If tm(k + 1) = tn(k) for k = 1̚(i - 2), then Ci = Ci∪tmtn(i - 1). 3.2 Removing the items in Ci that not conforming to Constraint 1 and 2, then the left items make up Si. 4. S = S1∪…∪SMAX - N. ``` ##### 特征选择 提取的N - grams数量通常非常大，这会影响分类的质量和效率。因此，需要对提取的N - grams进行特征选择，以获取用于分类的文档特征子集。这里使用了三种统计方法： 1. **信息增益（IG）**：信息增益衡量了通过知道文档中某个词项的存在或缺失而获得的用于类别预测的信息量。词项t的信息增益定义为： \[IG(t)=\sum_{c\in C}P(c)\left[log\frac{P(c)}{P(c|t)}+log\frac{P(c)}{P(c|\neg t)}\right]\] 2. **互信息（MI）**：互信息是统计语言建模中常用的衡量词项关联的准则。词项t和类别c之间的互信息准则定义为： \[MI(t,c)=log\frac{P(t,c)}{P(t)P(c)}\] 为了衡量词项在全局特征选择中的优劣，将词项的类别特定得分以两种方式进行组合： - 平均得分：\(MI_{avg}(t)=\sum_{c\in C}P(c)MI(t,c)\) - 最大得分：\(MI_{max}(t)=\max_{c\in C}MI(t,c)\) 3. **卡方统计量（χ²）**：卡方统计量衡量了词项t和类别c之间的独立性缺失程度。词项t和类别c之间的卡方统计量定义