分类

类型:
不限 游戏开发 计算机程序开发 Android开发 网站开发 笔记总结 其他
评分:
不限 10 9 8 7 6 5 4 3 2 1
原创:
不限
年份:
不限 2018 2019 2020

技术文章列表

  • 中山大学智慧健康服务平台应用开发-基本的UI界面设计

    一、实验题目实验一: 中山大学智慧健康服务平台应用开发
    二、实现内容2.1 基本的UI界面设计实现一个Android应用,界面呈现如图中的效果。

    2.1.1 要求
    该界面为应用启动后看到的第一个界面
    各控件的要求

    标题字体大小20sp,与顶部距离20dp,居中图片与上下控件的间距均为20dp,居中输入框整体距左右屏幕各间距20dp,内容(包括提示内容)如图所示,内容字体大小18sp按钮与输入框间距10dp,文字大小18sp。按钮背景框左右边框与文字间距10dp,上下边框与文字间距5dp,圆角半径180dp,背景色为#3F51B5四个单选按钮整体居中,与输入框间距10dp,字体大小18sp,各个单选按钮之间间距10dp,默认选中的按钮为第一个

    2.1.2 使用的组件TextView、EditText、ConstraintLayout、Button、ImageView、RadioGroup、RadioButton。实现一个Android应用,界面呈现如图中的效果。
    2.1.3 验收内容
    各控件的位置,间距,字体大小等属性与要求无误
    图片大小不作为验收内容给之一

    2.2 事件处理
    2.2.1 要求
    该界面为应用启动后看到的第一个界面
    各控件处理的要求

    点击搜索按钮
    如果搜索内容为空,弹出Toast信息“搜索内容不能为空”如果搜索内容为“Health”,根据选中的RadioButton项弹出如下对话框点击“确定”,弹出Toast信息——对话框“确定”按钮被点击点击“取消”,弹出Toast 信息——对话框“取消”按钮被点击否则弹出如下对话框,对话框点击效果同上

    RadioButton选择项切换:选择项切换之后,弹出Toast信息“XX被选中”,例如从图片切换到视频,弹出Toast信息“视频被选中”

    2.2.2 验收内容
    布局是否正常
    搜索内容为空时,提示是否正常
    输入搜索内容后,点击搜索按钮是否能根据不同的搜索内容显示相应的弹出框,以及弹出框内容是否符合要求
    点击弹出框的相应按钮是否能提示正确的内容
    RadioButton切换时,提示是否正常

    2.3 Intent、Bundle的使用以及RecyclerView、ListView的应用本次实验模拟实现一个健康食品列表,有两个界面,第一个界面用于呈现食品列表如下所示。

    数据在”manual/素材”目录下给出。
    点击右下方的悬浮按钮可以切换到收藏夹。

    上面两个列表点击任意一项后,可以看到详细的信息:

    2.3.1 UI要求食品列表
    每一项为一个圆圈和一个名字,圆圈和名字都是垂直居中。圆圈内的内容是该食品的种类,内容要处于圆圈的中心,颜色为白色。食品名字为黑色,圆圈颜色自定义,只需能看见圆圈内的内容即可。
    收藏夹
    与食品列表相似。
    食品详情界面
    界面顶部

    顶部占整个界面的1/3。每个食品详情的顶部颜色在数据中已给出。返回图标处于这块区域的左上角,食品名字处于左下角,星标处于右下角,边距可以自己设置。 返回图标与名字左对齐,名字与星标底边对齐。 建议用RelativeLayout实现,以熟悉RelativeLayout的使用。
    界面中部

    使用的黑色argb编码值为#D5000000,稍微偏灰色的“富含”“蛋白质”的argb编码值为#8A000000。”更多资料”一栏上方有一条分割线,argb编码值为#1E000000。右边收藏符号的左边也有一条分割线,要求与收藏符号高度一致,垂直居中。字体大小自定。”更多资料”下方分割线高度自定。这部分所有的分割线argb编码值都是#1E000000。
    界面底部

    使用的黑色argb编码值为#D5000000。
    标题栏
    两个界面的标题栏都需要去掉。
    2.3.2 功能要求使用RecyclerView实现食品列表。点击某个食品会跳转到该食品的详情界面,呈现该食品的详细信息。长按列表中某个食品会删除该食品,并弹出Toast,提示 “删除XX” 。
    点击右下方的FloatingActionButton,从食品列表切换到收藏夹或从收藏夹切换到食品列表,并且该按钮的图片作出相应改变。
    使用ListView实现收藏夹。点击收藏夹的某个食品会跳转到食品详情界面,呈现该食品的详细信息。长按收藏夹中的某个食品会弹出对话框询问是否移出该食品,点击确定则移除该食品,点击取消则对话框消失。
    商品详情界面中点击返回图标会返回上一层。点击星标会切换状态,如果原本是空心星星,则会变成实心星星;原本是实心星星,则会变成空心星星。点击收藏图表则将该食品添加到收藏夹并弹出Toast提示 “已收藏” 。
    三、实验结果3.1 基本的UI界面设计与基础事件处理3.1.1 实验截图切换按钮时候,显示当前切换到的按钮名字,如下图,视频被选中:

    搜索Health关键词时,显示对话框搜索成功:

    搜索其他关键词,无法正确搜索,显示搜索错误对话框:

    点击取消按钮时,显示toast取消被单击:

    3.1.2 实验步骤以及关键代码这个实验前两部分包括简单的UI设计以及UI的交互。
    首先,我们当然要从UI的构建开始。
    1.插入标题以及图片这里应用到了TextView以及ImageView两个控件。由于本次的ui是使用ConstraintLayout布局,所以必须对每一个控件设置左右上下分别对齐什么。故要利用app:layout_constraintLeft_toLeftOf 等属性,表示该组件的左边对齐于xx的左边,这里的textview就要与parent即整个页面的左边对齐,然后设置居中。宽度,大小就根据实验要求来设置,而id是用于后面的交互部分识别该控件用的。
    <TextView android:id="@+id/title" android:layout_width="wrap_content" android:layout_height="wrap_content" android:text="@string/title" android:textSize="20sp" app:layout_constraintTop_toTopOf="parent" android:layout_marginTop="20dp" app:layout_constraintLeft_toLeftOf="parent" app:layout_constraintRight_toRightOf="parent" /> <ImageView android:id="@+id/image" android:layout_width="wrap_content" android:layout_height="wrap_content" android:layout_marginTop="20dp" android:src="@mipmap/sysu" app:layout_constraintBottom_toTopOf="@+id/search_content" app:layout_constraintLeft_toLeftOf="parent" app:layout_constraintRight_toRightOf="parent" app:layout_constraintTop_toBottomOf="@id/title" />
    2.插入搜索输入框以及搜索按钮对于输入框要使用EditText控件,对于按钮要使用Button控件。对于输入框的显示内容,预先在string文件中写入,然后直接在控件中调用即可。对于button还用到了style属性,表示直接引用style写好的按钮样式。而style里面又调用了其他文件中已经预设好的属性,例如color中颜色。
    <style name="search_button"> <item name="android:textColor">@color/white</item> <item name="android:background">@drawable/button</item> </style>
    <EditText android:id="@+id/search_content" android:layout_width="0dp" android:layout_height="wrap_content" android:layout_marginLeft="20dp" android:layout_marginRight="10dp" android:layout_marginTop="20dp" android:gravity="center" android:hint="@string/search_content" android:textSize="18sp" app:layout_constraintBottom_toTopOf="@+id/radioGroup" app:layout_constraintLeft_toLeftOf="parent" app:layout_constraintRight_toLeftOf="@+id/but1" app:layout_constraintTop_toBottomOf="@id/image" /> <Button android:id="@+id/but1" style="@style/search_button" android:layout_width="wrap_content" android:layout_height="wrap_content" android:layout_marginRight="20dp" android:layout_marginTop="20dp" android:text="@string/search_button" android:textSize="18sp" app:layout_constraintBottom_toTopOf="@+id/radioGroup" app:layout_constraintRight_toRightOf="parent" app:layout_constraintTop_toBottomOf="@id/image" />
    3. 插入选择按钮选择按钮组要使用RadioGroup与RadioButton相配合,在group中设置边距以及大小,对于每一个radiobutton使用其他设置好的样式属性,在第一个选择按钮中设置checked属性设置为true就会默认第一个按钮被选定。
    <RadioGroup android:id="@+id/radioGroup" android:layout_width="wrap_content" android:layout_height="wrap_content" android:layout_marginTop="10dp" android:orientation="horizontal" app:layout_constraintLeft_toLeftOf="parent" app:layout_constraintRight_toRightOf="parent" app:layout_constraintTop_toBottomOf="@id/search_content"> <RadioButton android:id="@+id/selection1" style="@style/MyRadioButton" android:layout_height="match_parent" android:checked="true" android:text="@string/selection1" /> <RadioButton android:id="@+id/selection2" style="@style/MyRadioButton" android:text="@string/selection2" /> <RadioButton android:id="@+id/selection3" style="@style/MyRadioButton" android:text="@string/selection3" /> <RadioButton android:id="@+id/selection4" style="@style/MyRadioButton" android:text="@string/selection4" /> </RadioGroup>
    这就基本完成了UI的界面设置,接下来要根据他们的id来设置一些函数实现实验要求,例如弹出对话框或者toast等等。
    4.获取搜索输入框的内容,以及点击搜索按钮显示提示这一步主要要调用findViewById这个函数来分别得到输入框以及按钮,给按钮设置监听函数setOnClickListener, 然后在里面对于输入框的内容searchContent.getText().toString()来进行判断,分别有三种情况,搜索内容为空,搜索内容为Health,搜索内容为其他。
    然后,关于对话框的显示要使用dialog,分别给它设置标题,中间内容以及按钮。而toast则要对于对话框的按钮来设置监听函数,当点击时候来Toast.makeText()显示一个具体的toast内容。
    Button button =(Button) findViewById(R.id.but1); final EditText searchContent = (EditText) findViewById(R.id.search_content); button.setOnClickListener(new View.OnClickListener(){ @Override public void onClick(View view){ //搜索为空情况 if(TextUtils.isEmpty(searchContent.getText().toString())){ //弹出 Toast Toast.makeText(MainActivity.this, "搜索内容不能为空",Toast.LENGTH_SHORT).show(); } //搜索成功情况 else if(searchContent.getText().toString().equals("Health")){ AlertDialog.Builder dialog = new AlertDialog.Builder(MainActivity.this); dialog.setTitle("提示"); RadioButton temp = findViewById(radioGroup.getCheckedRadioButtonId()); dialog.setMessage(temp.getText().toString()+"搜索成功"); dialog.setPositiveButton("确定", new DialogInterface.OnClickListener() { @Override public void onClick(DialogInterface dialogInterface, int i) { Toast.makeText(MainActivity.this, "对话框“确定”按钮被点击",Toast.LENGTH_SHORT).show(); } }); dialog.setNegativeButton("取消", new DialogInterface.OnClickListener() { @Override public void onClick(DialogInterface dialogInterface, int i) { Toast.makeText(MainActivity.this, "对话框“取消”按钮被点击",Toast.LENGTH_SHORT).show(); } }); dialog.show(); } //搜索失败情况 else{ AlertDialog.Builder dialog = new AlertDialog.Builder(MainActivity.this); dialog.setTitle("提示"); dialog.setMessage("搜索失败"); dialog.setPositiveButton("确定", new DialogInterface.OnClickListener() { @Override public void onClick(DialogInterface dialogInterface, int i) { Toast.makeText(MainActivity.this, "对话框“确定”按钮被点击",Toast.LENGTH_SHORT).show(); } }); dialog.setNegativeButton("取消", new DialogInterface.OnClickListener() { @Override public void onClick(DialogInterface dialogInterface, int i) { Toast.makeText(MainActivity.this, "对话框“取消”按钮被点击",Toast.LENGTH_SHORT).show(); } }); dialog.show(); } } });
    4.对于选择按钮组的切换与上面相同,先要通过id来找到相应的控件,然后对于radioGroup来设置选择改变的监听函数,当切换的时候会根据选择的不同按钮上的信息来生成一个toast。
    final RadioGroup radioGroup = findViewById(R.id.radioGroup); final RadioButton radioButton = findViewById(radioGroup.getCheckedRadioButtonId()); radioGroup.setOnCheckedChangeListener(new RadioGroup.OnCheckedChangeListener(){ @Override //选择变化时,弹出toast提示信息 public void onCheckedChanged(RadioGroup group, int checkedID){ String str = ""; RadioButton select1 = findViewById(R.id.selection1); RadioButton select2 = findViewById(R.id.selection2); RadioButton select3 = findViewById(R.id.selection3); RadioButton select4 = findViewById(R.id.selection4); if(select1.getId() == checkedID){ str = select1.getText().toString(); } else if(select2.getId() == checkedID){ str = select2.getText().toString(); } else if(select3.getId() == checkedID){ str = select3.getText().toString(); } else if(select4.getId() == checkedID){ str = select4.getText().toString(); } Toast.makeText(MainActivity.this, str + "被选中",Toast.LENGTH_SHORT).show(); } });
    3.1.3 实验遇到的困难以及解决思路1.关于UI部分的边距问题起初对于ConstraintLayout布局不熟悉,不理解为什么需要对于一个控件的左右边限制跟随另一个的左右边,单纯认为只需要改变margin即可完成布局。而实际情况时,根据布局出来的结果可以看到仅改变margin之后相对于父亲来改变距离,而不能完全地设置两个组件的相应距离。于是完成一个组件时候,对于下一个组件的上下左右边缘要根据相对应的组件来限制一下。
    而在修改UI的时候,多使用preview功能以及在xml下切换至design模式,可以清晰看出组件之间的边距关系,查看布局是否正确。

    2.如何让中间的搜索框以及搜索按钮以合适的大小安放在同一行?这个问题就是在ui部分一直困扰我的,由于搜索框与左边要有限制,在右边又要与搜索按钮有限制,而搜索框也要与右边有限制。这样设置 app:layout_constraintRight_toRightOf 等等需要十分注意。
    而且输入框的长度也要合适,当 android:layout_width=”wrap_parent” 时候仅显示了提示内容的长度。而 android:layout_width=”fill_parent” 时候又占满了整个显示屏,显然是不行。而选择固定长度则不符合我们安卓手机界面设计的原则,无法在各种机型中显示合理。
    经过查询多种资料,可以通过设置 android:layout_width=”0dp” 来使这个输入框自适应边距,因此问题迎刃而解。
    3.实现交互部分的api比较通用的找到控件的函数为findViewById,通过id来找到控件,这与我们设置的id就很关键了,必须要注意大小写以及名字的正确性。
    关于组件的监听函数,包括点击按钮,切换radiobutton等等,都要了解其中的参数,查看手册。
    3.2 Intent、Bundle的使用以及RecyclerView、ListView的应用3.2.1 实验截图下图为食物列表的展示,浮标图案为前往收藏夹:

    下图为收藏夹初始页面的展示,浮标图案为返回主页样式:

    下图为大豆食物的详情信息:

    下图为点击星星以及收藏按钮产生的事件截图:

    下图为收藏大豆事件后,收藏夹的信息截图:

    下图为长按大豆列表删除时的操作截图:

    下图为在食物列表长按食物删除的操作截图:

    3.2.2 实验步骤以及关键代码本次实验的内容有点多,要完成三个页面的设计以及不同活动之间的信息交互。
    1.完成从搜索页面跳转到FoodList页面由于上次的实验中完成了一个搜索的界面,我为了将两次实验连接到一起,因此在搜索页面搜索switch时候会跳转到食物列表页面(即本次实验内容)
    要记得在mainfest中注册该活动,否则会出现应用闪退的现象,下面的两个页面也是如此,不再详述。

    这里使用startActivity以及intent来实现页面的跳转。
    ...//切换至食物列表,第二周任务的衔接第一周任务else if(searchContent.getText().toString().equals("switch")){ Intent intent = new Intent(); intent.setClass(MainActivity.this, FoodList.class); startActivity(intent);}...
    2.存储食物数据为了保存这些食物数据,我新建了一个MyCollection类来存储,类函数包括构造函数以及各个参数的get,set函数,不必详述。
    public class MyCollection implements Serializable { private String name; //食物名字 private String content; //食物图标 private String type; //食物种类 private String material; //食物成分 private boolean is_collected; //是否被收藏 private boolean is_star; //是否被加星 public MyCollection(){ is_collected =false; } public MyCollection(String _name, String _content, String _type, String _material, boolean _is_star){ name = _name; content = _content; type =_type; material = _material; is_star = _is_star; is_collected = false; } ... //各种get,set函数
    3.利用RecycleView实现FoodList这一部分可以说是这次实验的难点,我用了一天的时间才能理解RecycleView的实现过程。一个RecycleView需要一个Adater以及一个Holder来实现,存储的数据利用Holder,而用户点击的事件则利用Adater.
    首先实现MyViewHolder类,它必须继承RecyclerView.ViewHolder。其中通过findViewById函数来查找列表的填充项,如果已经查找过了就从数组中直接拿出即可,这样可以加快应用的速度,优化性能。
    public class MyViewHolder extends RecyclerView.ViewHolder { private SparseArray<View> views; private View view; public MyViewHolder(View _view) { super(_view); view = _view; views = new SparseArray<View>(); } public <T extends View> T getView(int _viewId) { View _view = views.get(_viewId); if (_view == null) { //创建view _view = view.findViewById(_viewId); //将view存入views views.put(_viewId, _view); } return (T) _view; }}
    接着是MyRecyclerViewAdapter类,它必须继承RecyclerView.Adapter类,其中利用MyViewHolder来存储列表的数据。该类实现点击的功能,这里新建了item的点击监听器,包括单击以及长按两种操作。
    除此之外,它必须重构onCreateViewHolder,onBindViewHolder,getItemCount这三个函数。
    在onBindViewHolder中为item来重构点击事件,其中长按事件函数要返回false,不然会与单击事件同时触发
    public class MyRecyclerViewAdapter<T> extends RecyclerView.Adapter<MyViewHolder>{ private List<MyCollection> data; private Context context; private int layoutId; private OnItemClickListener onItemClickListener; public MyRecyclerViewAdapter(Context _context, int _layoutId, List<MyCollection> _data){ context = _context; layoutId = _layoutId; data = _data; } //点击事件的接口 public interface OnItemClickListener{ void onClick(int position); void onLongClick(int position); } public void setOnItemClickListener(OnItemClickListener _onItemClickListener) { this.onItemClickListener = _onItemClickListener; } //删除数据 public void deleteData(int position){ data.remove(position); } @Override public MyViewHolder onCreateViewHolder(ViewGroup parent, int viewType) { MyViewHolder holder = new MyViewHolder(LayoutInflater.from(context).inflate(R.layout.item, parent, false)); return holder; } @Override public void onBindViewHolder(final MyViewHolder holder, int position) { //convert ((TextView)holder.getView(R.id.recipeName)).setText(data.get(position).getName()); ((TextView)holder.getView(R.id.img)).setText(data.get(position).getContent()); if (onItemClickListener != null) { //单击 holder.itemView.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View view) { onItemClickListener.onClick(holder.getAdapterPosition()); } }); //长按 holder.itemView.setOnLongClickListener(new View.OnLongClickListener() { @Override public boolean onLongClick(View view) { onItemClickListener.onLongClick(holder.getAdapterPosition()); return false; } }); } } @Override public int getItemCount() { if(!data.isEmpty()) return data.size(); return 0; }}
    我们先在FoodList.xml布局文件中预先设置了recycleview,以及新建一个item.xml来初始化列表项,包括两个textView组件来存放食物的标志以及文字。
    在FoodList.java中来通过recycleview的id来找到该组件,然后来通过adapter来设置。首先要利用setLatoutManager函数类似ListView来设置layout。
    然后设置监听器,单击跳转到详情页面根据点击的位置gotoDetail_for_Foodlist(position);该函数在后面部分叙述,此处只需知道它跳转到了详情页面。
    而长按时,要将数据删除,这里使用notifyItemRemoved(position);以及之前在Adapter实现了的删除函数来实现这一功能,最后弹出一个toast。
    RecyclerView recyclerView = findViewById(R.id.recyclerView); recyclerView.setLayoutManager(new LinearLayoutManager(FoodList.this)); // 类似ListView final MyRecyclerViewAdapter myAdapter = new MyRecyclerViewAdapter<MyCollection>(FoodList.this, R.layout.item, data2); myAdapter.setOnItemClickListener(new MyRecyclerViewAdapter.OnItemClickListener() { @Override public void onClick(int position) { gotoDetail_for_Foodlist(position); } @Override public void onLongClick(int position) { myAdapter.notifyItemRemoved(position); myAdapter.deleteData(position); Toast.makeText(FoodList.this,"移除第"+(position+1)+"个商品", Toast.LENGTH_SHORT).show(); } }); recyclerView.setAdapter(myAdapter); //不使用动画情况,后面为其加自定义动画,见实验思考内容
    到这里,我就完成了第一个页面FoodList中列表的设计,但是还需要一个浮动按键。根据实验的教程来引入依赖后,在FoodList.xml为其新建组件,设定id。
    然后在食物列表页面通过id找到按键来处理,这里要求改变图片以及展示的内容,需要用到setVisibility,setImageResource这两个函数,通过一个tag来确定显示哪个页面,然后通过设置其是否展示或者展示哪张图片即可。
    //点击浮标事件 final FloatingActionButton f_but = findViewById(R.id.btn); f_but.setOnClickListener(new View.OnClickListener(){ boolean tag_for_foodlist = true; @Override public void onClick(View v){ if(tag_for_foodlist){ findViewById(R.id.recyclerView).setVisibility(View.GONE);//设置Foodlist不可见 findViewById(R.id.listView).setVisibility(View.VISIBLE); tag_for_foodlist = false; f_but.setImageResource(R.mipmap.mainpage); } else{ findViewById(R.id.recyclerView).setVisibility(View.VISIBLE); findViewById(R.id.listView).setVisibility(View.GONE);//设置Favourite不可见 tag_for_foodlist = true; f_but.setImageResource(R.mipmap.collect); } } });
    4.利用ListView实现Collection收藏夹页面首先在FoodList建立listview组件,然后才能通过id来找到。
    ListView就比前面简单很多,可以直接使用simpleAdapter来直接设置,只需调整传入的内容参数即可,点击的监听器要分别设单击事件,前往详情页面;长按事件,弹出询问框是否删除,这一部分是上一实验的内容不再详述。
    //ListView部分 ListView listview = (ListView) findViewById(R.id.listView); simpleAdapter = new SimpleAdapter(this, favourite, R.layout.item, new String[] {"img", "recipeName"}, new int[] {R.id.img, R.id.recipeName}); listview.setAdapter(simpleAdapter); listview.setOnItemClickListener(new AdapterView.OnItemClickListener() { @Override public void onItemClick(AdapterView<?> adapterView, View view, int i, long l) { if(i != 0) gotoDetail_for_Collect(i); } }); listview.setOnItemLongClickListener(new AdapterView.OnItemLongClickListener() { @Override public boolean onItemLongClick(AdapterView<?> adapterView, View view, int i, long l) { // 处理长按事件 if(i != 0){ //弹出询问框 final int delete_num = i; AlertDialog.Builder dialog = new AlertDialog.Builder(FoodList.this); dialog.setTitle("删除"); dialog.setMessage("确定删除"+favourite.get(i).get("recipeName")+"?"); dialog.setPositiveButton("确定", new DialogInterface.OnClickListener() { @Override public void onClick(DialogInterface dialogInterface, int i) { favourite.remove(delete_num); simpleAdapter.notifyDataSetChanged(); } }); dialog.setNegativeButton("取消", new DialogInterface.OnClickListener() { @Override public void onClick(DialogInterface dialogInterface, int i) { } }); dialog.show(); } return true; //这样长按与短按不会同时触发 } });
    5.利用Relative布局,Linear布局,Constraint布局实现Detail详情页面的UI部分这一部分需要我了解各种布局的一些具体情况,比如如何设置水平垂直居中,如何设置三分之一,如何与别的组件保持在一水平线上等等。
    因为上次实验已经使用了Constraint布局来设计UI,所以这里只分析一下对于用Relative布局的详情页面的顶部,要将顶部设置为三分之一,需要利用android:layout_weight=”1”这一属性,需要注意的是使用这一属性时,必须将高度设置为0,让其自动来匹配页面,以达成三分之一的效果。
    对于RelativeLayout布局,layout_alignParentLeft表示返回图标位于页面的左侧,其次食物名字要与返回图标的左侧对齐就要使用android:layout_alignLeft=”@id/back”,里面的参数为想要对齐的id。
    对于星星图标的处理可以预先设置为空星星,而且增加tag来为后面的变化做准备。
    而我为了保存星星的状态,不使用这一方法,所以在xml上不写图片,而在Detail.xml根据食物来动态生成。
    <RelativeLayout android:id="@+id/top" android:layout_width="match_parent" android:layout_height="0dp" android:background="#3F51BB" android:layout_weight="1" > <ImageView android:id="@+id/back" android:layout_width="50dp" android:layout_height="50dp" android:src="@mipmap/back" android:layout_alignParentLeft="true" android:layout_marginTop="10dp" android:layout_marginStart="10dp" android:layout_marginLeft="10dp" /> <TextView android:id="@+id/name" android:layout_width="wrap_content" android:layout_height="wrap_content" android:layout_alignParentBottom="true" android:layout_marginBottom="20dp" android:layout_marginRight="20dp" android:text="牛奶" android:textSize="30dp" android:textColor="@color/white" android:layout_alignLeft="@id/back" android:layout_marginEnd="10dp" /> <ImageView android:id="@+id/star" android:layout_width="40dp" android:layout_height="40dp" android:layout_alignParentEnd="true" android:layout_alignTop="@+id/name" android:layout_marginEnd="20dp" android:layout_marginRight="20dp" android:layout_alignParentRight="true" /> </RelativeLayout>
    6.利用Intent,startActivity等实现不同活动之间的传递信息从前面点击监听器所绑定的跳转函数开始说明,这里是跳转到详情食物页面的函数,它必须根据坐标来将MyCollection中的内容读取出来,并将其放到bundle中,利用startActivityForResult来跳转到详情页面并等待返回参数来进行处理。这里需要的处理包括星星事件的点击,已经加入收藏夹的事件。
    private void gotoDetail_for_Foodlist(int position){ Intent intent = new Intent(); intent.setClass(FoodList.this,Details.class); Bundle bundle = new Bundle(); String s[] = new String [5]; s[0] = data2.get(position).getName(); s[1] = data2.get(position).getMaterial(); s[2] = data2.get(position).getType(); s[3] = data2.get(position).getContent(); s[4] = data2.get(position).getIs_star()?"yes":"no"; bundle.putStringArray("msg",s); intent.putExtras(bundle); startActivityForResult(intent,REQUEST_CODE);//REQUEST_CODE --> 1 }
    然后,在Detail.java中返回参数到主页面的函数。当点击星星以及收藏时候,我们只改变MyCollection的属性,而不是真正返回活动,而到点击返回按钮时候才根据这些改变的属性来传递不同的参数。

    当返回2时,表示详情页面出现了收藏事件,必须将MyCollection的信息传递回去bundle.putSerializable(“collect”, temp),并且使用setResult来返回参数
    当返回3时,表示详情页面出现了改变星星状态事件
    当返回4时,表示两种事件同时发生

    不然,则直接调用finish事件来结束活动。
    //处理返回按钮 final ImageView back_but = findViewById(R.id.back); back_but.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { if(temp.getIs_collected() == true && temp.getIs_star() != (str[4].equals("yes"))){ Intent intent = new Intent(Details.this, FoodList.class); Bundle bundle = new Bundle(); bundle.putSerializable("collect", temp); intent.putExtras(bundle); setResult(4,intent); //RESULT_CODE --> 4 } //收藏夹 else if (temp.getIs_collected() == true) { Intent intent = new Intent(Details.this, FoodList.class); Bundle bundle = new Bundle(); bundle.putSerializable("collect", temp); intent.putExtras(bundle); setResult(2,intent); //RESULT_CODE --> 2 } //保存星星状态 else if(temp.getIs_star() != (str[4].equals("yes"))){ Intent intent = new Intent(Details.this, FoodList.class); Bundle bundle = new Bundle(); bundle.putSerializable("collect", temp); intent.putExtras(bundle); setResult(3,intent); //RESULT_CODE --> 3 } Details.this.finish(); } });
    这样在主页面中只需重构OnActivityResult函数即可以处理这些事件。处理结果为2时,从intent中拿回食物的信息,通知收藏夹列表来改变列表,这里使用我的私有函数refreshList,太过简单也不再细述,详情参见代码。
    而处理结果为3时,则要在两个列表中查找所有该食物的状态,更改星星的情况,以此实现星星状态的长期保存。
    // 为了获取结果 @Override protected void onActivityResult(int requestCode, int resultCode, Intent data) { super.onActivityResult(requestCode, resultCode, data); if (resultCode == 2) { if (requestCode == REQUEST_CODE) { MyCollection mc = (MyCollection)data.getSerializableExtra("collect"); refreshList(mc,simpleAdapter); } } else if(resultCode == 3){ if (requestCode == REQUEST_CODE) { MyCollection mc = (MyCollection)data.getSerializableExtra("collect"); for(int i = 0; i < data2.size(); i++){ if(data2.get(i).getName().equals(mc.getName())){ data2.set(i,mc); } } for(int i = 0; i < favourite.size(); i++){ if(favourite.get(i).get("recipeName").toString().equals(mc.getName())){ favourite.get(i).remove("star"); favourite.get(i).put("star",mc.getIs_star()); } } } } else if(resultCode == 4){ if (requestCode == REQUEST_CODE) { MyCollection mc = (MyCollection)data.getSerializableExtra("collect"); for(int i = 0; i < data2.size(); i++){ if(data2.get(i).getName().equals(mc.getName())){ data2.set(i,mc); } } refreshList(mc,simpleAdapter); } } }
    7.在Detail页面来根据不同的食物内容来动态生成UI界面这里的动态包括,详情页面上部的颜色,以及名字,营养成分等等。星星的状态也要动态生成。
    通过intent拿出的信息来改变xml中相对应id的组件,只需注意id的正确,以及颜色的选取即可。
    Bundle bundle=this.getIntent().getExtras(); str = bundle.getStringArray("msg"); TextView name = findViewById(R.id.name); name.setText(str[0]); TextView material = findViewById(R.id.material); material.setText("富含 "+ str[1]); TextView type = findViewById(R.id.type); type.setText(str[2]); temp = new MyCollection(str[0],str[3],str[2],str[1],false); //根据上次情况保存星星状态 final ImageView star_but = findViewById(R.id.star); if(str[4].equals("yes")){ star_but.setImageResource(R.mipmap.full_star); temp.setIs_star(true); } else{ star_but.setImageResource(R.mipmap.empty_star); temp.setIs_star(false); }
    3.2.3 实验遇到的困难以及解决思路1.RecycleView无法正确生成列表按照老师给的教程一步步写好Adapter与Holder后,运行应用时出现闪退情况。报错信息为,无法得到资源。一有报错,第一步当然是将报错信息扔上搜索引擎,但是网页上的信息都说是因为setText()里面的参数为String而不是其他。但细看自己的程序并没有出现setText的错误参数情况。
    然后,我对于类的传参开始找问题,结果发现是convert函数在传参的时候,没有找到资源,而是一个空的对象。于是再修改convert函数后,完成了这一部分的工作。
    2.收藏列表的错误点击收藏列表的第一项为“*”与“收藏夹”,这两个不应该被触发点击事件,否则会传递一个空的MyCollection到详情页面会出现报错。所以必须在点击收藏列表的监听函数时加一个判断,当点击的是第一个item时,不要触发跳转事件。
    3.食物详情页面的UI设计不符合位置这次详情页面的UI有点难度,对于三分之一的上部设置就弄了相当长的时间,当知道使用layout_weight时候,然而在实际使用的时候,却并没有达到三分之一的效果。后来,才知道没有将height设置为0dp,而是为wrap_content.。这样导致权重设置失败。
    其次,对于设置分割线以及收藏图标如何垂直居中,间距合适遇到了困难。由于我在下部使用的是ConstrainLayout布局,所以必须要以别的组件来作相对设置位置。这里我对于这两个组件,分别相对于parent的上方,以及下面分割线的下方作为限制。这样就好像上下两个作用力,使其位于垂直居中的位置。
    最后只需调整线条的长度以及图片的大小即可。
    <TextView android:id="@+id/ver_line" android:layout_width="2dp" android:layout_height="45dp" android:background="#1E000000" app:layout_constraintTop_toTopOf="parent" app:layout_constraintBottom_toBottomOf="@id/line1" android:gravity="center" android:layout_marginRight="10dp" app:layout_constraintRight_toLeftOf="@+id/collect" /> <ImageView android:id="@+id/collect" android:layout_width="45dp" android:layout_height="45dp" android:scaleType="fitXY" android:src="@mipmap/collect" app:layout_constraintBottom_toBottomOf="@id/line1" app:layout_constraintTop_toTopOf="parent" app:layout_constraintRight_toRightOf="parent" android:layout_marginRight="20dp" />
    4.Detail页面与Foodlist页面进行交换信息时候,对于数据包的处理由于要使用intent来实现不同活动中的交互,必须将食物的信息传递到详情页面,以及在详情页面中改变后的食物信息传递回食物列表存储。于是,就要求他们交换信息时候必须要满足两个条件,第一是要一次传递一个食物对象,第二是要满足intent的信息交互函数。这里使用的是bundle的putSerializable函数,这也要求我们的食物类必须要实现Serializable类。
    Intent intent = new Intent(Details.this, FoodList.class); Bundle bundle = new Bundle(); bundle.putSerializable("collect", temp); intent.putExtras(bundle); setResult(2,intent); //RESULT_CODE --> 2
    四、实验思考及感想4.1 UI界面设计与基础事件交互本次是第一次安卓开发的实验,主要关于UI界面的设计与一些简单的交互,这与我之前学过的web网页设计十分相似,定义组件以及通过id来对于每一个组件来设置一些监听函数,完成所需要的功能。
    但是,安卓开发上也有许多不同之处,对于java文件中必须要了解调用组件的监听函数,名字比较长,而且参数多,必须在平时熟练使用并要经常查阅手册。
    对于ui界面,我这次主要是通过xml的书写来生成界面,用里面的一些属性来定义组件的大小,边距等等,除此之外,安卓开发中还很讲究文件的分类,将string,color,style设置成另外的文件,在主的xml可以调用这些文件中的内容来实现,这样的好处便于修改界面的内容,例如可以根据这个来开发中文英文不同的ui界面版本。
    4.2 Intent、Bundle的使用以及RecyclerView、ListView的应用这次实验花了不少的时间来理解不同列表的实现方式,学习了不同ui布局的位置设置,活动之间的交互信息方法,按钮监听函数。
    但是,对于实验基本要求所做出了的应用程序还是有一些不太完美的地方,于是,我做了一些改进的地方(加分项),使其更加符合日常使用,包括对于详情列表星星的状态保存,在详情页面不按返回图标而是点击手机的返回键时无法收藏该食物状态,还为RecycleList加了一个自定义的动画效果,使其更加美观。
    4.2.1 对于星星状态的持久化改进星星的状态持久化,我实现出来的效果是当该食物被加星后,无论是在食物列表还是在收藏列表都会出现加星的同步状态,不会出现个别加星个别不加星。
    这里实现的持久化,实际就是给食物添加多一个is_star属性来判断该食物的状态,并将该状态传递到详情页面来动态处理。
    //根据上次情况保存星星状态 final ImageView star_but = findViewById(R.id.star); if(str[4].equals("yes")){ star_but.setImageResource(R.mipmap.full_star); temp.setIs_star(true); } else{ star_but.setImageResource(R.mipmap.empty_star); temp.setIs_star(false); }
    而在改变后返回到其他界面时,也要将改变了的星星状态返回,以此改变该食物在数据结构中的信息
    else if(resultCode == 3){ if (requestCode == REQUEST_CODE) { MyCollection mc = (MyCollection)data.getSerializableExtra("collect"); for(int i = 0; i < data2.size(); i++){ //更新FoodList if(data2.get(i).getName().equals(mc.getName())){ data2.set(i,mc); } } for(int i = 0; i < favourite.size(); i++){ //更新CollectList if(favourite.get(i).get("recipeName").toString().equals(mc.getName())){ favourite.get(i).remove("star"); favourite.get(i).put("star",mc.getIs_star()); } } } }
    4.2.2 对于手机系统返回键的处理这里出现的bug是在详情页面点击收藏后,不按返回小图标,而是点击手机返回键时,无法收藏该食物。这是因为点击手机收藏键是没有将信息传递回主页面的,所以我们必须根据这个按键重构返回键的功能,来让该功能与点击返回小图标是一样的。
    当在详情页面,得到返回键被单击时,实现的功能与点击返回图标相同。而其他则继续执行系统的默认按键功能在最后添加return super.onKeyDown(keyCode, event);
    //点击返回时候,加入收藏也要生效 @Override public boolean onKeyDown(int keyCode, KeyEvent event) { if (keyCode == KeyEvent.KEYCODE_BACK) { //两种情况同时实现 if(temp.getIs_collected() == true && temp.getIs_star() != (str[4].equals("yes"))){ Intent intent = new Intent(Details.this, FoodList.class); Bundle bundle = new Bundle(); bundle.putSerializable("collect", temp); intent.putExtras(bundle); setResult(4,intent); //RESULT_CODE --> 4 } //收藏夹 else if (temp.getIs_collected() == true) { Intent intent = new Intent(Details.this, FoodList.class); Bundle bundle = new Bundle(); bundle.putSerializable("collect", temp); intent.putExtras(bundle); setResult(2,intent); //RESULT_CODE --> 2 } //保存星星状态 else if(temp.getIs_star() != (str[4].equals("yes"))){ Intent intent = new Intent(Details.this, FoodList.class); Bundle bundle = new Bundle(); bundle.putSerializable("collect", temp); intent.putExtras(bundle); setResult(3,intent); //RESULT_CODE --> 3 } else{ Details.this.finish(); } } return super.onKeyDown(keyCode, event); }
    4.2.3 实现RecycleList的动画在res文件夹建立anim文件夹来放置动画的xml文件,首先要建立layout_animation_fall_down.xml文件。
    其中animation为列表每一项item的动画,其文件在后面再实现,delay表示动画的延迟时间,animationOrder表示动画item的顺序是正常,即从大到小,在这里实现的效果就是从高到低。
    <?xml version="1.0" encoding="utf-8"?><layoutAnimation xmlns:android="http://schemas.android.com/apk/res/android" android:animation="@anim/item_animation_fall_down" android:delay="15%" android:animationOrder="normal" />
    接着对item实现layout_animation_fall_down.xml文件,来控制列表每一项的动画效果。
    translate组件中fromYDelta表示item首先位于y轴的上方20%出发,然后toYDelta表示item所要到达的位置,这里的0表示为回到本应该的位置。interpolator里面的属性表示减速实现动画过程。
    alpha组件表示透明度的变化,由0到1,加速实现动画过程。
    scale组件表示item的大小,由105%变化为100%,略微缩放动画。
    <set xmlns:android="http://schemas.android.com/apk/res/android" android:duration="500" > <translate android:fromYDelta="-20%" android:toYDelta="0" android:interpolator="@android:anim/decelerate_interpolator" /> <alpha android:fromAlpha="0" android:toAlpha="1" android:interpolator="@android:anim/decelerate_interpolator" /> <scale android:fromXScale="105%" android:fromYScale="105%" android:toXScale="100%" android:toYScale="100%" android:pivotX="50%" android:pivotY="50%" android:interpolator="@android:anim/decelerate_interpolator" /></set>
    这样就实现了一个列表的从上到下,逐渐出现的动画。
    4.3 感想通过不断的学习,总算理解了android的一些机制,也能简单的写出了一个程序了。但是对于java语言的虚函数,静态函数,接口,数据类型等等都需要加强,这会使我更方便地理解类与类之间的关系。对于ui的设计要熟练掌握三种布局的运用,可以适当给某些组件先赋值通过preview来查看位置,再在java文件中实现动态赋值,这样做既能保证ui也能动态生成页面。这次实验使用的是绑定数据是运用数组,猜想未来应该可以引入数据库的绑定,这样会使代码更加简洁。
    1 留言 2019-07-11 12:12:51 奖励20点积分
  • 真实感图形学研究

    一、介绍真实感图形学是计算机图形的核心内容之一,是最能直接反映图形学魅力的分支。
    寻求能准确地描述客观世界中各种现象与景观的数学模型,并逼真地再现这些现象与景观,是图形学的一个重要研究课题。很多自然景物难以用几何模型描述,如烟雾、植物、水波、火焰等。本文所讨论的几种建模及绘制技术都超越了几何模型的限制,能够用简单的模型描述复杂的自然景物。
    二、自然景物模拟  在计算机的图形设备上实现真实感图形必须完成的四个基本任务。

    三维场景的描述。三维造型
    将三维几何描述转换成为二维透视图。透视变换
    确定场景中的所有可见面。消隐算法,可见面探测算法
    计算场景中可见面的颜色。根据基于光学物理的光照模型计算可见面投射到观察者眼中的光亮度大小和色彩组成

    其中三维造型技术根据造型对象分成三类:

    曲面造型:研究在计算机内如何描述一张曲面,如何对它的形状进行交互式的显示和控制。曲面造型又分成规则曲面造型(如平面、圆柱面等)和不规则曲面两种。不规则曲面造型方法主要有Bezier曲线曲面、B样条曲线曲面和孔斯曲面等
    立体造型。研究如何在计算机内定义、表示一个三维物体。这些方法主要有体素构造法、边界表示法、八叉树法等等。曲面造型和立体造型合称为几何模型造型
    自然景物模拟。研究如何在计算机内模拟自然景物,如云、水流、树等等。本文将主要集中介绍有 关自然景物模拟的有关方法

    寻求能准确地描述客观世界中各种现象与景观的数学模型,并逼真地再现这些现象与景观,是图形学的一个重要研究课题。很多自然景物难以用几何模型描述,如烟雾、植物、水波、火焰等。本文所讨论的几种建模及绘制技术都超越了几何模型的限制,能够用简单的模型描述复杂的自然景物。
    2.1 分形与IFS2.1.1 分形几何分形(fractal)指的是数学上的一类几何形体,在任意尺度上都具有复杂并且精细的结构。一般来说分形几何体都是自相似的,即图形的每一个局部都可以被看作是整体图形的一个缩小的复本。例如,雪花曲线是一种典型的分形图形,生成方法如下:取一等边三角形,在每一边中间的三分之一处分别生长出一个小的等边三角形,重复上述过程就可以形成图2.1所示的曲线。理论上来说,无限递归的结果是形成了一个有限的区域,而该区域的周长却是无限的,并且具有无限数量的顶点。这样的曲线在数学上是不可微的。
    早在19世纪就已经出现了一些据有自相似特性的分形图形,但最初只是被看作一种奇异现象。本世纪70年代,Benoit B. Mandelbrot最早对分形进行系统研究,并创立了分形几何这一新的数学分支。Mandelbrot扩展了经典欧几里得几何中的维数,提出了分数维的概念。 分形几何并不只是抽象的数学理论。例如海岸线的轮廓,如果考虑其不规则性,同样具有无限的长度。Mandelbrot认为海岸、山脉、云彩和其他很多自然现象都具有分形的特性。因此,分形几何已经成为一个发展十分迅速的科学分支,尤其是在计算机图形学中,成为描述自然景物及计算机艺术创作的一种重要手段。此外,分形在图象压缩方面也有广阔的应用前景。
    2.1.2 仿射变换与迭代函数迭代函数系统IFS (Iteration Function System)最早是由Hutchinson于1981年提出的,现已成为分形几何中的重要研究内容之一。IFS是以仿射变换为框架,根据几何对象的整体与局部具有自相似结构,经过迭代而产生的。  、
    2.1.3 基于分形的景物生成由IFS码绘出的分形图形具有无穷细微的自相似结构,能对很多客观事物作出准确的反映,这种结构是难于用经典数学模型来描述的。只要变换选取适当,利用IFS就可以迭代地生成任意精度的图形效果,这也是其他绘制方法难以做到的。
    2.2 基于文法的模型美国科学家Aristid Lindenmayer于1969年提出了一种研究植物形态与生长的描述方法,以他的名字命名为L系统(L-grammars)。1984年,A. R. Smith将L系统应用于计算机图形学中。L系统实际上是一组形式语言,由特定的语法加以描述,这些语法由一系列产生式组成,所有产生式都是直接匹配的。例如,一种典型的L系统语法包括四个字母{A,B,[,]}和两条产生式规则:
    A→AAB→A[B]AA[B]从字母A出发,可以迭代地生成A、AA、AAAA等字母序列;从字母B出发,前几步迭代结果如下:
    BA[B]AA[B]AA[A[B]AA[B]]AAAA[A[B]AA[B]]……如果我们把由这种语法规则中的产生式迭代形成的词汇看作是某种图结构的一部分,把方括号中的内容视为前一个符号的分支,则上述文法的三次迭代结果如图2.2所示。在此基础上,适当改变分支的方向,加入随机动因素及在分支的终点绘制出叶子、花、果实等细节,就可以逼地真模拟出现实世界中各种形态的植物。
    当然,上述L系统本身并没有记录任何几何信息,因此基于L系统的建模语言必须能够同时支持文法描述和几何描述;如何对L系统的生长(迭代)过程加以控制也是一个需要进行研究的问题。对此,Reffye、Prusinkiewicz等人分别提出了各自的方法。
    总之,基于文法的L系统用于植物生长过程的模拟是非常成功的,为计算机真实感图形的绘制提供了又一个有力的工具。此外,这种思想也被成功地应用到了电子线路设计和建筑设计等很多方面。
    2.3 粒子系统Reeves于1983年提出的粒子系统方法是一种很有影响的模拟不规则物体的方法,能够成功地模拟由不规则模糊物体组成的景物。与其他传统图形学方法完全不同,这种方法充分体现了不规则模糊物体的动态性和随机性,从而能够很好地模拟火、云、水、森林和原野等许多自然景象。
    粒子系统的基本思想是采用许多形状简单的微小粒子作为基本元素来表示不规则模糊物体。这些粒子都有各自的生命周期,在系统中都要经历”产生”、”运动和生长”及”消亡”三个阶段。粒子系统是一个有”生命”的系统,因此不象传统方法那样只能生成瞬时静态的景物画面,而可产生一系列运动进化的画面,这使得模拟动态的自然景物成为可能。生成系统某瞬间画面的基本步骤是:

    产生新的粒子
    赋予每一新粒子一定的属性
    删去那些已经超过生存期的粒子
    根据粒子的动态属性对粒子进行移动和变换
    显示由有生命的粒子组成的图象

    粒子系统采用随机过程来控制粒子的产生数量,确定新产生粒子的一些初始随机属性,如初始运动方向、初始大小、初始颜色、初始透明度、初始形状以及生存期等,并在粒子的运动和生长过程中随机地改变这些属性。粒子系统的随机性使模拟不规则模糊物体变得十分简便。
    三、消隐及真实感图形生成  3.1 消隐在计算机图形学中,有三种方式表示三维物体:线框图、消隐图和真实感图。其中真实感图形的生成也要在消隐基础上进行光照处理。所谓消隐就是给定一组三维对象及投影方式(视见约束),判定线、面或体的可见性的过程。根据消隐在间的不同,消隐算法可分为两类:

    物体空间的消隐算法,消隐在规范化投影空间中进行,将物体表面的k个多边形中的每一个面与其余的k-1个面进行比较,精确地求出物体上每条棱边或每个面的遮挡关系。这类算法的计算量正比于k2
    图象空间的消隐算法,消隐在屏幕坐标系中进行,对屏幕上的每一个象素进行判断,确定在该象素点上可见的面。若屏幕分辨率为m×n,物体空间中共有k个多边形,则此类算法的的计算量正比于mnk

    大多数消隐算法都涉及排序和相关性的概念。排序是为了确定消隐对象之间的遮挡关系,通常在X、Y、Z三个方向分别进行。消隐算法的效率在很大程度上取决于排序的效率。相关性是指物体对象或其变换后的图象局部保持不变的性质,在消隐算法中利用相关性是提高排序率的重要手段。
    常用的物体空间消隐算法有多边形区域排序算法和列表优先算法等。
    Z-Buffer (深度缓存)是最简单的图象空间面消隐算法,深度缓存数组的使用避免了复杂的排序过程在分辨率一定的情况下,算法计算量只与多边形个数成正比。该算法也便于硬件实现和并行处理。在此基础上,Z-Buffer扫描线算法利用了多边形边和象素点的相关性,使得算法效率进一步提高。扫描线算法也为简单光照模型提供了良好的消隐基础。
    3.2 简单光照模型及明暗处理光照模型(Illumination Model)是根据有关光学定律,计算真实感图形中各点投射到观察者眼中的光线强度和色彩的数学模型。简单的局部光照模型假定光源是点光源,物体是非透明体,不考虑折射,反射光由环境光、漫反射光和镜面反射光组成。  基于局部光照模型及明暗处理的阴影生成算法也有很多。阴影是指景物中哪些没有被光源直接照射到的按区。在计算机生成的真实感图形中,阴影可以反映画面中景物的相对位置,增加图形的立体感和场景的层次感,丰富画面的真实感效果。阴影可分为本影和半影两种。本影加上它周围的半影组成软影区。单个点光源照明只能形成本影,多个点光源和线光源才能形成半影。
    对多边形表示的物体,一种计算本影的方法是影域多边形方法,环境中物体的影域定义为视域多面体和光源在景物空间中被物体轮廓多边形遮挡的区域的交集。这种方法的实现可以利用现有的扫描线消隐算法。Athherton等人提出了曲面细节多边形方法,以多边形区域分类的隐藏面消去算法为基础,通过从光源和视点两次消隐生成阴影。
    以上两种阴影生成方法只适用于用多边形表示的景物,无法解决光滑曲面片上的阴影生成问题。为此Williams提出了Z-Buffer方法,首先利用Z-Buffer算法按光源方向对景物进行消隐,然后再用Z-Buffer算法按视线方向进行会制。这种方法可以方便地在理包括光滑曲面的任意复杂的景物,但存储量大,阴影区域附近易产生走样。
    3.3 整体光照模型与光线跟踪照射到物体上的光线,不仅有从光源直接射来的,也有经过其它物体反射或折射来的。局部光照模型只能处理直接光照,为了对环境中物体之间的各种反射、折射光进行精确模拟,需要使用整体光照模型。
    相对于局部光照模型,整体光照模型可以表示为Iglobal=KRIR+ KTIT。其中Iglobal为非直接光照对物体上一点光强的贡献;IR为其他物体从视线的反射方向R反射或折射来的光强,KR为反射系数;KT为其 他物体从视线的折射方向T折射或反射来的光强,IT为折射系数。将Iglobal与局部光照模型的计算结果相叠加,就可以得到物体上点的光强。
    光线跟踪算法是典型的整体光照模型,最早由Goldste、Nagel和Appel等人提出,Appel用光线跟踪的方法计算阴影;Whited和Kay扩展了这一算法,用于解决镜面反射和折射问题。算法的基本思想如下:
    对于屏幕上的每个象素,跟踪一条从视点出发经过该象素的光线,求出与环境中物体的交点。在交点处光线分为两支,分别沿镜面反射方向和透明体的折射方向进行跟踪,形成一个递归的跟踪过程。光线每经过一次反射或折射,由物体材质决定的反射、折射系数都会使其强度衰减,当该光线对原象素光亮度的。贡献小于给定的阈值时,跟踪过程即停止。光线跟踪的阴影处理也很简单,只需从光线与物体的交点处向 光源发出一条测试光线,就可以确定是否有其他物体遮挡了该光源(对于透明的遮挡物体需进一步处理光强的衰减),从而模拟出软影和透明体阴影的效果。
    光线跟踪很自然地解决了环境中所有物体之间的消隐、阴影、镜面反射和折射等问题,能够生成十分逼真的图形,而且算法的实现也相对简单。但是,作为一种递归算法其计算量十分巨大。尽量减小求交计 算量是提高光线跟踪效率的关键,常用的方法有:包围盒(entents)、层次结构(hierarchies)及区域分割 (spatial partitioning)等技术。
    光线跟踪是一个典型的采样过程,各个屏幕象素的亮度都是分别计算的,因而会产生走样,而算法本身的计算量使得传统的加大采样频率的反走样技术难以实用。
    象素细分是一种适用于光线跟踪的反走样技术,具体方法是: 首先对每一象素的角点用光线跟踪计算亮度;然后比较各角点的亮度,若差异较大,则将象素细分为4个子区域,并对新增的5个角点用光线跟踪计算亮度;重复比较与细分,直到子区域各角点亮度差异小于给定的阀值为止;最后加权平均求出象素点的显示亮度。
    与象素细分不同,Cook、Porter和Carpenter 提出的分布式光线跟踪是一种随机采样的方法,在交点处镜面反射方向和折射方向所夹的立体角内,按照一定的分布函数同时跟踪若干根光线,然后进行加权平均。Cook等人还提出了利用分布式随机采样技术模拟半影、景深和运动模糊等效果的方法。
    光线跟踪的另一个问题是,光线都是从视点发出的,阴影测试光线则需另外处理,因而无法处理间接的反射或折射光源,例如镜子或透镜对光源所产生的作用就难以模拟。为解决这一问题,可以从光源和视点出发对光线进行双向跟踪。但是,大量从光源出发的光线根本不可能到达屏幕,这使得双向光线跟踪的计算量显著增大,难以实用。Heckbert和Hanrahanr提出的解决方法是只将从光源出发的光线跟踪作为常归光线跟踪的补充;Arvo方法则是对从光源发出进入环境的光线进行预处理;邵敏之和彭群生等人也提出 了基于空间线性八叉树结构的对光源所发出光线进行优化的双向光线跟踪算法。
    3.4 漫反射和辐射度方法常规光照模型假设物体间的漫反射是一个恒定的环境光,即使双向光线跟踪也只能处理物体间的反射与折射,而不能处理物体间的漫反射。最初由Goral等人于1984年及Nishita等人于1985年提出的辐射度方法是一种基于热能工程的方法,用光辐射的产生和反射代替环境光,从而能够精确处理对象之间的光反射问题。
    辐射度方法将景物和光源视为一个封闭的系统,在系统中光能量是守衡的;并假定构成景物的曲面都是理想的漫反射面。所谓辐射度,是指单位时间内从曲面上单位面积反射出去的光能量,记为B。在理想情况下,可以近似认为逼近曲面的面片上的光强是均匀的,即漫反射各向均匀。根据能量守衡定律
    辐射度方法的主要计算量在于计算形状因子。Cohen和Greenberg提出的半立方体方法是一种近似计算 封闭面形状因子的高效方法。首先以面片i的中心为原点,法向量为Z轴建立一个半立方体,将其五个表面划分成均匀的网格,每个网格单元的微形状因子可以预先求得;然后将场景中所有其他面片都投影到半立方体上,对于多个面片投影到同一个网格单元的情况需在投影方向上进行深度比较,网格单元只保留最近的面片,这一过程相当于Z-Buffer算法;最后将半立方体中所有与面片j相关的网格单元的微形状因子累加,即可得到面片i相对于面片j的形状因子Fij。 辐射度方法的优点在于算法与视点无关、计算和绘制可以分别独立进行、能够模拟颜色渗透效果等,但无法处理镜面反射与折射。
    在辐射度方法中,面片向特定方向辐射出的光能量仅总辐射度有关,而与所接受能量的方向无关。Immel、Cohen和Greenberg推广了这一方法,每个面片不只计算唯一的辐射度,而是将面片半球空间分割成有限个空间立体角的区域,在每个区域内分别计算输入输出的光能量,通过双向辐射函数计算向某一方向辐射能量的概率,每个顶点的光强可以通过对与视点方向最为接近的若干方向上的辐射度进行插值得到,并最终完成图形生成。这种改进方法可以处理包含镜面和透明物体的复杂场景,但要付出巨大的时间开销和空间开销。
    另一种方案是将辐射度与光线跟踪相结合,仅仅将两种方法的计算结果相加是不够的,必须同时处理漫反射面和镜面之间的光照关系。Wallace、Cohen和Greenberg提出了一种两步方法:

    第一步执行与视点无关的辐射度方法,辐射度的计算必须考虑镜面,这可以通过镜象法(mirror-world approach)予以模拟
    第二步执行基于视点的光线跟踪算法,处理整体镜面反射和折射,并生成图形。算法效率的关键在于第一步,其中镜象法只需处理理想镜面的反射作用,并据此对形状因子加以修正,形状因子的计算量将随镜面数量的增加而显著增加

    Sillon和Puech进一步扩展了上述两步法,在第一步时不采用镜象法,而是用递归的光线跟踪来计算形状因子,可以处理具有任意数量镜面及透明体的场景。
    3.5 纹理映射纹理映射(Texture Mapping)是通过将数字化的纹理图象覆盖或投射到物体表面,从而为物体表面增加表面细节的过程。纹理图象可以通过采样得到,也可以通过数学函数生成。物体的很多表面细节多边形逼近或其他几何建模的方法是难以表现的,因此纹理映射技术能够使得计算机生成的物体看起来更加逼真自然。
    纹理映射技术最早由Catmull提出,经Blinn和Newell改进后得到广泛应用,成为计算机图形学中的一种重要方法。将纹理映射到物体表面,可以看作是将一个屏幕象素投影到纹理空间的对应区域并计算该区域的平均颜色,以求得真正象素颜色的最佳近似值。具体地说,纹理图象存在于独立的纹理空间中,映射分为两步进行,先将屏幕象素通过四个角点坐标映射到三维物体表面,再进一步映射到纹理空间,形成一个四边形区域,即对屏幕象素映射到三维物体表面上所形成的复杂曲面片的近似。屏幕象素的纹理映射结果可以通过对纹理空间中四边形区域进行累加得到。也可以采用相反的映射方式,即从纹理空间到三维物 体再到屏幕象素进行映射,但这种映射方式需要占用更大的存储空间,更易产生走样,并且无法应用于扫描线算法。
    物体表面的纹理可分为两类:颜色纹理和几何纹理。颜色纹理主要是指同一表面各处呈现出不现的花纹和颜色;几何纹理主要指物体表面在微观上呈现出的起伏不平。上述纹理映射方法只能处理颜色纹理,所生成的物体表面仍然是光滑的。Blinn在纹理映射基础上提出的Bump Mapping方法是一种模拟物体表面粗糙纹理的技术,可以不用对物体的粗糙表面在几何上进行建模就可以改善物体表面的微观结构,如大理石纹理表面雕刻的文字、混凝土墙面等效果。此外,更高级的真实感图形效果如人脸上流淌的汗水也可以通过随时间变化的Bump mapping来模拟。Bump Map是一个二维数组,数组中每个元素是物体表面上一点比 其实际位置略高或略低的偏移向量。这些微小偏移被映射到物体表面一点后修正该点处的法向量,通过修正后的法向量进行光照计算。
    纹理图象和屏幕象素都是离散的采样系统,很容易产生走样,即丢失纹理细节,使表面边界产生锯齿。纹理映射中常用的反走样方法是卷积滤波法。屏幕象素是一个矩形区域,映射到纹理空间上为一任意四 边形,卷积滤波法就是取四边形所覆盖区域的纹理函数的卷积作为屏幕象素的光亮度,可以采用盒形、三角形、高斯分布及样条函数等作为滤波函数。在实际应用中为简化计算,常用正方形、矩形或椭圆等形状近似表示屏幕象素所覆盖的任意四边形区域。卷积滤波法是非线性的,计算量较大,并且不适用于Bump Mapping,因为Bump Mapping的纹理函数与象素的光亮度之间不是线性关系,此时可以使用前置滤波法。前置滤波是在纹理空间中按照不同的分辨率将一定区域内的纹理平均值预先算好,执行映射时只需按照屏幕象素所覆盖的区域大小选取一定的分辨率查表,并作适当线性插值即可。
    以上二维映射在很多情况下都能得到很好的效果,但有时会产生失真,如在三维曲面上仍会呈现出二维效果,以及产生纹理接缝问题等。Peachey和Perlin提出了一种基于实体纹理的方法,用物体上点在三维空间的位置的函数作为纹理,从而更精确地表现木材或大理石等的雕刻效果。
    其他一些材质的表面也可以用适当的方法模拟,如Gardner的透明映射方法可以用简单的形状模拟云彩。此外,很多基于物理模型、随机过程和分形几何等的方法也被用来生成自然纹理。
    1 留言 2019-06-27 11:19:59 奖励16点积分
  • 深度学习 21、RNN

    前文链接:https://write-bug.com/article/2644.html
    RNN循环神经网络
    RNN(循环神经网络):一类用于处理序列(时间、空间)数据的神经网络,RNN可用于分类、回归、机器翻译、文本相似度
    隐层的神经元不仅接收输入层的或者上一层的信息流,还要接受上一时刻的同层神经元的信息流,即隐层之间的连接,连接传递的权重就是记忆能力。
    此处的记忆能力理解为人的认知往往基于过往的经验与记忆,所以模拟时,同样根据激活函数的不同会产生梯度消失和梯度爆炸问题,也反映了人的记忆往往有限,过往太久的事不会记忆或者对现在产生影响过大。
    梯度消失:每次loss反向传播时,如果使用sigmoid这样的激活函数一直乘一个小数,在这个过程中一直变小,直到逼近于0梯度爆炸:每次loss反向传播时,如果使用relu这样的激活函数,x>0时,y=x,一直乘一个大于0的数,数值过大
    所以,他的优点就是在上下文推断时,可以根据上文推断下一个出现概率最大的单词,适合短期记忆,不适合长期记忆,很难学习长距离信息,那么同样的,比较符合大脑记忆曲线

    隐层展开后为上图样式。

    t-1, t, t+1表示时间序列
    X表示输入的样本
    St表示样本在时间t处的的记忆,St = f(WSt-1 +UXt)
    W表示输入的权重
    U表示此刻输入的样本的权重

    这里的W,U,V在每个时刻都是相等的(权重共享),隐藏状态: S=f(现有的输入+过去记忆总结)。

    以上,便是最基本的RNN原理,我们为了更好的模拟人们根据过往的经验来判断和写文章,引出了
    LSTM( Long Short Term Memory Network长短期记忆网络)
    LSTM结构更复杂,不仅适合短期记忆,也适合长期记忆。

    这条黑线就是从上一时刻的输入到此刻的输出,即单元状态流,用于记忆当前状态,乘号代表着当前时刻对记忆的削减,加号代表记忆的更新,也就是新信息的汇入。
    LSTM包含3个门 (– 遗忘门 – 输入门 – 输出门)这里有这个“门”的概念,下面一个一个解释:
    遗忘门

    上一刻的信息与此刻的新信息汇入后,σ层就会把信息转化为ft,如果决定要忘记,ft就是0,如果这 个信息要保留,则为1,选择部分记忆则按照实际情况输出0~1的数,也就是激活函数,如sigmoid

    ht-1是上个网络的output(输出)xt当前网络的input(输入)网络会自动学习到对应的权重矩阵
    输入门

    首先,上一刻的信息与此刻的新信息汇入后,,统一经过σ层,决定要更新啥信息。还要另外经过tanh层,将 信息转化为一个新的候选值,两者再相乘,就是cell state中需要更新的值了。


    接着,“遗忘门”和“输入门”已经决定好了 什么要遗忘,什么要更新

    输出门

    前面的门已经决定了信息的状态如何保留和更新,得到了Ct,现在把它经过tanh层,并再次与σ层识别哪一部分信息要输出的信息相乘就得到了输出信息ht,输出两路分别给输出(比如此刻的预测词)和下一时刻输入。
    GRULSTM的变体,比LSTM结构更加简单,效果也很好,GRU只有两个门:更新门、重置门


    zt和rt分别表示更新门和重置门

    更新门用于控制前一时刻的状态信息被带入到当前状态中的程度 ,更新门的值越大说明前一时刻的状态信息带入越多
    重置门控制前一状态有多少信息被写入到当前的候选集 h̃ t 上 ,重置门越小,前一状态的信息被写入的越少

    LSTM 实践# define modelclass RNNModel(nn.Module): """ 一个简单的循环神经网络""" def __init__(self, rnn_type, ntoken, ninp, nhid, nlayers, dropout=0.5): ''' 该模型包含以下几层: - 词嵌入层 - 一个循环神经网络层(RNN, LSTM, GRU) - 一个线性层,从hidden state到输出单词表 - 一个dropout层,用来做regularization ''' super(RNNModel, self).__init__() self.drop = nn.Dropout(dropout) self.encoder = nn.Embedding(ntoken, ninp) if rnn_type in ['LSTM', 'GRU']: self.rnn = getattr(nn, rnn_type)(ninp, nhid, nlayers, dropout=dropout) else: try: nonlinearity = {'RNN_TANH': 'tanh', 'RNN_RELU': 'relu'}[rnn_type] except KeyError: raise ValueError( """An invalid option for `--model` was supplied, options are ['LSTM', 'GRU', 'RNN_TANH' or 'RNN_RELU']""") self.rnn = nn.RNN(ninp, nhid, nlayers, nonlinearity=nonlinearity, dropout=dropout) self.decoder = nn.Linear(nhid, ntoken) self.init_weights() self.rnn_type = rnn_type self.nhid = nhid self.nlayers = nlayers def init_weights(self): initrange = 0.1 self.encoder.weight.data.uniform_(-initrange, initrange) self.decoder.bias.data.zero_() self.decoder.weight.data.uniform_(-initrange, initrange) def forward(self, input, hidden): ''' Forward pass: - word embedding - 输入循环神经网络 - 一个线性层从hidden state转化为输出单词表 ''' #print("input ", input.size()) emb = self.drop(self.encoder(input)) #print("emb ", emb.size()) output, hidden = self.rnn(emb, hidden) #print("output ", output.size()) #print(len(hidden)) output = self.drop(output) decoded = self.decoder(output.view(output.size(0)*output.size(1), output.size(2))) #print("output size: ", output.size()) #print("decoded before size: ", output.view(output.size(0)*output.size(1), output.size(2)).size()) #print("decoded after size: ", decoded.size()) #sys.exit() return decoded.view(output.size(0), output.size(1), decoded.size(1)), hidden def init_hidden(self, bsz, requires_grad=True): weight = next(self.parameters()) if self.rnn_type == 'LSTM': return (weight.new_zeros((self.nlayers, bsz, self.nhid), requires_grad=requires_grad), weight.new_zeros((self.nlayers, bsz, self.nhid), requires_grad=requires_grad)) else: return weight.new_zeros((self.nlayers, bsz, self.nhid), requires_grad=requires_grad)model = RNNModel("LSTM", VOCAB_SIZE, EMBEDDING_SIZE, EMBEDDING_SIZE, 2, dropout=0.5)#模型初始化if USE_CUDA: model = model.cuda()
    0 留言 2019-06-16 20:07:46 奖励15点积分
  • 机器学习 22 、决策树 、模型融合

    前文链接:https://write-bug.com/article/2666.html
    决策树决策树(decision tree)是一种基本的分类与回归方法,模型:树结构
    主要有两大类算法:ID3 、C4.5
    学过数据结构的都知道,一棵树由节点node和有向边directed edge 构成,而节点又有几个名词:根节点、父节点、子节点、叶子节点
    这里我们用各个节点表示特征(如年龄),边表示特征属性(如青年、老年),叶子节点表示label(如买、不买)
    用决策树分类时,来了一个人根据他的特征,对某一特征进行比对,将其分到对应的子节点继续比对,直到到达叶子节点,得到预测label

    特征维度:年龄、收入、信誉、学生
    现在假设每个人都有这四类特征的数据,如何用一颗树来对这些人做一个是否购买的分类,也就是落地到某个叶子节点,那用哪个特征来做根节点父节点子节点呢?有很多组合方式。
    首先处理训练数据:

    数据特征值离散化:0 1 2 ……编码

    我们在进行特征选择时,要选择对训练数据具有分类能力的特征,以提高决策树的学习效率,决定了用哪个特征来划分特征空间,如果利用一个特征进行分类的结果和随即分类的结果没有差别,那么这个特征没有分类能力,而特征选择的准则就是信息增益与信息增益率,从而引出了ID3与C4.5算法
    ID3ID3的特征选择就是利用信息增益来进行选择,这也是我们前面提到的到底用哪个特征作为根节点哪个特征作为子节点构建树呢?
    说到信息增益,这里介绍几个概念:
    熵=随机变量的不确定性
    条件熵=在一定条件下,随机变量的不确定性
    信息增益=熵-条件熵 在一定条件下,信息不确定性减少的程度

    我们通常使用H(X)符号代表随机变量X的熵:
    H(X)=E(I(X))E代表期望值函数,I(X)代表随机变量X的自信息量。

    不确定性函数I称为事件的信息量,事件X发生概率p的单调递减函数:
    𝐼(X) = 𝑙𝑜𝑔(1/ 𝑝)=−𝑙𝑜𝑔 𝑝
    信息熵:一个信源中,不能仅考虑单一事件发生的不确定性,需要考虑所有可能情况的平均不确定性,为−𝑙𝑜𝑔 𝑝 的统计平均值E
    𝐻 (X) = 𝐸 [−𝑙𝑜𝑔 (𝑝 (x𝑖))] = −∑𝑖 𝑝(x𝑖 )𝑙𝑜𝑔 (𝑝 (x𝑖))这里的熵可以理解为混乱度,数据混乱度越大,熵取值越大,随机变量的不确定性越大
    如果H=0或1,说明数据为纯净的,一定为买或不买,而H=0.5时,混乱度最大

    伯努利分布时熵与概率的关系
    选择特征做父节点:选择熵最大(混乱程度最大)的特征
    例:

    ID3 完全用熵的概念:信息增益
    原始数据,无条件下的熵:

    label=买+不买=1024个p买=640/1024=0.635p不买 = 384/1024=0.375根据信息熵公式
    H=-∑p log(p)H=0.9544那么在年龄条件下的条件熵:
    P青年=384/1024=0.375青年分为买和不买:
    p买=128/384p不买=256/384S=384H=0.9183同理:中年:由于都是买的,所以H=0老年:H=0.9157
    年龄的三个信息熵得到了,那如何使用呢,我们对年龄求平均期望:
    平均值=占比\*信息熵E(年龄)=0.375*0.9183+0.25*0+0.375*0.9157=0.6877这个年龄作为区分的话,可以带来0.6877的增益G(年龄)=0.9544-0.6877=0.2667 为信息增益同理

    E(学生)=0.7811 G(学生)=0.1733
    E(收入)=0.9361 G(收入)=0.0183
    E(信誉)=0.9048 G(信誉)=0.0496

    从上述可以看出,按照年龄划分,收益是最大的,信息增益最大,所以年龄作为根节点,同理,从而构建整颗树.
    所以我们构建一个attrList特征列表作为一个容器存放特征,无放回的取特征
    如果取完了特征,构建出了树,但是叶子节点还是不是纯净的怎么办呢?
    分类问题:少数服从多数
    回归问题:概率比较

    缺点:因为优先选择信息增益最大的,所以导致倾向于选择属性值较多的
    贪婪性:选择收益最大的

    贪婪不是最优的算法,可能觉得本次收益最大,但从长远看收益没那么大
    奥卡姆剃刀原理:尽量用最少的东西做最多的事
    用最少的特征,区分类别,不需要所有特征都用,用最简单的方式效果最好,最优的树
    不适用于连续变量:离散型特征属性如果是身高这种线性连续的特征,对应过多类别特征,应离散化使用
    Pseudocode:
    ID3 (Examples, Target_Attribute, Attributes) Create a root node for the tree If all examples are positive, Return the single-node tree Root, with label = +. If all examples are negative, Return the single-node tree Root, with label = -. If number of predicting attributes is empty, then Return the single node tree Root, with label = most common value of the target attribute in the examples. Otherwise Begin A ← The Attribute that best classifies examples. Decision Tree attribute for Root = A. For each possible value, vi, of A, Add a new tree branch below Root, corresponding to the test A = vi. Let Examples(vi) be the subset of examples that have the value vi for A If Examples(vi) is empty Then below this new branch add a leaf node with label = most common target value in the examples Else below this new branch add the subtree ID3 (Examples(vi), Target_Attribute, Attributes – {A}) End Return RootID3实践:

    class ID3DTree(object): def __init__(self): self.tree={} self.dataSet=[] self.labels=[] def loadDataSet(self,path,labels): recordlist = [] fp = open(path,"r") # 读取文件内容 content = fp.read() fp.close() rowlist = content.splitlines() # 按行转换为一维表 recordlist=[row.split("\t") for row in rowlist if row.strip()] self.dataSet = recordlist self.labels = labels def train(self): labels = copy.deepcopy(self.labels) self.tree = self.buildTree(self.dataSet,labels) # 创建决策树主程序 def buildTree(self,dataSet,labels): cateList = [data[-1] for data in dataSet] # 抽取源数据集的决策标签列 # 程序终止条件1 : 如果classList只有一种决策标签,停止划分,返回这个决策标签 if cateList.count(cateList[0]) == len(cateList): return cateList[0] # 程序终止条件2: 如果数据集的第一个决策标签只有一个 返回这个决策标签 if len(dataSet[0]) == 1: return self.maxCate(cateList) # 算法核心: bestFeat = self.getBestFeat(dataSet) # 返回数据集的最优特征轴: bestFeatLabel = labels[bestFeat] tree = {bestFeatLabel:{}} del(labels[bestFeat]) # 抽取最优特征轴的列向量 uniqueVals = set([data[bestFeat] for data in dataSet]) # 去重 for value in uniqueVals: subLabels = labels[:] #将删除后的特征类别集建立子类别集 splitDataset = self.splitDataSet(dataSet, bestFeat, value) # 按最优特征列和值分割数据集 subTree = self.buildTree(splitDataset,subLabels) # 构建子树 tree[bestFeatLabel][value] = subTree return tree def maxCate(self,catelist): # 计算出现最多的类别标签 items = dict([(catelist.count(i), i) for i in catelist]) return items[max(items.keys())] def getBestFeat(self,dataSet): # 计算特征向量维,其中最后一列用于类别标签,因此要减去 numFeatures = len(dataSet[0]) - 1 # 特征向量维数 = 行向量维度-1 baseEntropy = self.computeEntropy(dataSet) # 基础熵:源数据的香农熵 bestInfoGain = 0.0; # 初始化最优的信息增益 bestFeature = -1 # 初始化最优的特征轴 # 外循环:遍历数据集各列,计算最优特征轴 # i 为数据集列索引:取值范围 0~(numFeatures-1) for i in range(numFeatures): # 抽取第i列的列向量 uniqueVals = set([data[i] for data in dataSet]) # 去重:该列的唯一值集 newEntropy = 0.0 # 初始化该列的香农熵 for value in uniqueVals: # 内循环:按列和唯一值计算香农熵 subDataSet = self.splitDataSet(dataSet, i, value) # 按选定列i和唯一值分隔数据集 prob = len(subDataSet)/float(len(dataSet)) newEntropy += prob * self.computeEntropy(subDataSet) infoGain = baseEntropy - newEntropy # 计算最大增益 if (infoGain > bestInfoGain): # 如果信息增益>0; bestInfoGain = infoGain # 用当前信息增益值替代之前的最优增益值 bestFeature = i # 重置最优特征为当前列 return bestFeature def computeEntropy(self,dataSet): # 计算香农熵 datalen = float(len(dataSet)) cateList = [data[-1] for data in dataSet] # 从数据集中得到类别标签 items = dict([(i,cateList.count(i)) for i in cateList]) # 得到类别为key,出现次数value的字典 infoEntropy = 0.0 # 初始化香农熵 for key in items: # 计算香农熵 prob = float(items[key])/datalen infoEntropy -= prob * math.log(prob,2) # 香农熵:= - p*log2(p) --infoEntropy = -prob * log(prob,2) return infoEntropy # 分隔数据集:删除特征轴所在的数据列,返回剩余的数据集 # dataSet:数据集; axis:特征轴; value:特征轴的取值 def splitDataSet(self, dataSet, axis, value): rtnList = [] for featVec in dataSet: if featVec[axis] == value: rFeatVec = featVec[:axis] # list操作 提取0~(axis-1)的元素 rFeatVec.extend(featVec[axis+1:]) # list操作 将特征轴(列)之后的元素加回 rtnList.append(rFeatVec) return rtnList def predict(self,inputTree,featLabels,testVec): # 分类器 root = list(inputTree.keys())[0] # 树根节点 secondDict = inputTree[root] # value-子树结构或分类标签 featIndex = featLabels.index(root) # 根节点在分类标签集中的位置 key = testVec[featIndex] # 测试集数组取值 valueOfFeat = secondDict[key] # if isinstance(valueOfFeat, dict): classLabel = self.predict(valueOfFeat, featLabels, testVec) # 递归分类 else: classLabel = valueOfFeat return classLabel # 存储树到文件 def storeTree(self,inputTree,filename): fw = open(filename,'w') pickle.dump(inputTree,fw) fw.close() # 从文件抓取树 def grabTree(self,filename): fr = open(filename) return pickle.load(fr)C4.5C4.5 用的是信息增益率的概念
    由上面,我们的信息增益:
    𝐺𝑎𝑖𝑛 (𝑆,𝐴)= 𝐸𝑛𝑡𝑟𝑜𝑝𝑦(𝑆) − ∑𝑣∈𝑉𝑎𝑙𝑢𝑒(𝐴) |𝑆𝑣|/ |𝑆| 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 (𝑆𝑣)信息增益率:
    𝐺𝑎𝑖𝑛𝑅𝑎𝑡𝑖𝑜 𝐴 =𝐺𝑎𝑖𝑛(𝐴) / 𝐸𝑛𝑡𝑟𝑜𝑝𝑦(𝐴)比原来多除了一个entropy(A):属性背后的信息熵
    比如:前面的信息增益G(年龄)=0.9544-0.6877=0.2667
    𝐺𝑎𝑖𝑛𝑅𝑎𝑡𝑖𝑜 𝐴=0.2667/0.6877除以一个信息熵有什么好处呢?
    如果只考虑信息增益的话,我们没有考虑A集合背后的大小,A越大也就意味着集合越混乱的可能性越高,那么C4.5考虑到了这种情况,给集合的混乱度做一个中和
    C4.5实践:


    class C45DTree(object): def __init__(self): self.tree={} self.dataSet=[] self.labels=[] def loadDataSet(self,path,labels): recordlist = [] fp = open(path,"r") content = fp.read() fp.close() rowlist = content.splitlines() recordlist=[row.split("\t") for row in rowlist if row.strip()] self.dataSet = recordlist self.labels = labels def train(self): labels = copy.deepcopy(self.labels) self.tree = self.buildTree(self.dataSet,labels) def buildTree(self,dataSet,labels): cateList = [data[-1] for data in dataSet] if cateList.count(cateList[0]) == len(cateList): return cateList[0] if len(dataSet[0]) == 1: return self.maxCate(cateList) bestFeat, featValueList = self.getBestFeat(dataSet) bestFeatLabel = labels[bestFeat] tree = {bestFeatLabel:{}} del(labels[bestFeat]) for value in featValueList: subLabels = labels[:] splitDataset = self.splitDataSet(dataSet, bestFeat, value) subTree = self.buildTree(splitDataset,subLabels) tree[bestFeatLabel][value] = subTree return tree def maxCate(self,catelist): items = dict([(catelist.count(i), i) for i in catelist]) return items[max(items.keys())] def getBestFeat(self, dataSet): Num_Feats = len(dataSet[0][:-1]) totality = len(dataSet) BaseEntropy = self.computeEntropy(dataSet) ConditionEntropy = [] # 初始化条件熵 splitInfo = [] # for C4.5, calculate gain ratio allFeatVList=[] for f in range(Num_Feats): featList = [example[f] for example in dataSet] [splitI,featureValueList] = self.computeSplitInfo(featList) allFeatVList.append(featureValueList) splitInfo.append(splitI) resultGain = 0.0 for value in featureValueList: subSet = self.splitDataSet(dataSet, f, value) appearNum = float(len(subSet)) subEntropy = self.computeEntropy(subSet) resultGain += (appearNum/totality)*subEntropy ConditionEntropy.append(resultGain) # 总条件熵 infoGainArray = BaseEntropy*ones(Num_Feats)-array(ConditionEntropy) infoGainRatio = infoGainArray/array(splitInfo) # c4.5, info gain ratio bestFeatureIndex = argsort(-infoGainRatio)[0] return bestFeatureIndex, allFeatVList[bestFeatureIndex] def computeSplitInfo(self, featureVList): numEntries = len(featureVList) featureVauleSetList = list(set(featureVList)) valueCounts = [featureVList.count(featVec) for featVec in featureVauleSetList] # caclulate shannonEnt pList = [float(item)/numEntries for item in valueCounts ] lList = [item*math.log(item,2) for item in pList] splitInfo = -sum(lList) return splitInfo, featureVauleSetList def computeEntropy(self,dataSet): datalen = float(len(dataSet)) cateList = [data[-1] for data in dataSet] items = dict([(i,cateList.count(i)) for i in cateList]) infoEntropy = 0.0 for key in items: prob = float(items[key])/datalen infoEntropy -= prob * math.log(prob,2) return infoEntropy def splitDataSet(self, dataSet, axis, value): rtnList = [] for featVec in dataSet: if featVec[axis] == value: rFeatVec = featVec[:axis] rFeatVec.extend(featVec[axis+1:]) rtnList.append(rFeatVec) return rtnList # 树的后剪枝 # testData: 测试集 def prune(tree, testData): pass def predict(self,inputTree,featLabels,testVec): root = list(inputTree.keys())[0] secondDict = inputTree[root] featIndex = featLabels.index(root) key = testVec[featIndex] valueOfFeat = secondDict[key] # if isinstance(valueOfFeat, dict): classLabel = self.predict(valueOfFeat, featLabels, testVec) else: classLabel = valueOfFeat return classLabel def storeTree(self,inputTree,filename): fw = open(filename,'w') pickle.dump(inputTree,fw) fw.close() def grabTree(self,filename): fr = open(filename) return pickle.load(fr)之前的ID3和C4.5停止条件都是结点数据类型一致(即纯净),要不就是没有特征可以选择了,但是只有这两个条件限制,在特征多树学习过深的情况下,模型容易过拟合
    防止过拟合:

    停止条件:信息增益(比例)增长低于阈值,则停止
    – 阈值需要调校 将数据分为训练集和测试集
    – 测试集上错误率增长,则停止
    剪枝:

    相邻的叶子节点,如果合并后不纯度增加在允许范围内,则合并
    测试集错误率下降,则合并 等等

    sklearn- tree实践:
    from sklearn.tree import DecisionTreeRegressor# Fit regression modelregr_2 = DecisionTreeRegressor(max_depth=10)#深度阈值print >> sys.stderr, 'begin train ==============='regr_2.fit(X, y)print >> sys.stderr, 'begin predict ==============='# Predicty_2 = regr_2.predict(X_test)for p_label in y_2: print p_label #输出预测标签(回归值)print >> sys.stderr, 'end ==============='多分类用MSE做评估:
    import sysfrom sklearn import metricsimport numpy as npimport randomres_file = sys.argv[1]y_test = []y_pred = []with open(res_file, 'r') as fd: for line in fd: ss = line.strip().split('\t') if len(ss) != 2: continue t_label = float(ss[0].strip()) p_label = float(ss[1].strip()) y_test.append(t_label) y_pred.append(p_label)print "MSE:",metrics.mean_squared_error(y_test, y_pred)print "RMSE:",np.sqrt(metrics.mean_squared_error(y_test, y_pred))模型融合Ensemble Learning(集成学习)什么是集成学习呢?假设我有多个模型,每个模型的学习准确率都是80%,或者说每个模型的准确率有学习好的有学习坏的,这时就有很多数据没有预估正确,那么我使用多个模型来共同决策,少数服从多数,通过这种方式提升准确率,把多个弱分类器集成获得一个强分类器。
    集成学习里面有两类算法:Bagging和Boosting算法
    Bagging算法是以random forest随机森林为代表的算法
    Boosting算法是以AdaBoost算法和Gbdt为代表的算法
    通过介绍我们知道这是将多个模型融合,得到一个强模型的方法,那么我们是如何证明这种方式是否靠谱呢?
    用数学上的排列组合问题表示,假设二分类问题有5个精确度为70%的弱分类器,相互独立
    采用投票的方式将5个分类器的结果进行集成:
    𝐶5 3(0.73)(0.32)+ 𝐶5 4(0.74)(0.31)+ 𝐶5 5(0.71) = 10(.7^3)(.3^2)+5(.7^4)(.3)+(.7^5) = 83.7%如果有101个分类器,精确度就可以提升到99.9%

    问题:如何得到不同的分类器,并且尽量独立? (每个模型不尽相同,不相互影响)
    方法:将一个复杂的学习问题,分解成多个简单的学习问题

    Bagging– 对训练数据采样,得到多个训练集,分别训练模型
    – 对得到的多个模型进行平均 分类问题:投票方式进行集成 回归问题:模型的输出进行平均

    训练:同一训练数据随机抽取数据并行用不同的机器和模型同时训练
    测试:对模型预测出的各个分数进行投票或者平均
    适合弱分类器(容易过拟合,效果一般):
    不稳定:随机采样会得到较不同的分类器,每个基分类器准确率略高于50%
    例如:决策树
    不适合强分类器(本身准确率高,效果较好) :
    稳定:随机采样对结果影响不大
    甚至可能不如不集成,每个基分类器只有更少的训练样本
    例如:DNN(模型复杂时,时间成本大并且容易过拟合,为了抗过拟合,最有效的办法就是让训练数据越大越好,和bagging的选取数据思想不同)
    Random Forest
    Random Forest = Bagging+决策树
    随机森林生成方法:
    – 从样本集中通过重采样的方式产生n个样本
    – 建设样本特征数目为a,对n个样本选择a中的k个特征,用建立决策树的方式获得最佳分割点
    – 重复m次,产生m棵决策树
    – 多数投票机制进行预测
    每棵树样本不同,选择特征可能不同,形成树的形状、深度都不同。
    优点:

    训练速度快、容易实现并行
    训练完成后,反馈哪些是重要特征(类似LR中的特征权重,这里的决策树靠信息熵筛选)
    抗过拟合能力强 (多棵树抗过拟合)
    可解决分类、回归问题
    不平衡数据集,rf是平衡误差有效方法

    缺点:

    取值较多的属性,影响大
    噪音大的分类、回归问题会过拟合
    只能尝试参数和种子的选择,无法洞悉内部

    Boosting每个基分类器,基于之前的分类结果,已经分对的样本不用太多关心,集中力量对付分错样本,不等权投票,好的基分类器权重大
    – 对训练数据集进行采样,对错分样本加权采样
    – 多个模型按照分类效果加权融合

    训练:同一训练数据随机抽取数据串行用不同的机器和模型进行训练,首先模型一学习预估评分后,对出错的样本,提高采样权重,用模型二再次随机抽取数据,这时由于出错样本采样权重提高重点会放在出错的样本上,以此类推串行迭代下去
    测试:对各个模型预测出的各个分数乘以对应的错误率权重公式相加
    Boosting方法的两类思想:
    传统Boost→ Adaboost:对正确、错分样本加权,每步的迭代,错误样本加权,正确样本降权
    Gradient Boosting:每次建模建立在之前模型损失函数的梯度下降方向
    Adaboost
    对不同的模型分数加权求和,错误样本加权,正确样本降权


    给数据中的每一个样本一个权重
    训练数据中的每一个样本,得到第一个分类器
    计算该分类器的错误率,根据错误率计算要给分类器分配的权重(注意这里是分类器的权重) 即前面表示的每个模型预估后的分数乘对应的分类器权重求和

    错误率:𝜀 =未正确分类的样本数目/ 所有样本数目 分类器权重: 𝛼 =1/ 2 ln((1 – 𝜀)/ 𝜀)

    将第一个分类器分错误的样本权重增加,分对的样本权重减小(注意这里是样本的权重)
    错分样本权重:𝐷𝑖^ (𝑡+1) = 𝐷𝑖 ^(𝑡)𝑒^𝑎 /𝑆𝑢𝑚(𝐷),Di^t表示上一次样本的权重,分母:训练集的规模,样本个数
    正确样本权重:𝐷𝑖^ (𝑡+1) = 𝐷𝑖^ (𝑡)𝑒^(−𝑎) / 𝑆𝑢𝑚(𝐷)

    然后再用新的样本权重训练数据,得到新的分类器,到步骤3
    直到步骤3中分类器错误率为0,或者到达迭代次数
    将所有弱分类器加权求和,得到分类结果(注意是分类器权重)

    GBDT(Gradient Boosting Decision Tree)
    是一种迭代的决策树算法,该算法由多棵决策树组,所有树的结论累加起来做最终答案
    三个概念组成:
    – Regression Decistion Tree(DT、RT)
    – Gradient Boosting(GB)
    – Shrinkage(步长)
    分类树:衡量标准最大熵——预测分类标签值
    回归树:衡量标准是最小化均方差——预测实际数值
    GBDT中的树,属于回归树,不是分类树 – 要求所有树的结果进行累加是有意义的 – GBDT是结果累加,而不是多数投票
    GBDT核心: – 每一棵树学的是之前所有树结论和的残差 – 残差就是一个加预测值后能得真实值的累加量
    残差是什么?

    因为是回归树,那么我的节点值应该是这个节点的平均值即预估值,那么来了一个人落在左边这个节点就是15岁,但是对于某些人预估的大了,有的预估的小了,那我把残差整理成新的样本再建一棵树重新学习,尽量把残差学没了,就像以前的误差值,尽力把它学为0
    这里同样的,特征选择时也是利用信息熵的方式。
    残差是学习的最优方向,体现了Gradient
    Gradient Descend梯度下降实际上是在更新参数,并且最终参数等于每次迭代的增量的累加和:
    𝜃𝑡 = 𝜃𝑡−1 + 𝜃𝑡𝜃𝑡 = −𝑎𝑡𝑔𝑡 参数更新方向为负梯度方向𝜃 =∑𝜃𝑡 最终参数等于每次迭代的增量的累加和, 𝜃0为初值而Gradient Boost是在更新整个函数
    𝑓𝑡 𝑥 = 𝑓𝑡−1 𝑥 + 𝑓𝑡 (𝑥)𝑓𝑡(𝑥) = −𝑎𝑡𝑔𝑡(𝑥) 类似地,拟合了负梯度𝐹(𝑥) = ∑𝑓𝑡(𝑥) 最终参数等于每次迭代的增量的累加和 𝑓0(𝑥)为模型初值,通常为函数所以,Boosting是一种加法模型GBDT模型F定义为加法模型
    𝐹 (𝑥;𝑤) = ∑𝑎𝑡 ℎ𝑡(𝑥;𝑤𝑡)= 𝑓𝑡(𝑥;𝑤𝑡)x为输入样本,h为分类回归树,w是分类回归树的参数,a是每棵树的权重

    2.1的公式是loss值更新函数预估值,2.2是求残差
    但是这样的加法模式比较容易过拟合,这就涉及到了Shrinkage缩减技术:
    思想:每棵树只学到了真理的一小部分,累加的时候只累加一小部分,通过多学几棵树弥补不足
    假设: yi表示第i棵树上y的预测值, y(1~i)表示前i棵树y的综合预测值
    没有shrinkage时:
    – y(i+1) = 残差(y1~yi), 其中: 残差(y1~yi) = y真实值 - y(1 ~ i)
    – y(1 ~ i) = SUM(y1, …, yi)
    有shrinkage时:
    – 第2个方程调整为:y(1 ~ i) = y(1 ~ i-1) + step /* yi
    即对每次的结果都乘一个权重
    仍然以残差作为学习目标,但对于残差的学习,每次只累加一小部分(step残差)逐步逼近目标
    本质上,Shrinkage为每棵树设置了一个weight,累加时要乘以这个weight
    偏差、方差
    偏差bias:模型不准确
    尽量选择正确模型与复杂度
    模型越简单,预估能力越差,偏差越大,方差越低
    方差variance:模型不稳定
    防止过拟合

    我们的模型融合是可以同时把方差与偏差同时降低的方法。
    RF实践:
    sklearn - rf:
    测试数据:

    import sysimport numpy as npimport matplotlib.pyplot as pltimport pandas as pd# Importing the datasetsdatasets = pd.read_csv('Position_Salaries.csv')#pandas自动解析读取X = datasets.iloc[:, 1:2].values #级别Y = datasets.iloc[:, 2].values #金额# Fitting the Regression model to the datasetfrom sklearn.ensemble import RandomForestRegressorregressor = RandomForestRegressor(n_estimators = 300, random_state = 0)#300颗树regressor.fit(X,Y)# Predicting a new result with the Random Forest RegressionY_Pred = regressor.predict([[6.5]])print(Y_Pred)# Visualising the Random Forest Regression results in higher resolution and smoother curveX_Grid = np.arange(min(X), max(X), 0.01)X_Grid = X_Grid.reshape((len(X_Grid), 1))plt.scatter(X,Y, color = 'red')plt.plot(X_Grid, regressor.predict(X_Grid), color = 'blue')plt.title('Random Forest Regression Results')plt.xlabel('Position level')plt.ylabel('Salary')plt.show()output:

    pyspark-mllib-rf:
    测试数据:

    #coding=utf8from __future__ import print_functionimport sysfrom pyspark import SparkContext, SparkConffrom pyspark.mllib.regression import LabeledPointfrom pyspark.mllib.feature import HashingTF,IDF,StandardScalerfrom pyspark.mllib.classification import LogisticRegressionWithSGD,SVMWithSGD,NaiveBayesfrom pyspark.mllib.tree import DecisionTreefrom pyspark.mllib.tree import RandomForest, RandomForestModelfrom pyspark.mllib.util import MLUtilsreload(sys)sys.setdefaultencoding('utf-8')if __name__ == "__main__": #conf = SparkConf().setMaster("spark://master:7077").setAppName("lr_pyspark_test") conf = SparkConf().setMaster("local").setAppName("lr_pyspark_test") sc = SparkContext(conf=conf) #in_file = sc.textFile("file:///root/spark_test_5/pyspark_test/lr_pyspark_test/data/a8a") data = MLUtils.loadLibSVMFile(sc, "file:///root/spark_test_5/pyspark_test/lr_pyspark_test/data/a8a") (trainingData, testData) = data.randomSplit([0.7, 0.3]) model = RandomForest.trainClassifier(\ trainingData, numClasses=2, \ categoricalFeaturesInfo={},\ numTrees=3, \ featureSubsetStrategy="auto",\ impurity='gini', maxDepth=4, maxBins=32)#3颗树,gini系数方式 predictions = model.predict(testData.map(lambda x: x.features)) labelsAndPredictions = testData.map(lambda lp: lp.label).zip(predictions) testErr = labelsAndPredictions.filter(lambda (v, p): v != p).count() / float(testData.count()) print('Test Error = ' + str(testErr)) print('Learned classification forest model:') print(model.toDebugString()) ## Save and load model #model.save(sc,"target/tmp/myRandomForestClassificationModel") #sameModel = RandomForestModel.load(sc, "target/tmp/myRandomForestClassificationModel") sc.stop()GBDT实践:
    微软lightgbm方式:
    import sysimport lightgbm as lgb #pip安装import numpy as npfrom scipy.sparse import csr_matriximport pandas as pdfrom sklearn.metrics import mean_squared_errorfrom sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitfrom sklearn.datasets import make_classificationdata_in = 'D:\\bd\\share_folder\\a9a'def load_data(): target_list = [] fea_row_list = [] fea_col_list = [] data_list = [] row_idx = 0 max_col = 0 with open(data_in, 'r') as fd: for line in fd: ss = line.strip().split(' ') label = ss[0] fea = ss[1:] target_list.append(int(label)) for fea_score in fea: sss = fea_score.strip().split(':') if len(sss) != 2: continue feature, score = sss fea_row_list.append(row_idx) fea_col_list.append(int(feature)) data_list.append(float(score)) if int(feature) > max_col: max_col = int(feature) row_idx += 1 row = np.array(fea_row_list) col = np.array(fea_col_list) data = np.array(data_list) fea_datasets = csr_matrix((data, (row, col)), shape=(row_idx, max_col + 1)) x_train, x_test, y_train, y_test = train_test_split(fea_datasets, target_list, test_size=0.2, random_state=0) return x_train, x_test, y_train, y_testX_train,X_test,y_train,y_test = load_data()# 创建成lgb特征的数据集格式lgb_train = lgb.Dataset(X_train, y_train)lgb_eval = lgb.Dataset(X_test, y_test, reference=lgb_train)params = { 'task': 'train', 'boosting_type': 'gbdt', # 设置提升类型 'objective': 'regression', # 目标函数 'metric': {'l2', 'auc'}, # 评估函数 'num_leaves': 31, # 叶子节点数 'learning_rate': 0.05, # 学习速率 'feature_fraction': 0.9, # 建树的特征选择比例 'bagging_fraction': 0.8, # 建树的样本采样比例 'bagging_freq': 5, # k 意味着每 k 次迭代执行bagging 'verbose': 1 # <0 显示致命的, =0 显示错误 (警告), >0 显示信息}print('Start training...')# 训练 cv and traingbm = lgb.train(params,lgb_train,num_boost_round=20,valid_sets=lgb_eval,early_stopping_rounds=5)print('Save model...')# 保存模型到文件gbm.save_model('model.txt')print('Start predicting...')# 预测数据集y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration)print(y_test)print(y_pred)# 评估模型print('The rmse of prediction is:', mean_squared_error(y_test, y_pred) ** 0.5)部分模型output:
    0 留言 2019-06-21 08:22:26 奖励12点积分
  • 机器学习 14、分类算法-NB、AUC

    前文链接:https://write-bug.com/article/2428.html
    分类算法更新:NB、PR/AUC/ROC、LR、Softmax、DT、RF、GDBT、DNN、CNN、RNN
    什么是分类问题呢?
    最常见的机器学习任务:给定一个对象X,将其划分到预定义好的某一个类别Yi。
    比如说:性别识别,人群划分,新闻分类,query分类,商品分类,网页分类,垃圾邮件过滤,网页排序等等。
    对于性别识别来说,分辨男女,也就是二分类问题,即判断0和1问题。
    那我们如何评判一个人是男是女呢?这时就需要特征来解决:肤色、身高、体重、音色等等等等,我们人类打眼一看什么特征大概就知道这个人是男是女了,那机器是如何学会这个技能的呢?
    我们可以把这个机器当成是一个幼儿园小孩,如果幼儿园老师告诉小朋友,0:老虎很凶猛,1:小猫很温顺,那这时来了个狮子,小孩大脑里就会自动的拿狮子的特征去比对所见过的东西,觉得有些像老虎,那就会自然而然地离它远一些了。
    这个技能就是泛化能力,也就是说来了一个新东西,如果我能预测的很准的话,那就说明这次机器学习的模型是效果很好的,是具有泛化能力的。
    如果我想对文章做分类,一篇文章可以有很多类别,即多分类,那其中的特征是什么呢?关键词token,我提取出一篇文章的关键词,很容易就可以看出这篇文章属于哪类,每个词都有着对每个类别的倾向性,比如说‘股市’大概率都是财经文章。
    机器学习模型
    我们人类可以通过自己的学习经验一眼就可以把分类问题做出来,如果有大量数据的时候我们就需要机器去判断,也就是机器学习。
    机器学习目的:模型,可以帮我们对数据做预测。
    如果我想要机器学习对新数据预测的分类准确率高的话,我们就需要两点:

    好模型(老师/算法)
    好数据(教材/训练集)

    * 好模型 ≠ 复杂模型:

    复杂模型和性能开销成正比,即实现程度
    过拟合,对训练集学习太过深刻会把训练集中的错误数据知识也学习到了,缺少泛化能力,对测试预估效果影响较大

    评估模型学习效果:PR/AUC/ROC
    朴素贝叶斯(NB)算法
    我们在中文分词那节的语言模型中,推导过贝叶斯定理:
    p(s|c)=p(c|s)p(s)/p(c)推导:
    p(s|c) p(c)=p(s,c)—联合概率(同时发生的概率)->p(c|s)p(s)=p(c,s)-> p(s|c) p(c)= p(c|s)p(s)-> p(s|c)= p(c|s)p(s)/p(c)那假如我们设定:
    X:一篇文章
    Y:文章类别集合{}
    yi:第i个类别
    xi:文章某token
    p(yi|X):一篇文章属于哪个类别的概率
    则有:p(yi|X)=p(X|yi)p(yi)/p(X)
    p(yi):先验概率,即常识,已知规律
    我们看上面的设定来说,p(yi)代表着这个类别的概率,也就是说假设我训练集有100篇文章,我提前知道军事类别50,财经类别30,体育类别20,那么我们的先验概率也就固定下来了,p(y=军事)=50/100,以此类推,那么等到我测试集进行预测时,我的先验概率也按照这个比例来分布。
    p(X):常数,一篇文章出现的概率就像我们原先说的一个人说的每句话一样几率都是一样的。
    所以,公式简化为:
    p(yi|X)=p(X|yi)p(yi)p(X|yi)=p(x1|y1)\*p(x2|y1)\*p(x3|y1)....也就是把大X分成不同的关键词,但前提是独立同分布。
    所以朴素贝叶斯的前提:独立同分布
    那这里我需要对p(yi|X)=p(X|yi)p(yi)的参数进行估计:即最大似然估计
    p(yi),如何计算呢?统计,说白了就是我们刚才举例子的方法求得的。
    p(X|yi),两种计算方法:
    p(xi|yi)=count(xi,yi)/count(yi)count(xi,yi):即特征(关键词)xi和类别yi在训练数据中同时出现的次数
    count(yi):即某类别总数
    p(谷歌|军事)=军事类文章中包含‘谷歌’这个词的文章个数 / 军事类文章个数p(谷歌|军事)=军事类文章中包含‘谷歌’这个词的文章个数 / 军事类文章中所有词个数通过上面的分析与推导,我们得到了两个参数,如果来了一篇文章我们去预测属于那个类别,即p(yi|X),让这两个参数相乘就ok了。这个结果是一个概率,这就意味着如果是二分类问题,p(y=0|X)=70%,p(y=1|X)=30%,即有多少分类就要求多少个概率值,取概率最大的数,最致信。这个结果就是后验概率。
    优点:– 简单有效 – 结果是概率,对二值和多值同样适用
    缺点:– 独立性假设有时不合理
    NB实践:
    1.python DataConvert.py data/ nb_data
    数据准备:分好词的几千篇文章
    数据合并和转换:标签和token
    数据编码:token编码为数字,分测试集和训练集
    2.python NB.py 1 nb_data.train model
    训练数据训练,得到model(前面的两个参数)
    3.python NB.py 0 nb_data.test model out
    测试数据用model作预测—》求log
    二分类评估效果
    那我们怎么去评估我们的分类效果呢?对于二分类来说,我们最初使用混淆表(混淆矩阵)的方式进行评测:


    准确度Accuracy:(C11+C22)/(C11+C12+C21+C22)
    精确率Precision(y1):C11/(C11+C21)
    召回率Recall(y1):C11/(C11+C12)

    这种方式不好看,我们来替换成例子来看下:


    准确度Accuracy:(50+35)/(35+5+10+50)=85%
    精确率Precision(y1):50/(50+5)=90.9%
    召回率Recall(y1):50/(50+10)=83.3%

    上面的例子很明确,通常在工作中一般注重这两个指标,正确率(精确率)和召回率:

    正确率:预测样本中,正确的样本所占的比例,即看军事列
    召回率:预测样本中,正确的样本占同一类别总的样本比例,看军事行

    那么什么指标合适,在日常生活中,有的是侧重于召回,有的是侧重于正确率,越靠近底层一般越侧重于召回,越往上,越侧重于精确,即Nosq库那块侧重召回,排序模型那里侧重于精确
    上面我们提出了混淆矩阵,得到了准确率和召回率:
    这里引出了:PR、ROC、AUC
    有了这个正确率和召回率,我们可以获得一个PR曲线,即:同时评估正确率和召回率的方法就是通过PR曲线,p代表正确率,R代表召回率但是这个PR曲线很容构造成一个高正确率或高召回率的曲线,很难保证两全齐美,一般准确率高,召回率就低,召回率高,准确率低,可以构成一个二维码坐标,纵坐标是正确率,横坐标是召回率,用来确定阈值thd

    那么用生活中的两类场景来举例子:
    搜索场景,保证召回的前提下,再提高准确率
    疾病检测,保证准确性前提,提升召回
    PR曲线是个评测指标,用来协助你去选择阀值的,这个阈值怎么理解呢?比如我几篇文章被预测为军事的概率分别是0.7、0.8、0.6,如果阈值设置为thd=0.5,那么这三篇文章全被分辨为正例,都是军事。通过对阈值的调参,我得到的混淆矩阵里面的数值不同。
    那么我们看下ROC曲线的评测指标:

    纵轴:真阳率,召回率,TP/(TP+FN)
    横轴:假阳率FP/(FP+FN)
    那么ROC曲线有什么用,其实ROC曲线是为了得到AUC,即ROC曲线下的面积,,不同的阈值生成不同的混淆矩阵数值,打一个点就得到下面的曲线

    但是这样计算比较麻烦,我们可以利用其他方式去理解AUC,即负样本排在正样本前面的概率。
    假如A 0.1 B 0.9 我们假设负样本排正样本前面的概率认为正确,即A在B前面,认为是一次正确,B排在A前面,认为是一次错误。也就是按照概率进行倒序排序,上面是最小的概率,那么理想状态下,所有负例应该排在正例前面才对。
    我们可以通过一个AWK来计算:
    cat auc.raw | sort -t$'\t' -k2g |awk -F'\t' '($1==-1){++x;a+=y;}($1==1){++y;}END{print 1.0-a/(x\*y);}'x*y是正负样本pair对,a代表错误的个数,a/x*y 错误的概率,1-a/x*y 正确概率
    解释一下这个linux命令,按照第二个模型打的分数进行循环判断,小的排在前面,大的分数排在后面,当有的分数是比较小,但是不是该类的,这个a就加一个y,y从0开始加,直到结束,能够找到有多少a,进而计算评估的正确率
    例如:来了个文章,我们假如是军事类为+1,财经为-1,当然这个文章是军事类文章,即+1,然后我们设置一个阀值为0,即分类预测的分数 >0 认为是+1,<=0 认为是-1,x是负样本的个数,y是所有正样本个数,a是错误的样本个数

    那么这个最差就是0.5,压根不知道好坏,评测是到底是正确的评测还是错误的评测。最完美就是1或者0了
    0 留言 2019-04-28 12:40:13 奖励13点积分
  • 机器学习 15、分类算法 -LR

    前文链接:https://write-bug.com/article/2439.html
    逻辑回归前节中,我们分析了什么是分类以及机器学习的模型介绍、NB算法的应用、和二分类模型的评估。我们在这里再次总结一下机器学习的要素(括号内是对于LR而言):

    机器学习用数据训练出模型再应用的过程
    训练集训练所用的输入与输出
    测试集评估所用的输入与输出
    监督学习机器学习中,分为监督学习和非监督式学习,而监督式学习就是数据集有着明确的答案(即label),可供后续寻找输入输出之间的关系(误差)
    模型描述输入输出之间关系的方式(等式参数)
    训练学习输入输出之间关系的过程
    预测解决输入的预期输出的过程
    评估衡量模型好坏的过程
    泛化能力对一个前所未见的输入可以给出一个正确的预测

    在谈LR之前,我们需要介绍一些铺垫知识:
    一元线性回归何为回归为题?假如有一二维坐标系,横坐标x:西瓜重量,纵坐标y:西瓜价格,上面散落着一些点,即每个西瓜重量都有着对应的价格。如下图:

    那我如何根据这些数据,获取到一些规律,每次随意给我一个西瓜重量我都可以预测一个合理价格出来呢?我们需要像图中绿色的那条线一样,尽力去拟合所有数据,即 y=wx+b,给定x西瓜重量,返回y西瓜价格,未知参数:w,b。
    在上图中我们可以看到很多data点,同样的也就可以画出很多条线,那我们如何才能找到最可以拟合所有数据的最优线呢?我们可以给每个点和每条线之间都求取点到线的距离,即线没有拟合点的误差值,那么当我们找最优线的时候,我们把每次和这条线求的所有误差值加起来,看谁最小就好了,即最小化误差平方和:
    ∑((wx+b) - y)^2即loss function 找出最优参数,获取最优线。
    Error = y - y^那么如何求取最优参数?因为lossfunc为二次方程,坐标系中为下凸函数,所以求导=0就可以得出极小值:最优参数w,b

    模型输出:y^=wx+b
    模型参数:w,b

    多元线性回归在一元中,我们输入x为一个单因素值,即标量。在多元中,我们输入的x为多因素值,即向量。那么什么情况为多因素值呢?比如还是西瓜,那我的西瓜价格不只是重量影响着,还有颜色,拍的响声等等,而这些因素就是西瓜的特征,而西瓜在这里成为样本。
    但是这种多维度向量并不能在二维坐标系中显示,每个样本都有着多维度特征,可以想象,像二维坐标系中显示一样,在高纬度空间中散落着这些点,如果要做回归问题,就需要有一个超平面拟合这些数据点,如果做分类问题则需要一个超平面去尽力把两类样本点分开,而这里的西瓜问题是个回归问题。而这个超平面也就意味着我们的参数也变成了多维向量。即:
    X[x1,x2,x3...xn]W[w1,w2,w3,...wn]wx向量相乘是求内积。
    之前我们的等式y=wx+b,在机器学习中有了些新的名称:

    X:样本特征向量
    W:权重向量
    B:偏置

    比如:

    X样本为一个西瓜,那么西瓜的特征可能有:重量、颜色、响声、把的位置等等
    W权重即这些特征的重要程度,每个特征的权重都影响着最后的score
    B偏置的意思就是比如说各个地区的西瓜长得样子普遍不一样,那对于这类样本来说给他一个惩罚值平衡样本数据

    同样的,我们得到多元回归方程:
    𝑓(𝑥𝑖,𝑤,𝑏) = ∑𝑤𝑗𝑥𝑖𝑗 + 𝑏 = [𝑥𝑖1 ⋯ 𝑥𝑖𝑘][𝑤1 ⋮ 𝑤𝑘]+ 𝑏 = 𝑤𝑖𝑥 + 𝑏我们把b约去得到:
    𝑓(𝑥𝑖,𝑤,𝑏) = [𝑥𝑖1 ⋯ 𝑥𝑖𝑛][𝑤1 ⋮ 𝑤𝑛]+ 𝑏 = [𝑥𝑖1 ⋯ 𝑥𝑖𝑛 1][𝑤1 ⋮ 𝑤𝑛 𝑏]= 𝑤 · 𝑥𝑖所以只需要求:
    𝑓(𝑥𝑖,𝑤) = 𝑤𝑥和前面一样,为了求取最优参数,需要最小化误差平方和:
    min 𝑤 𝐿(𝑤) = ∑ (𝑤𝑥𝑖 – 𝑦𝑖)^2------》e只不过单因素标量变成了多因素向量了而已。
    同样,求导=0,但是这里w也是个向量, 根据微积分公式需要对每个w特征权重求偏导,得出:
    W=(XTX)^-1 XTYXT为X向量的转置,Y为输出后的向量
    当XT X 不可逆时,设定正数λ,W=(XTX + λI)^-1 XTY
    逻辑回归逻辑回归,logistic回归,是一种广义的线性回归分析模型,常用于数据挖掘,疾病自动诊断,经济预测等领域。常用于二分类问题,而多分类问题常用SoftMax函数来解决。
    上节说过,二分类问题也就是01问题,比如判断一个人是男是女,可以从多个特征来分辨:肤色、身高、体重、音色等等,每个特征都有自己的权重,像前面一样代表各个特征的影响度。
    设定1为男性,0为女性,则P(y=1|x)代表男性的概率,P(y=0|x)代表女性的概率。通常情况下,我们研究正例的概率,也就是y=1的概率,那么有:
    P(y=1|x)=f(x)这里的输入和前面的多元线性回归一样,但是输出是一个score,即
    f(x)=wx但是这里的score也就是y是一条直线,值域是(-∞,+∞),而概率的值域是[0-1],那如何让P(y=1|x)=wx呢?一起来推导下:
    exp(wx)的值域是[0,+无穷)p(y=0|x) = 1 - p(y=1|x)p(y=1|x) / (1 - p(y=1|x))的值域是[0,+无穷)p(y=1|x) / (1 - p(y=1|x))= exp(wx)p(y=1|x) = 1/(exp(-wx) +1)以上,我们通过压缩变换值域把他强制变到一个0-1的概率值
    在实际应用中,是客观存在这种非线性变换函数的,这里LR用Sigmoid函数:

    可以发现,和我们上面的想法推导几乎一致,但是这个函数不是我们推导出来的,而是客观存在的函数:

    那么这里我们求w这个最优参数值呢?
    在NB朴素贝叶斯中求取概率值,我们运用最大似然估计参数从而求得概率值。
    那么在这里我们同样对P运用最大似然:
    P(Y|X)=P^y * P^(1-y)这么表示并无实际含义,只是当y=0或1时的概率,那我们对它使用极大似然估计参数w:
    MLE w = arg max log(P(Y|X)) = arg max Π P(yi|xi) = arg max ∑ log P(yi|xi) = arg max ∑(yi LogP(y=1|X) +(1-yi) LogP(y=0|X))p(y=1|x) = 1/(exp(-wx) +1)p(y=0|x) = 1 - p(y=1|x)所以有:
    L(w)=-∑(yi log(𝜂(wx)) +(1-yi) (1-log(𝜂(wx))))为什么前面有个减号呢?最大似然函数是求取参数的极大值,是上凸函数,前面加个符号,图像就变成了下凸函数,这样我们就可以求取到参数极小值。
    看到上面的式子,如果你熟悉信息熵的话,是可以直接得到上面的式子的,即
    MLEmax = lossfunction min (- min CrossEntropy)信息熵公式:
    H(x)= - ∑ P(xi)log(p(xi))后面我们会有地方介绍信息熵,我们得到上面的L(w)负对数似然公式,由于它是高阶连续可导下凸函数,此时就可以将他作为损失函数来求解:
    利用梯度下降法更新参数w,求导得:
    ▽L(w)= -∑(yi- 𝜂(wx))xi机器学习的损失函数是人为设计的,用于评判模型好坏(对未知的预测能力)的一个标准,就像去评判任何一件事物一样,从不同角度看往往存在不同的评判标准,不同的标准往往各有优劣,并不冲突。唯一需要注意的就是最好选一个容易测量的标准,不然就难以评判了。
    其次,既然不同标准并不冲突,那使用最小二乘作为逻辑回归的损失函数当然是可以,那这里为什么不用最小二乘而用最大似然呢?请看一下最小二乘作为损失函数的函数曲线
    J(θ)=∑(yi- 𝜂(θx))
    以及最大似然作为损失函数的函数曲线
    L(w)=-∑(yi log(𝜂(wx)) +(1-yi) (1-log(𝜂(wx))))
    很显然,图2比图1展现的函数要简单多,很容易求到参数的最优解(凸函数),而图1很容易陷入局部最优解(非凸函数)。这就是前面说的选取的标准要容易测量,这就是逻辑回归损失函数为什么使用最大似然而不用最小二乘的原因了。
    此时,我们就可以和前面一样通过lossfunc求取最优参数w,通过不断降低差距来使预测值接近真实值(即反向传递的误差):
    由于L(w)是高阶连续可导的凸函数,根据凸优化理论,可利用梯度下降法、 牛顿法等求解,求导得到梯度:
    ▽L(w)= -∑(yi- 𝜂(wx))xi梯度:大小为导数的值,方向指向误差上升最快的方向
    当参数w维度大于1时,用相同的方法对各个维度求e偏导数(e(w)’),偏导数所组成的向量就是梯度。
    导数和梯度的区别是:导数是变化率,而梯度是一个和参数维度一样的向量。
    各个维度的数值等于对应的偏导数,那么让参数向梯度相反的方向更新,从而减小误差值。所以,使用梯度下降法更新最小化F(W),从而更新参数W:

    设置初始化w,计算F(w)=sigmoid(wx ) ->预估值我们的数据前面说过都是有label值的,也就是真实值,得到预测值和真实值之间的误差,我们希望通过学习数据让误差越来越小。
    计算梯度
    ▽F(w)=▽L(w)= -∑(yi- 𝜂(wx))xi此时我们已经得到了y真实值,w初始化值,x样本特征值,可以发现,梯度式子里面就是一个误差公式,那我们通过计算就可以直接代入乘以样本向量,得到梯度。下降方向
    dir = -▽F(w)负号:前面说过,反方向是下降最快方向
    尝试梯度更新
    𝑤𝑛𝑒𝑤 = 𝑤 +步长∗ 𝑑𝑖𝑟 得到下降后的 𝑤𝑛𝑒𝑤和F(w𝑛𝑒𝑤)如果 F(w𝑛𝑒𝑤)- F(w)较小,停止; 否则 ;跳到第2步
    1 留言 2019-05-08 22:26:17 奖励21点积分
  • 机器学习 16、分类算法 -Softmax

    前文链接:https://write-bug.com/article/2467.html
    梯度下降BGD
    在前文中,我们通过梯度下降法最优化更新参数w,那么上节那种迭代的方法为BGD,批量梯度下降。这种方法每次都把所有数据集都遍历一遍,从而每次都可以更新最优的参数。这种方式比较慢,实用性差但是效果好。

    SGD
    正常工作中,我们通常使用SGD,随机梯度下降,此种方法快,使用当前数据集的最优参数通过多次迭代不断逼近全局最优值。

    MBGD
    工业界中,常用方法minibatch小批量梯度下降,把所有样本分为不同的批次依次执行BGD(参数不变一直更新同一参数),效果介于前两种之间的折中方式。


    高参:不是模型参数,又影响训练结果的因素,根据不同的任务,人工调节
    Learning rate:参数以多大的幅度利用梯度更新,即走的步长epoch:遍历所有样本次数Batch size :每个batch中包含多少个样本的个数
    Batch:批次,每次epoch中,包含多个batch
    Step:更新一次批量
    shuffle优化:每次取的样本做随机打乱

    更新过程:
    计算误差值,将误差作为参数计算梯度,将所有参数减去对应梯度乘以学习速率完成一次更新
    多分类Softmax逻辑回归是Softmax的一般形式。在二分类中我们求取p(y=1|x)=sigmoid(wx)的概率作为正例,同时只求一组w,b的权重就可以了。
    但是在多分类中,我们的分类集合为{1,2,3,4。。。。。k}应用:数字识别、文章分类等
    那么这时,我们就需要对这个样本属于每个分类都求取一组权重:
    P(y=1|x)—w1=e^(w1x)P(y=2|x)—w2=e^(w2x)P(y=3|x)—w3=e^(w3x)P(y=1|x)=w1/(w1+w2+w3)所以求取到的每个概率看那个概率最大就属于哪个类。
    在给定输入x,对每一个类别j估算出概率值为p(y=j|x)
    输出一个k维向量(元素和为1)来表示这k个估计的概率值

    向量中所有概率相加=1。
    我们知道,逻辑回归的损失函数是

    那么由此我们可推广出softmax回归损失函数:


    k:当前类别,m:真实label
    只不过是softmax对k个值进行累加,logic对2个值进行累加
    同样的,对损失函数求导得:

    这时,你可能会好奇,到底怎么logic就成了softmax的特殊情况了,若k=2,Softmax回归退化为logistic回归:

    两个参数向量均减去向量θ1:

    此时,就得到了两个参数组成的向量,此值就是原来的概率值。
    我们在上面得到了梯度公式,就可以通过每个类乘学习率,各自更新自己的权重,得到一列权重向量。
    L1、L2正则我们可以看到上面提出的三种梯度公式都有一个λw,而这个λw可加可不加,加了之后相当于每次迭代更新时都变相给各自的权重加了个约束,对于大部分训练,效果都会变好,即正则化项。

    λ:衰退权重
    常用正则化项:

    L1范数:λ|w| 又称lassoL2范数:λ|w|^2 又称ridge(岭回归)当然在训练中,L1和L2是可以加起来跑的。L1+L2:(梯度+L1+L2)

    在日常使用中,我们需要对所有维度做一个综合考虑,达到效果最好。假设分辨男女的特征,类似戴眼镜这种没有区分能力的特征我们需要把他的w学为0,还有如果我的w声音学到了1000,w身高学到了100,w体重学到了10,单纯看每一个特征它的w都比较合理,但是从整体来看,w小的特征就会被强特征淹没掉,比如前面这几个只要出现了声音特征可能就一定确认为男性。这样的效果并不是我们想要的,泛化能力弱。
    这个正则项就是对w的惩罚项,如果加了正则项就相当于压缩了w:
    L1:|w|<1L2:sqrt(|w|^2)<1W是一组向量在公式中与各自的X相乘作内积,那上面压缩了w就相当于对每个w乘一个相同小数,Wold和Wnew比例关系相同,那么和之前的wx就是一回事了。


    由上图,我们把每次w更新的值想象为等高线(效果相同),在同倍数缩小时,和L1,L2构成的图形相交(每次更新的w都和我们的λ有着直接联系,看如何选择最优那组w)达到限制w扩散过大的目的。同时从图形中我们可以看出一些特点:

    L1:w1+w2=1,某时w与其角上会重合,过小的w会被优化为0,形成稀疏矩阵
    从系统实现角度:大大减少参数存储空间(只存储有数部分)、针对性强,泛化能力好,防止过拟合
    L2: w1^2+w2^2=1,与圆相交相切几乎都不为0,不会产生稀疏矩阵,可以对一票否决权的这种权重惩罚的也大,让权值尽可能小,防止过拟合

    欠拟合、过拟合在大部分算法中,都存在过拟合问题,即一个模型在训练集上表现得非常好,但是在实际测试中效果差,将噪声一起学到了模型中

    上图中,既可以表现过拟合的现象,又是一种防止过拟合的方法:即交叉验证
    上面的线为测试集错误率,下面为训练集错误率,在训练的同时进行测试(每训练几轮测试一下),一旦测试集错误率上升,立即停止训练,防止过拟合。
    那么还有什么防止方法呢?

    筛选特征(过多特征的筛选、降维)
    人工筛选:根据时间、重要程度等等对特征进行优先级排列或筛选
    机器筛选(如mrMR信息增益(-决策树)):比如一个特征对男女判断是否有用,可以对其求auc

    特定模型方法
    增加惩罚项(L1、L2)
    决策树高度

    增加训练数据(万能)
    神经网络Dropout(减边)

    欠拟合:一般都是训练轮数不够,那么一般增加训练轮数和决策树拓展分支
    1 留言 2019-05-16 13:39:17 奖励16点积分
  • 机器学习 18、聚类算法-Kmeans

    前文链接:https://write-bug.com/article/2530.html
    上节 我们暂时实现了一下单机版推荐系统,并且串了下知识,这节介绍下聚类,说起聚类就得先提下监督和非监督式学习:

    监督式学习:我们之前学习的分类、回归问题中的排序模型LR、Softmax,包括后面的dnn,dt等等都是需要数据事先有一个标签label作为新特征的分类
    非监督式学习:而这个有些类似之前的推荐算法,并没有特定的类别作为比对

    而今天学习的算法聚类算法也是非监督式学习。
    聚类是什么?之前对于文本分类来说,需要事先设定好类别标签对新文本进行概率分类、对label对比,而这里的聚类则可以既不需要设定类别,也不需要事先设定文本中心,其可自动将数据划分到不同的类中,使相似的数据划分到相同的类中,这种方法可应用到几乎所有分类中,用户聚类、商品聚类、生物特征、基因、图像聚类等等分类。
    比如说,随机系统中有10000篇文章,我只告诉系统分为多少个类,其他什么都不告诉,这个系统就可以自动操作完成。
    事实上,就是对特征的向量化及空间划分。
    向量化如果想对一个文章、物品等作聚类,那聚类之前,如何表示文章呢?
    向量
    比如之前的tfidf,用一个向量来表示物品之后作cos、内积、计算质心等等
    质心:各个向量的点构成的空间的中心,即每个点到这个点的最短平均距离
    A:(a1, a2, a3)B:(b1, b2, b3)C:(c1, c2, c3)质心=( (a1+b1+c1)/3, (a2+b2+c2/3, (a3+b3+c3)/3)距离矩阵、相似度矩阵
    此矩阵就像之前的推荐算法中的矩阵,各个pair相似度的矩阵
    评估如何评估聚类效果?
    内部方法
    同类尽可能相似,不同类尽可能不相似

    分子为对象到质心距离和,越小越好
    分母为质心距离,越大越好
    外部方法(准确P、召回R)
    之前利用pr曲线找到最好的分类面,但是需要有监督的情况下才能用,这里如果想用,在特定情况下,比如说文章有固定标签,用这种方法训练后再告诉label评估效果,但是工作中几乎遇到的都是无标签的,所以这种方法是很鸡肋的方法,工作中基本用内部方法解决。
    F=PR /(P+R)聚类类别层次聚类


    自底向上凝聚聚类,从不同的对象凝聚结果形成聚合节点,成树状
    自顶向下分裂聚类,从一个对象分裂结果形成分裂节点,成树状

    优点:

    可通过阈值灵活控制类个数
    层次用于概念聚类,分类后人工对其打标签,抽象概念。

    凝聚实现:

    将每个对象样本分为一类,得到N个类
    找到最接近的两个类合并为一个类:两层for循环遍历所有样本,计算cos相似度
    重新计算新类与旧类之间距离:类别之间距离和类别与对象之间距离的计算方式一般使用组合链的方式进行计算:即类中质心距离(平均距离),而与之相对的有单链(最近距离)和全链(最远距离)两种方式,一般工作中就直接使用组合链方式
    重复直到最后合并为一个类
    复杂度O(n^3)

    非层次聚类:Kmeans
    层次聚类是一种需要将向量两两比较聚类的方法,但这种方法的计算时间过长,影响效率,而Kmeans是随机选择对象作为类别中心,然后优化这些中心点的位置,使尽可能收敛到和真实中心一致的算法。
    步骤:

    任意选择K个点作为初始聚类中心 (初始化类个数)
    根据每个聚类的中心,计算每个对象与这些中心的距离(cos、欧式距离),并根据 最小距离重新对相应对象进行划分

    欧式距离:A:(a1, a2, a3) B:(b1, b2, b3)距离=sqrt((a1-b1)^2 + (a2-b2)^2 + (a3-b3)^2 )
    重新计算每个聚类的中心 (更新质心计算)
    当满足一定条件,如类别划分不再发生变化时,算法终止,否则 继续步骤2和3
    复杂度:O(Ktn^2)K个点,n个对象,t次循环,n次计算质心

    之前介绍时为什么说是向量化并分割空间,下面这个图每个点都是空间中的向量点,把两个中心点相连,中心分割的垂线就是分割面,再迭代更新质心位置,从而分割空间


    一定条件:

    轮数
    WCSS损失函数:最小化簇内对象到质心的距离平方和

    wcss变小,即空间变化不剧烈

    缺点:过于依赖初始点选择,可能导致的结果大不一样
    解决方法:只能多训练几轮,求质心平均值或者选择最小的wcss的模型。
    模型:最终计算结果的K个中心点向量
    K选择,业务场景:
    举例:半个性化推荐,即热榜推荐列表只有一部分是个性化对用户的推荐(如视频网站首页上半部),但是当用户上亿,但热榜或首页展示目录只有10个,候选集合只有100个的时候怎么办?如何给大量的用户也做一个模糊的推荐?如何在100个候选集合中选择10个作为推荐列表?
    对上亿用户作聚类,可以随意聚几千个类,再用这几千个类的向量和每个物品向量作cos,选出分数前10的物品向量作为此用户类的候选集合。
    用户向量化:利用历史行为作用户画像:token作向量
    层次 vs Kmeans

    从上面两张图,我们可以看到右面Kmeans算法的暴力分割和缺点,在生活中的数据大部分都是球面原始数据,也是Kmeans的强项,左面的那种长条数据只能用层次聚类分辨出来,而与此同时左面五颜六色的单点都是噪音数据,前面说过层次聚类非常耗时,并且我们事先并不知道数据的分布,所以部分解决办法就是增加K类个数。
    Kmeans粒度比较粗,层次粒度比较细。
    聚类这种发现规律的分类效果永远无法赶上分类回归那种有监督式的效果,即有老师无老师的区别。如果效果不好,可以适当增加K个数增加准确率。
    0 留言 2019-05-29 15:55:53 奖励16点积分
  • 【Cocos Creator实战教程(3)】——TiledMap(瓦片地图)组件 精华

    1. 前言瓦片地图是由一张一张的正方形小图片拼接成的地图,例如炸弹人,QQ堂都是非常典型的瓦片游戏。瓦片地图(Tile Map) 不但生成简单,并且可以灵活的用于Cocos2d-x引擎。不论你的游戏是角色扮演游戏, 平台动作游戏或仿打砖块游戏,这些游戏地图可以使用开源的瓦片地图编辑器Tiled Map Editor生成并保存为TMX文件格式,被Cocos2d-x支持。
    2. 步骤2.1 安装Tiled Map Editoredit(编辑)->preferences(参数)里面可以设置语言
    2.2 TiledMap制作新建一张地图

    建立三个图层和一个对象层并将资源图块导入 (最下面的图层将显示在最下面)



    ground层:用ground图块填充满(按住鼠标左键)
    barriers层:用barrier图块
    stars层:用star图块

    最终效果如下图

    选择players对象层,在如图位置插入两个图块对象,并更改名称如图

    给星星添加一个属性

    保存为tmx文件,和图片文件放在一起
    2.3 Cocos Creator中使用TiledMap:
    新建一个TiledMapTest工程,创建一个Game场景
    将刚才生成的tmx文件和相关图片一起添加到工程
    将map.tmx文件拖入层级管理器或者属性编辑器,就会自动生成map节点以及其子节点(也就是图层节点)【没有对象层节点】
    最后将player(安卓小机器人)图片拖入(位置随意),创建player节点,并使其为map节点的子节点。
    调整map和player节点的锚点都为(0,0)也就是左下角
    创建map.js脚本添加到map节点

    cc.Class({ extends: cc.Component, properties: { }, // use this for initialization onLoad: function () { this.player = this.node.getChildByName('player'); this.loadMap(); cc.systemEvent.on(cc.SystemEvent.EventType.KEY_DOWN, this.onKeyDown, this); }, onKeyDown:function(event){ var newTile = cc.p(this.playerTile.x, this.playerTile.y); switch(event.keyCode) { case cc.KEY.up: newTile.y -= 1; break; case cc.KEY.down: newTile.y += 1; break; case cc.KEY.left: newTile.x -= 1; break; case cc.KEY.right: newTile.x += 1; break; default: return; } this.tryMoveToNewTile(newTile); }, //加载地图文件时调用 loadMap: function () { //初始化地图位置 this.node.setPosition(cc.visibleRect.bottomLeft); //地图 this.tiledMap = this.node.getComponent(cc.TiledMap); //players对象层 let players = this.tiledMap.getObjectGroup('players'); //startPoint和endPoint对象 let startPoint = players.getObject('startPoint'); let endPoint = players.getObject('endPoint'); //像素坐标 let startPos = cc.p(startPoint.offset.x, startPoint.offset.y); let endPos = cc.p(endPoint.offset.x, endPoint.offset.y); //障碍物图层和星星图层 this.barriers = this.tiledMap.getLayer('barriers'); this.stars = this.tiledMap.getLayer('stars'); //出生Tile和结束Tile this.playerTile = this.startTile = this.getTilePos(startPos); this.endTile = this.getTilePos(endPos); //更新player位置 this.updatePlayerPos(); }, tryMoveToNewTile: function(newTile) { let width = this.tiledMap.node.width; let height = this.tiledMap.node.height; if (newTile.x < 0 || newTile.x >= width) return; if (newTile.y < 0 || newTile.y >= height) return; if (this.barriers.getTileGIDAt(newTile)) {//GID=0,则该Tile为空 cc.log('This way is blocked!'); return false; } this.tryCatchStar(newTile); this.playerTile = newTile; this.updatePlayerPos(); if (cc.pointEqualToPoint(this.playerTile, this.endTile)) { cc.log('succeed'); } }, tryCatchStar: function(newTile){ let GID = this.stars.getTileGIDAt(newTile); let prop = this.tiledMap.getPropertiesForGID(GID); if (this.stars.getTileGIDAt(newTile)) {//GID=0,则该Tile为空 this.stars.removeTileAt(newTile); } }, //将像素坐标转化为瓦片坐标 getTilePos: function(posInPixel) { let mapSize = this.node.getContentSize(); let tileSize = this.tiledMap.getTileSize(); let x = Math.floor(posInPixel.x / tileSize.width); let y = Math.floor(posInPixel.y / tileSize.height); return cc.p(x, y); }, updatePlayerPos: function() { let pos = this.barriers.getPositionAt(this.playerTile); this.player.setPosition(pos); },});
    最终如下图:

    3. 总结#CC.TiledMap:~properties:tmxFile//地图文件mapLoaded//地图加载是调用的函数~function:getMapSize()//setMapSize()//getTileSize()//setTileSize()//getLayer(name)//returns TieldLayergetObjectGroup(name)//returns TMXObjectGroupgetPropertiesForGID(GID)//returns Object(属性字典)#CC.TieldLayer getPositionAt(pos)//returns Vec2(像素坐标) 参数是瓦片坐标removeTileAt(pos)//瓦片坐标getTileGIDAt(pos)//returns Number(全局唯一标识,0为空)getTileAt(pos)//returns _ccsg.Sprite //removeChild(sprite);setTileGID(gid,pos)//相当于在pos位置添加GID的图块(原来的图块删除)getTileSize()//setTleSize()//getMapTileSize()#TMXObjectGroup:~properties:~function:var getObject(var objectName)//返回属性字典#_ccsg.Sprite://cocos js 里的Sprite,继承自CC.Node,而不是组件~properties:xywidthheightopacity...//节点的属性都有~function:var setSpriteFrame(var spriteFrameName)var runAction(var action) ...//节点的方法都有

    图块放置的位置是基于像素坐标,而图块在map中的索引是基于瓦片坐标(整数),所以在脚本文件中要适时转变
    对象层的对象(比如我们上面做的两个player point),在Cocos Creator中是不会显示的
    对象层记录的是位置信息,图层记录的是图片信息
    .tmx文件其实保存的图块的一种映射关系,所以图块文件和地图文件要始终放在一起,不然可能会显示出错
    GID是图块在一个地图文件中的唯一ID,(图块指的是右下角的图块文件,每一个图块都不相同,瓦片指的指地图中的块,可以是相同的图块),GID为0说明该Tile的图块为空
    当利用getPropertiesForGID(GID)之类的方法时,得到的返回值是属性字典,可以直接通过点方法得到其属性值,属性值都是字符串类型
    当用到getTileAt(pos)时,得到的返回值是Cocos2d 的Sprite,而不是Cocos Creator的Sprite,相关方法可以查找Cocos2d js的API,需要注意的一点是,Cocos2d的Sprite是继承自节点的,而不是组件式,所以我们可以直接这样写“mySprite.x = 100”而不是“mySprite.node.x = 100”
    地图中同一层只能使用一张图集里的图块

    注意:本教程资源部分来源于网络
    2 留言 2018-11-24 18:06:17 奖励15点积分
  • 计算机视觉现代优化方法

    1. 概述本次实验中,我基于OpenCV,实现了一个二维图像配准工具,全部代码均为自行实现,OpenCV用于计算图像变换与相似度。
    该工具能够将一幅图像进行变换,并与另一幅图像相匹配。支持包括平移、旋转(含平移、缩放)、仿射与透视共四种变换,使用L1、L2、无穷范数作为优化的目标函数,实现了暴力算法、梯度下降法、模拟退火算法来求解该优化问题。
    2. 应用问题如果两幅图像,它们是在同一场景、不同角度下拍摄的,那么,存在一种图像变换,使得其中一幅图像经过变换后,能与另一图像大部分重合。
    上述图像变换被称为配准(registration)T,被变换的图像被称为参考图像I_M,另一图像被称为目标图像I_F。优化的目标是使变换后的参考图像T(I_M)与目标图像I_F的差异尽可能低。
    最简单的图像变换是平移变换,需要确定两个参数: x和 y; 旋转变换通常与缩放、平移共同进行,需要确定四个参数: x、y、theta、scale; 仿射变换将矩形图像线性映射至一个平行四边形,需要确定三个坐标点,共六个参数,三个坐标点分别表示原图左上、右上、左下角变换至新图像的坐标位置; 透视变换与仿射变换相似,不同的是原图像的四个顶点可变换至任意的四边形,所以需要确定四个坐标点,共八个参数。此外,也有更为精细的图像变换方法,但相比于上述简单变换,其参数较多,难以优化,故本次实验不予考虑。
    对于图像相似度,需针对使用场景选择合适的度量方法。本实验中,实现的方法有L1(1范数)、L2(2范数)、无穷范数三种。
    总的来说,问题可以总结为如下步骤:

    输入参考图像、目标图像;
    选择合适的变换,确定参数范围;
    设置初始参数,在这个参数下变换参考图像,并计算与目标图像的差异;
    调整参数,使上述差异达到最小值;
    输出最优参数作为配准变换。

    3. 数据来源本实验使用在实验室拍摄的四张照片作为测试数据。














    4. 实现算法4.1 软件界面本实验搭建了一个二维图像配准工具。”主界面”可进行配准的各项设置,并展示参考图像与目标图像:

    “结果界面”会在运行配准之后弹出,分左中右三栏,分别为变换后的参考图像、变换后的参考图像与目标图像的对比(会交替显示两图像)、目标函数优化曲线:

    4.2 优化算法在上述基础上实现了三种优化算法,分别是暴力算法、梯度下降法、模拟退火算法。执行算法前,首先会在Registration::initialize()函数中针对不同变换方式,初始化变换的各项参数,例如旋转变换(四个参数):
    params.resize(4); // cx cy angle scalelimits.resize(4);steps.resize(4);limits[0] = std::make_pair(-c / 2, c / 2);limits[1] = std::make_pair(-r / 2, r / 2);limits[2] = std::make_pair(-180, 180);limits[3] = std::make_pair(0.5, 2);for (int i = 0; i < params.size(); i++) { params[i] = limits[i].first;}steps[0] = 1;steps[1] = 1;steps[2] = 1;steps[3] = 0.01;
    其中params表示参数数组,limits表示各个参数的取值范围,steps表示各个参数邻域的步长。
    暴力算法使用深度优先搜索遍历整个可行解空间,可求解出全局的最优解:
    void Registration::optimizeNaive(int pos) { if (pos >= params.size()) { completeIteration(); return; } for (float i = limits[pos].first; i <= limits[pos].second; i += steps[pos]) { params[pos] = i; optimizeNaive(pos + 1); }}
    梯度下降法在每轮迭代中,寻找当前最优解的邻域中最优的可行解,并以此代替最优解,直到邻域中没有比当前解更好的解为止。我实现的函数中,某个可行解的邻域定义为将第i个参数增加或减少steps[i]得到的可行解的集合(i为某个随机参数的序号)。因梯度下降法与初始值选取密切相关,选择不当会导致陷入局部最优解,我在函数中增加了一个外循环,每轮循环随机选择一组初始值,并开始一轮新的梯度下降:
    void Registration::optimizeGD() { for (int i = 0; i < 10000; i++) { double tmp_loss = 1e30; double cur_loss = 1e30; for (int j = 0; j < params.size(); j++) { // give random start values params[j] = random(limits[j].first, limits[j].second); } while (true) { std::vector<float> old = params; std::vector<float> best = params; for (int pos = 0; pos < params.size(); pos++) { params[pos] = old[pos] + steps[pos]; optimizeGDHelper(best, cur_loss); params[pos] = old[pos] - steps[pos]; optimizeGDHelper(best, cur_loss); params[pos] = old[pos]; } if (tmp_loss == cur_loss) { break; } tmp_loss = cur_loss; params = best; completeIteration(); } completeIteration(); }}void Registration::optimizeGDHelper(std::vector<float>& best, double& cur_loss) { applyTransform(); double s = getSimilarity(trans_img, tar_img, similarity_type); if (s < cur_loss) { cur_loss = s; best = params; }}
    模拟退火算法与梯度下降法相比,具有跳出局部最优解的能力。当温度较低时,算法不容易跳出局部最优解,从而退化为梯度下降法。所以,如果在温度下降到很低时没能跳入最优解附近,算法同样会收敛于局部最优解。因此,与上述梯度下降法的代码类似,我也使用了一层外循环,用于生成多个随机初始参数:
    void Registration::optimizeSA() { for (int i = 0; i < 10000; i++) { for (int j = 0; j < params.size(); j++) { // give random start values params[j] = random(limits[j].first, limits[j].second); } applyTransform(); double fi = getSimilarity(trans_img, tar_img, similarity_type); double temp = 10; double r = 0.99; int k = 1000; while (k > 0) { // select a random neighbor int len = params.size(); int r1 = rand() % len; double r2 = random(1, 10) * ((rand() % 2) * 2 - 1); params[r1] += r2 * steps[r1]; applyTransform(); double fj = getSimilarity(trans_img, tar_img, similarity_type); double delta = fj - fi; if (random(0, 1) < exp(-delta / temp)) { // jump to this neighbor completeIteration(iter % 10 == 0); fi = fj; } else { params[r1] -= r2 * steps[r1]; } temp *= r; k--; } completeIteration(); }}
    4.3 实现细节
    计算图像变换、图像相似度需要遍历图像每一像素,这一过程是较为耗时的。对此,代码中将图像先缩小至原有尺寸的1/10,即,像素数变为原来的1/100,再进行变换、相似度计算。最终再恢复至原有图像尺寸。
    图像变换后,其周围可能出现空白区域(下图),在计算图像相似度时,这一区域也是需要计算的(否则会倾向于生成全是边界的图像),所以需要填补这一区域。我使用的方法是计算全图像的平均颜色,并以平均颜色填补。


    5. 实验结果与分析5.1 目标函数值可视化下图展示了4号图片到1号图片的平移变换的优化目标函数值。平移变换有两个参数,所以可以映射到二维空间。使用上述暴力算法计算出参考图像平移至所有位置,计算其目标函数值,便得到如下的可视化结果。
    从图中可以看出目标函数最优值(最小值)位于图像中间附近,有局部最优值,但该函数较为光滑,因此可认为性质较好。

    5.2 结果5.2.1 暴力算法暴力算法效率较低,所以只进行了平移变换、旋转变换的实验。其中,平移变换约耗时3秒,旋转变换耗时数分钟。
    该算法可以确保找到最优解,可作为其他算法的验证手段。
    下图是枚举平移变换参数时,相似度函数的变化曲线:

    5.2.2 梯度下降法下图是使用梯度下降法优化仿射变换配准问题的结果,在迭代至5000轮左右时,已经找到较好的结果。这里,每一轮迭代指的是找到一个新的最优值,或开启一次新的梯度下降。
    右侧的蓝色曲线表示梯度下降过程的目标函数值变化,可以看出,在每轮梯度下降过程内,目标函数值能够快速下降。

    5.2.3 模拟退火算法下图使用了模拟退火算法来计算5.2.2中相同的优化问题以便对比。该方法约在4000轮左右取得一个较好的解,更好的解出现在50000轮左右。
    相比于梯度下降法,模拟退火在每轮迭代中不需要计算所有邻域解,而梯度下降计算数量为参数个数*2,所以模拟退火的迭代速度高于梯度下降。
    为了使两次模拟退火之间可以区分,我在两次模拟退火的能量函数之间插入了一个峰值。观察蓝色曲线可以发现,每次运行模拟退火时,前期能量函数波动较大(因为跳到更差的解的几率很大),在后期逐渐趋于稳定,类似梯度下降的结果。

    5.3 参数调整三种算法中,只有模拟退火算法有需要调整的参数。包括迭代次数k、初始温度temp与温度衰减系数r。
    k控制何时停止迭代,根据曲线取值即可。
    起初不知道如何设置初始温度与衰减系数,将温度设置得很高,衰减也很快,然后发现优化效果不如梯度下降法。分析各个参数的作用与模拟退火算法的优势之后,我得到结论:

    初始温度应与目标函数值在同一量级;
    衰减系数应调整到使得温度在进行了一半的迭代轮数之后下降到足够低,进而使得优化只向更优的可行解跳跃。

    最终的曲线和期望一致,一开始有较大的波动,随后逐渐稳定直至收敛。
    5.4 分析与结论本次实验我得到了如下结论:

    经过对比试验,对于二维照片配准问题,使用2范数作为相似性度量函数的效果较好,其次是1范数。
    参数空间的邻域结构非常重要。例如仿射变换矩阵尺寸为2*3,有六个参数,若直接优化这六个参数,则优化结果较差,很难收敛到最优解。原因可能是这六个参数的现实意义不够明确(例如,增大第一个参数会使图像怎样变化),且参数之间存在较大关联性(例如,同时增大第一个、第五个参数,作用是放大图像,而只改变一个则图像会变得不自然)。仿射变换的另一种表示方式是,原图像的左上、右上、左下三个顶点分别变换到了新图像的哪些位置,同样需要六个参数描述,但这些参数的可解释性更强,目标函数也更容易优化至最优。实验发现,选择合适的参数能够让目标函数的性质更好,更容易收敛到全局最优解。
    模拟退火算法在图像配准问题上的优势不明显。对于特别不光滑的目标函数,梯度下降算法是无能无力的,因为选择一个随机初始值下降至全局最优值的概率非常低。而模拟退火算法有助于跳出这些波动,相比梯度下降法更容易得到最优解。但是对于图像配准问题,其目标函数性质较好,局部最优解较少。于是,多次使用梯度下降算法也能够找到全局最优解,模拟退火算法的优势难以体现。
    0 留言 2019-06-16 23:22:40 奖励20点积分
  • 基于python构建搜索引擎系列——(六)系统展示及总结

    系统展示前几个博客已经介绍完搜索引擎的所有功能,为了实现更好的用户体验,需要一个web界面。这一部分是另一个队员做的,我这里借用他的代码。
    我们利用开源的Flask Web框架搭建了展示系统,搜索引擎只需要两个界面,一个是搜索界面,另一个是展示详细新闻的页面(实际搜索引擎没有这个页面)。编写好这两个模板页面并调用前面给出的接口,得到数据,展示出来就可以。
    这一部分没有太多需要讲解的算法,直接上效果图(点击图片可以查看大图)。


    由于数据量不大,只有1000条新闻,所以第一页中后面几个结果相关度就不是很高了。但是经过测试,在大数据量的情况下,不论是搜索的速度、准确率、召回率以及推荐阅读的相关度,都达到了不错的效果。
    总结至此,整个新闻搜索引擎构建完毕,总体效果令人满意,不过还是有很多可以改进的地方。下面总结一下本系统的优点和不足。
    优点倒排索引存储方式。因为不同词项的倒排记录表长度一般不同,所以没办法以常规的方式存入关系型数据库。通过将一个词项的倒排记录表序列化成一个字符串再存入数据库,读取的时候通过反序列化获得相关数据,整个结构类似于邻接表的形式。
    推荐阅读实现方式。利用特征提取的方法,用25个关键词表示一篇新闻,大大减小了文档词项矩阵规模,提高计算效率的同时不影响推荐新闻相关性。
    借用了Reddit的热度公式,融合了时间因素。
    不足构建索引时,为了降低索引规模,提高算法速度,我们将纯数字词项过滤了,同时忽略了词项大小写。虽然索引规模下降了,但是牺牲了搜索引擎的正确率。
    构建索引时,采用了jieba的精确分词模式,比如句子“我来到北京清华大学”的分词结果为“我/ 来到/ 北京/ 清华大学”,“清华大学”作为一个整体被当作一个词项,如果搜索关键词是“清华”,则该句子不能匹配,但显然这个句子和“清华”相关。所以后续可以采用结巴的搜索引擎分词模式,虽然索引规模增加了,但能提升搜索引擎的召回率。
    在推荐阅读模块,虽然进行了维度约减,但是当数据量较大时(数十万条新闻),得到的文档词项矩阵也是巨大的,会远远超过现有PC的内存大小。所以可以先对新闻进行粗略的聚类,再在类内计算两两cosine相似度,得到值得推荐的新闻。
    在热度公式中,虽然借用了Reddit的公式,大的方向是正确的,但是引入了参数k1k1和k2k2,而且将其简单的设置为1。如果能够由专家给出或者经过机器学习训练得到,则热度公式的效果会更好。
    本文转载自:

    http://bitjoy.net/2016/01/09/introduction-to-building-a-search-engine-6
    http://bitjoy.net/2016/01/09/introduction-to-building-a-search-engine-7
    1 留言 2019-06-06 17:05:21 奖励12点积分
  • 基于python构建搜索引擎系列——(五)推荐阅读 精华

    虽然主要的检索功能实现了,但是我们还需要一个“推荐阅读”的功能。当用户浏览某条具体新闻时,我们在页面底端给出5条和该新闻相关的新闻,也就是一个最简单的推荐系统。

    推荐模块的思路是度量两两新闻之间的相似度,取相似度最高的前5篇新闻作为推荐阅读的新闻。
    我们前面讲过,一篇文档可以用一个向量表示,向量中的每个值是不同词项t在该文档d中的词频tf。但是一篇较短的文档(如新闻)的关键词并不多,所以我们可以提取每篇新闻的关键词,用这些关键词的tfidf值构成文档的向量表示,这样能够大大减少相似度计算量,同时保持较好的推荐效果。
    jieba分词组件自带关键词提取功能,并能返回关键词的tfidf值。所以对每篇新闻,我们先提取tfidf得分最高的前25个关键词,用这25个关键词的tfidf值作为文档的向量表示。由此能够得到一个1000*m的文档词项矩阵M,矩阵每行表示一个文档,每列表示一个词项,m为1000个文档的所有互异的关键词(大概10000个)。矩阵M当然也是稀疏矩阵。
    得到文档词项矩阵M之后,我们利用sklearn的pairwise_distances函数计算M中行向量之间的cosine相似度,对每个文档,得到与其最相似的前5篇新闻id,并把结果写入数据库。
    推荐阅读模块的代码如下:
    from os import listdirimport xml.etree.ElementTree as ETimport jiebaimport jieba.analyseimport sqlite3import configparserfrom datetime import *import mathimport pandas as pdimport numpy as npfrom sklearn.metrics import pairwise_distancesclass RecommendationModule: stop_words = set() k_nearest = [] config_path = '' config_encoding = '' doc_dir_path = '' doc_encoding = '' stop_words_path = '' stop_words_encoding = '' idf_path = '' db_path = '' def __init__(self, config_path, config_encoding): self.config_path = config_path self.config_encoding = config_encoding config = configparser.ConfigParser() config.read(config_path, config_encoding) self.doc_dir_path = config['DEFAULT']['doc_dir_path'] self.doc_encoding = config['DEFAULT']['doc_encoding'] self.stop_words_path = config['DEFAULT']['stop_words_path'] self.stop_words_encoding = config['DEFAULT']['stop_words_encoding'] self.idf_path = config['DEFAULT']['idf_path'] self.db_path = config['DEFAULT']['db_path'] f = open(self.stop_words_path, encoding = self.stop_words_encoding) words = f.read() self.stop_words = set(words.split('\n')) def write_k_nearest_matrix_to_db(self): conn = sqlite3.connect(self.db_path) c = conn.cursor() c.execute('''DROP TABLE IF EXISTS knearest''') c.execute('''CREATE TABLE knearest (id INTEGER PRIMARY KEY, first INTEGER, second INTEGER, third INTEGER, fourth INTEGER, fifth INTEGER)''') for docid, doclist in self.k_nearest: c.execute("INSERT INTO knearest VALUES (?, ?, ?, ?, ?, ?)", tuple([docid] + doclist)) conn.commit() conn.close() def is_number(self, s): try: float(s) return True except ValueError: return False def construct_dt_matrix(self, files, topK = 200): jieba.analyse.set_stop_words(self.stop_words_path) jieba.analyse.set_idf_path(self.idf_path) M = len(files) N = 1 terms = {} dt = [] for i in files: root = ET.parse(self.doc_dir_path + i).getroot() title = root.find('title').text body = root.find('body').text docid = int(root.find('id').text) tags = jieba.analyse.extract_tags(title + '。' + body, topK=topK, withWeight=True) #tags = jieba.analyse.extract_tags(title, topK=topK, withWeight=True) cleaned_dict = {} for word, tfidf in tags: word = word.strip().lower() if word == '' or self.is_number(word): continue cleaned_dict[word] = tfidf if word not in terms: terms[word] = N N += 1 dt.append([docid, cleaned_dict]) dt_matrix = [[0 for i in range(N)] for j in range(M)] i =0 for docid, t_tfidf in dt: dt_matrix[i][0] = docid for term, tfidf in t_tfidf.items(): dt_matrix[i][terms[term]] = tfidf i += 1 dt_matrix = pd.DataFrame(dt_matrix) dt_matrix.index = dt_matrix[0] print('dt_matrix shape:(%d %d)'%(dt_matrix.shape)) return dt_matrix def construct_k_nearest_matrix(self, dt_matrix, k): tmp = np.array(1 - pairwise_distances(dt_matrix[dt_matrix.columns[1:]], metric = "cosine")) similarity_matrix = pd.DataFrame(tmp, index = dt_matrix.index.tolist(), columns = dt_matrix.index.tolist()) for i in similarity_matrix.index: tmp = [int(i),[]] j = 0 while j < k: max_col = similarity_matrix.loc[i].idxmax(axis = 1) similarity_matrix.loc[i][max_col] = -1 if max_col != i: tmp[1].append(int(max_col)) #max column name j += 1 self.k_nearest.append(tmp) def gen_idf_file(self): files = listdir(self.doc_dir_path) n = float(len(files)) idf = {} for i in files: root = ET.parse(self.doc_dir_path + i).getroot() title = root.find('title').text body = root.find('body').text seg_list = jieba.lcut(title + '。' + body, cut_all=False) seg_list = set(seg_list) - self.stop_words for word in seg_list: word = word.strip().lower() if word == '' or self.is_number(word): continue if word not in idf: idf[word] = 1 else: idf[word] = idf[word] + 1 idf_file = open(self.idf_path, 'w', encoding = 'utf-8') for word, df in idf.items(): idf_file.write('%s %.9f\n'%(word, math.log(n / df))) idf_file.close() def find_k_nearest(self, k, topK): self.gen_idf_file() files = listdir(self.doc_dir_path) dt_matrix = self.construct_dt_matrix(files, topK) self.construct_k_nearest_matrix(dt_matrix, k) self.write_k_nearest_matrix_to_db()if __name__ == "__main__": print('-----start time: %s-----'%(datetime.today())) rm = RecommendationModule('../config.ini', 'utf-8') rm.find_k_nearest(5, 25) print('-----finish time: %s-----'%(datetime.today()))
    这个模块的代码量最多,主要原因是需要构建文档词项矩阵,并且计算k邻居矩阵。矩阵数据结构的设计需要特别注意,否则会严重影响系统的效率。我刚开始把任务都扔给了pandas.DataFrame,后来发现当两个文档向量合并时,需要join连接操作,当数据量很大时,非常耗时,所以改成了先用python原始的list存储,最后一次性构造一个完整的pandas.DataFrame,速度比之前快了不少。
    本文转载自:http://bitjoy.net/2016/01/09/introduction-to-building-a-search-engine-5
    1 留言 2019-06-03 15:49:20 奖励14点积分
  • 基于python构建搜索引擎系列——(三)构建索引 精华

    目前正是所谓的“大数据”时代,数据量多到难以计数,怎样结构化的存储以便于分析计算,是当前的一大难题。上一篇博客我们简单抓取了1000个搜狐新闻数据,搜索的过程就是从这1000个新闻中找出和关键词相关的新闻来,那么怎样快速搜索呢,总不可能依次打开xml文件一个字一个字的找吧,这时就需要借助倒排索引这个强大的数据结构。
    在讲倒排索引之前,我们先介绍一下布尔检索。布尔检索只是简单返回包含某个关键词的文档,比如查询“苹果手机”,则返回所有包含“苹果”和“手机”关键词的文档,布尔检索并不对返回结果排序,所以有可能返回的第一个文档是“某个男孩边吃苹果边玩手机…“。
    实现布尔检索并不难,我们需要构建一个如下图的词项文档矩阵:

    每行对应一个词项,每列对应一个文档,如果该值为1,表示该行词项出现在该列文档中。比如词项”苹果“出现在doc1和doc3文档中,如果我们要找同时出现”苹果“和”手机“的文档,只需把他们对应的向量取出来进行”与“操作,此为101&011=001,所以doc3同时出现了”苹果“和”手机“两个关键词,我们将其返回。
    布尔检索虽然很快,但是它也有很多缺陷,比如不能对结果排序,词项只有出现和不出现两种状态,但是一篇文档中出现10次“苹果“和只出现1次”苹果“,他们的相关度肯定是不相同的。所以需要对布尔检索进行改进。
    在扫描文档时,不但记录某词项出现与否,还记录该词项出现的次数,即词项频率(tf);同时我们记录该文档的长度(ld),以及某词项在不同文档中出现的次数,即文档频率(df)。

    这样我们就得到了如上图的倒排索引。左边部分被称为词典,存储的是1000个新闻中所有不同的词项;右边部分被称为倒排记录表,存储的是出现Term_i的那些文档信息。倒排索引中存储的变量都是为了给后续检索模型使用。
    讲到这里,我们需要解决如下几个问题。

    怎样得到一篇文档中的所有词项。给我们一篇新闻稿子,人类很容易分辨出”苹果“和”手机“是两个不同的词项,但是计算机怎么知道是这两个词呢?为什么不是”苹”、”国手“和”机“呢?这就需要进行中文分词,我们可以借助开源的jieba中文分词组件来完成,jieba分词能够将一个中文句子切成一个个词项,这样我们就可以统计tf, df了。
    有些词,如”的“、”地“、”得“、”如果“等,几乎每篇文档都会出现,他们起不到很好的区分文档的效果,这类词被称为”停用词“,我们需要把他们去掉。去停词的步骤可以在jieba分词之后完成。
    怎样存储倒排记录表。假设1000个文档共有20000个不同的词项,如果用类似图1的矩阵形式存储,需要耗费100020000=210^7个存储单元,但是图1往往是一个稀疏矩阵,因为一个文档中可能只出现了200个不同的词项,剩余的19800个词项都是空的。用矩阵方式存储时空效率都不高。所以我们可以采用图2的方式,词典用B-树或hash存储,倒排记录表用邻接链表存储方式,这样能大大减少存储空间。如果我们要将图2保存到数据库,可以对倒排记录表序列化成一个长的字符串,写入到一个单元格,读取的时候再反序列化。比如每个Doc内部用’\t’连接,Doc之间用’\n’连接,读取的时候split即可。

    倒排索引构建算法使用内存式单遍扫描索引构建方法(SPIMI),其实就是依次对每篇新闻进行分词,如果出现新的词项则插入到词典中,否则将该文档的信息追加到词项对应的倒排记录表中。SPIMI的伪代码如下:
    SPIMI-Invert(token_stream) output_file = NEWFILE() dictionary = NEWHASH() while(free memory available) do token ← next(token_stream) // 即不在词典中 if term(token) !∈dictionary // 加入词典并返回词典位置 then postings_list = AddToDictionary(dictionary, term(token)) // 找到词典位置 else postings_list = GetPostingList(dictionary, term(token)) // 关键词对应存储倒排文档的数据结构可用空间是否已满 if full(postings_list) // 重新分配关键词对应存储倒排文档的数据结构可用空间 使其变为原来2倍 then postings_list = DoublePostingList(dictinary, term(token)) // 将文档信息放入倒排表中 AddToPostingsList(postings_list,docId(token))//对词典排序(便于以后合并词典)sorted_terms ← SortTerms(dictionary)// 将倒排信息写入磁盘WriteBlockToDisk(sorted_terms, dictionary, output_file)return output_file
    下面是构建索引的所有代码:
    from os import listdirimport xml.etree.ElementTree as ETimport jiebaimport sqlite3import configparserclass Doc: docid = 0 date_time = '' tf = 0 ld = 0 def __init__(self, docid, date_time, tf, ld): self.docid = docid self.date_time = date_time self.tf = tf self.ld = ld def __repr__(self): return(str(self.docid) + '\t' + self.date_time + '\t' + str(self.tf) + '\t' + str(self.ld)) def __str__(self): return(str(self.docid) + '\t' + self.date_time + '\t' + str(self.tf) + '\t' + str(self.ld))class IndexModule: stop_words = set() postings_lists = {} config_path = '' config_encoding = '' def __init__(self, config_path, config_encoding): self.config_path = config_path self.config_encoding = config_encoding config = configparser.ConfigParser() config.read(config_path, config_encoding) f = open(config['DEFAULT']['stop_words_path'], encoding = config['DEFAULT']['stop_words_encoding']) words = f.read() self.stop_words = set(words.split('\n')) def is_number(self, s): try: float(s) return True except ValueError: return False def clean_list(self, seg_list): cleaned_dict = {} n = 0 for i in seg_list: i = i.strip().lower() if i != '' and not self.is_number(i) and i not in self.stop_words: n = n + 1 if i in cleaned_dict: cleaned_dict[i] = cleaned_dict[i] + 1 else: cleaned_dict[i] = 1 return n, cleaned_dict def write_postings_to_db(self, db_path): conn = sqlite3.connect(db_path) c = conn.cursor() c.execute('''DROP TABLE IF EXISTS postings''') c.execute('''CREATE TABLE postings (term TEXT PRIMARY KEY, df INTEGER, docs TEXT)''') for key, value in self.postings_lists.items(): doc_list = '\n'.join(map(str,value[1])) t = (key, value[0], doc_list) c.execute("INSERT INTO postings VALUES (?, ?, ?)", t) conn.commit() conn.close() def construct_postings_lists(self): config = configparser.ConfigParser() config.read(self.config_path, self.config_encoding) files = listdir(config['DEFAULT']['doc_dir_path']) AVG_L = 0 for i in files: root = ET.parse(config['DEFAULT']['doc_dir_path'] + i).getroot() title = root.find('title').text body = root.find('body').text docid = int(root.find('id').text) date_time = root.find('datetime').text seg_list = jieba.lcut(title + '。' + body, cut_all=False) ld, cleaned_dict = self.clean_list(seg_list) AVG_L = AVG_L + ld for key, value in cleaned_dict.items(): d = Doc(docid, date_time, value, ld) if key in self.postings_lists: self.postings_lists[key][0] = self.postings_lists[key][0] + 1 # df++ self.postings_lists[key][1].append(d) else: self.postings_lists[key] = [1, [d]] # [df, [Doc]] AVG_L = AVG_L / len(files) config.set('DEFAULT', 'N', str(len(files))) config.set('DEFAULT', 'avg_l', str(AVG_L)) with open(self.config_path, 'w', encoding = self.config_encoding) as configfile: config.write(configfile) self.write_postings_to_db(config['DEFAULT']['db_path'])if __name__ == "__main__": im = IndexModule('../config.ini', 'utf-8') im.construct_postings_lists()
    运行之后会在./data/下生成一个ir.db数据库文件,这就是构建好的索引数据库。
    本文转载自:http://bitjoy.net/2016/01/07/introduction-to-building-a-search-engine-3
    1 留言 2019-05-30 14:51:46 奖励15点积分
  • 基于python构建搜索引擎系列——(二)网络爬虫 精华

    网络爬虫又称网络蜘蛛、Web采集器等,它是一种按照一定的规则,自动地抓取万维网信息的程序或者脚本。
    我们在设计网络爬虫的时候需要注意两点:

    鲁棒性:Web中有些服务器会制造采集器陷阱(spider traps),这些陷阱服务器实际上是Web页面的生成器,它能在某个域下生成无数网页,从而使采集器陷入到一个无限的采集循环中去。采集器必须能从这些陷阱中跳出来。当然,这些陷阱倒不一定都是恶意的,有时可能是网站设计疏忽所导致的结果
    礼貌性:Web服务器具有一些隐式或显式的政策来控制采集器访问它们的频率。设计采集器时必须要遵守这些代表礼貌性的访问政策

    采集器的基本架构如下图所示。

    基本上是”抓取→分析→得到新的URL→再抓取→再分析”这样一个死循环过程。
    以上内容摘自王斌老师翻译的《信息检索导论》课本。
    由于我们要做的是一个新闻搜索引擎,所以抓取的是新闻数据,对于爬虫,网上也有很多的开源程序,如nutch等,Github上还有人专门开发了抓取新闻的组件newspaper,可以很方便的提取新闻标题、正文、时间等信息。不过用python写爬虫也是分分钟的事情,下面我们一起来试一试。
    首先找一个新闻网站,为简单起见,要找那种结构清晰、html代码便于解析的门户网站,比如搜狐新闻、参考消息等。
    搜狐新闻的国内要闻列表如下:

    结构非常清楚,左边是带URL的标题,右边括号里有新闻时间。这一页列表就有200条新闻,如果我们要获取1000条,只要不断模拟点击下一页即可。下一页的URL也只是在首页的基础上加上_xxx.shtml,xxx就是不同的页码。
    查看列表的html源码,得知列表都在类名为newsblue1的td中,所以只需要解析html源码就可以得到新闻标题、URL和时间,python解析html可以用BeautifulSoup包,非常方便。
    进入到新闻详细页面,正文部分如下:

    查看html源码,正文位于类名为text clear的div中,据此可以很方便的提取新闻正文。
    得到一条新闻的所有数据之后,我们需要将之结构化成xml文件,借助相应的xml包可以很方便的完成这项工作。xml格式定义如下:
    <?xml version="1.0" encoding="utf-8"?><doc> <id></id> <url></url> <title></title> <datetime></datetime> <body></body></doc>
    注意爬虫需要访问网络,难免会出现一些异常,所以捕获异常是非常有必要的。另外,搜狐每篇新闻正文后面都会有一段’//‘开始的注释,这个需要过滤掉,短于140个字的新闻我也过滤掉了。整个搜索系统的配置参数都存储在config.ini文件中。
    下面是完整的python 3.4+代码:
    from bs4 import BeautifulSoupimport urllib.requestimport xml.etree.ElementTree as ETimport configparserdef get_news_pool(root, start, end): news_pool = [] for i in range(start,end,-1): page_url = '' if i != start: page_url = root +'_%d.shtml'%(i) else: page_url = root + '.shtml' try: response = urllib.request.urlopen(page_url) except Exception as e: print("-----%s: %s-----"%(type(e), page_url)) continue html = response.read() soup = BeautifulSoup(html) td = soup.find('td', class_ = "newsblue1") a = td.find_all('a') span = td.find_all('span') for i in range(len(a)): date_time = span[i].string url = a[i].get('href') title = a[i].string news_info = ['2016-'+date_time[1:3]+'-'+date_time[4:-1]+':00',url,title] news_pool.append(news_info) return(news_pool)def crawl_news(news_pool, min_body_len, doc_dir_path, doc_encoding): i = 1 for news in news_pool: try: response = urllib.request.urlopen(news[1]) except Exception as e: print("-----%s: %s-----"%(type(e), news[1])) continue html = response.read() soup = BeautifulSoup(html) try: body = soup.find('div', class_ = "text clear").find('div').get_text() except Exception as e: print("-----%s: %s-----"%(type(e), news[1])) continue if '//' in body: body = body[:body.index('//')] body = body.replace(" ", "") if len(body) <= min_body_len: continue doc = ET.Element("doc") ET.SubElement(doc, "id").text = "%d"%(i) ET.SubElement(doc, "url").text = news[1] ET.SubElement(doc, "title").text = news[2] ET.SubElement(doc, "datetime").text = news[0] ET.SubElement(doc, "body").text = body tree = ET.ElementTree(doc) tree.write(doc_dir_path + "%d.xml"%(i), encoding = doc_encoding, xml_declaration = True) i += 1if __name__ == '__main__': config = configparser.ConfigParser() config.read('../config.ini', 'utf-8') root = 'http://news.sohu.com/1/0903/61/subject212846158' news_pool = get_news_pool(root, 854, 849) crawl_news(news_pool, 140, config['DEFAULT']['doc_dir_path'], config['DEFAULT']['doc_encoding']) print('done!')
    本文转载自:http://bitjoy.net/2016/01/04/introduction-to-building-a-search-engine-2
    1 留言 2019-05-28 20:16:43 奖励13点积分
  • 大数据 17、单机推荐系统

    前文链接:https://write-bug.com/article/2491.html
    通过前面介绍的算法基础,我们可以利用CB、CF算法作召回和粗排,利用LR作精排打分,最后关联出特定用户正在收听的特定音乐的推荐集合,最终形成可视化页面。

    上图是推荐系统的base版本,可通过前几节的知识串接起来,后面会陆续介绍可替换的组件及更多业务情况。
    我们可以看到用户在页面浏览时,可以通过点击、收听等行为我们进行user_id,item_id的收集,与此同时,我们使用用户的行为信息对检索引擎进行检索,即召回阶段的计算结果,之后我们需要对返回的候选集合进行精排,通过lr对用户特征+物品元数据信息作回归打分从而把筛选的候选集合再次排序,实现个性化。
    项目流程:
    1.数据准备
    用户画像数据:user_profile.datauserid,性别,年龄,收入,地域
    物品(音乐)元数据:music_metaitemid,name,desc,时长,地域,标签
    用户行为数据:user_watch_pref.smluserid,itemid,该用户对该物品的收听时长,点击时间(小时)

    首先,将3份数据融合到一份数据中,python gen_base.py 代码解析数据,实现对数据的拼接;得到数据merge_base.data。

    输入:user_profile.data music_meta user_watch_pref.sml 三份数据
    输出:merge_base.data 拼接后的数据

    也可用hive处理:
    create external table user_profile(user_id string,sex string,age string,money string,place string) row format delimited fields terminated by ',';load data local inpath '/usr/local/src/code/recsys_test/data/user_profile.data' into table user_profile;create external table music_meta(item_id string,name string,desc string,hour string,place string,tag string) row format delimited fields terminated by '\001';load data local inpath '/usr/local/src/code/recsys_test/data/music_meta' into table music_meta;create external table user_watch_pref (user_id string,item_id string,listen_hour string,hour string) row format delimited fields terminated by '\001';load data local inpath '/usr/local/src/code/recsys_test/data/ user_watch_pref.sml ' into table user_watch_pref;3张表数据融合为一份数据user_watch_pref user_id,item_id,listen_hour,hour,user_profile sex,age,money,placemusic_meta name,desc,hour,placeinsert overwrite directory '/data' row format delimited fields terminated by ',' select distinct(a.user_id),a.item_id,a.listen_hour,a.hour,c.sex,c.age,c.money, c.place,b.name,b.desc,b.hour,b.placefrom user_watch_pref as a, user_profile as c,music_meta as bwhere a.user_id = c.user_id and a.item_id=b.item_id;
    2.召回、CB算法在学习推荐算法时,我们可以发现,不管是cb还是cf都可以通过对mr倒排式的协同过滤算法对数据进行处理,只是token item_id,score和user item_id,score 的区别。
    以token itemid score形式整理训练数据
    gen_cb_train.py 我们这里的代码对item的name,desc,tag进行分词并给予不同的权重便可以形成我们的数据。

    输入:merge_base.data 总数据
    输出:cb_train.data 3列数据

    要点:对item_id 进行去重,对不同元数据分词分数给予不同权重,如果音乐名字、描述、标签中出现相同的token,我们就把相应的分数乘各自的权重相加,如果不相同便加入token字典
    RATIO_FOR_NAME = 0.9RATIO_FOR_DESC = 0.1RATIO_FOR_TAGS = 0.05用协同过滤算法跑出item-item数据 mr_cf倒排式
    最后得到基于cb的ii矩阵,这里我也用hive弄了下,但是没想到怎么整理出ii矩阵:
    cb_train.datatoken,item_id,tfidfcreate external table cb_train (token string,item_id string,tfidf string) row format delimited fields terminated by ',';load data local inpath '/usr/local/src/code/recsys_test/data/cb_train.data into table cb_train;token,item_id,scoresum(sqrt(sum(s^2))):select token,item_id,sum(power(tfidf,2)) over(partition by item_id) as scorefrom cb_train order by item_id limit 100;s/sum(sqrt(sum(s^2))):insert overwrite directory '/data/cb_z' row format delimited fields terminated by ',' select t.token,t.item_id,cb_train.tfidf/sqrt(score) as f_scorefrom(select token,item_id,sum(power(tfidf,2)) over(partition by item_id) as scorefrom cb_train)t,cb_trainwhere t.item_id=cb_train.item_id and t.token = cb_train.token;limit 300;暂存:token,item_id,scorecreate external table cb_train_score (token string,item_id string,score string) row format delimited fields terminated by ',';load data inpath '/data/cb_z/000000_0'into table cb_train_score;对数据格式化,item-> item list形式,整理出KV形式
    gen_reclist.py并标记数据计算算法:

    输入:cb.result ii矩阵
    输出:cb_reclist.redis 粗排、标记、聚合

    类似如下数据:
    SET CB_5305109176 726100303:0.393048_953500302:0.393048_6193109237:0.348855灌库(redis)
    下载redis-2.8.3.tar.gz安装包,进行源码编译,执行make,然后会在src目录中,得到bin文件(redis-server 服务器,redis-cli 客户端)。
    启动redis server服务:
    ]# ./src/redis-server然后换一个终端执行:]# ./src/redis-cli,连接服务
    接下来灌数据(批量灌):
    需要安装unix2dos(格式转换)
    ]# cat cb_reclist.redis | /usr/local/src/redis-2.8.3/src/redis-cli --pipe验证:
    ]# ./src/redis-cli执行:
    127.0.0.1:6379> get CB_5305109176"726100303:0.393048_953500302:0.393048_6193109237:0.348855"3.召回、CF算法以userid itemid score形式整理训练数据 gen_cf_train.py
    得到userid对item的最终分数,即user收听时长表示对item的喜欢分数 score = float(t_finished) / float(t_all)
    用协同过滤算法跑出item-item数据 mr_cf,最后得到基于cf的ii矩阵
    对数据格式化,item-> item list形式,整理出KV形式
    unix2dos cf_reclist.redis灌库
    cat cf_reclist.redis | /usr/local/src/redis-2.8.3/src/redis-cli –pipe与上面cb算法一样流程.
    4.为lr模型作特征提取:
    user: gender、age
    item:name_token
    输入:merge_base.data
    输出:

    samples.data 特征提取数据user_feature.data 用户特征数据,为使用模型作数据准备item_feature.data 物品特征数据,为使用模型作数据准备name_id.dict 为包装数据作准备

    这里的label值用用户的收听时长来作判断:
    # label info label = float(watch_time) / float(total_time) final_label = '0' if label >= 0.82: final_label = '1' elif label <= 0.3: final_label = '0' else: continue用户特征分数初始化为1,物品特征分数运用jieba分词的idf作为初始分数
    形成如下数据:



    模型使用时,只有w,b 怎么使用,我需要有个库去存储user_fea、item_fea。实时拼接出特征,再通过model预测。
    用sk-learn进行模型训练,得到w,b。解析samples数据,还原矩阵:

    target_list:存储每个样本的label标签
    fea_row_list:存储样本行信息
    fea_col_list:存储样本列信息
    data_list:存储真实数据score

    转换数据并分割数据集:
    fea_datasets = csr_matrix((data, (row, col)), shape=(row_idx, max_col + 1))x_train, x_test, y_train, y_test = train_test_split(fea_datasets, target_list, test_size=0.2, random_state=0) # 28分为测试集及训练集训练
    x_train, x_test, y_train, y_test = load_data()model = LogisticRegression(penalty='l1')model.fit(x_train, y_train)for w_list in model.coef_: for w in w_list: print >> ff_w, "w: ", w for b in model.intercept_: print >> ff_b, "b: ", b print "precision: ", model.score(x_test, y_test)#预测print "MSE: ", np.mean((model.predict(x_test) - y_test) ** 2)#误差平方根auc评估
    for y in y_test: print >> ff_t, yfor y in model.predict_proba (x_test): print >> ff_p, y
    评估:auc:paste T.txt P.txt >auc.txt,awk无图形测试:但是需要回归的浮点分数不能用分类的label
    回归:model.predict_proba()
    分类:model.predict() :0&1

    5.推荐引擎及可视化通过前面的层层处理,我们得到了user&item特定的候选集合如何随意来了一个用户推荐个性化呢?

    解析请求:userid,itemid,pyweb模拟页面
    加载模型:加载排序模型(model.w,model.b),加载并解析数据
    检索候选集合:利用cb,cf去redis里面检索数据库,得到候选集合。截断粗排候选集合,得到item_list
    获取用户特征:userid
    获取物品特征:itemid,这两步用到上面说的特征库
    打分(逻辑回归),排序。对拼接出的特征进行检索wx计算,更新分数,并通过sigmoid函数压缩分数
    top-n过滤
    数据包装(itemid->name),返回

    之后,再把最终的候选集合列表,post到前端页面。
    此上,即为单机版本的推荐系统实现,但是在工作中思路大概是这样,只是拓宽了算法组件、机器、备份、分流等等东西,需要多个部门共同协作。
    0 留言 2019-05-27 18:11:17 奖励14点积分
显示 60 到 75 ,共 15 条
eject