题解思路与方法

问题分析

给定一个二维数据集，每行是一个样本，最后一列为标签。要对每个特征计算基尼指数，选择基尼值最小的特征。基尼指数常用于决策树（CART）算法的划分标准。

算法流程

1. 记样本总数为 $n$，特征数为 $m$。

题目内容

给定一个数据集，其中每一行代表一个样本，每一列代表一个特征，最后一列是样本的标签。请你计算每个特征的基尼指数，并输出基尼指数最小的特征的索引和对应的基尼指数。 基尼指数的计算公式:对于一个特征，其基尼指数定义为:

$Gini(D,A)=$$\sum_{v∈V}$$\frac{|D^v|}{D}$$Gini(D^v)$

其中，$D$是数据集，$A$是特征，$V$是特征$A$得所有可能的取值，$D^V$是在特征$A$取值为$v$的情况下的数据集，$|D|$是数据集的样本数量，$|D^v|$是在特征$A$取之为$v$的情况的样本数量，$Gini(D^v)$是在特征$A$取值为$v$的情况下的数据集的基尼值，其计算公式为:

$Gini(D)=1-$$\sum_{k=1}^k(p_k)^2$

其中，$K$是标签的所有可能取值，$P_k$是在数据集$D$中标签取值为$k$的样本比例。

输入描述

一个二维列表，其中每一个子列表代表一个样本，每个样本包含一些特征值和一个标签值。所有的特征值都是数值型的，标签值是字符串。你可以假设输入的数据集至少包含一个样本，并且每个样本至少包含一个特征和一个标签。

输出描述

一个元组，第一个元素是基尼指数最小的特征的索引，第二个元素是该特征的基尼指数(保留1位小数)。如果有多个特征的基尼指数相同，输出索引最小的那个。

样例1

输入

[[1.0, 'yes'], [1.0, 'no'], [2.0, 'yes'], [2.0, 'no']]

输出

(0, 0.5)