思路

这个问题的核心是模拟决策树（特别是CART算法）在选择最佳分裂特征时的过程。决策树在构建时，需要在每个节点上选择一个特征进行分裂，目标是让分裂后的数据子集“纯度”尽可能高。 基尼指数就是衡量数据纯度的一种指标。一个集合的基尼指数越小，其纯度越高。

题目要求我们找到使整个数据集在分裂后基尼指数最小的那个特征。解题的整体思路如下：

1. 遍历所有特征：我们需要对数据集的每一个特征（即输入二维list中每个子list的除了最后一个元素之外的其它元素）进行评估。

2. 计算每个特征的条件基尼指数：对于每一个特征 A，我们需要计算如果用它来分裂数据集，最终得到的条件基尼指数 $Gini(D|A)$ 是多少。

   • 确定分裂点：一个特征可能有多个不同的取值。题目中的描述是“根据特征 A 是否取某一值 a 被分割为 $D_1, D_2$”。这意味着对于特征 A 的每一个唯一值 a，我们都可以进行一次二元分裂：

     • 子集 $D_1$：特征 A 的值等于 a 的所有样本。
     • 子集 $D_2$：特征 A 的值不等于 a 的所有样本。

   • 选择特征的最佳分裂：一个特征可能会因为其不同的取值而产生多个不同的条件基尼指数。例如，如果一个特征有 v1, v2, v3 三个值，我们可以分别计算按 v1 分裂、按 v2 分裂、按 v3 分裂后的基尼指数。该特征最终的评判指标，是这所有可能分裂中产生的最小的那个基尼指数。

3. 比较并找出最优特征：我们依次计算出每个特征的最小条件基尼指数，然后比较这些值。值最小的那个特征，就是我们要找的最佳分裂特征。我们返回该特征的索引即可。

4. 处理特殊情况：

   • 如果一个分裂产生的子集为空，其基尼指数为0。
   • 如果一个特征的所有值都相同，那么无论如何分裂，都会导致一个子集为空，另一个子集是全集。这种分裂是没有意义的，其条件基尼指数等于未分裂前的总基尼指数。
   • 如果多个特征算出的最小基尼指数相同，根据题目样例和常规算法实践，选择索引靠前的那个特征。

好的，这是一个不包含任何中文提示，可以直接运行并处理输入的版本。

将以下代码复制并运行。您可以直接粘贴完整的二维列表（例如 [[0,0,0,0,0],[0,0,0,1,0],[0,1,0,1,1],[0,1,1,0,0],[0,0,0,0,0]]）到终端，然后按 Enter，再按 Ctrl+D (Linux/macOS) 或 Ctrl+Z + Enter (Windows) 来结束输入并查看结果。

python

import sys
import numpy as np
from collections import Counter

def calculate_gini(labels):
    """
    计算一个数据子集的基尼指数。
    """
    if len(labels) <= 1:
        return 0.0
    
    counts = Counter(labels)
    total_samples = len(labels)
    
    gini = 1.0
    for count in counts.values():
        p = count / total_samples
        gini -= p ** 2
        
    return gini

def find_best_feature(data):
    """
    找到使整个数据集合基尼指数最小的特征对应的索引。
    """
    try:
        dataset = np.array(data)
    except ValueError:
        return -1 # 子列表长度不一致

    if dataset.ndim != 2 or dataset.shape[1] < 2:
        return -1 # 非二维或列数不足

    X = dataset[:, :-1]
    y = dataset[:, -1]
    
    num_samples, num_features = X.shape
    
    min_gini_value = float('inf')
    best_feature_idx = -1
    
    for i in range(num_features):
        feature_col = X[:, i]
        unique_values = np.unique(feature_col)
        
        if len(unique_values) <= 1:
            continue
            
        current_feature_min_gini = float('inf')
        
        for value in unique_values:
            mask = (feature_col == value)
            
            d1_labels = y[mask]
            d2_labels = y[~mask]
            
            if len(d1_labels) == 0 or len(d2_labels) == 0:
                continue
            
            gini1 = calculate_gini(d1_labels)
            gini2 = calculate_gini(d2_labels)
            
            p1 = len(d1_labels) / num_samples
            conditional_gini = p1 * gini1 + (1 - p1) * gini2
            
            if conditional_gini < current_feature_min_gini:
                current_feature_min_gini = conditional_gini

        if current_feature_min_gini < min_gini_value:
            min_gini_value = current_feature_min_gini
            best_feature_idx = i
            
    return best_feature_idx

def main():
    """
    主函数，用于读取输入并执行计算。
    """
    try:
        # 读取所有输入行并将其合并为一个字符串
        full_input_str = sys.stdin.read()
        # 使用 eval 将完整的字符串转换为 list 对象
        input_data = eval(full_input_str)
    except (SyntaxError, NameError):
        # 如果输入不是有效的 Python 列表格式，则不执行任何操作
        return

    # 检查是否成功解析为列表
    if not isinstance(input_data, list):
        return

    # 调用核心函数进行计算
    best_idx = find_best_feature(input_data)
    
    # 仅当找到有效索引时才打印结果
    if best_idx != -1:
        print(best_idx)

if __name__ == "__main__":
    main()

题目内容

某电商平台计划向定向用户发起一次大促活动，向受邀用户定向投放活动入口。通过构建一系列特征，使用决策树对用户进行分类，被分类为正样本的用户可以获得入场资格。使用基尼指数作为特征的优先级决策指标，给定一个数据集，其基尼指数可以表示为:

$Gini(D)=1-\sum^k_{k=1}(\frac{∣C_k∣}{∣D∣})^2$

其中 $C_k$ 代表的是属于某一类的样本个数，$D$ 是整个数据集的样本数量，如果样本集合 $D$ 根据特征 $A$ 是否取某一值 $a$ 被分割为 $D_1,D_2$ ，两部分，那么在特征 $A$ 的条件下，集合的基尼指数可以定义为:

$Gini(D∣A)=\frac{∣D_1∣}{∣D∣}Gini(D_1)+\frac{∣D_2∣}{∣D∣}Gini(D_2)$

现给定一个数据集，要求给出对于使整个集合基尼指数最小的特征，请结合题目信息，输入、输出和补充完成完成作答。

输入描述

输入一个二维 $list$ ，每个子 $list$ 最后一个元素是 $label$ ，其他元素是对应特征的值。

输出描述

要求给出使整个数据集合基尼指数最小的特征对应的索引。

补充说明

$(1)$可以使用形如 $numpy、pandas$ 的第三方代码库。

$(2)$为了保证唯一性，请严格遵循输入输出描述进行作答。

$(3)$形如 $sys.stdin$ 等方法结合 $for$ 循环和 $eval$ 函数即可读取并还原输入数据。

样例1

输入

[[0,0,0,0,0],[0,0,0,1,0],[0,1,0,1,1],[0,1,1,0,0],[0,0,0,0,0]]

输出

1

说明

第 $2$ 列特征下，整个集合对应的基尼指数最小，其索引为 $1$ ，所以返回值为 $1$