韓家煒 數據挖掘概念與技術 第三版 習題3.12
取 鳶尾花數據集iris.data 作為待離散化的數據集合，使用ChiMerge算法，對四個數值屬性進 行離散化，對四個屬性進行區間合并，最終合并區間個數剩下為6個即停：即max_interval=6。
一、樣本數據
iris.data 數據形式為：前面4列是屬性，最后一列是數據類名，
5.1,3.5,1.4,0.2,Iris-setosa
4.9,3.0,1.4,0.2,Iris-setosa
4.7,3.2,1.3,0.2,Iris-setosa
6.6,2.9,4.6,1.3,Iris-versicolor
5.2,2.7,3.9,1.4,Iris-versicolor
6.0,3.0,4.8,1.8,Iris-virginica
6.9,3.1,5.4,2.1,Iris-virginica
........
?此數據集一共3個類名：String[] classifies = {"Iris-setosa","Iris-versicolor","Iris-virginica"};
?
二、算法理論：
算法理論步驟參考：?http://blog.csdn.net/zhaoyl03/article/details/8689440
第一步：初始化?
初始化時，一個數據認為是一個區間，每個屬性對該屬性下的各個區間進行升序排序
第二步：合并區間：（直到剩下區間數目為6）
(1)?計算每一對相鄰區間的卡方值
? 卡方公式是：?
其中observed是expected是一個二行n列矩陣，二行是兩個區間，n列是指數據一共有n個類。
? ? ? ?這里iris.data數據中一共有三個類，所以是2行3列矩陣：e.g
?observedmatrix:(下面表只有紅色數字部分才為observedmatrix[2][3]的值。)
| 區間： | 類別Iris-setosa | 類別 Iris-versicolor | 類別 Iris-virginica | i行計算1的總個數 |
| {3.0} | 1 | 0 | 0 | 1 |
| {3.1,3.2,3.3} | 0 | 1 | 2 | 3 |
| j列計算1的總個數 | 1 | 1 | 2 | 4 ? ?(矩陣里 1的總個數 ) |
?
?
expectedmatrix[i][j]是由上面
observedmatrix所得，
expectedmatrix[i][j]= （obser矩陣的i行1的總個數* j列1的總個數）/（observ矩陣里1的總個數）?
?expectedmatrix:
| 區間： | 類別 Iris-setosa | 類別 Iris-versicolor | 類別 Iris-virginica |
| {3.0} | 1*1/4=0.25 | 1/4=0.25 | 2*1/4=0.5 |
| {3.2,3.3} | 1*3/4=0.75 | 1/4=0.25 | 2*3/4 = 1.5 |
?
因為是2行3列矩陣，所以一共卡方迭加了2*3=6次; (
observedmatrix[i][j]-
expectedmatrix[i][j])/?
expectedmatrix[i][j]
所以 ?chisquare = (1-0.25)^2 /0.25 + (0-0.25)^2/0.25 +(0-0.5)^2/0.5 + (0-0.75)^2/0.75 + (1-0.25)^2/0.25 + (2-1.5)^2/1.5
(2)?將上面卡方值最小的一對區間合并
? ? ??
第三步：輸出結果：6個區間的最大最小值
?
?
三、算法理論數據結構化
將上面算法理論數據結構化：
iris.data ?中
1.屬性：每個屬性都有多個區間，所以定義屬性是一個list，list的元素是什么類型呢？ 是一個區間類型（所以寫一個區間類：包括 區間最大最小值，區間包含的元素）。
2.區間：每個區間會包含很多元素，所以也需要一個list來存，list元素什么類型好？ ?再寫一個數據 Data類，包括(數據，數據對應的類別（在卡方運算里會用到類別）)
?所有數據都具備了結構了，整體結構這是最重要的。
List<Interval>[] attributelists =
new
ArrayList[attributenum];
for
(
int
i=0;i<attributenum;i++
) {
attributelists[i]
=
new
ArrayList<Interval>
();
}
class
Interval {
//
每個區間都是有最小值最大值，以及該區間所包含的所有數據
public
double
maxvalue = 0.0
;
public
double
minvalue = 0.0
;
public
List<Data> intervallist =
new
ArrayList<Data>();
//
區間里的list每個元素都是Data類型
}
class
Data {
//
每個數據都包含它的值和類別
public
double
value = 0.0
;
public
String classify = ""
;
}
?
?
四、Java 實現
public class
ChiMergeTest {
public
static
int
classificationnum = 3;
//
類個數
public
static
int
attributenum = 4
;
public
static
List<Interval>[] attributelists =
new
ArrayList[attributenum];
//
右邊不能Arraylist<interval>!!
public
static
String[] classifies = {"Iris-setosa","Iris-versicolor","Iris-virginica"
};
public
static
void
main(String[] args)
throws
Exception {
String inputpath
= "iris.data"
;
readFile(inputpath);
//
將輸入數據的 結構化
chiMerge();
printresult();
}
?
對應上面算法步驟：
第一步：初始化?
初始化時，一個數據認為是一個區間，每個屬性對該屬性下的各個區間進行升序排序
public
static
void
readFile(String inputpath)
throws
Exception {
BufferedReader br
=
new
BufferedReader(
new
FileReader(inputpath));
String line
=
br.readLine();
for
(
int
i=0;i<attributenum;i++
) {
attributelists[i]
=
new
ArrayList<Interval>
();
}
while
(line!=
null
&& line.length()>0
) {
String[] temp
= line.split(",");
//
將數據分隔，
for
(
int
i=0; i<attributelists.length; i++) {
//
遍歷屬性名
Interval interval =
new
Interval();
Data onedata
=
new
Data();
onedata.value
=
Double.parseDouble(temp[i]);
onedata.classify
= temp[4
];
interval.minvalue
= interval.maxvalue =
onedata.value;
interval.intervallist.add(onedata);
//
區間加入了一個數據
attributelists[i].add(interval);
//
第i個屬性加入了一個區間
}
line
=
br.readLine();
}
br.close();
sort();
}
public
static
void
sort() {
//
初步建立屬性list時，對區間進行排序
for
(
int
i = 0; i<attributenum; i++
){
List
<Interval> attrlist =
attributelists[i];
Collections.sort(attrlist,
new
IntervalComparator());
//
排序
combineRepeatedData(attrlist);
//
CombineRepeatedDatawithHash(attrlist);
//
等同于上面方法，不同順序會再被打算。麻煩。
}
//
for
}
public
static
void
combineRepeatedData(List<Interval>
attrlist) {
for
(
int
j=0; j<attrlist.size()-1 ;j++
) {
Interval inteFront
=
attrlist
.get(j)
;
Interval intevbehind
= attrlist.get(j+1
);
List
<Data> listFront =
inteFront.intervallist;
List
<Data> listbehind =
intevbehind.intervallist;
Data dataFront
= listFront.get(0
);
Data databehind
= listbehind.get(0
);
while
(databehind.value == dataFront.value &&(j<attrlist.size()-1) ) {
//
屬性list已經排序，如果后面一個data值跟前面data相同，則合并到前面的。
attrlist.get(j).intervallist
.addAll
(listbehind);
//用得不熟！！
attrlist
.remove
(j
+1
);
if
((j<attrlist.size()-1
)) {
inteFront
=
attrlist.get(j);
intevbehind
= attrlist.get(j+1
);
listFront
=
inteFront.intervallist;
listbehind
=
intevbehind.intervallist;
dataFront
= listFront.get(0
);
databehind
= listbehind.get(0
);
}
}
}
}
class
IntervalComparator
implements
Comparator {
//
升序了。
對list引用類型寫compartor排序方法很重要！！
public
int
compare(Object arg0, Object arg1) {
Interval i1
=
(Interval)arg0;
Interval i2
=
(Interval)arg1;
Data x1
= i1.intervallist.get(0);
//
一開始所有區間就一個元素而已
Data x2 = i2.intervallist.get(0
);
int
result = 0
;
if
(x2.value<
x1.value)
{result
= 1
; }
if
(x2.value>
x1.value)
{result
= -1
; }
return
result;
}
}
?
第二步：合并區間：（直到剩下區間數目為6）
public
static
void
chiMerge() {
for
(
int
i=0; i<attributelists.length; i++
){
List
<Interval> attrlist =
attributelists[i];
while
(attrlist.size()>6){
//
最終的終止條件是形成6個區間
double
minchisquare = 10000000;
//
定義一個屬性里最小的卡方值 。。 變量放在的位置很重要，是放在循環里面還是外面很重要，就因為這個找錯誤還挑不出來，白花了兩個小時
int
minchisquareindex =0;
//
記住兩個區間最小卡方值的第一個區間在屬性list的下標
//
遍歷一個屬性的相鄰的兩個區間
for
(
int
j=0; j<attrlist.size()-1;j++){
//
遍歷一個屬性的每個兩個區間比較
Interval interval1 = attrlist.get(j);
//
要比較兩個區間
Interval interval2 = attrlist.get(j+1
);
Matrixs matrixs
=
buildObseredandExpectedMatrixs
(attrlist,interval1, interval2);
//
返回了兩個observed,expected矩陣
double
chisquarevalue =
calchi
(matrixs);
//
計算兩個區間的卡方值
if
(chisquarevalue < minchisquare ){
//
找最小的卡方值
minchisquare =
chisquarevalue;
minchisquareindex
= j;
//
表示當前最小的卡方值的兩個區間中第一個區間在該屬性list的下標位置
}
}
//
for
mergetwoIntervals(
attrlist,minchisquareindex);
//
合并第i個屬性list里的最小兩個區間。最終的合并！
}
//
while
}
}
?
(1)?計算每一對相鄰區間的卡方值
public
static
double
calchi(Matrixs matrixs) {
double
[][] observedMatrix =
new
double
[2][3
];
double
[][] expectedMatrix =
new
double
[2][3
];
observedMatrix
=
matrixs.observedMatrix;
expectedMatrix
=
matrixs.expectedMatrix;
//
求卡方
int
chisquarevalue =0
;
for
(
int
r=0; r<2; r++
) {
for
(
int
c=0;c<3;c++
) {
chisquarevalue
+= (observedMatrix[r][c]- expectedMatrix[r][c]) *(observedMatrix[r][c]- expectedMatrix[r][c]) /
expectedMatrix[r][c] ;
}
}
//
System.out.println("卡方值："+chisquarevalue);
return
chisquarevalue;
}
public
static
Matrixs buildObseredandExpectedMatrixs(List<Interval> attrlist,Interval interval1,Interval interval2) {
//
返回兩個矩陣：obeserved和expected矩陣
//
建立observedMatrix
double
[][] observedMatrix =
new
double
[2][3
];
double
[][] expectedMatrix =
new
double
[2][3
];
int
[] linesum =
new
int
[2] ;
//
矩陣兩行的計算
int
[] columnsum =
new
int
[3];
//
矩陣三列都計算
linesum[
0] =
interval1.intervallist.size();
linesum[
1] =
interval2.intervallist.size();
int
allsum = linesum[0] + linesum[1
];
columnsum[
0]= columnsum[1] = columnsum[2] = 0;
//
初始化列
//
取第一個區間
for
(
int
k=0; k< interval1.intervallist.size() ; k++) {
//
遍歷一個區間里所有元素
Data data =
interval1.intervallist.get(k);
if
(data.classify.equals(classifies[0])) {
//
是類別1：Iris-setosa
columnsum[0]++
;
observedMatrix[
0][0]++
;
}
else
if
(data.classify.equals(classifies[1])) {
//
是類別2：Iris-versicolor
columnsum[1]++
;
observedMatrix[
0][1]++
;
}
else
if
(data.classify.equals(classifies[2])) {
//
是類3
columnsum[2]++
;
observedMatrix[
0][2]++
;
}
}
//
for
//
取第2個區間
for
(
int
k=0; k< interval2.intervallist.size() ; k++) {
//
遍歷一個區間里所有元素
Data data =
interval2.intervallist.get(k);
if
(data.classify.equals(classifies[0])) {
//
是類別1：Iris-setosa
columnsum[0]++
;
observedMatrix[
1][0]++
;
}
else
if
(data.classify.equals(classifies[1])) {
//
是類別2：Iris-versicolor
columnsum[1]++
;
observedMatrix[
1][1]++
;
}
else
if
(data.classify.equals(classifies[2])) {
//
是類3
columnsum[2]++
;
observedMatrix[
1][2]++
;
}
}
//
for
//
建立expectedMatrix
for
(
int
r=0; r<2; r++
) {
for
(
int
c=0;c<3;c++
) {
expectedMatrix[r][c]
= linesum[r] * columnsum[c] /
allsum;
if
(expectedMatrix[r][c]==0.0
)
expectedMatrix[r][c]
=0.0001;
//
因為求卡方的時候，這個值會作分母，所以分母不能作0.分母變小，則卡方值就大，卡方值越大，越不相似，越不會被合并了
}
}
Matrixs matrixs
=
new
Matrixs();
matrixs.expectedMatrix
=
expectedMatrix;
matrixs.observedMatrix
=
observedMatrix;
return
matrixs;
}
}
class
Matrixs {
public
double
[][] observedMatrix =
new
double
[2][3
];
public
double
[][] expectedMatrix =
new
double
[2][3
];
}
(2)?將上面卡方值最小的一對區間合并
public
static
void
mergetwoIntervals(List<Interval> attrlist,
int
minchisquareindex) {
//
List<Interval> attrlist =attributelists[0];
//
將當前最小的卡方值對應的兩個區間進行合并；刪去已被合并的區間
List<Data> mergedlist = attrlist.get(minchisquareindex+1).intervallist;
//
被合并的區間里的數據list
attrlist.get(minchisquareindex).intervallist.addAll(mergedlist);
attrlist.get(minchisquareindex).maxvalue
= attrlist.get(minchisquareindex+1).maxvalue;
//
該區間的最大值是第二個區間的最大值，因為區間已經排過序了
attrlist.remove(minchisquareindex+1);
//
該屬性刪去已被合并的區間
}
?
?
?第三步：輸出結果：6個區間的最大最小值
public
static
void
printresult() {
for
(
int
i=0; i<attributenum; i++
){
System.out.println(
"第"+(i+1)+"個屬性："
);
for
(
int
j=0; j<attributelists[i].size(); j++) {
//
每個屬性是list，遍歷屬性list每一個元素
Interval in =
attributelists[i].get(j);
System.out.println(
"( "+in.minvalue +" , " + in.maxvalue + " )" );
//
每個interval類里的list每個元素都是一個Data類型
}
}
}
?
?最終結果如下：
第1個屬性：
(
4.3 , 4.8
) (
4.9 , 5.2
) (
5.3 , 5.3
) (
5.4 , 6.9
) (
7.0 , 7.0
) (
7.1 , 7.9
)
第2個屬性：
(
2.0 , 2.0
)(
2.2 , 2.2
) (
2.3 , 2.3
) (
2.4 , 3.5
) (
3.6 , 3.6
) (
3.7 , 4.4
)
第3個屬性：
(
1.0 , 1.9
) (
3.0 , 4.4
) (
4.5 , 4.5
) (
4.6 , 4.7
) (
4.8 , 5.1
) (
5.2 , 6.9
)
第4個屬性：
(
0.1 , 0.6
) (
1.0 , 1.5
) (
1.6 , 1.6
) (
1.7 , 1.7
) (
1.8 , 1.8
) (
1.9 , 2.5 )
?
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
