题解

题面描述

给定包含 $N$ 篇文档的文本数据集，每篇文档由一个类别标签（取值为 "positive" 或 "negative"）和文本内容构成。要求使用 $Bag\text{-}of\text{-}Words$ 模型提取文本特征，利用卡方检验计算每个单词与类别标签之间的相关性。卡方统计量的计算公式为
$\chi^2$= $\sum_{i=1}^{2}$ $\sum_{j=1}^{2}$ $\frac{(O_{ij}-E_{ij})^2}{E_{ij}}$ 其中 $O_{ij}$ 表示观察到的频数，$E_{ij}$ 表示在独立性假设下计算的期望频数，计算公式为

具体步骤如下：

1. 读取输入数据集，第一行是文档数 $N$，接下来的 $N$ 行每行格式为

题目内容

假设你团队正在开发一个文本分类模型，用于将客户评论分类为正面或负面。由于文本数据具有高维度的特性，模型训练和预测的效率受到影响。你提议使用卡方检验进行特征选择，挑选出与分类任务最相关的词汇，降低数据的维度，从而提高模型的性能。

请你编写一个程序，使用卡方检验对给定的文本数据集进行特征选择。

具体要求如下:

1.读取输入数据集，包含多篇标注了类别的文本文档。

2.提取特征，采用词频($Bag-of-Words$)模型，将文本转换为特征向量。(不能忽视单词字母大小写)

3.计算每个特征(词)的卡方统计量，衡量其与类别标签的相关性。

4.根据卡方统计量选择前$(k)$个最重要的特征。

5.输出选定的特征列表。

输入描述

• 第一行包含一个整数$(N)$，表示文档的数量。
• 接下来的$(N)$行，每行包含一个文档，格式为:$<label>$\t
• $<label>$: 文档的类别，取值为'positive'或'negative',
• \t:一个制表符，分隔类别标签和文档内容。
• $<text>$: 文档的内容，由若干单词组成，单词之间用空格分隔。
• 最后一行包含一个整数$(k)$，表示需要选择的特征数量。

输出描述

输出$(k)$行，每行包含一个单词(特征)，按照卡方统计量从大到小排序。如果多个特征的卡方值相同，按字母顺序升序排列。

补充说明

• 卡方检验公式

对于每个特征(单词)，卡方统计量计算公式为:

$x^2$=$\sum^2_{i=1}$$\sum ^2_{j=1}$$\frac{(O_{ij}-E_{ij})^2}{E_{ij}}$ 其中:

• $(O_{ij})$是观察到的频数，表示特征是否出现和类别的四种组合情况,

• $E_{ij}$是期望频数，按照独立性假设计算:

  $E_{ij}$=$\frac{(特征是否出现的行数)×(类别的列和)}{总样本数}$

样例1

输入

6
positive I love this movie
negative I hate this movie
positive This film was fantastic
negative This film was terrible
positive What a great experience
negative What a bad experience
3

输出

bad
fantastic
great

说明

• 步骤1：读取$6$ 篇文档及其类别标签。
• 步骤 2：统计每个单词在不同类别中的出现次数，计算卡方统计量。
• 步骤3：根据卡方值从大到小排序，选择前$3$个特征。自测验入
• 步骤4：输出选定的特征列表。

样例2

输入

2
1 1

输出

-1